¿La inserción de elementos en un vector daña un puntero del vector?

Question

En un programa para simular puertas lógicas me pasaran de utilizar matrices

node N[1000]; 

a vectores

vector<node> N; 

Y mi programa funcionaba perfectamente antes de usar vectores pero ahora que imprime resultados erróneos, por lo que trataron de depuración y descubrí que el insecto pasa aquí:

node* Simulator::FindNode(string h) 
{ 
    int i; 
    for(i = 0; i < NNodes; i++) 
    { 
     if (N[i].getname() == h) 
     { 
      return &N[i]; 
     } 
    } 

    node n ; 
    N.push_back(n); 
    N[NNodes].setname(h); 
    NNodes++; 
    return &N[NNodes-1]; //why?because of NNodes++ 
} 

// ... 

node* inp1; 
node* inp2; 
node* out; 
string NodeName; 

inp_file >> NodeName; 
inp1 = FindNode(NodeName); 
s1 = inp1; 

inp_file >> NodeName; 
inp2 = FindNode(NodeName); //inp1 is destroyed here 

inp_file >> NodeName; 
out = FindNode(NodeName); //inp2 and inp1 are destroyed here 

al llamar FindNode para la primera vez, la primera i puntero np1 apunta al lugar correcto que es &N[0].

Al llamar al FindNode por segunda vez, el 1er puntero inp1 apunta a basura y el segundo puntero inp2 apunta al lugar correcto &N[1].

Al llamar al FindNode por tercera vez, tanto el 1º como el 2º punteros (inp1, inp2) apuntan a la basura. Y el 3er puntero señala el lugar correcto.

¿Por qué sucedería eso?
¿Cómo funciona el vector cuando les inserto elementos y qué tipo de punteros debo usar para señalar los elementos de vectores?

Answer 1

Algunas cosas.

En primer lugar, por lo que puedo decir NNodes es solo el seguimiento del tamaño. Pero tienes std::vector::size() para eso. Luego lo usa para obtener el último elemento insertado, pero puede usar std::vector::back() para eso: return &N.back();.

También su parámetro se está pasando por valor, cuando probablemente debería pasarse por const-reference: const string& h. Esto evita copias innecesarias, y en general * debe pasar las cosas por referencia constante en lugar de por valor.

Y esto es malo:

node n; 
N.push_back(n); 
N[NNodes].setname(h); 

node probablemente debería tener un constructor que toma un const string& y establece el nombre durante la inicialización. De esa manera usted nunca puede tener un nodo sin nombre, como en:

node n(h); 
N.push_back(n); 

O más concisa:

N.push_back(node(h)); 

mucho mejor.

En segundo lugar, sí, vector puede invalidar los punteros a los elementos; es decir, cada vez que se necesita aumentar la capacidad del vector. Si puede, reserve() la capacidad por adelantado para evitar reasignaciones. En tu caso no puedes, entonces puedes ir a dos rutas diferentes.

La primera ruta es a level of indirection. En lugar de apuntar directamente a las cosas, ingrese su índice en la matriz. Tenga en cuenta que si bien su dirección puede cambiar, su ubicación dentro del vector no lo hará. Tendría Simulator::FindNode devuelva un size_t, y devuelva N.size() - 1. Agregue un miembro como node& GetNode(size_t index), que solo hace return N[index]; (se comprobará el error si lo desea). Ahora, cuando necesite un miembro, dele el índice a ese miembro en GetNode y obtendrá una referencia de ese nodo.

La otra ruta es cambiar su contenedor. Puede usar un deque, por ejemplo. Esto no tiene un almacenamiento contiguo, pero se parece mucho a vector. push_back y pop_back siguen siendo O (1), y todavía tiene buena coherencia de caché. (Y, por cierto, deque oficios de almacenamiento contiguo a la capacidad de push_front y pop_front en O (1) tiempo también)

Lo importante es que deque se no punteros Invalidate durante un empuje o pop operación de cualquiera fin.Funciona mediante una especie de híbrido de lista de vectores, donde se obtienen fragmentos de almacenamiento para elementos vinculados entre sí. Cambie su almacenamiento subyacente al deque (y no tome ni coloque nada en el medio), y puede señalar las cosas bien.

Sin embargo, por lo que puedo decir, tiene un mapa terriblemente ineficiente. Estás asignando nombres a nodos. Probablemente solo deba usar std::map, que tiene la interfaz exacta que intenta recrear. Incluso puede señalar cualquier elemento en un mapa, lo que nunca invalida las cosas.

_{* La regla es, pasar por const referencia a menos que el tipo es primitivo (incorporada como int, double, etc.), si el tamaño de los tipos es menor que sizeof(void*), o si van a necesitar una copia de todos modos.}

Es decir, no haga esto:

void foo(const std::string& s) 
{ 
    std::string ss(s); // make a copy, use copy 
} 

Pero hacer esto:

void foo(std::string s) // make a copy, use copy 
{ 
} 

Answer 2

Sí, puede volver a asignar todo el almacenamiento intermedio, haciendo que todos los punteros en la ubicación anterior no sean válidos.

Puede limitar esto mediante la asignación previa, pero eso es solo un aumento de rendimiento. La mejor manera es usar índices en lugar de punteros sin procesar.

Answer 3

Cuando un vector crece, se reasigna, lo que efectivamente invalida todos los punteros a los elementos del vector.

Si sabe de antemano cuántos elementos tendrá en el vector, puede usar el método reserve() para preasignar espacio.

Answer 4

Devolver un puntero a un miembro interno de STL probablemente no sea la mejor idea. Cuando le das un objeto a un contenedor STL básicamente estás cediendo el control del mismo. Le está diciendo al STL que puede moverlo como lo considere conveniente para mantener las promesas que le da el contenedor. Devolver el índice donde se encuentra el nodo es una mejor idea, como mencionó Steven Sudit.

Una vez que obtenga el índice, puede crear una función que devuelva una copia del contenido del nodo que le interesa. De esta manera, también mantiene la encapsulación de datos con el contenedor STL, no permitiendo que nadie más modifique su contenido.

Answer 5

Sí, las inserciones invalidarán los punteros antiguos para vectorizar elementos en la reasignación. Si desea utilizar punteros estables realmente difíciles, puede cambiar de vector a deque. Ofrece una interfaz muy similar al vector y puede crecer sin reasignar y mueve los contenidos anteriores al asignar más fragmentos.

El precio que paga por usar un deque en lugar de un vector es un nivel más de indirección en el acceso aleatorio. Dependiendo de su uso, eso puede ser totalmente irrelevante. Debería iterar sobre deque el deque completo si es necesario mediante el uso de iteradores. Eso será tan rápido como iterar sobre un vector.

La ganancia es: cero reasignaciones!

Answer 6

Imagina que necesitas escribir el código basado en arreglos para que pueda cambiar el tamaño de la matriz si es necesario.

Imagina cómo lo harías.

Imagine qué pasaría con los indicadores obsoletos.

Vuelva a escribir su código para usar índices en lugar de punteros, o para garantizar que no se vuelva a asignar, según corresponda.