Cómo se refieren a estructuras recursivas a través de punteros usando vectores

Question

Tengo estructuras, llamémosles sn, que se parecen:

struct sn { 
    string name; 
    vector<sn*> connected_to; 
}; 

Ahora, supongamos que tengo el vector connected_to ya se anunció desde 0 - 9; y estoy conectando sn A, a sn B:

A.connected_to[0] = &B; 

Tengo la sensación de que estoy haciendo esto incorrectamente. Esencialmente lo que estoy tratando de hacer es evitar copiar la estructura cuando estoy conectando las estructuras ... es decir:

struct sn { 
    string name; 
    vector<sn> connected_to; 
}; 

// ... 

A.connected_to[0] = B; 

hace esto copia algo? El problema más fundamental es, por supuesto, que no entiendo cómo funcionan realmente los vectores, punteros y referencias.

Answer 1

Su segundo enfoque es probably illegal. Sin embargo, en algunas implementaciones de la biblioteca estándar podría funcionar. En esos casos, los objetos que agregue se copiarán (incluidos todos sus elementos secundarios: cuando se copia un contenedor estándar, también se copian todos los elementos que contiene). Por lo tanto, tal estructura de datos solo sería adecuada para representar un árbol.

Su primer enfoque, por otro lado, está bien, porque un puntero a un tipo incompleto es en sí mismo un tipo válido (§3.9.2/3 - [basic.compound]) ^✝. Como solo almacena un puntero, el objeto no se copiará. Sin embargo, debes tener cuidado cuando comiences a eliminar este gráfico. Dependiendo de qué tipo de gráfico que se está modelando, hay tres escenarios cuando las aplican:

^{✝_{There are some restrictions. Tenga en cuenta que en su caso el tipo solo está incompleto dentro de la definición (de sn); en el momento en que realmente lo usa, sn está completo, por lo tanto, también puede eliminarlo.}}

Trees

En caso de un árbol, cada niño tiene exactamente uno de los padres. Por lo tanto, al eliminar la estructura, comenzaría desde la raíz, y cada nodo simplemente tendría que eliminar todos sus elementos secundarios. Esto funcionaría recursivamente con las hojas, que no tienen hijos.

Para implementar esto de manera eficiente, puede almacenar los niños en un boost::ptr_vector<sn>. Por lo tanto, no tendrá que escribir un destructor usted mismo: el ptr_vector eliminará todos sus elementos.

Directed Acyclic Graphs (DAG)

En un DAG un nodo puede tener múltiples padres, por lo tanto usted tiene que tener cuidado de no borrar el mismo nodo dos veces (esto sucedería si cada nodo simplemente elimina todos sus hijos - por esta razón, una ptr_vector no funcionará aquí). Una forma de manejar esto es usar el recuento de referencias: cada nodo cuenta cuántos otros nodos apuntan a él, y solo cuando el recuento de referencias llega a cero, el nodo se elimina realmente. Puede automatizar esto almacenando los nodos en un std::vector<std::shared_ptr<sn> > (o boost::shared_ptr si usa un compilador anterior a C++ 11). El shared_ptr administra el recuento de referencias internamente, y solo eliminará el objeto al que apunta cuando ya no hay más shared_ptr -instancias apuntando a ese objeto (cuando el recuento de referencias es cero).

Cyclic Graphs

En un gráfico cíclico, un nodo también puede ser su propio padre (ya sea directamente, si contiene bucles, o indirectamente, a través de un ciclo). Por lo tanto, si cada nodo elimina todos sus elementos secundarios, eso daría como resultado un ciclo infinito de llamadas de destrucción. A shared_ptr también podría fallar aquí, porque cuando tiene un cycle of shared_ptr referencing each other, su recuento de referencia nunca llegará a cero. Ahora es el momento de pensar en la diferencia entre que posee un objeto y que hace referencia a. Cada nodo debe tener exactamente un padre que lo posee, pero puede tener varios que lo hagan referencia. El propietario, y solo el propietario, es responsable de eliminar ese nodo. Como se explica en la excelente respuesta que he vinculado anteriormente, esto se puede implementar usando una combinación de shared_ptr y weak_ptr.

