Reglas de invalidación de iterador

543

¿Cuáles son las reglas de invalidación de iterador para contenedores C ++?

Preferiblemente en un formato de lista de resumen.

(Nota: Esto está destinado a ser una entrada a las preguntas frecuentes de C ++ de Stack Overflow . Si desea criticar la idea de proporcionar preguntas frecuentes en este formulario, entonces la publicación en meta que comenzó todo esto sería el lugar para hacerlo. Respuestas a esa pregunta se monitorea en la sala de chat de C ++ , donde la idea de las preguntas frecuentes comenzó en primer lugar, por lo que es muy probable que su respuesta sea leída por aquellos a quienes se les ocurrió la idea).

Carreras de ligereza en órbita
fuente
¿Deberían las respuestas estar en el mismo formato que su respuesta?
PW
@PW IMO que sería preferible para la simetría pero no puedo imponerla: P
Carreras de ligereza en órbita el
¿Qué pasa con c ++ 20?
Walter
1
@Walter aún no existe;)
ligereza corre en órbita
Esta pregunta es, para citar a Leela de Futurama, de las edades estúpidas, y en mi modesta opinión debería dejarse abierta.
Roman Luštrik

Respuestas:

112

C ++ 17 (Todas las referencias son del borrador final de trabajo de CPP17 - n4659 )


Inserción

Contenedores de secuencia

  • vector: Las funciones insert, emplace_back, emplace,push_back causa reasignación si el nuevo tamaño es mayor que la antigua capacidad. La reasignación invalida todas las referencias, punteros e iteradores que hacen referencia a los elementos en la secuencia. Si no ocurre una reasignación, todos los iteradores y referencias antes del punto de inserción siguen siendo válidos. [26.3.11.5/1]
    Con respecto a la reservefunción, la reasignación invalida todas las referencias, punteros e iteradores que se refieren a los elementos de la secuencia. No se realizará una reasignación durante las inserciones que sucedan después de una llamada reserve()hasta el momento en que una inserción haría que el tamaño del vector sea mayor que el valor de capacity(). [26.3.11.3/6]

  • deque: Una inserción en el medio de la deque invalida todos los iteradores y referencias a elementos de la deque. Una inserción en cualquier extremo de la deque invalida todos los iteradores de la deque, pero no tiene ningún efecto sobre la validez de las referencias a elementos de la deque. [26.3.8.4/1]

  • list: No afecta la validez de iteradores y referencias. Si se produce una excepción, no hay efectos. [26.3.10.4/1].
    El insert` emplace_front` emplace_back` emplace`push_front , push_backlas funciones se ajustan a esta regla.

  • forward_list: Ninguna de las sobrecargas de insert_after afectará la validez de iteradores y referencias [26.3.9.5/1]

  • array: Como regla , los iteradores de una matriz nunca se invalidan durante la vida útil de la matriz. Sin embargo, se debe tener en cuenta que durante el intercambio, el iterador continuará apuntando al mismo elemento de matriz y, por lo tanto, cambiará su valor.

Contenedores Asociativos

  • All Associative Containers: El insertyemplace miembros no afectarán la validez de los iteradores y las referencias al contenedor [26.2.6 / 9]

Contenedores asociativos no ordenados

  • All Unordered Associative Containers: Rehashing invalida los iteradores, cambia el orden entre los elementos y cambia en qué elementos de los cubos aparecen, pero no invalida los punteros o las referencias a los elementos. [26.2.7 / 9]
    Los miembros inserty emplaceno afectarán la validez de las referencias a los elementos del contenedor, pero pueden invalidar todos los iteradores del contenedor. [26.2.7 / 14]
    Los miembros inserty emplaceno afectarán la validez de los iteradores si (N+n) <= z * B, donde Nes el número de elementos en el contenedor antes de la operación de inserción, nes el número de elementos insertados, Bes el conteo de cubos del contenedor, yz es el factor de carga máxima del contenedor. [26.2.7 / 15]

  • All Unordered Associative Containers: En el caso de una operación de fusión (por ejemplo, a.merge(a2)), los iteradores que hacen referencia a los elementos transferidos y todos los iteradores a los que se hace referencia ase invalidarán, pero los iteradores a los elementos restantes a2seguirán siendo válidos. (Tabla 91 - Requisitos de contenedor asociativo no ordenados)

