Iterator Invalidation

Iterators simply point to container elements, so it’s possible for iterators to become invalid when certain container modifications occur. For example, if you invoke clear on a vector, all of its elements are removed. If a program had any iterators that pointed to that vector’s elements before clear was called, those iterators would now be invalid. Section 23 of the C++ standard discusses all the cases in which iterators (and pointers and references) are invalidated for each Standard Library container. Here we summarize when iterators are invalidated during insert and erase operations.

When inserting into a:

• vector—If the vector is reallocated, all iterators pointing to that vector are invalidated. Otherwise, iterators from the insertion point to the end of the vector are invalidated.

• deque—All iterators are invalidated.

• list or forward_list—All iterators remain valid.

• Ordered associative container—All iterators remain valid.

• Unordered associative container—All iterators are invalidated if the containers need to be reallocated.

When erasing from a container, iterators to the erased elements are invalidated. In addition:

• vector—Iterators from the erased element to the end of the vector are invalidated.

• deque—If an element in the middle of the deque is erased, all iterators are invalidated.