¿Cambiar el tamaño de un vector invalida los iteradores?

Encontré que este código C ++:

vector a; a.push_back(1); a.push_back(2); vector::iterator it = a.begin(); a.push_back(4); cout << *it; 

imprime un gran número aleatorio; pero si agrega a.push_back(3) entre la 3ª y la 4ª líneas, se imprimirá 1. ¿Puede explicarme esto?

Editado con una redacción más cuidadosa

sí, cambiar el tamaño de un vector puede invalidar todos los iteradores que apuntan al vector.

El vector se implementa asignando internamente una matriz donde se almacenan los datos. Cuando el vector crece, esa matriz puede quedarse sin espacio, y cuando lo hace, el vector asigna una matriz nueva, más grande, copia los datos a eso y luego elimina la matriz anterior.

Entonces sus iteradores anteriores, que apuntan a la memoria anterior, ya no son válidos. Si el vector se redimensiona hacia abajo (por ejemplo, pop_back() ), sin embargo, se utiliza la misma matriz. La matriz nunca se reduce de tamaño automáticamente.

Una forma de evitar esta reasignación (y la invalidación del puntero) es llamar primero a vector::reserve() , para reservar espacio suficiente para que esta copia no sea necesaria. En su caso, si llamó a a.reserve(3) antes de la primera operación push_back() , entonces la matriz interna sería lo suficientemente grande como para que push_back ‘s se pueda realizar sin tener que reasignar la matriz, por lo que sus iteradores permanecerán válido.

Los iteradores de vectores solo se invalidan cuando el vector realiza una reasignación.

La llamada a push_back(4) hace que el vector asigne un nuevo bloque de memoria: esto es lo que hace que su iterador no sea válido. Cuando también usa push_back(3) , no se realiza una reasignación para push_back(4) por lo que el iterador sigue siendo válido.

Sí, cualquier acción que pueda cambiar el tamaño del vector puede invalidar los iteradores.

Editar: eso incluye operaciones (por ejemplo, erase() , resize() ) que reducen el tamaño del contenedor. erase() no invalida todos los iteradores, pero invalida cualquier iterador que se refiera a cualquier punto después de los elementos borrados. resize() se define en términos de insert() y erase() , por lo que tiene el mismo potencial.

Las reglas para la invalidación del iterador son específicas de un contenedor.

Ahora la invalidación puede tener 2 significados con un vector:

  1. Invalidación = punto fuera del rango definido por [inicio, fin]
  2. Invalidación = apuntar a un objeto diferente del original

Como puede ver, el segundo es mucho más estricto:

 std::vector myVector; myVector.push_back(0); myVector.push_back(1); std::vector::iterator it = myVector.begin(); // it points to 0 myVector.erase(it); // it points to 1 myVector.erase(it); // it == myVector.end() 

En este caso, es ‘válido’ ya que siempre está en el rango inclusivo [inicio, fin] y, por lo tanto, se puede usar con seguridad para cualquier operación en myVector. Por otro lado, la expresión (* it) sigue cambiando: primero devuelve 0, luego 1, luego tiene un comportamiento indefinido …

En general, las personas preferirán hablar sobre el segundo requisito, e invalidar un iterador simplemente significa que (* it) puede no producir el mismo resultado que antes.


Ahora que se dice esto, hay varias formas de invalidar un iterador en un Vector (de hecho, es la estructura menos estable del STL).

Durante la adición de elementos:

  • Esto puede desencadenar una reasignación (1) si myVector.size () == myVector.capacity (), ya que al comprobar esto es propenso a errores, generalmente consideramos que cualquier adición invalidará los iteradores
  • Si quieres ser “quisquilloso” y sabe que la reasignación no se desencadena, entonces todavía tienes que preocuparte por la insert . La inserción de un elemento invalida los iteradores que apuntan a esta posición actual y todas las subsecuentes, ya que los elementos se desplazan un paso hacia el final del vector.

Durante la eliminación de elementos:

  • No hay reasignación, incluso si el búfer ahora es mucho más grande de lo necesario. Sin embargo, es posible forzar esto, usando la contracción para adaptarse a la expresión idiomática (2).
  • Todos los iteradores que apuntan más allá del elemento eliminado se invalidan. Especialmente, el iterador ‘final’ anterior ahora está más allá del rango [inicio, final] y no puede usarse con seguridad dentro de los algoritmos AWL, por ejemplo.

(1) La estructura interna de std :: vector es una matriz de T, esto se debe a la compatibilidad con los C-programs (usando & myVector.front () como la dirección de la matriz) y porque garantiza la contigüidad y un mínimo sobrecarga espacial (es decir, la cantidad de espacio tomado por los datos propios del vector frente a la cantidad de espacio ocupado por un objeto)

En cualquier momento, puedes saber cuántos objetos puede contener un vector usando el método .capacity ().

Cuando desea insertar un objeto y el vector no tiene la capacidad necesaria, se desencadena una llamada al método .reserve (size_t). Este método, si la cantidad de elementos requeridos es superior a la capacidad actual, desencadena una reasignación .

El vector luego asigna una nueva matriz de elementos (su tamaño es generalmente 2 * n + 1 donde n es la capacidad actual), copia los elementos de la matriz actual a la nueva matriz, descarta la matriz actual.

Debido a que descarta la matriz actual, sus iteradores se invalidan ya que los iteradores de vectores generalmente son simples punteros (para mayor eficiencia).

Tenga en cuenta que si los iteradores se implementan como: una referencia al vector + un recuento, y la desreferenciación en realidad era * (& m_vector.front () + n) la reasignación no los invalidaría … pero serían menos eficientes.

(2) Reducir para ajustar: Advertencia, esto desencadena una COPIA de los elementos e invalida los iteradores.

 // myVector has 10 elements, but myVector.capacity() == 1000 myVector.swap(std::vector(myVector)); 

Primero crea un vector temporal, que asignará solo tanta memoria como sea necesario (con un mínimo de acuerdo con la biblioteca) y copiará los elementos de myVector. Luego, la operación de intercambio intercambia los almacenamientos intermedios de myVector y esta copia, y así myVector ahora almacena un buffer con la cantidad mínima de memoria necesaria. Al final de la operación, se destruye el temporal y se libera la memoria que contiene.

Para referencia futura, todos los tipos de trucos STL como este se encuentran en el sitio web de SGI: http://www.sgi.com/tech/stl/Vector.html

Si necesita que los iteradores permanezcan válidos después de agregar o eliminar a una colección, eche un vistazo a otro tipo de colección, como una lista.

Sin embargo, lo mejor que puede hacer es identificar fuera de la matriz de funciones que desea de una colección (acceso aleatorio, etc.) y luego elegir el contenedor correcto.

Vea el artículo de la wikipedia sobre Standard_Template_Library Containers para un punto de partida. Si tiene dinero en efectivo, le recomiendo las “formas específicas de STL eficaz: 300 formas de mejorar el uso de la biblioteca de plantillas estándar” de Scott Meyer.

Disculpas por la falta de enlaces de apoyo, soy un novato aquí y carezco de la reputación de publicar esto con más de uno.