LinkedList détails d'implémentation de constructeur de copie

Question

Je commence à apprendre C++ et comme un exercice décident d'implémenter une classe LinkedList simple (Ci-dessous, il y a une partie du code). J'ai une question concernant la façon dont le constructeur de copie devrait être mis en œuvre et la meilleure façon d'accéder aux données sur l'original 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) { 

    } 
... 

Si mon accès constructeur de copie des données sur chaque nœud du LinkedList d'origine directement?

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

Ou devrais-je accéder aux données via l'accesseur correspondant? (Je sais que je n'ai pas l'accesseur (s) défini).

En outre, j'ai l'intention de créer un itérateur personnalisé afin qu'il puisse être possible de parcourir le LinkedList. Dois-je utiliser dans le constructeur de copie pour accéder aux données sur chaque nœud?

Une autre question (complètement hors-sujet, je sais), quand et/ou pourquoi devrions-nous déclarer un pointeur vers une LinkedList

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

au lieu de

LinkedList<int> l; 

Answer 1

Je suppose append correctement gérer les détails tête/queue initiale, oui? Si oui, ce que vous avez maintenant est génial et simple: Parcourez l'autre liste, et prenez son article et ajoutez une copie à ma liste. Parfait.

Eh bien, presque. Utilisez une liste d'initialisation pour initialiser les variables membres:

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

Aussi, peut-être une question de style, ce WOKS au lieu d'une boucle while:

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

En fait, je vous recommande ce lieu. Lorsque vous avez des itérateurs, vous devez faire quelque chose comme:

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

Il suit simplement le style d'une boucle for-up. (Initialiser quelque chose, vérifier quelque chose, faire quelque chose). Bien que pour les itérateurs, ce sera probablement différent. (Plus tard)

---

Ou devrais-je accéder aux données via l'accesseur correspondant? (Je sais que je n'ai pas l'accesseur (s) défini).

De plus, j'ai l'intention de créer un itérateur personnalisé afin qu'il soit possible de parcourir la liste LinkedList. Dois-je utiliser dans le constructeur de copie pour accéder aux données sur chaque nœud?

Ces itérateurs sont vos accesseurs. Vous ne voulez pas voulez exposer vos pointeurs tête-queue internes, que d'une recette pour un désastre. Le but de la classe est de pas exposer les détails. Cela dit, les itérateurs sont l'enveloppe abstraite entourant ces détails. Une fois que vous avez vos itérateurs, vous pouvez les utiliser pour parcourir la liste au lieu de l'arithmétique du pointeur. Cela rejoint récemment asked question.En général, vous devez utiliser vos abstractions pour traiter vos données. Donc oui une fois que vous avez vos itérateurs en place, vous devriez utiliser ceux-ci pour parcourir les données.

La plupart des classes qui fournissent des itérateurs fournissent également un moyen d'insérer des données avec un itérateur de début et de fin. Ceci est généralement appelé insert, comme ceci: insert(iterBegin, iterEnd). Cela boucle à travers les itérateurs, en ajoutant ses données à la liste.

Si vous aviez cette fonctionnalité, votre copie constructeur serait simplement:

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

Où insert est mis en œuvre comme la boucle for nous avions ci-dessus.

---

Une autre question (complètement hors-sujet, je sais), quand et/ou pourquoi devrions-nous déclarer un pointeur vers une LinkedList

LinkedList * l = new LinkedList(); au lieu de LinkedList l;

La première est l'allocation dynamique, la seconde est l'allocation automatique (pile). Vous devriez préférer l'allocation de pile. C'est presque toujours plus rapide et plus sûr (puisque vous n'avez pas besoin de supprimer quoi que ce soit). En fait, un concept appelé RAII repose sur le stockage automatique, donc les destructeurs sont garantis pour fonctionner.

Utilisez uniquement l'allocation dynamique lorsque vous en avez besoin.

Answer 2

Je pense qu'il est toujours très utile d'implémenter votre propre liste chaînée car cela vous aide à apprendre les détails des pointeurs, des structures de données, etc. Assurez-vous de ne pas utiliser votre classe de liste chaînée en code réel. De nombreuses bibliothèques existantes sont déjà écrites et testées. Le meilleur code est le code que vous n'avez pas à écrire. Voir std::list.

Je ne vois aucun problème dans la façon dont vous avez implémenté votre constructeur de copie. Vous feriez bien de déplacer le code vers une fonction de copie dédiée et d'appeler cela depuis le constructeur, afin qu'il y ait moins de code à maintenir. Mais en général, l'utilisation des détails de mise en œuvre de votre classe à partir de la classe elle-même est non seulement acceptable, mais dans de nombreux cas, elle sera préférée car elle sera aussi rapide que possible. En ce qui concerne la création de la liste avec le nouveau ou la création sur la pile, c'est une décision qui s'applique non seulement à votre classe, mais aussi aux structures de données en général. Règle de base simplifiée: allouer sur la pile si vous le pouvez, allouer sur le tas si nécessaire. Vous auriez besoin par exemple si vous avez besoin de la liste pour survivre à la fonction dans laquelle il est créé.

Et encore une fois de ne pas rouler manuellement votre propre code, si vous décidez d'utiliser new pour allouer sur le tas, vous devriez utiliser des pointeurs intelligents au lieu d'essayer de gérer la mémoire vous-même. Prenez-vous cette habitude maintenant. N'attendez pas de travailler sur le code «réel». Beaucoup de gens que vous rencontrerez ne vous seront d'aucune utilité dans votre recherche d'un meilleur code, et insisteront pour "utiliser simplement new".