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

Question

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 utilizando el iterador de forma segura, independientemente del tipo de la colección o el iterador?

Para evitar confusiones, aquí está el orden de las operaciones que hablo:

1. Obtener un iterador de la colección.
2. Modificar la colección (obviamente no es un elemento, sino la propia colección).
3. Utilice el iterador obtenido en el paso 1. ¿Es aún válido de acuerdo con el estándar STL?

Answer 1

Depende del contenedor. p.ej. si es un vector, después de modificar el contenedor, todos los iteradores pueden ser invalidados. Sin embargo, si es un list, los iteradores irrelevantes para el lugar modificado seguirán siendo válidos.

• iteradores de un vector se invalidan cuando se reasigna su memoria. 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 (incluidos push_front y push_back) invalida todos los iteradores que hacen referencia a deque. Erase en medio de deque invalida todos los iteradores que hacen referencia al deque. Erase al principio o al final de deque (incluidos pop_front y pop_back) invalida un iterador solo si apunta al elemento borrado. [2]

• List s tienen la importante propiedad de que la inserción y empalme no invalidan los iteradores a la lista de elementos, y que incluso la eliminación invalida sólo los iteradores que apuntan a los elementos que se eliminan. [3]

• Map tiene la importante propiedad de que la inserción de un nuevo elemento en una map no invalida 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)

Answer 2

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.

Answer 3

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 un 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 un std::deque, agregar al comienzo o al final los iteradores existentes válidos, pero agregar cualquier otro lugar puede invalidarlos, pero mi memoria es lo suficientemente pobre como para verificar antes de depender de eso).