simple - listas enlazadas en c++ codigo fuente

¿Por qué las listas enlazadas usan punteros en lugar de almacenar nodos dentro de los nodos? (10)

¿Por qué es mejor usar punteros en una lista vinculada?

La razón es que cuando crea un objeto Node , el compilador tiene que asignar memoria para ese objeto y para eso se calcula el tamaño del objeto.
El compilador conoce el tamaño del puntero a cualquier tipo y, por lo tanto, con el puntero autorreferencial se puede calcular el tamaño del objeto.

Si se usa Node m_node entonces el compilador no tiene idea sobre el tamaño del Node y se atascará en una recursión infinita de calcular sizeof(Node) . Recuerde siempre: una clase no puede contener un miembro de su propio tipo .

He trabajado con listas vinculadas anteriormente en Java, pero soy muy nuevo en C ++. Estaba usando esta clase de nodo que me fue dada en un proyecto muy bien

class Node { public: Node(int data); int m_data; Node *m_next; };

pero tenía una pregunta que no fue respondida muy bien. ¿Por qué es necesario usar

Node *m_next;

para apuntar al siguiente nodo en la lista en lugar de

Node m_next;

Entiendo que es mejor usar la versión de puntero; No voy a discutir hechos, pero no sé por qué es mejor. Obtuve una respuesta no tan clara sobre cómo el puntero es mejor para la asignación de memoria, y me preguntaba si alguien aquí podría ayudarme a comprenderlo mejor.

C ++ no es Java. Cuando escribes

Node m_next;

en Java, eso es lo mismo que escribir

Node* m_next;

en C ++. En Java, el puntero es implícito, en C ++ es explícito. Si tú escribes

Node m_next;

en C ++, coloca una instancia de Node allí dentro del objeto que está definiendo. Siempre está ahí y no se puede omitir, no se puede asignar con new y no se puede eliminar. Este efecto es imposible de lograr en Java, y es totalmente diferente de lo que Java hace con la misma sintaxis.

El último ( Node m_next ) debería contener el nodo. No lo señalaría. Y entonces no habría vinculación de elementos.

El enfoque que describe es compatible no solo con C ++, sino también con su lenguaje (en su mayoría) de subconjunto C. Aprender a desarrollar una lista vinculada de estilo C es una buena manera de presentarse a las técnicas de programación de bajo nivel (como la administración manual de memoria), pero generalmente no es una práctica recomendada para el desarrollo moderno de C ++.

A continuación, he implementado cuatro variaciones sobre cómo administrar una lista de elementos en C ++.

raw_pointer_demo utiliza el mismo enfoque que el suyo: se requiere la gestión manual de la memoria con el uso de punteros sin formato. El uso de C ++ aquí es solo para syntactic-sugar , y el enfoque utilizado es compatible con el lenguaje C.
En shared_pointer_demo la gestión de la lista todavía se realiza manualmente, pero la gestión de la memoria es automatic (no utiliza punteros sin formato). Esto es muy similar a lo que probablemente haya experimentado con Java.
std_list_demo usa el contenedor de list biblioteca estándar. Esto muestra cuán mucho más fáciles son las cosas si confía en las bibliotecas existentes en lugar de crear las suyas propias.
std_vector_demo usa el contenedor de vector biblioteca estándar. Esto gestiona el almacenamiento de la lista en una única asignación de memoria contigua. En otras palabras, no hay punteros a elementos individuales. Para ciertos casos bastante extremos, esto puede volverse significativamente ineficiente. Sin embargo, en casos típicos, esta es la mejor práctica recomendada para la gestión de listas en C ++ .

De nota: De todos estos, solo el raw_pointer_demo realmente requiere que la lista se destruya explícitamente para evitar la "pérdida" de memoria. Los otros tres métodos destruirían automáticamente la lista y su contenido cuando el contenedor se salga del alcance (al finalizar la función). El punto es: C ++ es capaz de ser muy "similar a Java" a este respecto, pero solo si elige desarrollar su programa utilizando las herramientas de alto nivel a su disposición.

