Reglas de invalidación de iteradores para contenedores de C++

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

Jun 22 '11 17:06

C++11 (Fuente: Reglas de invalidación de iteradores (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 se invalidan) [23.3.6.5/1]
• deque: todos los iteradores y referencias se invalidan, a menos que el miembro insertado esté al final (delante o detrás) de la deque (en cuyo caso se invalidan todos los iteradores, pero las referencias a elementos no se ven afectadas) [23.3.3.4/1]
• list: todos los iteradores y referencias no se ven afectados [23.3.5.4/1]
• forward_list: todos los iteradores y referencias no se ven 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 se ven afectados [23.2.4/9]

Contenedores asociativos sin clasificar

• unordered_[multi]{set,map}: todos los iteradores se invalidan cuando se produce el refrito, pero las referencias no se ven afectadas [23.2.5/8]. La repetición no se produce 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 sólo los iteradores y las referencias a los elementos borrados y al iterador pasado el final; borrar el primer elemento invalida sólo los iteradores y las referencias a los elementos borrados; borrar cualquier otro elemento invalida todos los iteradores y referencias (incluido el iterador pasado el 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}: sólo se invalidan los iteradores y las referencias a los elementos borrados [23.2.4/9]

Contenedores asociativos desordenados

• unordered_[multi]{set,map}: sólo 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

Cambiar el tamaño

• 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 del 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 cualquier referencia, puntero o iterador que haga referencia 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 a swap(), no está claro si los iteradores "finales" están sujetos a las reglas por contenedor enumeradas anteriormente ; debes asumir, de todos modos, que lo son.

Nota 4

vectory soporte para todos los contenedores asociativos desordenadosreserve(n) , lo que garantiza que no se producirá ningún 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 desordenados porque una propuesta futura permitirá la especificación de un factor de carga mínimo, lo que permitiría que se produzca una 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.

Jun 22 '2011 15:06

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_backprovocan una reasignación si el nuevo tamaño es mayor que la capacidad anterior. La reasignación invalida todas las referencias, punteros e iteradores que hacen referencia a los elementos de la secuencia. Si no se produce ninguna 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 hacen referencia a los elementos de la secuencia. No se realizará ninguna reasignación 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 capacity(). [26.3.11.3/6]

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

• list: No afecta la validez de iteradores y referencias. Si se lanza una excepción, no hay efectos. [26.3.10.4/1].
  Las funciones insert, emplace_front, emplace_back, emplace, push_front, push_backestán cubiertas por esta regla.

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

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

Contenedores asociativos

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

Contenedores asociativos desordenados

• All Unordered Associative Containers: La repetición invalida los iteradores, cambia el orden entre los elementos y cambia en qué depósitos aparecen los elementos, pero no invalida los punteros ni las referencias a los elementos. [26.2.7/9]
  Los miembros insertand emplaceno afectarán la validez de las referencias a elementos del contenedor, pero pueden invalidar todos los iteradores del contenedor. [26.2.7/14]
  Los miembros insertand 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 recuento de depósitos del contenedor y zes el factor de carga máximo del contenedor. [26.2.7/15]

• All Unordered Associative Containers: En 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 que hacen referencia a ase invalidarán, pero los iteradores a los elementos que permanecen a2seguirán siendo válidos. (Tabla 91: requisitos de contenedores asociativos desordenados)

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 a dequeinvalida solo el iterador pasado 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 sólo los iteradores y las referencias a los elementos borrados. Una operación de borrado que no borra ni el primer elemento ni el último elemento de a dequeinvalida el iterador pasado el final y todos los iteradores y referencias a todos los elementos de 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 las funciones erase, pop_front, pop_back. y funciones miembro: Borra todos los elementos de la lista a los que hace referencia un iterador de lista para el cual se cumplen las siguientes condiciones: , . Invalida solo los iteradores y las referencias a los elementos borrados [26.3.10.5/15]. Función miembro: borra todos menos el primer elemento de cada grupo consecutivo de elementos iguales a los que hace referencia el iterador en el rango para el cual (para la versión de único sin argumentos) o (para la versión de único con un argumento de predicado) se cumple. Invalida solo los iteradores y las referencias a los elementos borrados. [26.3.10.5/19]clear
removeremove_ifi*i == valuepred(*i) != false
uniquei[first + 1, last)*i == *(i-1)pred(*i, *(i - 1))

• forward_list: erase_afterinvalidará solo los iteradores y las 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 los cuales 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 a los que hace referencia el iterador i en el rango [primero + 1, último) para el cual *i == *(i-1)(para la versión sin argumentos) o pred(*i, *(i - 1))(para la versión con un predicado argumento) se cumple. 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 a y puede invalidar el iterador pasado el final (Tabla 87 — Requisitos del contenedor de secuencia). Pero para forward_list, clearno invalida los iteradores pasados ​​el final. [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 el final. (Tabla 87 — Requisitos del contenedor de secuencias)

Contenedores asociativos

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

• All Associative Containers: Los extractmiembros invalidan sólo los iteradores del 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 del 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 las referencias, punteros o iteradores que hagan referencia 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: binario_op no invalidará iteradores o subrangos, ni modificará elementos en el rango [primero, último]. [29.8.3/5]

etcétera...

Jan 02 '2019 10:01