Detalles de implementación del constructor de copia LinkedList

Question

Estoy empezando a aprender C++ y como ejercicio decido implementar una clase simple LinkedList (A continuación hay una parte del código). Tengo una pregunta sobre la forma en que se debe implementar el constructor de copias y la mejor forma de acceder a los datos en el 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) { 

    } 
... 

En caso de que mi copia de acceso constructor de los datos en cada nodo del original LinkedList directamente?

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

¿O debería acceder a los datos a través del accesorio correspondiente? (Sé que no tengo el/los accesorio (s) definido (s)).

Además, tengo la intención de crear un iterador personalizado para que pueda ser iterado sobre el LinkedList. ¿Debo usar en el constructor de copia para acceder a los datos en cada nodo?

Otra pregunta (completamente fuera de tema, lo sé), cuándo y/o por qué deberíamos declarar un puntero a una LinkedList

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

en lugar de

LinkedList<int> l; 

Answer 1

Asumo Append adecuadamente manejar los detalles iniciales de la cabeza/cola, ¿sí? Si es así, lo que tienes ahora es genial y simple: ve a través de la otra lista, toma su artículo y agrega una copia a mi lista. Perfecto.

Bueno, casi. Utilice una lista de inicialización para inicializar variables miembro:

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

Además, tal vez una cuestión de estilo, este woks en lugar de un bucle while:

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

De hecho, me gustaría recomendar este lugar. Cuando tenga iteradores, haría algo como:

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

Simplemente sigue el estilo de un for-loop mejor. (Inicializa algo, revisa algo, haz algo). Aunque para los iteradores, probablemente sea diferente. (Más tarde)

---

O debería tener acceso a los datos a través del método correspondiente? (Sé que no tengo el/los accesorio (s) definido (s)).

Además, tengo la intención de crear un iterador personalizado para que pueda iterar sobre LinkedList. ¿Debo usar en el constructor de copia para acceder a los datos en cada nodo?

Esos iteradores son sus accesorios. Usted no desea exponer sus punteros internos de cola, que una receta para el desastre. El propósito de la clase es no exponer los detalles. Dicho esto, los iteradores son el contenedor abstracto alrededor de esos detalles.

Una vez que tenga sus iteradores, podrá usarlos para recorrer la lista en lugar de la aritmética del puntero. Esto se relaciona con esto recientemente asked question.En general, debes usar tus abstracciones para manejar tus datos. Entonces, sí, una vez que tenga sus iteradores en su lugar, debe usarlos para iterar a través de los datos.

La mayoría de las clases que proporcionan iteradores también proporcionan una forma de insertar datos dado un iterador de inicio y fin. Esto generalmente se llama insert, así: insert(iterBegin, iterEnd). Esto recorre los iteradores, añadiendo sus datos a la lista.

Si tuviera dicha funcionalidad, el constructor copia sería simplemente:

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

Dónde insert se implementa como el ciclo for que teníamos anteriormente.

---

Otra pregunta (completamente fuera de tema, lo sé), cuándo y/o por qué deberíamos declarar un puntero a una LinkedList

ListaEnlazada * l = new LinkedList(); en lugar de LinkedList l;

La primera es la asignación dinámica, la segunda es la asignación automática (pila). Deberías preferir la asignación de la pila. Casi siempre es más rápido y más seguro (ya que no necesita eliminar nada). De hecho, un concepto llamado RAII se basa en el almacenamiento automático, por lo que se garantiza la ejecución de los destructores.

Utilice solo la asignación dinámica cuando sea necesario.

Answer 2

Creo que sigue siendo un ejercicio muy valioso para implementar su propia lista vinculada, ya que le ayuda a aprender los detalles de punteros, estructuras de datos, etc. Solo asegúrese de no utilizar su clase de lista vinculada en código real ya que hay muchas bibliotecas existentes que ya están escritas y probadas. El mejor código es el código que no tienes que escribir. Ver std::list.

No veo ningún problema en la forma en que ha implementado su constructor de copia. Puede que sea conveniente mover el código a una función de copia dedicada y llamarlo desde el constructor, para que haya menos código que mantener. Pero, en general, utilizar los detalles de implementación de su clase dentro de la clase en sí no solo es aceptable, sino que en muchos casos se prefiere, ya que será lo más rápido posible.

En cuanto a crear la lista con nuevo vs crearlo en la pila, esta es una decisión que se aplica no solo a su clase sino a las estructuras de datos en general. Regla general simplificada: asigne en la pila si puede, asigne en el montón si lo necesita. Necesitaría, por ejemplo, si necesitara la lista para sobrevivir más tiempo que la función en la cual fue creada.

Y de nuevo volviendo a no rodar manualmente su propio código, si decide usar new para asignar en el montón, debe utilizar punteros inteligentes en lugar de tratar de administrar la memoria usted mismo. Sumérgete en este hábito ahora. No espere hasta que esté trabajando en el código 'real'. Muchas personas con las que te encuentres no serán útiles en tu búsqueda para escribir un código mejor e insistirán en "solo usar new".