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

Question

Encontré que este código C ++:

vector<int> a;
a.push_back(1);
a.push_back(2);
vector<int>::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 tercera y la cuarta línea, imprimirá 1. ¿Me lo puede explicar?

Answer 1

Editado con una redacción más cuidadosa

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

El vector se implementa mediante la asignación interna de 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 nueva matriz más grande, copia los datos y luego elimina la matriz anterior.

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

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

Answer 2

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

La llamada a push_back (4) está causando que el vector asigne un nuevo bloque de memoria; esto es lo que hace que su iterador se vuelva inválido. Cuando también utiliza push_back (3) , no se realiza ninguna reasignación para push_back (4) , por lo que el iterador sigue siendo válido.

Answer 3

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 los iteradores todos , pero invalida cualquier iterador que se refiera a cualquier punto después del elemento o elementos borrados. resize () se define en términos de insert () y erase () , por lo que tiene el mismo potencial.

Answer 4

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. Invalidation = punto fuera del rango definido por [begin, end]
2. Invalidation = apunte a un objeto diferente del original

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

std::vector<int> myVector;
myVector.push_back(0);
myVector.push_back(1);

std::vector<int>::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' porque siempre está en el rango inclusivo [comenzar, finalizar] y, por lo tanto, puede usarse de manera segura 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 prefieren 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 las adiciones de elementos:

• Esto puede desencadenar una reasignación (1) si myVector.size () == myVector.capacity (), ya que al verificar esto es propenso a errores, generalmente consideramos que cualquier adición invalidará los iteradores
• Si quiere ser 'quisquilloso' y sabe que la reasignación no se activa, aún debe preocuparse por insert . Insertar un elemento invalida los iteradores que apuntan a esta posición actual y a todos los posteriores, 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, utilizando el modificador para ajustar (2).
• Todos los iteradores que apuntan más allá del elemento eliminado se invalidan. Especialmente, el iterador anterior 'final' ahora está más allá del rango [inicio, final] y no se puede usar de manera segura dentro de los algoritmos STL, por ejemplo.

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

En cualquier momento, puede 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 activa una llamada al método .reserve (size_t). Este método, si el número 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 son generalmente punteros simples (por eficiencia).

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

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

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

Primero crea un vector temporal, que asignará solo la cantidad de memoria necesaria (con un mínimo dependiendo de la biblioteca), y copiará los elementos de myVector. Luego, la operación de intercambio intercambia los búferes de myVector y esta copia, y así myVector ahora guarda un búfer con la mínima cantidad de memoria necesaria. Al final de la operación, el temporal se destruye y la memoria que contiene se libera.

Answer 5

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

Si necesita que los iteradores sigan siendo válidos después de agregar o eliminar 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 características que desea de una colección (acceso aleatorio, etc.) y luego elegir el contenedor correcto.

Consulte el artículo de Wikipedia sobre Standard_Template_Library Containers para obtener un punto de partida. Si tiene el efectivo, le recomiendo Scott Meyer '' Efectivo STL: 50 formas específicas para mejorar su uso de la Biblioteca de plantillas estándar ''.

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