adelante adelante -- ++ campo con c++11 campo con linked-list camp codereview Relacionados El problema

simple forward_list


6
vote

problema

Español
  //  NODE implementation template <typename T> class forward_list_node{ public:     using value_type = T;     using pointer_type = T*;     using reference_type = T&;      forward_list_node(value_type value = 0) :  data(value), next(nullptr) {     }      forward_list_node<value_type> * get_next() const{         return this->next;     }      void set_next(forward_list_node<value_type> * node){         this->next = node;     }      value_type get_data() const{         return this->data;     }      void set_data(value_type value){         this->data = value;     }  private:     value_type data;     forward_list_node<value_type> * next; };   //  FORWARD_list implementation template <typename T> class forward_list{ public:     using value_type = T;     using pointer_type = T*;     using reference_type = T&;      using node = forward_list_node<value_type>;     using node_pointer = node *;      // ctor     forward_list() : head(nullptr), tail(nullptr){     }      //  dtor     ~forward_list(){         node_pointer ptr = this->head, tmptr;          while(ptr != nullptr){             tmptr = ptr;             std::cout << "GC: " << ptr->get_data() << " deleting..." << std::endl;             ptr = ptr->get_next();             delete tmptr;         }      }      forward_list& push_back(value_type value){         node_pointer item = new node(value);          if(this->tail) this->tail->set_next(item);         this->tail = item;         if(!this->head) this->head = this->tail;          return *this;     }      value_type pop_front(){         node_pointer item;         value_type data = 0;          if(this->tail && this->head){             data = this->head->get_data();             item = this->head;             this->head = this->head->get_next();         }          return data;     }   private:     node_pointer head, tail; };   

Aquí está el código que escribí para probar mis habilidades. Este código es un programa de lista simple en vínculo individual. Utiliza la función push_back () para presionar un elemento al final y pop_front () Function para obtener el primer elemento en la lista, como una cola .

Ahora necesito algunos comentarios para que mi programa sea más eficiente. ¿Qué me aconsejarías?

Original en ingles
//  NODE implementation template <typename T> class forward_list_node{ public:     using value_type = T;     using pointer_type = T*;     using reference_type = T&;      forward_list_node(value_type value = 0) :  data(value), next(nullptr) {     }      forward_list_node<value_type> * get_next() const{         return this->next;     }      void set_next(forward_list_node<value_type> * node){         this->next = node;     }      value_type get_data() const{         return this->data;     }      void set_data(value_type value){         this->data = value;     }  private:     value_type data;     forward_list_node<value_type> * next; };   //  FORWARD_list implementation template <typename T> class forward_list{ public:     using value_type = T;     using pointer_type = T*;     using reference_type = T&;      using node = forward_list_node<value_type>;     using node_pointer = node *;      // ctor     forward_list() : head(nullptr), tail(nullptr){     }      //  dtor     ~forward_list(){         node_pointer ptr = this->head, tmptr;          while(ptr != nullptr){             tmptr = ptr;             std::cout << "GC: " << ptr->get_data() << " deleting..." << std::endl;             ptr = ptr->get_next();             delete tmptr;         }      }      forward_list& push_back(value_type value){         node_pointer item = new node(value);          if(this->tail) this->tail->set_next(item);         this->tail = item;         if(!this->head) this->head = this->tail;          return *this;     }      value_type pop_front(){         node_pointer item;         value_type data = 0;          if(this->tail && this->head){             data = this->head->get_data();             item = this->head;             this->head = this->head->get_next();         }          return data;     }   private:     node_pointer head, tail; }; 

Here is the code i wrote to test my skills. This code is simple singly linked list program. it uses push_back() function to push an item at the end and pop_front() function to get the first item in the list just like a queue.

Now i need some feedbacks to make my program more efficient. What would you advise me?

        
         
         

Lista de respuestas

4
 
vote
vote
La mejor respuesta
 

Memoria de fugas

