Правильность реализации связанного списка

Я начал изучать C ++, и я хотел попросить вас взглянуть на мою связанную реализацию списка и дать комментарии, в чем проблема. Он компилируется и работает отлично, но мне любопытно, насколько корректны константы, правильное использование указателей /ссылок и т. Д., Поэтому не стесняйтесь меня судить по мне!

Я читал об этих концепциях в Интернете, но это не заводит меня далеко, без мнения опытного программиста на C ++.

Node:

#include <iostream>

#pragma once
template <typename T>
class Node
{
const char * const _key;
Node *_next;
T _value;

public:
Node(const char * const key, const T &value) : _key(key), _value(value), _next(nullptr) {}

const char * const getKey()
{
    return _key;
}

Node *getNext()
{
    return _next;
}

void setNext(Node *next)
{
    _next = next;
}

T &getValue()
{
    return _value;
}
};

Связанный список:

#include <iostream>
#include "Node.h"

#pragma once

template <typename T>

class LinkedList
{
int _count;
Node<T> *_first;

public:
LinkedList() : _count(0), _first(nullptr) {}

Node<T> *add(const char * const key, const T &value)
{
    Node<T> *first = new Node<T>(key, value);
    first->setNext(_first);
    _first = first;
    _count++;
    return _first;
}

void remove(const char * const key)
{
    Node<T> *next = _first;
    Node<T> *previous = nullptr;

    while (next)
    {
        if (next->getKey() == key)
        {
            if (next == _first)
                _first = next->getNext();
            else
                previous->setNext(next->getNext());
            _count--;
            return;
        }
        previous = next;
        next = next->getNext();
    }
}

int getCount() 
{ 
    return _count;
}

Node<T> * const getFirst()
{
    return _first;
}
};

Я не слишком уверен, как правильно определить значение внутри класса Node, потому что я хочу поддерживать как примитивные типы, так и объекты.

Это действительно сработало для меня, хотя это, вероятно, неверно?

if (next->getKey() == key)
11 голосов | спросил Michael Naumov 30 J0000006Europe/Moscow 2014, 07:59:26

3 ответа


11

В вашем коде есть немало проблем с вашим кодом. Я знаю, что вы сказали, что вам «очень сложно», но объем знаний, необходимых для написания относительно полной реализации связанных списков в C ++, - это больше, чем просто любой другой язык.

Как второстепенный момент, я собираюсь изменить все, что имеет префикс _ (например, _first или _key), используя postfix underscore (поэтому ---- +: = 3 =: + ---- и first_). Причиной этого является то, что определенные символы зарезервированы для использования компилятором; правила являются тайными, но самое простое:

  • Избегайте чего-либо с лидирующим подчеркиванием (key_)
  • Избегайте чего-либо с двумя символами подчеркивания (_<varname>)

Изменить: Как отметил @JerryCoffin, вам следует избегать <varname>__ где угодно (префикс, постфикс и т. д.).

Первая (и самая большая) проблема заключается в том, что это никогда не освобождает какую-либо память, выделенную кучей (то есть память, выделенная с помощью __ ). Каждый раз, когда вы делаете:

new

Это будет выделять память из кучи. В отличие от собранных мусором языков (большинство языков, кроме C и C ++), вы можете, программист, освободить эту память, когда закончите с ней. Здесь это означает ручную запись деструктора:

Node<T> *first = new Node<T>(key, value);

Это гарантирует, что память будет восстановлена.

Чтобы согласиться с этим, существует несколько методов, которые неявно генерируются для вас, когда вы пишете класс на C ++. Это оператор присваивания копий и конструктор копирования. Они имеют следующие формы:

~LinkedList()
{
    Node<T>* next = _first;
    while(next != nullptr) {
        first_ = first_->next;
        delete next;
        next = first_;
    }
}

Когда они называются? Скажем, вы определяете LinkedList& operator=(const LinkedList& rhs); // Copy assignment LinkedList(const LinkedList& rhs); // Copy constructor :

LinkedList<int>

Методы, которые C ++ реализует для вас здесь, будут делать то, что вы не хотите, чтобы они делали: указатель LinkedList<int> a; // Do some operations on a, such as adding nodes LinkedList<int> b; // Some operations on b b = a; // Calls the copy assignment operator, operator= LinkedList<int> c(a); // Calls the copy constructor будет равен на b.first_. Это означает, что если деструктор для a.first_ вызывается, то a будет указывать на ячейки памяти, которые были исправлены с помощью b (что очень, очень плохо).

Чтобы исправить это, они должны быть реализованы для правильной работы. Итак, что правильно делать? Давайте посмотрим на них поочередно:

Конструктор копирования просто должен скопировать каждый элемент переданного в delete по очереди:

LinkedList

Оператор присваивания копии должен:

  1. Освободите текущую память с помощью LinkedList(const LinkedList& rhs) { Node<T>* tmp = rhs.first_; while(tmp != nullptr) { add(tmp->key_, tmp->value_); } }
  2. Скопировать каждое значение в список this

Итак, реализация выглядит примерно так:

rhs

Это на самом деле очень хорошо известная вещь в C ++: она называется правилом трех (или в более современном C ++, правиле из пяти ), но игнорируйте это на момент). Что он говорит:

Если вам нужно вручную написать какой-либо один из операторов назначения деструктора /копирования конструктора /копии, вам необходимо вручную определить все три из них .

Для полного изучения этого вопроса вы можете прочитать это сообщение .