Answer 2

A.connected_to[0] = &B;

sirve Copiar algo: el valor del puntero temporal de la expresión &B.

La clase de plantilla vectorial siempre realizará la construcción y destrucción automática de copias, pero la construcción de copia de un tipo primitivo equivale a la asignación y destrucción de un tipo primitivo, incluidos los punteros, es una operación no operativa.

Un puntero es un tipo muy básico: casi nada se hace automáticamente cuando se utilizan punteros. Debajo del capó es solo un valor integral correspondiente a una dirección en la memoria. Cuando desreferencia un puntero, el compilador simplemente confía en que el puntero mantenga la dirección de (o "apunte a") un objeto del tipo correcto.

Por ejemplo, las clases dadas Foo y Bar que no están relacionados por herencia:

Foo *ptr1, *ptr2; 
Bar *ptr3; 
    // All pointers are uninitialized. 
    // Dereferencing them is undefined behavior. Most likely a crash. 
    // The compiler will almost certainly issue a warning. 
ptr1= new Foo(); // ptr1 now points to a valid Foo. 
ptr2 = ptr1; // ptr2 points to the same Foo. 
ptr3=(Bar*)ptr1; // This is an obvious programmer error which I am making here for demonstration. 
// ptr3 points to the same block of memory as ptr1 & 2. 
// Dereferencing it is likely to do strange things. 
delete ptr1; // The compiler is allowed to set ptr1 to 0, but you can't rely on it. 
    // In either case dereferencing ptr1 is once again undefined behavior 
    // and the value of ptr2 is unchanged. 

El compilador es mucho menos probable que emitir una advertencia si ve ptr1 sin referencia que después de la eliminación de antes de la inicialización. Prácticamente nunca emitirá una advertencia si desreferencia ptr2 después de eliminar el objeto a través de ptr1. Si no tiene cuidado como otros lo han advertido, su vector de punteros puede llevarlo a inadvertidamente invocar un comportamiento indefinido de esta manera.

que presentó el muy mal molde de un Foo* a un Bar* para ilustrar la confianza absoluta del compilador en ti. El compilador le permite hacerlo y gustosamente tratará los bits como si fueran una barra cuando desreferencia ptr3.

La biblioteca estándar de C++ ofrece pocas clases de plantillas que ofrecen un comportamiento tipo puntero con mucha más seguridad automática. Por ejemplo, el std::shared_pointer:

std::shared_ptr es un puntero inteligente que gestiona la vida de un objeto, normalmente asignados con new. Varios objetos shared_ptr pueden administrar el mismo objeto; el objeto se destruye cuando se destruye o restablece el último shared_ptr apuntando a él. El objeto es destruido mediante delete-expression o un eliminador personalizado que se suministra a shared_ptr durante la construcción.

Si su entorno aún no proporciona la biblioteca estándar de C++ 11, podría proporcionar la biblioteca de impulso o el espacio de nombres std::tr1::. Ambos proporcionan un shared_ptr muy similar. std::auto_ptr, que está seguro de tener, es similar pero permite que solo un auto_ptr haga referencia a un objeto en un momento determinado. _{(C++ 11 introduce std::unique_ptr como un reemplazo previsto para auto_ptr. El auto_ptr es incompatible con la mayoría de los contenedores de la plantilla std. unique_ptr se pueden colocar en un contenedor de plantilla con std::move.)}

Es posible romper cualquiera de estos clases guardando u obteniendo el puntero y monkeying con ello, por ejemplo

Foo *basic_ptr=new Foo(); 
std::auto_ptr<Foo> fancy_ptr(basic_ptr); 
delete basic_ptr; // Oops! This statement broke our auto_ptr. 

También se romperá si se pasa en una dirección de una variable en el almacenamiento automático:

Foo aFoo; 
std::auto_ptr<Foo> fancy_ptr(&aFoo); // automatic storage automatically breaks auto_ptr 

Si usted acaba de hacer std::shared_ptr<sn> fresh_sn(new sn()) y luego usar un std::vector< std::shared_ptr<sn> > se le multa.