Подробности реализации конструктора ссылок LinkedList

Question

Я начинаю изучать C++ и, как упражнение, решает реализовать простой класс LinkedList (Ниже приведена часть кода). У меня возник вопрос о том, как должен быть реализован конструктор копирования, и наилучшим образом получить доступ к данным на исходном LinkedList.

template <typename T> 
    class LinkedList { 

     struct Node { 
      T data; 
      Node *next; 

      Node(T t, Node *n) : data(t), next(n) {}; 
     }; 

    public: 
     LinkedList(); 
     LinkedList(const LinkedList&); 
     ~LinkedList(); 

     //member functions 
     int size() const;    //done 
     bool empty() const;   //done 
     void append(const T&);   //done 
     void prepend(const T&);  //done 
     void insert(const T&, int i); 
     bool contains(const T&) const; //done 
     bool removeOne(const T&);  //done 
     int removeAll(const T&);  //done 
     void clear();     //done 
     T& last();      //done 
     const T& last() const;   //done 
     T& first();     //done 
     const T& first() const;  //done 
     void removeFirst();   //done 
     T takeFirst();     //done 
     void removeLast(); 
     T takeLast(); 


     //delete when finished 
     void print();     
     //end delete 

     //operators 
     bool operator ==(const LinkedList<T> &other) const; //done 
     bool operator !=(const LinkedList<T> &other) const; //done 
     LinkedList<T>& operator =(const LinkedList<T> &other); //done 


    private: 
     Node* m_head; 
     Node* m_tail; 
     int m_size; 

    }; 

    template<typename T> 
    LinkedList<T>::LinkedList() : m_head(0), m_tail(0), m_size(0) { 

    } 
... 

В случае, если моя копия доступа конструктора данных на каждом узле исходного LinkedList напрямую?

template<typename T> 
LinkedList<T>::LinkedList(const LinkedList& l) { 

    m_head = 0; 
    m_tail = 0; 
    m_size = 0; 

    Node *n = l.m_head; 

    // construct list from given list 
    while(n) { 
     append(n->data); 
     n = n->next; 
    } 
} 

Должен ли я получить доступ к данным через соответствующий аксессор? (Я знаю, что у меня нет определенных аксессуаров).

Кроме того, я намерен создать пользовательский итератор, чтобы можно было выполнить итерацию по LinkedList. Должен ли я использовать в конструкторе копирования доступ к данным на каждом узле?

Другой вопрос (полностью вне темы, я знаю), когда и/или почему мы должны объявить указатель на LinkedList

LinkedList<int> *l = new LinkedList<int>(); 

вместо

LinkedList<int> l; 

Answer 1

Я предполагаю, что добавление будет правильно обрабатывать начальные детали головы/хвоста, да? Если это так, то, что у вас сейчас, велико и просто: перейдите в другой список, возьмите его и добавьте копию в свой список. Отлично.

Ну, почти. Используйте список инициализации для инициализации переменных-членов:

template<typename T> 
LinkedList<T>::LinkedList(const LinkedList& l) : 
m_head(0), m_tail(0), m_size(0) 
{ 
// ... 
} 

Кроме того, может быть, вопрос стиля, это ковшики вместо время цикла:

// construct list from given list 
for (Node *n = l.m_head; n != 0; n = n->next) 
    append(m->data); 

На самом деле, я бы рекомендовал это вместо. Если у вас есть итераторы, вы бы сделали что-то вроде:

for (const_iterator iter = l.begin(); iter != l.end(); ++iter) 
    append(*iter); 

Это просто следует за стилем для петли лучше. (Инициализируйте что-нибудь, проверьте что-нибудь, сделайте что-нибудь). Хотя для итераторов это, вероятно, будет отличаться. (Более позднее)

---

Или я должен получить доступ к данным через соответствующий аксессору? (Я знаю, что у меня нет определенных аксессуаров).

Кроме того, я намерен создать пользовательский итератор, чтобы можно было выполнить итерацию по LinkedList. Должен ли я использовать в конструкторе копирования доступ к данным на каждом узле?

Эти итераторы - ваши аксессоры. Вам не надо хотите разоблачить свои внутренние указатели на хвост, которые являются рецептом катастрофы. Целью класса является не выставить детали. Тем не менее, итераторы являются абстрактной оболочкой вокруг этих деталей.

Как только у вас есть свои итераторы, вы можете использовать их для перебора списка вместо арифметики указателя. Это связано с этим недавно asked question.В общем, вы должны использовать свои абстракции для обработки ваших данных. Итак, да, если у вас есть ваши итераторы , вы должны использовать их для перебора данных.

Большинство классов, которые предоставляют итераторы, также предоставляют способ вставки данных с учетом итератора начала и окончания. Обычно это называется insert, например: insert(iterBegin, iterEnd). Это происходит через итераторы, добавляя данные в список.

Если у вас была такая функциональность, ваша копия-конструктор будет просто:

insert(l.begin(), l.end()); // insert the other list's entire range 

Где insert реализуется как для петли мы имели выше.

---

Другой вопрос (полностью вне темы, я знаю), когда и/или почему мы должны объявить указатель на LinkedList

LinkedList * л = новый LinkedList(); вместо LinkedList l;

Первый - динамическое распределение, второе - автоматическое (стековое) распределение. Вы должны предпочесть распределение стека. Это почти всегда быстрее и безопаснее (поскольку вам ничего не нужно удалять). На самом деле концепция RAII опирается на автоматическое хранение, поэтому деструкторы гарантированно работают.

Используйте только динамическое распределение, когда вам нужно.

Answer 2

Я думаю, что это по-прежнему очень ценное упражнение для реализации вашего собственного связанного списка, поскольку оно поможет вам узнать подробности указателей, структур данных и т. Д. Просто не забудьте использовать свой класс связанных списков в реальном коде, так как там есть много существующих библиотек, которые уже написаны и протестированы. Лучший код - это код, который вам не нужно писать. См. std::list.

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

Что касается создания списка с новым или его созданием в стеке, это решение относится не только к вашему классу, но и к структурам данных в целом. Более упрощенное эмпирическое правило: выделите в стеке, если сможете, выделите кучу, если вам нужно. Вам понадобится, например, если вам нужно перечислить список, чтобы пережить функцию, в которой она создана.

И снова возвращаясь к тому, чтобы не перекладывать собственный код, если вы решили использовать new для размещения в куче, вы должны использовать интеллектуальные указатели вместо того, чтобы пытаться самостоятельно управлять памятью. Приступайте к этой привычке. Не ждите, пока вы работаете над «настоящим» кодом. Многие люди, с которыми вы сталкиваетесь, будут бесполезны для вас в поисках лучшего кода и будут настаивать на «просто использовании new».