Adaptadores de contenedores

  • stack: heredado del contenedor subyacente
  • queue: heredado del contenedor subyacente
  • priority_queue: heredado del contenedor subyacente

Borradura

Contenedores de secuencia

  • vector: Las funciones erasee pop_backinvalidan iteradores y referencias en o después del punto de borrado. [26.3.11.5/3]

  • deque: Una operación de borrado que borra el último elemento de un dequeinvalida solo el iterador pasado y el final y todos los iteradores y referencias a los elementos borrados. Una operación de borrado que borra el primer elemento de un elemento dequepero no el último invalida solo iteradores y referencias a los elementos borrados. Una operación de borrado que no borra ni el primer elemento ni el último elemento de un dequeinvalida el iterador pasado-fin y todos los iteradores y referencias a todos los elementos del deque. [Nota: pop_fronty pop_backson operaciones de borrado. —Nota final] [26.3.8.4/4]

  • list: Invalida solo los iteradores y las referencias a los elementos borrados. [26.3.10.4/3]. Esto se aplica a erase, pop_front, pop_back, clearfunciones.
    removey remove_iffunciones miembro: borra todos los elementos de la lista referidos por un iterador de lista ipara el que se cumplen las siguientes condiciones: *i == value, pred(*i) != false. Invalida solo los iteradores y las referencias a los elementos borrados [26.3.10.5/15].
    uniquefunción miembro: borra todos los elementos excepto el primer elemento de cada grupo consecutivo de elementos iguales mencionados por el iterador ien el rango (para la versión de unique con un argumento predicado). Invalida solo los iteradores y las referencias a los elementos borrados. [26.3.10.5/19][first + 1, last) para el cual*i == *(i-1) (para la versión de unique sin argumentos) opred(*i, *(i - 1))

  • forward_list: erase_afterinvalidará solo iteradores y referencias a los elementos borrados. [26.3.9.5/1].
    removey remove_iffunciones miembro: borra todos los elementos de la lista a los que hace referencia un iterador de lista i para el que se cumplen las siguientes condiciones: *i == value(para remove()), pred(*i)es verdadero (para remove_if()). Invalida solo los iteradores y las referencias a los elementos borrados. [26.3.9.6/12].
    uniquefunción miembro: borra todos menos el primer elemento de cada grupo consecutivo de elementos iguales mencionados por el iterador i en el rango [primero + 1, último) para los cuales *i == *(i-1)(para la versión sin argumentos) o pred(*i, *(i - 1))(para la versión con un predicado argumento) se sostiene. Invalida solo los iteradores y las referencias a los elementos borrados. [26.3.9.6/16]

  • All Sequence Containers: clearinvalida todas las referencias, punteros e iteradores que hacen referencia a los elementos de ay puede invalidar el iterador pasado-final (Tabla 87 - Requisitos del contenedor de secuencia). Pero para forward_list, clearno invalida los iteradores pasados. [26.3.9.5/32]

  • All Sequence Containers: assigninvalida todas las referencias, punteros e iteradores que hacen referencia a los elementos del contenedor. For vectory deque, también invalida el iterador pasado al final. (Tabla 87 - Requisitos del contenedor de secuencia)

Contenedores Asociativos

  • All Associative Containers: Los erasemiembros invalidarán solo iteradores y referencias a los elementos borrados [26.2.6 / 9]

  • All Associative Containers: Los extractmiembros invalidan solo iteradores al elemento eliminado; los punteros y las referencias al elemento eliminado siguen siendo válidos [26.2.6 / 10]

