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.
std::vector<int> v{1, 2, 3}; auto it = v.begin(); v.push_back(4); // may reallocate: it is now invalid
Try it
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.
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
eraseandinsert. They return the iterator that replaces the invalidated one. push_backin a range-basedforover the same vector is a bug, because the hidden iterators are invalidated when the vector reallocates.- Prefer erase-remove or
std::erase_ifto 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. reservedoes not make unlimited growth safe: it only prevents reallocation whilesize() <= capacity().- Sanitizers help:
-fsanitize=addressor the debug mode-D_GLIBCXX_DEBUGcatch many invalid iterator uses at run time. - Reference stability is a reason to choose
list,maporunordered_mapwhen other parts of the program hold pointers to elements.