index - std:: vector c++ delete
¿Pop_back() realmente invalida*todos*iteradores en un std:: vector? (11)
(Utilizo el esquema de numeración como se usa en el borrador de trabajo C ++ 0x, que se puede obtener 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 miembro de contenedor o pasar un contenedor como argumento a una función de biblioteca no invalidará los iteradores ni cambiará los valores de los objetos dentro de ese contenedor .
Ambos accediendo a end () como aplicar prefix-- no tienen tal efecto, erase () however:
23.2.6.4 (referente a vector.erase () punto 4):
Efectos: invalida iteradores y referencias en o después del punto del borrado.
Entonces, en conclusión: pop_back () solo invalidará un iterador al último elemento, según el estándar.
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 se llama a pop_back() , it invalida. Pero no encuentro ningún documento que hable sobre la invalidación de los iteradores en std::vector::pop_back() .
¿Tienes algunos enlaces sobre eso?
Aquí está su respuesta, directamente de The Holy Standard:
23.2.4.2 Un vector cumple con todos los requisitos de un contenedor y de un contenedor reversible (dado en dos tablas en 23.1) y de una secuencia, incluyendo la mayoría de los requisitos de secuencia opcionales (23.1.1).
23.1.1.12 Tabla 68 expressiona.pop_back () return typevoid semántica operacional a.erase (- a.end ()) containervector, list, deque
Observe que a.pop_back es equivalente a a.erase (- a.end ()). Mirando las especificaciones del vector en el borrado:
23.2.4.3.3 - iterator erase (iterator position) - effects - Invalida todos los iteradores y referencias después del punto del borrado
Por lo tanto, una vez que llame a pop_back, cualquier iterador del elemento final anterior (que ahora ya no existe) se invalidará.
Al mirar su código, el problema es que cuando elimina el elemento final y la lista se vacía, aún la incrementa y sale del final de la lista.
Aquí hay una cita de la documentación de STL de SGI ( http://www.sgi.com/tech/stl/Vector.html ):
[5] Los iteradores de un vector se invalidan cuando su memoria se reasigna. Además, insertar o eliminar un elemento en el medio de un vector invalida todos los iteradores que apuntan a elementos que siguen al punto de inserción o eliminación. De esto se deduce que puede evitar que los iteradores de un vector se invaliden si usa reserve () para preasignar tanta memoria como el vector alguna vez 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 final (). Realmente necesitamos ver los datos para los cuales el código falla, así como la manera en que falla al decidir qué está pasando. 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 el ++ en el iterador ocurren en la misma iteración, como señala @mikhaild. Sin embargo, en este código no es el caso: ++ no ocurre cuando se llama a pop_back.
Algo malo aún puede suceder cuando apunta al último elemento, y el último elemento es menor que 10. Ahora estamos comparando un elemento invalidado con un end (). Todavía puede funcionar, pero no se pueden hacer garantías.
Consulte 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 las referencias a él.
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 (), el siguiente "it ++" mueve el puntero a ints.end () + 1, por lo que ahora "it" se está escapando de ints.end (), y tienes un loop infinito escaneando todo tu memoria :).
Es posible que desee considerar el uso del valor de retorno de borrar en lugar de cambiar el elemento posterior a la posición eliminada y volver a aparecer. Para el borrado de secuencias, se devuelve un iterador que señala el elemento uno más allá del elemento que se elimina. Tenga en cuenta que este método puede causar más copia 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 std::remove_if (como mi primer algoritmo), por lo que puede no ser la forma más eficiente de hacerlo, pero es breve.
La "especificación oficial" es el estándar de 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 operacional" de los requisitos del contenedor especifica que pop_back () es equivalente a {iterator i = end (); --yo; borrar (i); }. la sección [vector.modifiers] para borrar dice "Efectos: invalida iteradores y referencias en o después del punto del borrado".
Si desea el argumento de la intuición, pop_back es no-fail (ya que la destrucción de value_types en contenedores estándar no permite lanzar excepciones), por lo que no puede hacer ninguna copia o asignación (ya que pueden lanzar), lo que significa que puede adivinar el iterador del elemento borrado y el iterador final son invalidados, pero el resto no.
La llamada a pop_back() elimina el último elemento en el vector y, por lo tanto, el iterador de ese elemento se invalida. La llamada pop_back() no invalida los iteradores a los elementos antes del último elemento, solo la reasignación hará eso. De la "Referencia de la biblioteca estándar de C ++" de Josuttis:
Insertar o quitar elementos invalida referencias, punteros e iteradores que hacen referencia al siguiente elemento. Si una inserción provoca la reasignación, invalida todas las referencias, iteradores y punteros.
Los iteradores solo se invalidan al reasignar el almacenamiento. Google es tu amigo: ver nota 5 .
Tu código no funciona por otros motivos.
pop_back () solo lo invalidará si apunta al último elemento del vector. Por lo tanto, su código fallará siempre que el último int en el vector sea menor que 10, como se muestra a continuación:
* it = ints.back (); // Establecer * en el valor que ya tiene
ints.pop_back (); // Invalidar el iterador
continuar; // Loop round y acceder al iterador no válido
pop_back() invalida únicamente los iteradores que apuntan al último elemento. De la referencia de la biblioteca estándar de C ++:
Insertar o quitar elementos invalida referencias, punteros e iteradores que hacen referencia al siguiente elemento. Si una inserción provoca la reasignación, invalida todas las referencias, iteradores y punteros.
Entonces, para responder a su pregunta, no, no invalida todos los iteradores.
Sin embargo, en el ejemplo del código, puede invalidarlo cuando apunta al último elemento y el valor está por debajo de 10. En este caso, el depurador STL de Visual Studio marcará el iterador como invalidado, y además comprobará que no sea igual al final ( ) mostrará una afirmación.
Si los iteradores se implementan como punteros puros (como lo harían probablemente en todos los casos de vector STL sin 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 el último elemento correctamente.