Adaptadores de contenedores

  • stack: heredado del contenedor subyacente
  • queue: heredado del contenedor subyacente
  • priority_queue: heredado del contenedor subyacente

Requisitos generales del contenedor relacionados con la invalidación del iterador:

  • 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 . [26.2.1 / 12]

  • ninguna swap()función invalida ninguna referencia, puntero o iterador que se refiera a los elementos de los contenedores que se intercambian. [Nota: El iterador end () no hace referencia a ningún elemento, por lo que puede invalidarse. —Nota final] [26.2.1 / (11.6)]

Como ejemplos de los requisitos anteriores:

  • transformalgoritmo: Las funciones opy binary_opno invalidarán iteradores o subrangos, ni modificarán elementos en los rangos [28.6.4 / 1]

  • accumulatealgoritmo: en el rango [primero, último], binary_opno modificará elementos ni invalidará iteradores o subrangos [29.8.2 / 1]

  • reducealgoritmo: binary_op no invalidará iteradores o subrangos, ni modificará elementos en el rango [primero, último]. [29.8.3 / 5]

y así...

PW
fuente
77
Oh PW tu héroe!
Carreras de ligereza en órbita el
2
@LightnessRacesinOrbit: Intenté hacerlo según su formato de respuesta original. :)
PW
1
¿podemos también tener una lista para std::string? Creo que es diferente std::vectordebido a SSO
sp2danny
1
@ sp2danny: debido a SSO, stringfalla el segundo requisito general mencionado anteriormente. Entonces no lo incluí. También trató de seguir el mismo patrón de las entradas anteriores de preguntas frecuentes.
PW
@LightnessRaceswithMonica Gracias a todos por el arduo trabajo. Tengo una pregunta que me confunde por días. ¿Qué significa "invalidado" exactamente en estos contextos? ¿Significa "invalidated" can mean "no longer points to what it used to", not just "may not point to any valid element"que @Marshall Clow describió en esta respuesta ? ¿O solo indica solo 1 de las 2 condiciones?
Rick
410

C ++ 03 (Fuente: Reglas de invalidación de iterador (C ++ 03) )


Inserción

Contenedores de secuencia

  • vector: todos los iteradores y referencias antes del punto de inserción no se ven afectados, a menos que el nuevo tamaño del contenedor sea mayor que la capacidad anterior (en cuyo caso todos los iteradores y referencias están invalidados) [23.2.4.3/1]
  • deque: todos los iteradores y referencias están invalidados, a menos que el miembro insertado esté al final (anverso o reverso) de la eliminación (en cuyo caso todos los iteradores están invalidados, pero las referencias a elementos no se ven afectadas) [23.2.1.3/1]
  • list: todos los iteradores y referencias no afectados [23.2.2.3/1]

Contenedores asociativos

  • [multi]{set,map}: todos los iteradores y referencias no afectados [23.1.2 / 8]

Adaptadores de contenedores

  • stack: heredado del contenedor subyacente
  • queue: heredado del contenedor subyacente
  • priority_queue: heredado del contenedor subyacente

Borradura

Contenedores de secuencia

  • vector: cada iterador y referencia después del punto de borrado se invalida [23.2.4.3/3]
  • deque: todos los iteradores y referencias están invalidados, a menos que los miembros borrados estén al final (anverso o reverso) de la eliminación (en cuyo caso solo los iteradores y las referencias a los miembros borrados están invalidados) [23.2.1.3/4]
  • list: solo se invalidan los iteradores y las referencias al elemento borrado [23.2.2.3/3]

Contenedores asociativos

  • [multi]{set,map}: solo se invalidan los iteradores y las referencias a los elementos borrados [23.1.2 / 8]

Adaptadores de contenedores

  • stack: heredado del contenedor subyacente
  • queue: heredado del contenedor subyacente
  • priority_queue: heredado del contenedor subyacente