Tienes una pérdida de memoria. En pop_front , solo mueve el head , pero no eliminas la cabeza anterior.

  value_type pop_front(){     node_pointer item;     value_type data = 0;      if(this->tail && this->head){         data = this->head->get_data();         item = this->head;         this->head = this->head->get_next(); // old head unreachable!     }      return data; }   

Aquí hay un Mnemonic: Si una de sus funciones es una dual a otra, y una de estas usas new , la otra debe probable Uso delete < / Código>. push_back es el DUAL DE pop_front . Los primeros usos new , pero este último le falta delete .

es la cola vacía?

Vamos a usar un forward_list :

  head0  

¿Cómo puedo saber si he leído todos los contenidos de la cola? No es distinguible:

  head1  

Eso no va a terminar bien. Su interfaz mínima debe incluir un método 99887766655443312 . Puede agregar head3 , pero eso no es necesario.

Además, tienes que pensar en la cola vacía un poco más. Volviendo head4 No es posible si tengo una cola de head5 . De hecho, head6 ni siquiera se compila si uso un head7 .

Desde mi punto de vista, 99887766555443318 en la lista vacía debe lanzar una excepción o no devuelve nada. Así es como se especifica en head9 . Allí, value_type pop_front(){ node_pointer item; value_type data = 0; if(this->tail && this->head){ data = this->head->get_data(); item = this->head; this->head = this->head->get_next(); // old head unreachable! } return data; } 0 elimina el frente (si existe), y accede al frente real con value_type pop_front(){ node_pointer item; value_type data = 0; if(this->tail && this->head){ data = this->head->get_data(); item = this->head; this->head = this->head->get_next(); // old head unreachable! } return data; } 1 .

Después de esos dos comentarios, terminamos con el siguiente value_type pop_front(){ node_pointer item; value_type data = 0; if(this->tail && this->head){ data = this->head->get_data(); item = this->head; this->head = this->head->get_next(); // old head unreachable! } return data; } 2 :

  value_type pop_front(){     node_pointer item;     value_type data = 0;      if(this->tail && this->head){         data = this->head->get_data();         item = this->head;         this->head = this->head->get_next(); // old head unreachable!     }      return data; } 3  

en lugar de value_type pop_front(){ node_pointer item; value_type data = 0; if(this->tail && this->head){ data = this->head->get_data(); item = this->head; this->head = this->head->get_next(); // old head unreachable! } return data; } 4 , usamos value_type pop_front(){ node_pointer item; value_type data = 0; if(this->tail && this->head){ data = this->head->get_data(); item = this->head; this->head = this->head->get_next(); // old head unreachable! } return data; } 5 para construir un valor predeterminado del tipo dado. Ahora su value_type pop_front(){ node_pointer item; value_type data = 0; if(this->tail && this->head){ data = this->head->get_data(); item = this->head; this->head = this->head->get_next(); // old head unreachable! } return data; } 6 funciona con otros tipos que los puntos integrales o flotantes.

Ocultar detalles de implementación

Su value_type pop_front(){ node_pointer item; value_type data = 0; if(this->tail && this->head){ data = this->head->get_data(); item = this->head; this->head = this->head->get_next(); // old head unreachable! } return data; } 7 es un detalle de implementación de value_type pop_front(){ node_pointer item; value_type data = 0; if(this->tail && this->head){ data = this->head->get_data(); item = this->head; this->head = this->head->get_next(); // old head unreachable! } return data; } 8 . No debe estar expuesto al usuario. Además, se puede simplificar:

  value_type pop_front(){     node_pointer item;     value_type data = 0;      if(this->tail && this->head){         data = this->head->get_data();         item = this->head;         this->head = this->head->get_next(); // old head unreachable!     }      return data; } 9  

Ahora el usuario no sabe que hay ningún tipo de nodo. Después de todo, su interfaz pública de new0 nunca expuso esos nodos de la primera manera.

Su constructor está bien:

  new1  

Usted destructor también está bien, aunque no necesita el new2 . Además, no desea imprimir texto en un destructor por lo general, a excepción de la depuración. Tenga en cuenta que estoy usando el nuevo new3 descrito anteriormente aquí:

  new4  

El tamaño de la lista

Su new5 está bien. Sin embargo, no devolvería un 99887766655443336 . Sin embargo, eso depende de su caso de uso. Una función new7 debería estar bien, también.

también, agregaría un detalle adicional:

  new8  

El nuevo new9 proporciona una manera fácil de ver si la lista está vacía:

  delete0  

Esto solucionaría el problema que se muestra arriba en el ejemplo delete1 . Debe disminuir la variable, por supuesto, si usa delete2 , y debe agregarlo a sus variables de miembro. Pero ambos se dejan como ejercicio.

Naming

Su nombramiento estaba bien, sin embargo, si prefije o postfix sus variables de miembro, puede desplegar delete3 . De esa manera, también puede simplemente llamar delete4 delete5 por ejemplo. Pero eso es preferencia personal.

El único Naming-Nitpick real que tuvo fue delete6 en lugar de delete7 en el destructor. Sabemos que es un puntero debido a su tipo, es mucho más interesante de lo que apunta a .

Otro

Debe agregar un constructor de copia, operador de asignación de copia, mover constructor y mover el operador de asignación o prohibir las operaciones explícitamente con delete8 .

 

Leaking memory

You have a memory leak. In pop_front, you only move the head, but you don't delete the previous head.

value_type pop_front(){     node_pointer item;     value_type data = 0;      if(this->tail && this->head){         data = this->head->get_data();         item = this->head;         this->head = this->head->get_next(); // old head unreachable!     }      return data; } 

Here's a mnemonic: if one of your functions is a dual to another, and one of these uses new, the other one should likely use delete. push_back is the dual of pop_front. The first uses new, but the latter is missing delete.

Is the queue empty?

Let's use a forward_list:

forward_list<int> list_of_zeros;  list_of_zeros.push_back(0); list_of_zeros.push_back(0); list_of_zeros.push_back(0); 

How do I know whether I've read all the contents of the queue? It's not distinguishable:

for(int zero; (zero = list_of_zeros.pop_front()) == 0; ){     // handle zero } 

That's not going to end well. Your minimal interface should include a size method. You can add empty(), but that's not necessary.

Also, you have to think about the empty queue a little bit more. Returning 0 isn't possible if I have a queue of std::string. Indeed, pop_front won't even compile if I use a fordward<std::string>.

From my point of view, pop_front on the empty list should throw an exception or return nothing. That's how it is specified in std::forward_list. There pop_front removes the front (if it exists), and you access the actual front with front().

After those two comments, we end up with the following pop_front:

value_type pop_front(){     if(this->head == nullptr) {         return value_type();                  // see remark below         //or: throw <your_exception_type>;     }     data = this->head->get_data();      node_pointer old_head = this->head;      if(this->head == this->tail) {         this->head = nullptr;         this->tail = nullptr;     } else {         this->head = this->head->get_next();     }      delete old_head;      return data; } 

Instead of return 0, we use return value_type() to construct a default value of the given type. Now your pop_front works with other types than integral or floating point ones.

Hide implementation details

Your forward_list_node is an implementation detail of forward_list. It shouldn't be exposed to the user. Also, it can be simplified:

template <typename T> class forward_list{     struct forward_list_node {         T data;         forward_list_node * next;     };      using node = forward_list_node;     using node_pointer = node *;  public:     using value_type = T;     using pointer_type = T*;     using reference_type = T&; 

Now the user doesn't know that there is any kind of node. After all, your public interface of forward_list never exposed those nodes in the first way.

Your constructor is fine:

// ctor forward_list() : head(nullptr), tail(nullptr){ } 

You destructor is fine too, although you don't need the ptr. Also, you don't want to print text in a destructor usually, except for debugging. Note that I'm using the new forward_list_node described above here:

//  dtor ~forward_list(){     while(this->head != nullptr){         node_pointer old_head = this->head;         this->head = this->head->next;         delete old_head;     } } 

The size of the list

Your push_back is also fine. However, I would not return a forward_list&. That depends on your use case, though. A void function should be fine, too.

Also, I would add an additional detail:

// using your old interface for simplicity: forward_list& push_back(value_type value){     node_pointer item = new node(value);      if(this->tail) this->tail->set_next(item);     this->tail = item;     if(!this->head) this->head = this->tail;      number_of_nodes++; // this detail      return *this; } 

The new number_of_nodes provides an easy way to see whether the list is empty:

size_t size() const {     return number_of_nodes; } 

This would fix the problem shown above in the list_of_zeros example. You have to decrease the variable of course if you use pop_front, and you need to add it to your member variables. But both of them are left as an exercise.

Naming

Your naming was fine, however, if you prefix or postfix your member variables, you can drop this->. That way, you can also simply call get_data() data() for example. But that's personal preference.

The only real naming-nitpick I had was ptr instead of old_head in the destructor. We know that it's a pointer due to its type, it's much more interesting what it points to.

Other

You should add a copy constructor, copy assignment operator, move constructor and move assignment operator or forbid those operations explicitly with = delete.

 
 
3
 
vote

regla de cinco:

Dado que el contenedor tiene propiedad de elementos, es responsable de prevenir la corrupción de los datos dentro. Tiene que cuidar de esos recursos cuando se copia / se movió. Dado que se declara destructor explícito, la generación predeterminada de copia y se mueven la operación s está deshabilitada. Sería genial tener una regla de cinco implementados, especialmente para los contenedores.

El contenedor no es tan genérico

Este es el problema más fácil de usar. Cumplica una enorme restricción en el T .

  value_type data = 0;   

Esta línea le dice al compilador que 9988777665544332 debe estar asignable (copiar o mover) o en C ++ 17 Copiar constructible desde cero. Hay demasiados tipos que no son de copia constructibles o asignables de / a cero.

demasiadas llamadas de constructor de copia inútil:

Este es el mayor problema de rendimiento potencial.

Algunos ejemplos con algunas explicaciones:

      value_type data = 0;      if(this->tail && this->head){         data = this->head->get_data();         item = this->head;         this->head = this->head->get_next();     }      //excerpt from node     value_type get_data() const{         return this->data;     }   

Por lo tanto, la primera construcción de copia ocurre en la línea mencionada en el párrafo anterior. La segunda vez es cuando se invoca get_data() . Copia Construye los datos internos, luego copiar la asignación ocurre nuevamente cuando se le asigna 9988777665544335 . Esto culmina la naturaleza no genérica del código. Luego, la última construcción de copias ocurre cuando se devuelve data . 4 Copie las llamadas de construcción / asignación solo para obtener los datos de la cola. ¿No es manera demasiado ?

  forward_list& push_back(value_type value){     node_pointer item = new node(value);      if(this->tail) this->tail->set_next(item);     this->tail = item;     if(!this->head) this->head = this->tail;      return *this; }  //excerpt from node void set_data(value_type value){     this->data = value; }   

aproximadamente lo mismo que arriba, solo en otra dirección.

En realidad, el compilador puede elegir algunas (o todas las innecesarias) copiar las llamadas constructor, pero no significa que no se debe importarle al respecto.

Código genérico:

Algunas personas intentan escribir un caso especial primero, luego hazlo genérico. Aunque esto funciona para casos simples, no va a funcionar cuando el número de parámetros de plantilla / paquetes de parámetros comienzan a aumentar. El problema es que crea esa dependencia de muchos a muchos, lo que hace que "pegue diferentes partes", muy duro / propenso a errores al final. Para casos como este, debería funcionar.

Encontré pensar en términos de conceptos (o restricciones) una excelente manera de realizar la mayoría de las tareas de metaprogramas. Saber C ++ conceptos debe facilitarlo en eso.

Especificación de excepción:

Debido a copiar la naturaleza constructiva del contenedor, probablemente no pueda garantizar nada, por lo que podría ser genial arreglar eso.

 

Rule of five:

Since container has ownership of elements, it is responsible for preventing corruption of the data inside. It has to take care of those resources when copied/moved. Since explicit destructor is declared, default generation of copy and move operations is disabled. It would be great to have rule of five implemented, especially for the containers.

The container is not so generic

This is the biggest easy of use issue. It places enormous restriction on the T.

value_type data = 0; 

This line tells the compiler that T should be assignable (copy or move) or in C++17 copy constructible from zero. There are way too many types that are not copy constructible or assignable from/to zero.

Too many useless copy constructor calls:

This is the biggest potential performance issue.

A few examples with some explanations:

    value_type data = 0;      if(this->tail && this->head){         data = this->head->get_data();         item = this->head;         this->head = this->head->get_next();     }      //excerpt from node     value_type get_data() const{         return this->data;     } 

So, first copy construction happens on the line mentioned in the previous paragraph. The second time is when get_data() is invoked. It copy constructs the internal data, then copy assignment happens again when data is assigned to it. This culminates the non-generic nature of the code. Then, the last copy construction happens when data is returned. 4 copy construction/assignment calls just to get the data off of the queue. Isn't it way too much?

forward_list& push_back(value_type value){     node_pointer item = new node(value);      if(this->tail) this->tail->set_next(item);     this->tail = item;     if(!this->head) this->head = this->tail;      return *this; }  //excerpt from node void set_data(value_type value){     this->data = value; } 

Roughly the same as above, just in another direction.

Actually compiler can elide some (or all unnecessary ones) copy constructor calls, but it doesn't mean that one shouldn't care about it.

Generic code:

Some people try to write special case first, then make it generic. Although this works for simple cases, it is not going to work when number of template parameters/parameter packs start increasing. The problem is that it creates that many-to-many dependency, which makes "sticking different parts together" very hard/error prone at the end. For cases like this it should work though.

I found thinking in terms of concepts (or constraints) a great way to accomplish most of the metaprogramming tasks. Knowing C++ concepts should facilitate in that.

Exception specification:

Due to copy constructive nature of the container it probably can't guarantee anything, so it might be great to fix that.

 
 
         
         

Relacionados problema

4  Eliminar nodos alternativos de una lista vinculada  ( Delete alternate nodes of a linked list ) 
Si la lista vinculada es 1- & gt; 2- & gt; 3- & gt; 4 entonces la salida debe ser 1- & gt; 3. Si la lista vinculada es 1- & gt; 2- & gt; 3- & gt; 4- & gt; 5,...

4  ADT Pila con Linkedlist  ( Adt stack with linkedlist ) 
Actualmente estoy preparando para mi examen y estoy tratando de implementar algunos tipos de datos abstractos con listas vinculadas como preparación para el e...

1  DEQUEUE () en la implementación de la cola que utiliza una lista circular vinculada  ( Dequeue in queue implememtation that uses a circular linked list ) 
Utilizo una lista de enlaces circulares para implementar un queue , y solo sostiene un 99887776665544332 (Tenga en cuenta que 99887776655443333 enlaces a...

14  Implementando una lista relacionada adecuada para un entorno profesional  ( Implementing a proper linked list for a professional environment ) 
Tengo algunas preocupaciones: ¿Es normal que la clase tenga al menos un nodo? En otras palabras, esta implementación no puede tener una lista vinculada va...

0  Agregando dos números extremadamente grandes usando una estructura de datos personalizada  ( Adding two extremely large numbers using a custom data structure ) 
Tengo una implementación para agregar 2 números extremadamente grandes, mayor que el techo proporcionado por long , por ejemplo, 1238913893838383813813813813...

3  Lista doblemente vinculada en óxido usando los punteros crudos  ( Doubly linked list in rust using raw pointers ) 
Estoy practicando la oxidación escribiendo una lista doblemente vinculada usando los punteros crudos, 9988776655544330 Para asignar datos en el montón, 998...

5  Destructor para una lista vinculada  ( Destructor for a linked list ) 
El código completo se encuentra aquí: https://gist.github.com/4521540 < / p> Es un maniquí List en C ++. Mi preocupación es para liberar la memoria. No s...

10  Lista vinculada de objetos de conejito  ( Linked list of bunny objects ) 
El ejercicio es el ejercicio de la lista de conejitos vinculados; El último ejercicio para principiantes de aquí . Estoy buscando comentarios sobre absolut...

5  Cola de bloqueo con la exactitud de la lista doblemente vinculada  ( Lock free queue with doubly linked list correctness ) 
Necesito una cola de bloqueo que se implementa mediante la lista doblemente vinculada. es mi código correcto? ¿Hay algún error? ¿Hay alguna mejoras a realiz...

7  Simulando una lista enlazada lineal usando una matriz  ( Simulating a linear linked list using an array ) 
Un programa para simular una lista enlazada lineal usando una matriz: Especificaciones: A Y: cree un nuevo nodo con el valor de datos y, y agregue este...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos