¿Pop_back() realmente invalida *todos* los iteradores en un std::vector?

Question

std::vector<int> ints;

// ... fill ints with random values

for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
    if(*it < 10)
    {
        *it = ints.back();
        ints.pop_back();
        continue;
    }
    it++;
}

Este código no funciona porque cuando pop_back() se llama, it queda invalidado.Pero no encuentro ningún documento que hable sobre la invalidación de iteradores en std::vector::pop_back().

¿Tienes algunos enlaces sobre eso?

Answer 1

el llamado a pop_back() elimina el último elemento del vector y, por lo tanto, el iterador de ese elemento queda invalidado.El pop_back() la llamada lo hace no invalide los iteradores de los elementos anteriores al último elemento, solo la reasignación lo hará.De la "Referencia de la biblioteca estándar de C++" de Josutti:

Insertar o eliminar elementos invalida referencias, punteros e iteradores que se refieren al siguiente elemento.Si una inserción causa reasignación, invalida todas las referencias, iteradores y punteros.

Answer 2

Aquí está su respuesta, directamente de The Holy Standard:

23.2.4.2 Un vector satisface todos los requisitos de un contenedor y de un contenedor reversible (que figuran en dos tablas en 23.1) y de una secuencia, incluida la mayoría de los requisitos de secuencia opcionales (23.1.1).

23.1.1.12 Tabla 68 ExpressionA.POP_Back () return wystipoide operacional semánticaa.erase(--a.end())contenedorvector, lista, deque

Observe que a.pop_back es equivalente a a.erase(--a.end()).Mirando los detalles del vector sobre el borrado:

23.2.4.3.3 - borrado del iterador (posición del iterador) - efectos - Invalida todos los iteradores y referencias después del punto de borrado.

Por lo tanto, una vez que llama a pop_back, cualquier iterador del elemento final anterior (que ahora ya no existe) queda invalidado.

Al observar su código, el problema es que cuando elimina el elemento final y la lista queda vacía, aún lo incrementa y sale del final de la lista.

Answer 3

(Utilizo el esquema de numeración utilizado en el borrador de trabajo de C++ 0x, obtenible aquí

La Tabla 94 en la página 732 dice que pop_back (si existe en un contenedor de secuencia) tiene el siguiente efecto:

{ iterator tmp = a.end(); 
--tmp; 
a.erase(tmp); } 

23.1.1, punto 12 establece que:

A menos que se especifique lo contrario (ya sea explícitamente o definiendo una función en términos de otras funciones), invocar una función de miembro del contenedor o pasar un contenedor como argumento a una función de biblioteca no invalidará a los iteradores o cambiará los valores de los objetos dentro de ese contenedor .

Tanto el acceso a end() como la aplicación del prefijo no tienen tal efecto; sin embargo, erase():

23.2.6.4 (con respecto al punto 4 de vector.erase()):

Efectos:Invalida iteradores y referencias en o después del punto de borrado.

Entonces en conclusión:pop_back() solo invalidará un iterador hasta el último elemento, según el estándar.

Answer 4

Aquí hay una cita de la documentación STL de SGI (http://www.sgi.com/tech/stl/Vector.html):

[5] Los iteradores de un vector se invalidan cuando se reasigna su memoria.Además, insertar o eliminar un elemento en medio de un vector invalida todos los iteradores que apuntan a elementos que siguen al punto de inserción o eliminación.De ello se deduce que puede evitar que los iteradores de un vector sean invalidados si usa reserve() para preasignar tanta memoria como el vector usará, y si todas las inserciones y eliminaciones están al final del vector.

Creo que se deduce que pop_back solo invalida el iterador que apunta al último elemento y al iterador end().Realmente necesitamos ver los datos en los que falla el código, así como la forma en que no logra decidir qué está sucediendo.Por lo que puedo decir, el código debería funcionar; el problema habitual en dicho código es que la eliminación del elemento y ++ en el iterador ocurre en la misma iteración, como señala @mikhaild.Sin embargo, en este código no es el caso:it++ no sucede cuando se llama a pop_back.

Aún puede suceder algo malo cuando apunta al último elemento y el último elemento es menor que 10.Ahora estamos comparando un invalidado eso y terminar().Es posible que todavía funcione, pero no se pueden ofrecer garantías.

Answer 5

Los iteradores solo se invalidan en la reasignación del almacenamiento.Google es tu amigo: ver nota al pie 5.

Su código no funciona por otras razones.

Answer 6

pop_back() invalida sólo los iteradores que apuntan al último elemento.De la referencia de la biblioteca estándar de C++:

Insertar o eliminar elementos invalida referencias, punteros e iteradores que se refieren al siguiente elemento.Si una inserción causa reasignación, invalida todas las referencias, iteradores y punteros.

Entonces, para responder a tu pregunta, no, no invalida. todo iteradores.

Sin embargo, en su ejemplo de código, puede invalidar it cuando apunta al último elemento y el valor es inferior a 10.En cuyo caso, el STL de depuración de Visual Studio marcará el iterador como invalidado y, al comprobar si no es igual a end(), se mostrará una afirmación.

Si los iteradores se implementan como punteros puros (como probablemente lo harían en todos los casos de vectores STL que no son de depuración), su código debería funcionar.Si los iteradores son más que punteros, entonces su código no maneja este caso de eliminar correctamente el último elemento.

Answer 7

El error es que cuando "it" apunta al último elemento del vector y si este elemento es menor que 10, este último elemento se elimina.Y ahora "it" apunta a ints.end(), luego "it++" mueve el puntero a ints.end()+1, así que ahora "it" huye de ints.end(), y tienes un bucle infinito escaneando todos tus memoria :).

Answer 8

La "especificación oficial" es el estándar C++.Si no tiene acceso a una copia de C++03, puede obtener el último borrador de C++0x en el sitio web del Comité: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2723.pdf

La sección "Semántica operativa" de los requisitos del contenedor especifica que pop_back() es equivalente a { iterator i = end();--i;borrar(yo);}.la sección [vector.modifiers] para borrar dice "Efectos:Invalida iteradores y referencias en o después del punto de borrado."

Si desea el argumento de intuición, pop_back no falla (ya que la destrucción de value_types en contenedores estándar no puede generar excepciones), por lo que no puede realizar ninguna copia o asignación (ya que pueden generar), lo que significa que puede adivinar que el iterador del elemento borrado y el iterador final se invalidan, pero el resto no.

Answer 9

pop_back() sólo invalidará él si él estaba apuntando al último elemento del vector.Por lo tanto, su código fallará siempre que el último int del vector sea menor que 10, de la siguiente manera:

*es = ints.back();// Establece *it el valor que ya tiene
ints.pop_back();// Invalidar el iterador
continuar;// Realiza un bucle y accede al iterador no válido

Answer 10

Es posible que desee considerar usar el valor de retorno de borrar en lugar de cambiar el elemento posterior a la posición eliminada y volver a aparecer.Para secuencias, borrar devuelve un iterador que apunta al elemento más allá del elemento que se está eliminando.Tenga en cuenta que este método puede provocar más copias que su algoritmo original.

for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
    if(*it < 10)
        it = ints.erase( it );
    else
        ++it;
}

std::remove_if También podría ser una solución alternativa.

struct LessThanTen { bool operator()( int n ) { return n < 10; } };

ints.erase( std::remove_if( ints.begin(), ints.end(), LessThanTen() ), ints.end() );

std::remove_if es (como mi primer algoritmo) estable, por lo que puede que no sea la forma más eficiente de hacerlo, pero es conciso.

Answer 11

Consulta la información aquí (cplusplus.com):

Eliminar el último elemento

Elimina el último elemento del vector, reduciendo efectivamente el tamaño del vector en uno e invalidando todos los iteradores y referencias al mismo.