Использование LinkedList& operator=(const LinkedList& rhs) { // Stop self assignment, like: a = a; if(&rhs != this) { // Step 1: Free current memory Node<T>* tmp = first_; while(tmp->next != nullptr) { first_ = first_->next; delete tmp; tmp = first_; } count_ = 0; // Step 2: Create a copy of rhs temp = rhs.first_; while(tmp != nullptr) { add(tmp->key_, tmp->value_); } } return *this; } в качестве ключа в связанном списке необычно и не подходит с основной идеей структуры данных. Если вы хотите что-то посмотреть по ключу, вы обычно ищете структуру данных, называемую const char * const (или map, или hashmap; для него есть несколько имен). Я бы удалил там сложность и просто избавился от члена dictionaryполностью.

key

Я также удалил возврат void add(const T &value) { Node<T> *first = new Node<T>(key, value); first->next_ = first_; first_ = first; count_++; } . Обычно вы не хотите, чтобы пользователи вашего класса имели прямой доступ к Node<T> *.

Ваша функция Node<T> * также теряет память, вам снова нужно иметь remove.

delete

Изменить: как вы написали поиск, гораздо более похожий на словарь. Для стандартного списка библиотек вы часто используете что-то вроде Node<T>* tmp = next; if (next == _first) { _first = next->getNext(); delete tmp; // Need a delete here } else { previous->setNext(next->getNext()); delete tmp; // Or here } _count--; , которое берет предикат (это просто причудливое слово для функции который возвращает bool). Это позволяет вам использовать фактическую функцию для выбора того, что вы ищете. В качестве примера, если у вас есть std::find_if struct:

Student

Затем у вас был список учеников:

struct Student
{
    std::string name;
    int age;
    int year;
};

Возможно, вам захочется найти студента, у которого есть имя «Джон»: это будет выглядеть так:

std::list<Student> students;

Фактически, это фактически вернет iterator в контейнер.

Это также дает вам больше гибкости, так как вы можете использовать ту же функцию, чтобы найти студента, который, например, 17 лет:

std::find_if(students.begin(), students.end(), [](const Student& s)
    { return s.name == "John"; });

Изменить 2: Как указывалось, оператор присваивания копий не написан наилучшим образом. Во-первых, важно понимать, почему это так. Если вы посмотрите на шаги, которые мы пройдем, мы сначала освободим всю сохраненную память, а затем перепишем текущий список. Проблема заключается в том, что если что-то выдает исключение во время любого из них, мы останемся с несоответствующим статусом объекта. Способ исправить это - использовать то, что обычно называют «копировать и заменять». Это также имеет приятное свойство, которое позволяет нам повторное использование кода, сокращая дублирование.

Первым портом вызова является запись функции (члена) std::find_if(students.begin(), students.end(), [](const Student& s) { return s.age == 17; }); :

swap

Тогда свободная функция, которая переходит к этому:

template <typename T>
void LinkedList<T>::swap(LinkedList<T>& other)
{
    using std::swap;
    swap(first_, other.first_);
    swap(count_, other.count_);
}

Теперь мы можем написать оператор присваивания копии следующим образом:

template <typename T>
void swap(LinkedList<T>& a, LinkedList<T>& b)
{
    a.swap(b);
}

Обратите внимание, что параметр LinkedList& operator=(LinkedList rhs) { swap(*this, rhs); return *this; } теперь принимается по значению . Это выполнит построение копии, поэтому после ввода вызова rhs будет содержать полную копию. Тогда все, что должно произойти, - это несколько указателей. Обратите внимание также, что исходная память, которая была сохранена, уничтожается: когда rhs выходит из области видимости в конце функции, ее деструктор вызывается , Так как теперь он указывает (что было) исходную память для rhs, эта память правильно исправлена.

Это имеет ряд преимуществ: во-первых, оно кратким и повторным использованием кода, во-вторых, оно безопасно: если какая-либо операция бросает, наш объект остается в согласованном состоянии - обновление эффективно атомарно; он либо работает полностью, либо полностью не работает.

Используя this, вы также можете легко написать оператор присваивания перемещения.

ответил Yuushi 30 J0000006Europe/Moscow 2014, 08:55:56
6
  • геттеры и сеттеры

    Точкой объявления элемента private является ограничение доступа к нему. Предоставление неконтролируемого getter и setter (как getNext() и setNext()) побеждает эту цель. Вы также можете сделать публикацию _next.

    Реальная цель ограничения доступа заключается в том, чтобы помочь клиенту не испортить работу (научный термин поддерживает инвариант ). Я не вижу, какой инвариант поддерживается _value. Класс Node не имеет значения, какое значение хранит узел; это клиентский код. A _value getter просто усложняет жизнь клиента.

  • итераторы . Их отсутствие блокирует ваш класс из библиотеки алгоритмов STL. Клиент должен будет переопределить все, что предоставляется STL бесплатно.

ответил vnp 30 J0000006Europe/Moscow 2014, 10:25:46
5

Реализация Node является нетипичной для общей реализации. Узел действительно является лишь частью связанного списка и ему просто нужны два элемента данных: его данные и указатель на следующий узел (и указатель на предыдущий узел для дважды связанного списка). Ему не нужны свои собственные функции-члены, но он может также иметь свой собственный конструктор, вместо того, чтобы сам список заботиться об этом.

template <typename T>
struct Node
{
    T data;
    Node* next;

    Node(T data) : data(data), next(nullptr) {}
};

Хотя это может быть class, все в порядке сделать его struct, потому что его можно просто определить внутри класса LinkedList, безопасно как private.

Разное:.

  • Вы должны удалить <iostream>, так как он не используется, , если вы собираетесь реализовать функция отображения в LinkedList. Если вы перегрузите operator<<, тогда вам просто понадобится <ostream>. Несмотря на это, это не относится к Node.

  • getCount() должен быть const как он не должен изменять какие-либо элементы данных:

    int getCount() const
    { 
        return _count;
    }
    
ответил Jamal 30 J0000006Europe/Moscow 2014, 08:30:21

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132