Redimensionando

  • vector: según insertar / borrar [23.2.4.2/6]
  • deque: según insertar / borrar [23.2.1.2/1]
  • list: según insertar / borrar [23.2.2.2/1]

Nota 1

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 . [23,1 / 11]

Nota 2

No está claro en C ++ 2003 si los iteradores de "finalización" están sujetos a las reglas anteriores ; debe suponer, de todos modos, que lo son (como es el caso en la práctica).

Nota 3

Las reglas para la invalidación de punteros son las mismas que las reglas para la invalidación de referencias.

Carreras de ligereza en órbita
fuente
55
Buena idea, solo para comentar: creo que los contenedores asociativos podrían plegarse en una sola línea, y podría valer la pena agregar otra línea de los asociativos no ordenados ... aunque no estoy seguro de cómo podría ser la parte de rehashing mapeado en insertar / borrar, ¿conoce alguna forma de verificar si se activará o no una repetición?
Matthieu M.
1
IIRC, en algún lugar la especificación dice que el iterador final no es un iterador "para objetos dentro de ese contenedor". Me pregunto cómo esas garantías buscan el iterador final en cada caso.
Johannes Schaub - litb
1
@MuhammadAnnaqeeb: Esta respuesta ciertamente no lo deja claro, ya que tomé un atajo, pero la intención es decir que cambiar el tamaño es inserción / borrado, ya que si se requiere una reasignación, puede considerar que es lo mismo que borrar luego reinsertando todos los elementos afectados. Esa sección de la respuesta ciertamente podría mejorarse.
Carreras de ligereza en órbita el
1
@Yakk: Pero no lo hace; ver el texto estándar citado. Sin embargo, parece que eso se solucionó en C ++ 11. :)
ligereza corre en órbita
1
@metamorphosis: deque almacena datos en bloques no contiguos. Insertar al principio o al final puede asignar un nuevo bloque, pero nunca se mueve alrededor de elementos anteriores, por lo que los punteros siguen siendo válidos. Pero las reglas para ir al elemento siguiente / anterior cambian si se asigna un nuevo bloque, por lo que los iteradores se invalidan.
Nick Matteo
357

C ++ 11 (Fuente: Reglas de invalidación de iterador (C ++ 0x) )


Inserción

Contenedores de secuencia

  • vector: todos los iteradores y referencias antes del punto de inserción no se ven afectados, a menos que el nuevo tamaño del contenedor sea mayor que la capacidad anterior (en cuyo caso todos los iteradores y referencias están invalidados) [23.3.6.5/1]
  • deque: todos los iteradores y referencias están invalidados, a menos que el miembro insertado esté al final (anverso o reverso) de la eliminación (en cuyo caso todos los iteradores están invalidados, pero las referencias a elementos no se ven afectadas) [23.3.3.4/1]
  • list: todos los iteradores y referencias no afectados [23.3.5.4/1]
  • forward_list: todos los iteradores y referencias no afectados (se aplica a insert_after) [23.3.4.5/1]
  • array: (n / a)

Contenedores asociativos

  • [multi]{set,map}: todos los iteradores y referencias no afectados [23.2.4 / 9]

Contenedores asociativos sin clasificar

  • unordered_[multi]{set,map}: todos los iteradores se invalidan cuando se produce la repetición, pero las referencias no se ven afectadas [23.2.5 / 8]. La repetición no ocurre si la inserción no hace que el tamaño del contenedor exceda z * Bdonde zestá el factor de carga máximo y Bel número actual de cubos. [23.2.5 / 14]

Adaptadores de contenedores

  • stack: heredado del contenedor subyacente
  • queue: heredado del contenedor subyacente
  • priority_queue: heredado del contenedor subyacente

Borradura