/*BINFMTCXX: -Wall -Werror -std=c++11 */ #include <iostream> #include <algorithm> #include <string> #include <list> #include <vector> #include <memory> using std::cerr;

/** Brief Create a list, show it, then destroy it */ void raw_pointer_demo() { cerr << "/n" << "raw_pointer_demo()..." << "/n"; struct Node { Node(int data, Node *next) : data(data), next(next) {} int data; Node *next; }; Node * items = 0; items = new Node(1,items); items = new Node(7,items); items = new Node(3,items); items = new Node(9,items); for (Node *i = items; i != 0; i = i->next) cerr << (i==items?"":", ") << i->data; cerr << "/n"; // Erase the entire list while (items) { Node *temp = items; items = items->next; delete temp; } }

raw_pointer_demo()... 9, 3, 7, 1

/** Brief Create a list, show it, then destroy it */ void shared_pointer_demo() { cerr << "/n" << "shared_pointer_demo()..." << "/n"; struct Node; // Forward declaration of ''Node'' required for typedef typedef std::shared_ptr<Node> Node_reference; struct Node { Node(int data, std::shared_ptr<Node> next ) : data(data), next(next) {} int data; Node_reference next; }; Node_reference items = 0; items.reset( new Node(1,items) ); items.reset( new Node(7,items) ); items.reset( new Node(3,items) ); items.reset( new Node(9,items) ); for (Node_reference i = items; i != 0; i = i->next) cerr << (i==items?"":", ") << i->data; cerr<<"/n"; // Erase the entire list while (items) items = items->next; }

shared_pointer_demo()... 9, 3, 7, 1

/** Brief Show the contents of a standard container */ template< typename C > void show(std::string const & msg, C const & container) { cerr << msg; bool first = true; for ( int i : container ) cerr << (first?" ":", ") << i, first = false; cerr<<"/n"; }

/** Brief Create a list, manipulate it, then destroy it */ void std_list_demo() { cerr << "/n" << "std_list_demo()..." << "/n"; // Initial list of integers std::list<int> items = { 9, 3, 7, 1 }; show( "A: ", items ); // Insert ''8'' before ''3'' items.insert(std::find( items.begin(), items.end(), 3), 8); show("B: ", items); // Sort the list items.sort(); show( "C: ", items); // Erase ''7'' items.erase(std::find(items.begin(), items.end(), 7)); show("D: ", items); // Erase the entire list items.clear(); show("E: ", items); }

std_list_demo()... A: 9, 3, 7, 1 B: 9, 8, 3, 7, 1 C: 1, 3, 7, 8, 9 D: 1, 3, 8, 9 E:

/** brief Create a list, manipulate it, then destroy it */ void std_vector_demo() { cerr << "/n" << "std_vector_demo()..." << "/n"; // Initial list of integers std::vector<int> items = { 9, 3, 7, 1 }; show( "A: ", items ); // Insert ''8'' before ''3'' items.insert(std::find(items.begin(), items.end(), 3), 8); show( "B: ", items ); // Sort the list sort(items.begin(), items.end()); show("C: ", items); // Erase ''7'' items.erase( std::find( items.begin(), items.end(), 7 ) ); show("D: ", items); // Erase the entire list items.clear(); show("E: ", items); }

std_vector_demo()... A: 9, 3, 7, 1 B: 9, 8, 3, 7, 1 C: 1, 3, 7, 8, 9 D: 1, 3, 8, 9 E:

int main() { raw_pointer_demo(); shared_pointer_demo(); std_list_demo(); std_vector_demo(); }

En java

Node m_node

almacena un puntero a otro nodo. No tienes elección al respecto. En C ++

Node *m_node

significa lo mismo. La diferencia es que en C ++ puedes almacenar el objeto en lugar de un puntero. Es por eso que tienes que decir que quieres un puntero. En C ++:

Node m_node

significa almacenar el nodo aquí (y eso claramente no puede funcionar para una lista; terminas con una estructura definida recursivamente).

En una nota al margen, si el primer miembro de una clase o estructura es el siguiente puntero (por lo que no hay funciones virtuales o cualquier otra característica de una clase que signifique que el siguiente no es el primer miembro de una clase o estructura), entonces usted puede usar una clase o estructura "base" con solo un puntero siguiente y usar un código común para operaciones básicas de listas vinculadas como agregar, insertar antes, recuperar desde el frente, .... Esto se debe a que C / C ++ garantiza que la dirección del primer miembro de una clase o estructura es la misma que la dirección de la clase o estructura. La clase o estructura del nodo base solo tendría un puntero siguiente para ser utilizado por las funciones básicas de la lista vinculada, luego la conversión de texto se usaría según sea necesario para convertir entre el tipo de nodo base y los tipos de nodo "derivados". Nota al margen: en C ++, si la clase de nodo base solo tiene un siguiente puntero, entonces supongo que las clases derivadas no pueden tener funciones virtuales.

No es solo mejor, es la única forma posible.

Si almacenara un objeto Node dentro de sí mismo, ¿cuál sería sizeof(Node) ? Sería sizeof(int) + sizeof(Node) , que sería igual a sizeof(int) + (sizeof(int) + sizeof(Node)) , que sería igual a sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node))) , etc. hasta el infinito.

Un objeto como ese no puede existir. Es imposible

Porque esto en C ++

int main (..) { MyClass myObject; // or MyClass * myObjectPointer = new MyClass(); .. }

es equivalente a esto en Java

public static void main (..) { MyClass myObjectReference = new MyClass(); }

donde ambos crean un nuevo objeto de MyClass utilizando el constructor predeterminado.

Utiliza un puntero, de lo contrario su código:

class Node { //etc Node m_next; //non-pointer };

... no se compilaría, ya que el compilador no puede calcular el tamaño del Node . Esto se debe a que depende de sí mismo, lo que significa que el compilador no puede decidir cuánta memoria consumiría.

Visión de conjunto

Hay 2 formas de referenciar y asignar objetos en C ++, mientras que en Java solo hay una.

Para explicar esto, los siguientes diagramas muestran cómo se almacenan los objetos en la memoria.

1.1 Elementos de C ++ sin punteros

class AddressClass { public: int Code; char[50] Street; char[10] Number; char[50] POBox; char[50] City; char[50] State; char[50] Country; }; class CustomerClass { public: int Code; char[50] FirstName; char[50] LastName; // "Address" IS NOT A pointer !!! AddressClass Address; }; int main(...) { CustomerClass MyCustomer(); MyCustomer.Code = 1; strcpy(MyCustomer.FirstName, "John"); strcpy(MyCustomer.LastName, "Doe"); MyCustomer.Address.Code = 2; strcpy(MyCustomer.Address.Street, "Blue River"); strcpy(MyCustomer.Address.Number, "2231 A"); return 0; } // int main (...) ....................................... ..+---------------------------------+.. ..| AddressClass |.. ..+---------------------------------+.. ..| [+] int: Code |.. ..| [+] char[50]: Street |.. ..| [+] char[10]: Number |.. ..| [+] char[50]: POBox |.. ..| [+] char[50]: City |.. ..| [+] char[50]: State |.. ..| [+] char[50]: Country |.. ..+---------------------------------+.. ....................................... ..+---------------------------------+.. ..| CustomerClass |.. ..+---------------------------------+.. ..| [+] int: Code |.. ..| [+] char[50]: FirstName |.. ..| [+] char[50]: LastName |.. ..+---------------------------------+.. ..| [+] AddressClass: Address |.. ..| +-----------------------------+ |.. ..| | [+] int: Code | |.. ..| | [+] char[50]: Street | |.. ..| | [+] char[10]: Number | |.. ..| | [+] char[50]: POBox | |.. ..| | [+] char[50]: City | |.. ..| | [+] char[50]: State | |.. ..| | [+] char[50]: Country | |.. ..| +-----------------------------+ |.. ..+---------------------------------+.. .......................................

Advertencia : la sintaxis de C ++ utilizada en este ejemplo es similar a la sintaxis de Java. Pero, la asignación de memoria es diferente.

1.2 Elementos de C ++ que utilizan punteros

class AddressClass { public: int Code; char[50] Street; char[10] Number; char[50] POBox; char[50] City; char[50] State; char[50] Country; }; class CustomerClass { public: int Code; char[50] FirstName; char[50] LastName; // "Address" IS A pointer !!! AddressClass* Address; }; ....................................... ..+-----------------------------+...... ..| AddressClass +<--+.. ..+-----------------------------+...|.. ..| [+] int: Code |...|.. ..| [+] char[50]: Street |...|.. ..| [+] char[10]: Number |...|.. ..| [+] char[50]: POBox |...|.. ..| [+] char[50]: City |...|.. ..| [+] char[50]: State |...|.. ..| [+] char[50]: Country |...|.. ..+-----------------------------+...|.. ....................................|.. ..+-----------------------------+...|.. ..| CustomerClass |...|.. ..+-----------------------------+...|.. ..| [+] int: Code |...|.. ..| [+] char[50]: FirstName |...|.. ..| [+] char[50]: LastName |...|.. ..| [+] AddressClass*: Address +---+.. ..+-----------------------------+...... ....................................... int main(...) { CustomerClass* MyCustomer = new CustomerClass(); MyCustomer->Code = 1; strcpy(MyCustomer->FirstName, "John"); strcpy(MyCustomer->LastName, "Doe"); AddressClass* MyCustomer->Address = new AddressClass(); MyCustomer->Address->Code = 2; strcpy(MyCustomer->Address->Street, "Blue River"); strcpy(MyCustomer->Address->Number, "2231 A"); free MyCustomer->Address(); free MyCustomer(); return 0; } // int main (...)

Si marca la diferencia entre ambas formas, verá que en la primera técnica, el elemento de dirección se asigna dentro del cliente, mientras que en la segunda forma, debe crear cada dirección explícitamente.

Advertencia: Java asigna objetos en la memoria como esta segunda técnica, pero la sintaxis es como la primera forma, lo que puede ser confuso para los recién llegados a "C ++".

Implementación

Entonces su ejemplo de lista podría ser algo similar al siguiente ejemplo.

class Node { public: Node(int data); int m_data; Node *m_next; }; ....................................... ..+-----------------------------+...... ..| Node |...... ..+-----------------------------+...... ..| [+] int: m_data |...... ..| [+] Node*: m_next +---+.. ..+-----------------------------+...|.. ....................................|.. ..+-----------------------------+...|.. ..| Node +<--+.. ..+-----------------------------+...... ..| [+] int: m_data |...... ..| [+] Node*: m_next +---+.. ..+-----------------------------+...|.. ....................................|.. ..+-----------------------------+...|.. ..| Node +<--+.. ..+-----------------------------+...... ..| [+] int: m_data |...... ..| [+] Node*: m_next +---+.. ..+-----------------------------+...|.. ....................................v.. ...................................[X]. .......................................

Resumen

Dado que una lista vinculada tiene una cantidad variable de elementos, la memoria se asigna según sea necesario y está disponible.

ACTUALIZAR:

También vale la pena mencionar, como @haccks comentó en su publicación.

Que a veces, las referencias o punteros de objetos, indican elementos anidados (también conocido como "Composición UML").

Y a veces, las referencias o punteros de objetos indican elementos externos (también conocido como "Agregación UML").

Pero, los elementos anidados de la misma clase, no se pueden aplicar con la técnica "sin puntero".