Do STL iterators guarantee validity after modifying a collection?

Question

Let's say I have some kind of collection, and I got an iterator to get started. Now let me say that I modified the collection. Can I use an iterator safely, regardless of the type of collection or iterator?

To avoid confusion, here is the order of operations I'm talking about:

• Get the iterator of the collection.
• Change the collection (obviously not the element in it, but the collection itself).
• Use the iterator obtained in step 1. Is it valid according to the STL standard ?!

Answer 1

Depends on the container. for example, if it is vector , after changing the container all iterators can be canceled. However, if it is a list , iterators unrelated to the modified location remain valid.

• Vector iterators are not valid when reallocating memory. In addition, inserting or deleting an element in the middle of a vector invalidates all iterators pointing to elements following the insertion or deletion point. It follows that you can prevent vector iterators from being invalid if you use reserve() to predefine as much memory as the vector will use, and if all insertions and deletes are at the end of the vector. [one]

• The semantics of canceling an iterator for deque is as follows. Insert (including push_front and push_back ) invalidates all iterators that reference deque . Erase in the middle of deque invalidates all iterators that reference deque . Erase at the beginning or end of deque (including pop_front and pop_back ) invalidates the iterator only if it points to the erased element. [2]

• list have the important property that insertion and splicing do not invalidate iterators for enumerating elements, and that even deleting invalidates only iterators that indicate elements to delete. [3]

• Map has the important property that inserting a new element into a Map element does not invalidate iterators pointing to existing elements. Erasing an element from the map also does not cancel any iterators, except, of course, for iterators that actually point to the element to be erased. [4] (same for set , multiset and multimap )

Answer 2

It depends on the collection in question. For example, changing std::vector (for example, adding an element) can invalidate all iterators in this vector. Unlike std::list , iterators remain valid when you add another element to the list. In some cases, the rules are even more complicated (for example, if the memory works with std::deque , adding to the beginning or end causes existing iterators to be valid, but adding it somewhere else may invalidate them, but my memory is quite poor, you should check before depending on this).

Answer 3

No, iterators are only good when the iterated container does not change. If the collection is modified, the iterator must be retrieved.