Contenedores de secuencia

  • vector: cada iterador y referencia en o después del punto de borrado se invalida [23.3.6.5/3]
  • deque: borrar el último elemento invalida solo los iteradores y las referencias a los elementos borrados y al iterador pasado al final; borrar el primer elemento invalida solo iteradores y referencias a los elementos borrados; borrar cualquier otro elemento invalida todos los iteradores y referencias (incluido el iterador pasado al final) [23.3.3.4/4]
  • list: solo se invalidan los iteradores y las referencias al elemento borrado [23.3.5.4/3]
  • forward_list: solo se invalidan los iteradores y las referencias al elemento borrado (se aplica a erase_after) [23.3.4.5/1]
  • array: (n / a)

Contenedores asociativos

  • [multi]{set,map}: solo se invalidan los iteradores y las referencias a los elementos borrados [23.2.4 / 9]

Contenedores asociativos no ordenados

  • unordered_[multi]{set,map}: solo se invalidan los iteradores y las referencias a los elementos borrados [23.2.5 / 13]

Adaptadores de contenedores

  • stack: heredado del contenedor subyacente
  • queue: heredado del contenedor subyacente
  • priority_queue: heredado del contenedor subyacente

Redimensionando

  • vector: según insertar / borrar [23.3.6.5/12]
  • deque: según insertar / borrar [23.3.3.3/3]
  • list: según insertar / borrar [23.3.5.3/1]
  • forward_list: según insertar / borrar [23.3.4.5/25]
  • array: (n / A)

Nota 1

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 . [23.2.1 / 11]

Nota 2

ninguna función swap () invalida las referencias, punteros o iteradores que se refieren a los elementos de los contenedores que se intercambian. [Nota: El iterador end () no hace referencia a ningún elemento, por lo que puede invalidarse . —Nota final] [23.2.1 / 10]

Nota 3

Aparte de la advertencia anterior con respecto swap(), no está claro si los iteradores de "finalización" están sujetos a las reglas por contenedor mencionadas anteriormente ; debes asumir, de todos modos, que lo son.

Nota 4

vectory todos los contenedores asociativos no ordenados son compatibles, lo reserve(n)que garantiza que no se producirá un cambio de tamaño automático al menos hasta que el tamaño del contenedor crezca n. Se debe tener precaución con los contenedores asociativos desordenados porque una propuesta futura permitirá la especificación de un factor de carga mínimo, lo que permitiría que se produzca la repetición insertdespués de que suficientes eraseoperaciones reduzcan el tamaño del contenedor por debajo del mínimo; la garantía debe considerarse potencialmente nula después de un erase.

Carreras de ligereza en órbita
fuente
Además swap(), ¿cuáles son las reglas para la validez del iterador en la asignación de copiar / mover?
adiós
@LightnessRacesinOrbit: al igual que la inserción, el borrado, el cambio de tamaño y el intercambio, la asignación de copia / movimiento también son funciones miembro de std :: vector, por lo que creo que también podría proporcionarles las reglas de validez del iterador.
adiós
@goodbyeera: ¿Te refieres a copiar / mover asignando un elemento? Esto no afectará a ningún iterador. ¿Por qué lo haría? Estás tocando la Nota 1 anterior.
Carreras de ligereza en órbita
1
Creo que cometí un error, porque std::basic_stringno parece contarse como un contenedor, y ciertamente no es un contenedor en la sección de la norma a la que se aplica la nota. Aún así, ¿dónde dice que SSO no está permitido (sé que COW lo está)?
Deduplicador
2
¿Son todas estas reglas iguales en C ++ 14? C ++ 17 (hasta donde se sabe ahora)?
einpoklum
40

Es probablemente la pena añadir que un iterador inserción de cualquier tipo ( std::back_insert_iterator, std::front_insert_iterator,std::insert_iterator ) se garantiza que permanecerá válida siempre y cuando todas las inserciones se realizan a través de este iterador y se produce ningún otro evento independiente iterador-invalidar.

