loop instead for based c++ c++11 iterator c++03 c++-faq

instead - for auto p m c++



Reglas de invalidación del iterador (4)

Dado que esta pregunta atrae 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::vector ''s Operación de inserción en la validez de los iteradores y referencias con respecto a reserve() y capacity() , que la respuesta más votada no se dio cuenta.

C ++ 03:

La reasignación invalida todas las referencias, punteros e iteradores que se refieren a los elementos en la secuencia. Se garantiza que no se llevarán a cabo reasignaciones durante las inserciones que ocurren después de una llamada a reserve () hasta el momento en que una inserción haga que el tamaño del vector sea mayor que el tamaño especificado en la llamada a reserva () más reciente .

C ++ 11:

La reasignación invalida todas las referencias, punteros e iteradores que se refieren a los elementos en la secuencia. Se garantiza que no se llevarán a cabo reasignaciones durante las inserciones que ocurren después de una llamada a reserve () hasta el momento en que una inserción haga que el tamaño del vector sea mayor que el valor de capacidad () .

Así que en C ++ 03, no es "a 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, en cambio, debe 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 llamada de reserve() anterior (que podría ser menor que la capacity() actual capacity() ya que una reserve() podría resultar en un mayor capacity() que la solicitada), cualquier insert() posterior podría causar una reasignación e invalidar todos los iteradores y referencias. En C ++ 11, esto no sucederá y siempre puede confiar en la capacity() para saber con certeza que la próxima reasignación no tendrá lugar antes de que el tamaño supere la capacity() .

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

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

Preferiblemente en un formato de lista de resumen.

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

Probablemente vale la pena agregar que se garantiza que un iterador de inserción de cualquier tipo ( std::back_insert_iterator , std::front_insert_iterator , std::insert_iterator ) seguirá siendo válido siempre que todas las inserciones se realicen a través de este iterador y ningún otro iterador independiente. evento ocurre.

Por ejemplo, cuando realiza una serie de operaciones de inserción en un std::vector utilizando std::insert_iterator , es muy posible que estas inserciones activen la reasignación de vectores, lo que invalidará todos los iteradores que "apuntan" 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 que preocuparse por activar la reasignación de vectores.

Esto, nuevamente, se aplica solo a las inserciones realizadas a través del propio iterador de inserción. Si el evento de invalidación del iterador es activado por alguna acción independiente en el contenedor, entonces el iterador de inserción se invalida también 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();

se garantiza que 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. Iterador obviamente se volverá inválido, pero continuará siendo válido.

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

Inserción

Contenedores de secuencia

  • vector : todos los iteradores y las referencias anteriores al punto de inserción no se verán afectados, a menos que el nuevo tamaño del contenedor sea mayor que la capacidad anterior (en cuyo caso todos los iteradores y las referencias se invalidan) [23.2.4.3/1]
  • deque : todos los iteradores y las referencias se invalidan, a menos que el miembro insertado esté al final (frente o atrás) del deque (en cuyo caso todos los iteradores se invalidan, pero las referencias a los 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 las referencias se invalidan, a menos que los miembros borrados estén al final (frente o atrás) del deque (en cuyo caso solo se invalidan los iteradores y las referencias a los miembros borrados) [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

Redimensionamiento

  • 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 de miembro de contenedor o pasar un contenedor como un argumento a una función de biblioteca no invalidará los iteradores de, o cambiará los valores de, objetos dentro de ese contenedor . [23.1 / 11]

Nota 2

No está claro en C ++ 2003 si los iteradores "finales" están sujetos a las reglas anteriores ; Debería 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 reglas como las reglas para la invalidación de referencias.

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

Inserción

Contenedores de secuencia

  • vector : todos los iteradores y las referencias anteriores al punto de inserción no se verán afectados, a menos que el nuevo tamaño del contenedor sea mayor que la capacidad anterior (en cuyo caso todos los iteradores y las referencias se invalidan) [23.3.6.5/1]
  • deque : todos los iteradores y las referencias se invalidan, a menos que el miembro insertado esté al final (frente o atrás) del deque (en cuyo caso todos los iteradores se invalidan, pero las referencias a los 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 un reinicio, pero las referencias no se ven afectadas [23.2.5 / 8]. El reinicio no se produce si la inserción no hace que el tamaño del contenedor exceda de z * B donde z es el factor de carga máximo y B el número actual de cucharones. [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 el iterador del pasado; borrar el primer elemento invalida solo los iteradores y las referencias a los elementos borrados; el borrado de cualquier otro elemento invalida todos los iteradores y referencias (incluido el iterador del 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 desordenados

  • 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

Redimensionamiento

  • 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 de miembro de contenedor o pasar un contenedor como un argumento a una función de biblioteca no invalidará los iteradores de, o cambiará los valores de, objetos dentro de ese contenedor . [23.2.1 / 11]

Nota 2

ninguna función swap () invalida las referencias, los punteros o los 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 ser invalidado . "Nota final" [23.2.1 / 10]

Nota 3

Aparte de la advertencia anterior sobre swap() , no está claro si los iteradores de "fin" están sujetos a las reglas por contenedor enumeradas anteriormente ; Deberías suponer, de todos modos, que lo son.

Nota 4

vector y todos los contenedores asociativos no ordenados admiten la 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 hasta n . Se debe tener precaución con los contenedores asociativos no ordenados porque una propuesta futura permitirá la especificación de un factor de carga mínimo, lo que permitiría que se produzca un nuevo lavado en el insert después de que suficientes operaciones de erase reduzcan el tamaño del contenedor por debajo del mínimo; La garantía debe considerarse potencialmente nula después de un erase .