LinkedList Kopierkonstruktor Implementierungsdetails

Question

Ich fange an, C++ zu lernen, und beschließe als Übung, eine einfache LinkedList Klasse (unten finden Sie einen Teil des Codes). Ich habe eine Frage bezüglich der Art und Weise der Kopie Konstruktor implementiert werden sollte und der beste Weg, die Daten auf dem ursprünglichen LinkedList zugegriffen werden sollte.

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

    }
...

Soll mein Kopierkonstruktor auf die Daten jedes Knotens der 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 den/die Accessor(s) nicht definiert habe).

Außerdem beabsichtige ich, einen benutzerdefinierten Iterator zu erstellen, so dass es möglich sein kann, über die LinkedList . Sollte ich in der Kopie Konstruktor verwenden, um die Daten auf jedem Knoten zugreifen?

Eine andere Frage (völlig off-topic, ich weiß), wann und/oder warum sollten wir einen Zeiger auf eine LinkedList

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

anstelle von

LinkedList<int> l;

Answer 1

Ich gehe davon aus, dass append die anfänglichen Kopf/Schwanz-Details richtig behandeln wird, ja? Wenn ja, dann ist das, was Sie jetzt haben, großartig und einfach: Gehen Sie durch die andere Liste, nehmen Sie deren Element und fügen Sie eine Kopie zu meiner Liste hinzu. Perfekt.

Nun, fast. Verwenden Sie eine Initialisierungsliste, um Mitgliedsvariablen 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, dies woks statt einer while-Schleife:

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

Ich würde stattdessen Folgendes empfehlen. Wenn Sie Iteratoren haben, würden Sie etwas tun wie:

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

Es entspricht einfach besser dem Stil einer for-Schleife. (Etwas initialisieren, etwas prüfen, etwas tun). Bei Iteratoren wird es wahrscheinlich anders sein. (Mehr dazu später)

---

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

Außerdem beabsichtige ich, einen benutzerdefinierten Iterator zu erstellen, so dass es möglich sein kann, über die LinkedList zu iterieren. Sollte ich in der Kopie Konstruktor verwenden, um die Daten auf jedem Knoten zugreifen?

Diese Iteratoren sind Ihre Accessoren. Sie nicht Ihre internen Kopf-Schwanz-Zeiger freilegen wollen, ist das ein Rezept für eine Katastrophe. Der Zweck der Klasse ist es no die Details aufdecken. Das heißt, Iteratoren sind die abstrakte Hülle für diese Details.

Sobald Sie Ihre Iteratoren haben, könnten Sie sie verwenden, um durch die Liste anstelle von Zeiger-Arithmetik zu iterieren. Dies knüpft an diese kürzlich gestellte Frage . Im Allgemeinen sollten Sie Ihre Abstraktionen verwenden, um mit Ihren Daten umzugehen. Also ja, sobald Sie Ihre Iteratoren vorhanden sind, sollten Sie diese verwenden, um die Daten zu iterieren.

Die meisten Klassen, die Iteratoren bereitstellen, bieten auch eine Möglichkeit, Daten mit einem Anfangs- und End-Iterator einzufügen. Dies wird normalerweise als insert etwa so: insert(iterBegin, iterEnd) . Diese Schleife durchläuft die Iteratoren und fügt die Daten an die Liste an.

Wenn Sie eine solche Funktionalität hätten, wäre Ihr Copy-Constructor einfach:

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

Wo insert ist wie die oben beschriebene for-Schleife implementiert.

---

Eine weitere Frage (völlig off-topic, ich weiß), wann und/oder warum sollten wir einen Zeiger auf eine LinkedList deklarieren

LinkedList *l = new LinkedList(); anstelle von LinkedList l;

Bei der ersten handelt es sich um eine dynamische Zuweisung, bei der zweiten um eine automatische (Stack-)Zuweisung. Sie sollten die Stack-Zuweisung bevorzugen. Sie ist fast immer schneller und auch sicherer (da Sie nichts löschen müssen). Ein Konzept namens RAII basiert auf automatischer Speicherung, so dass die Ausführung von Destruktoren garantiert ist.

Verwenden Sie die dynamische Zuteilung nur, wenn es sein muss.

Answer 2

Ich denke, es ist immer noch eine sehr wertvolle Übung, eine eigene verknüpfte Liste zu implementieren, da man so die Details von Zeigern, Datenstrukturen usw. lernt. Stellen Sie nur sicher, dass Sie Ihre Linked-List-Klasse nicht in echtem Code verwenden, da es viele bestehende Bibliotheken gibt, die bereits geschrieben und getestet sind. Der beste Code ist der Code, den man nicht schreiben muss. Siehe std::list .

Ich sehe kein Problem in der Art und Weise, wie Sie Ihren Kopierkonstruktor implementiert haben. Sie könnten jedoch gut daran tun, den Code in eine spezielle Kopierfunktion zu verschieben und diese vom Konstruktor aus aufzurufen, damit Sie weniger Code pflegen müssen. Aber im Allgemeinen ist die Verwendung der Implementierungsdetails Ihrer Klasse innerhalb der Klasse selbst nicht nur akzeptabel, sondern in vielen Fällen vorzuziehen, da dies so schnell wie möglich ist.

Was die Erstellung der Liste mit new gegenüber der Erstellung auf dem Stack angeht, so ist dies eine Entscheidung, die nicht nur für Ihre Klasse, sondern für Datenstrukturen im Allgemeinen gilt. Vereinfachte Faustregel: Auf dem Stack zuweisen, wenn Sie können, auf dem Heap zuweisen, wenn Sie müssen. Das ist zum Beispiel der Fall, wenn die Liste die Funktion, in der sie erstellt wird, überdauern soll.

Und um noch einmal darauf zurückzukommen, dass Sie Ihren eigenen Code nicht von Hand schreiben sollten, wenn Sie sich für die Verwendung von new auf dem Heap zuzuordnen, sollten Sie intelligente Zeiger verwenden, anstatt zu versuchen, den Speicher selbst zu verwalten. Machen Sie sich das jetzt zur Gewohnheit. Warten Sie nicht, bis Sie an "echtem" Code arbeiten. Viele Leute, denen Sie begegnen, werden Ihnen bei Ihrer Suche nach besserem Code nicht helfen und darauf bestehen, "einfach nur new ".