¿Los iteradores de STL garantizan la validez después de que se cambió la colección?

Digamos que tengo algún tipo de colección y obtuve un iterador para el comienzo. Ahora digamos que modifiqué la colección. ¿Puedo seguir usando el iterador de forma segura, independientemente del tipo de la colección o el iterador?

Para evitar confusiones, este es el orden de las operaciones del que hablo:

  1. Obtenga un iterador de la colección.
  2. Modificar la colección (obviamente no es un elemento, sino la colección en sí).
  3. Use el iterador obtenido en el paso 1. ¿Es aún válido según el estándar STL?

Depende del contenedor. por ejemplo, si se trata de un vector , después de modificar el contenedor, todos los iteradores pueden invalidarse. Sin embargo, si se trata de una list , los iteradores irrelevantes para el lugar modificado seguirán siendo válidos.

  • 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. [1]

  • La semántica de la invalidación del iterador para deque es la siguiente. Insert (incluyendo push_front y push_back ) invalida todos los iteradores que se refieren a un deque . Erase en el medio de un deque invalida todos los iteradores que se refieren al deque . Erase al principio o al final de un deque (incluidos pop_front y pop_back ) invalida un iterador solo si apunta al elemento borrado. [2]

  • List listas tienen la propiedad importante de que la inserción y el empalme no invalidan los iteradores para listar elementos, y que incluso la eliminación invalida solo los iteradores que apuntan a los elementos que se eliminan. [3]

  • Map tiene la propiedad importante de que insertar un nuevo elemento en un map no invalida los iteradores que apuntan a los elementos existentes. Borrar un elemento de un mapa tampoco invalida ningún iterador, excepto, por supuesto, para los iteradores que realmente apuntan al elemento que se está borrando. [4] (lo mismo para set , multiset y multimap )

Eso depende de la colección en cuestión. Solo por ejemplo, modificar un std::vector (por ejemplo, agregar un elemento en alguna parte) puede invalidar todos los iteradores en ese vector. Por el contrario, con una std::list , los iteradores siguen siendo válidos cuando agrega otro elemento a la lista. En algunos casos, las reglas son aún más complejas (por ejemplo, si la memoria sirve, con std::deque , agregar al comienzo o al final deja iteradores existentes válidos, pero agregar cualquier otro lugar puede invalidarlos, pero mi memoria es suficientemente pobre que debes verificar antes de depender de eso).

No, los iteradores solo son buenos mientras que el contenedor iterado no se modifica. Si se modifica una colección, el iterador se debe obtener de nuevo.