LinkedList Kopieren Konstruktor Implementierungsdetails

Question

Ich fange an, C++ zu lernen und als Übung beschließen, eine einfache LinkedList Klasse zu implementieren (unten gibt es einen Teil des Codes). Ich habe eine Frage bezüglich der Art, wie der Kopierkonstruktor implementiert werden sollte und wie die Daten auf dem Original LinkedList am besten zu erreichen sind.

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) { 

    } 
... 

Sollte mein Copykonstruktor Zugriff auf die Daten auf jedem Knoten des ursprünglichen LinkedList direkt?

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; 
    } 
} 

Oder sollte ich auf die Daten über den entsprechenden Accessor zugreifen? (Ich weiß, dass ich die Accessoren nicht definiert habe).

Ich beabsichtige auch, einen benutzerdefinierten Iterator zu erstellen, so dass es möglich ist, über die LinkedList zu iterieren. Soll ich im Kopierkonstruktor auf die Daten auf jedem Knoten zugreifen?

Eine andere Frage (komplett vom Thema, ich weiß), wann und/oder warum sollten wir einen Zeiger auf eine LinkedList

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

statt

LinkedList<int> l; 

Answer 1

erklären gehe ich davon aus ordnungsgemäß anhängen Handle die anfänglichen Kopf/Schwanz-Details, ja? Wenn das der Fall ist, ist das, was Sie jetzt haben, großartig und einfach: Gehen Sie durch die andere Liste, und nehmen Sie das Objekt und fügen Sie eine Kopie zu meiner Liste hinzu. Perfekt.

Nun, fast. Verwenden Sie eine Initialisiererliste auf Membervariablen zu initialisieren:

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

auch vielleicht eine Frage des Stils, das statt einer while-Schleife Wok:

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

In der Tat, würde ich dies stattdessen empfehlen. Wenn Sie Iteratoren haben, würden Sie etwas wie tun:

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

Es folgt nur den Stil einer for-Schleife besser. (Initialisiere etwas, überprüfe etwas, tue etwas). Für Iteratoren wird es wahrscheinlich anders sein. (Dazu später mehr)

---

Oder sollte ich Zugriff auf die Daten über den entsprechenden Zugriffs? (Ich weiß, dass ich die Accessoren nicht definiert habe).

Außerdem beabsichtige ich, einen benutzerdefinierten Iterator zu erstellen, damit es möglich ist, über die LinkedList zu iterieren. Soll ich im Kopierkonstruktor auf die Daten auf jedem Knoten zugreifen?

Diese Iteratoren sind Ihre Accessoren. Sie nicht wollen Ihre internen Kopf-Schwanz-Zeiger, dass ein Rezept für eine Katastrophe offen legen. Der Zweck der Klasse ist nicht die Details auszusetzen. Das heißt, Iteratoren sind der abstrakte Wrapper um diese Details.

Sobald Sie Ihre Iteratoren haben, können Sie sie verwenden, um die Liste anstelle von Zeigerarithmetik zu durchlaufen. Dies knüpft an diese kürzlich asked question.Im Allgemeinen sollten Sie Ihre Abstraktionen verwenden, um mit Ihren Daten umzugehen. Also, sobald Sie Ihre Iteratoren an Ort und Stelle haben, sollten Sie diese verwenden, um über die Daten zu iterieren.

Die meisten Klassen, die Iteratoren bereitstellen, bieten auch eine Möglichkeit zum Einfügen von Daten bei einem Anfangs- und Enditerator. Dies wird normalerweise insert genannt, wie folgt: insert(iterBegin, iterEnd). Dadurch werden die Iteratoren durchlaufen und die Daten an die Liste angehängt.

Wenn Sie eine solche Funktionalität hatte, Ihre Kopie-Konstruktor würde einfach sein:

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

Wo insert wie die for-Schleife implementiert wir oben hatten.

---

Eine andere Frage (komplett vom Thema, ich weiß), wann und/oder warum sollten wir einen Zeiger auf eine LinkedList

LinkedList * l = new LinkedList() zu erklären; anstelle von LinkedList l;

Die erste ist dynamische Zuweisung, die zweite ist automatische (Stapel-) Zuweisung. Sie sollten die Stapelzuordnung bevorzugen. Es ist fast immer schneller und auch sicherer (da Sie nichts löschen müssen). Tatsächlich basiert ein Konzept namens RAII auf automatischem Speicher, so dass Destruktoren garantiert laufen.

Verwenden Sie die dynamische Zuordnung nur, wenn Sie müssen.

Answer 2

Ich denke, es ist immer noch eine sehr wertvolle Übung, um Ihre eigene verkettete Liste zu implementieren, da es Ihnen hilft, die Details von Zeigern, Datenstrukturen usw. zu lernen. Stellen Sie sicher, dass Sie Ihre verkettete Listenklasse nicht in echtem Code verwenden sind viele vorhandene Bibliotheken, die bereits geschrieben und getestet wurden. Der beste Code ist der Code, den Sie nicht schreiben müssen. Siehe std::list.

Ich sehe kein Problem in der Art, wie Sie Ihren Kopierkonstruktor implementiert haben. Es kann gut sein, den Code in eine dedizierte Kopierfunktion zu verschieben und diese dann vom Konstruktor aus aufzurufen, damit weniger Code verwaltet werden muss. Aber im Allgemeinen ist die Verwendung der Implementierungsdetails Ihrer Klasse innerhalb der Klasse selbst nicht nur akzeptabel, sondern wird in vielen Fällen bevorzugt, da sie so schnell wie möglich ist.

Wie zum Erstellen der Liste mit neuen vs Erstellen auf dem Stapel ist dies eine Entscheidung, die nicht nur für Ihre Klasse, sondern Datenstrukturen im Allgemeinen gilt. Über vereinfachte Faustregel: Auf dem Stapel allokieren, wenn Sie können, auf dem Heap zuordnen, wenn Sie müssen. Sie müssten zum Beispiel, wenn Sie die Liste benötigen, um die Funktion zu überleben, in der es erstellt wird.

Und wieder zurück zu nicht Hand-Rolling eigenen Code, wenn Sie sich entscheiden, new zu verwenden, auf dem Heap zuweisen, sollten Sie Smart-Zeigern verwenden, anstatt zu versuchen, den Speicher selbst zu verwalten. Begeben Sie sich jetzt in diese Gewohnheit. Warten Sie nicht, bis Sie an echtem Code arbeiten. Viele Menschen, denen Sie begegnen, werden Ihnen bei Ihrer Suche nach besserem Code nicht helfen und bestehen darauf, "nur new" zu verwenden.