Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Containers

C++ iterator invalidation rules

Reference for C++ iterator, pointer and reference invalidation: which vector, deque, list, map and unordered container operations break them, and safe erase patterns.

An iterator, pointer or reference into a container becomes invalid when an operation moves or destroys the element it refers to, or changes the container's structure. Using an invalid iterator is undefined behavior: it may appear to work, read stale data, or crash. Which operations invalidate what depends on the container, and knowing the rules is the difference between a correct loop and an intermittent bug.

The rules follow from how each container stores its elements. A vector keeps everything in one array, so growth reallocates and moves everything. A list or map allocates each element (node) separately, so inserting never moves existing elements. A deque is in between.

C++
std::vector<int> v{1, 2, 3};
auto it = v.begin();
v.push_back(4);        // may reallocate: it is now invalid

Try it

C++ Capacity changes invalidate vector iterators

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

C++ Safe erasing while looping

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The rules

Container Insert Erase
vector If capacity is exceeded, all iterators, pointers and references are invalidated. Otherwise only those at or after the insertion point. Those at or after the erased element (including end()).
string Like vector: any call that grows the string past its capacity (append, +=, insert, reserve) invalidates all. Moving a short string may also change where its characters live, because of the small string optimization. Those at or after the point.
deque Insertion in the middle invalidates all. At either end, iterators are invalidated but pointers and references to elements stay valid. Middle: all. At either end: only the erased elements (and end()).
list, forward_list Nothing is invalidated. Only the erased elements.
map, set, multimap, multiset Nothing is invalidated. Only the erased elements.
unordered_* A rehash (when the load factor is exceeded) invalidates iterators, but pointers and references to elements stay valid. Only the erased elements.
flat_map, flat_set Like vector: insertion and erasure can invalidate everything at or after the position, and reallocation invalidates all. Same.
array Cannot grow or shrink. swap swaps the elements, so iterators then refer to elements of the other array. n/a

clear() invalidates every iterator, pointer and reference to an element. swap of two containers (other than array) keeps iterators valid but they now refer to elements in the other container. Moving a container into another normally transfers the elements, so pointers stay valid.

Usage notes

  • Use the return value of erase and insert. They return the iterator that replaces the invalidated one.
  • push_back in a range-based for over the same vector is a bug, because the hidden iterators are invalidated when the vector reallocates.
  • Prefer erase-remove or std::erase_if to a hand-written erase loop over a vector (see Erase-remove idiom).
  • Store indexes or keys instead of iterators when you must keep positions across insertions into a vector.
  • reserve does not make unlimited growth safe: it only prevents reallocation while size() <= capacity().
  • Sanitizers help: -fsanitize=address or the debug mode -D_GLIBCXX_DEBUG catch many invalid iterator uses at run time.
  • Reference stability is a reason to choose list, map or unordered_map when other parts of the program hold pointers to elements.