He encontrado que este código C++:¿Cambiar el tamaño de un vector invalida los iteradores?
vector<int> a;
a.push_back(1);
a.push_back(2);
vector<int>::iterator it = a.begin();
a.push_back(4);
cout << *it;
impresión de un número aleatorio grande; pero si agrega a.push_back(3) entre la 3ª y 4ª líneas, se imprimirá 1. ¿Puede explicarme esto?
Editado con una cuidadosa redacción más
sí, cambiar el tamaño de un vector podría invalidar todos los iteradores que señalan en el 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.
De modo que 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 al vector::reserve(), para reservar suficiente espacio para que esta copia no sea necesaria. En su caso, si llamó al 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 pueda realizar sin tener que reasignar la matriz, por lo que sus iteradores seguirán siendo válidos.
La primera oración no coincide con el último párrafo. Si cambia el tamaño de un vector a un tamaño que es menor que la capacidad reservada por una llamada de reserva anterior, se garantiza que los iteradores válidos antes del cambio de tamaño seguirán siendo válidos. Entonces: "Cambiar el tamaño de un vector puede invalidar todos los iteradores que apuntan al vector". –
La situación es así: se produce la invalidación * si * la nueva adición supera el espacio reservado * y * la nueva asignación de bajo nivel se encuentra en una parte diferente de la memoria (porque los asignadores de bajo nivel pueden intentar hacer crecer el bloque en su lugar)) Pero por diseño, 'std :: vector()' evita que descubras si se aplican estas condiciones. Por lo tanto, la única forma de asegurarse de que los iteradores permanezcan válidos después de un 'push_back()' es reservar manualmente el espacio suficiente antes de tiempo. – dmckee
En realidad, puede verificar la 'capacidad' en la mayoría de las implementaciones, aunque no sé si el estándar lo requiere. –
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 ninguna 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 los iteradores que hacen referencia 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.
Reducir el tamaño no debería. –
Las reglas para la invalidación del iterador son específicas de un contenedor.
Ahora invalidación puede tener 2 significados con un vector:
Como se puede ver, el segundo es mucho más estricta:
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 [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 prefieren hablar sobre el segundo requisito e invalidar un iterador simplemente significa que (* it) puede no producir el mismo resultado que antes.
Ahora que esto se dice, hay varias maneras para invalidar un iterador en un vector (de hecho, es la estructura más inestable del STL).
Durante adiciones de elementos:
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:
(1) La estructura interna de un std :: vector es un vector de T, esto es debido para la compatibilidad con la C-programas (usando & myVector.front() como la dirección de la matriz) y porque garantiza la contigüidad y una sobrecarga espacial mínima (es decir, la cantidad de espacio tomada por el vector de datos propios 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 desencadena 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 en la nueva matriz, descarta la matriz actual.
Como 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 eliminación de referencias era en realidad * (& m_vector.front() + n) reasignación no invalidaría ellos ... pero que sería menos eficiente.
(2) Contraer 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<int>(myVector));
Se crea primero un vector temporal, que destinará únicamente la cantidad de memoria que se necesita (con un mínimo en función de 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 futuras referencias, todas las clases STL de curiosidades de este tipo son en el sitio web de SGI: http://www.sgi.com/tech/stl/Vector.html
Si necesita iteradores permanecer válida después de añadir o eliminar a una colección, echar un vistazo a otro tipo de colección, como una lista.
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 no tengo la reputación de publicar esto con más de uno.
Cuando tengo preguntas como estas, un google rápido puede responderlas. Googleing "std vector push_back" puede llevarlo [aquí] (http://en.cppreference.com/w/cpp/container/vector/push_back), y si lo lee, dice "Si el nuevo tamaño() es mayor que la capacidad(), entonces todos los iteradores y referencias (incluido el iterador pasado) se invalidan. De lo contrario, solo se invalida el iterador pasado-al-fin ". – Cornstalks