Por ejemplo, cuando realiza una serie de operaciones de inserción en un std::vectormediantestd::insert_iterator , es muy posible que estas inserciones activen la reasignación de vectores, lo que invalidará todos los iteradores que "apunten" a ese vector. Sin embargo, se garantiza que el iterador de inserción en cuestión seguirá siendo válido, es decir, puede continuar con seguridad la secuencia de inserciones. No hay necesidad de preocuparse por desencadenar la reasignación de vectores.

Esto, nuevamente, se aplica solo a las inserciones realizadas a través del iterador de inserción. Si el evento de invalidación de iterador se desencadena por alguna acción independiente en el contenedor, el iterador de inserción también se invalida de acuerdo con las reglas generales.

Por ejemplo, este código

std::vector<int> v(10);
std::vector<int>::iterator it = v.begin() + 5;
std::insert_iterator<std::vector<int> > it_ins(v, it);

for (unsigned n = 20; n > 0; --n)
  *it_ins++ = rand();

está garantizado para realizar una secuencia válida de inserciones en el vector, incluso si el vector "decide" reasignar en algún lugar en medio de este proceso. itObviamente, Iterator dejará de ser válido, pero it_insseguirá siendo válido.

Hormiga
fuente
22

Como esta pregunta genera tantos votos y se convierte en una pregunta frecuente, creo que sería mejor escribir una respuesta por separado para mencionar una diferencia significativa entre C ++ 03 y C ++ 11 con respecto al impacto de std::vectorla operación de inserción en el validez de iteradores y referencias con respecto a reserve()y capacity(), que la respuesta más votada no notó.

C ++ 03:

La reasignación invalida todas las referencias, punteros e iteradores que hacen referencia a los elementos en la secuencia. Se garantiza que no se realice una reasignación durante las inserciones que suceden después de una llamada a reserve () hasta el momento en que una inserción haría que el tamaño del vector sea mayor que el tamaño especificado en la llamada más reciente a reserve () .

C ++ 11:

La reasignación invalida todas las referencias, punteros e iteradores que hacen referencia a los elementos en la secuencia. Se garantiza que no se realice una reasignación durante las inserciones que suceden después de una llamada a reserve () hasta el momento en que una inserción haría que el tamaño del vector sea mayor que el valor de la capacidad () .

Entonces, en C ++ 03, no es " unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)" como se menciona en la otra respuesta, sino que debería ser " greater than the size specified in the most recent call to reserve()". Esto es una cosa que C ++ 03 difiere de C ++ 11. En C ++ 03, una vez que insert()hace que el tamaño del vector alcance el valor especificado en la reserve()llamada anterior (que bien podría ser más pequeño que el actual, capacity()ya que reserve()podría resultar más grande capacity()de lo solicitado), cualquier posterior insert()podría causar la reasignación e invalidar Todos los iteradores y referencias. En C ++ 11, esto no sucederá y siempre puede confiar capacity()en saber con certeza que la próxima reasignación no tendrá lugar antes de que se supere el tamaño capacity().

En conclusión, si está trabajando con un vector C ++ 03 y quiere asegurarse de que no se reasignará cuando realice la inserción, es el valor del argumento al reserve()que le pasó anteriormente el que debe verificar el tamaño, no el valor de retorno de una llamada a capacity(), de lo contrario puede sorprenderse con una reasignación " prematura ".

Neverhoodboy
fuente
14
Sin embargo, dispararía a cualquier compilador que me hiciera esto, y ningún jurado en el país me condenaría.
Yakk - Adam Nevraumont
99
No "fallé en notar" esto; fue un error editorial en C ++ 03 que se corrigió en C ++ 11. Ningún compilador principal aprovecha el error.
Carreras de ligereza en órbita el
1
@Yakk Creo que gcc ya invalida los iteradores en tales situaciones.
ShreevatsaR
2

Aquí hay una buena tabla resumen de cppreference.com :

ingrese la descripción de la imagen aquí

Aquí, la inserción se refiere a cualquier método que agrega uno o más elementos al contenedor y la eliminación se refiere a cualquier método que elimine uno o más elementos del contenedor.

DarioP
fuente