Iterator Invalidation

Overview

Iterator invalidation is one of the most prevalent sources of undefined behavior in production C++ code. The standard imposes exact invalidation rules for every container and every mutating operation — rules that differ substantially between contiguous-storage sequence containers, node-based associative containers, and hash containers. Using an invalidated iterator is undefined behavior: the program may crash, silently produce wrong output, or corrupt heap metadata.

The standard distinguishes three categories of handles: iterators, pointers to elements, and references to elements. Their invalidation rules differ — most visibly for std::deque, where operations that push to the front or back invalidate all iterators but leave existing element references valid.

Invalidation Rules by Container

std::vector and std::string

std::vector (and std::string, which follows identical rules) stores elements in a single contiguous allocation. Any operation that causes reallocation invalidates every outstanding iterator, pointer, and reference to elements.

Pre-allocating with reserve before a batch of insertions eliminates reallocation entirely and keeps any pre-obtained iterators into the existing prefix stable:

std::vector<int> v;
v.reserve(1024); // prevents reallocation up to 1024 elements

auto first = v.begin(); // stable while size() stays ≤ capacity()
for (int i = 0; i < 1024; ++i)
    v.push_back(i * i); // no reallocation — first remains valid

std::deque

std::deque stores elements in fixed-size chunks, producing a split between iterator and reference stability:

Code that holds raw pointers or references to deque elements can survive a push_back; any iterator taken before that push_back is invalid.

std::list and std::forward_list

Individually-allocated node containers provide the strongest stability guarantee in the standard library:

• Insertion — including splice — never invalidates any iterator, pointer, or reference.
• Erasure invalidates only the iterator(s) to the erased node(s).

std::forward_list (C++11) follows the same rules; before_begin() is never invalidated by any operation.

std::list<int> lst = {1, 2, 3, 4, 5};
auto it = std::next(lst.begin(), 2); // points to 3

lst.push_front(0); // it remains valid
lst.erase(lst.begin()); // removes 1; it still valid
// *it == 3, guaranteed

std::map, std::set, std::multimap, std::multiset

Red-black tree containers extend the same stability guarantee:

• Insertion never invalidates any existing iterator, pointer, or reference.
• Erasure invalidates only the iterator to the erased element.

This makes tree-based associative containers the right choice when you need long-lived iterators alongside frequent modifications.

std::unordered_map, std::unordered_set, and variants

Hash containers are more volatile than their tree-based counterparts:

• Insertion invalidates all iterators if it triggers a rehash (when size() + 1 > max_load_factor() * bucket_count()). Pointers and references to elements survive rehash and remain valid.
• Erasure invalidates only the iterator to the erased element; pointers and references remain valid.
• rehash() and reserve() (C++11) invalidate all iterators; pointers and references remain valid.

std::flat_set and std::flat_map (C++23) back their elements in a sorted contiguous sequence. Any insertion or erasure invalidates all iterators, pointers, and references — identical to std::vector.

Common Pitfalls

Erasing inside a range-for loop

Range-for desugars to a begin/end iterator pair maintained by the compiler. Erasing elements inside the body invalidates the internal advance iterator:

std::vector<int> v = {1, 2, 3, 4, 5};

// Undefined behavior — erasing inside range-for invalidates the hidden iterator
for (int x : v)
    if (x % 2 == 0)
        v.erase(std::find(v.begin(), v.end(), x));

Use the erase-remove idiom (C++98) or std::erase_if (C++20):

// C++98 erase-remove idiom
v.erase(std::remove_if(v.begin(), v.end(),
        [](int x){ return x % 2 == 0; }), v.end());

// C++20: std::erase_if — canonical, avoids the idiom entirely
std::erase_if(v, [](int x){ return x % 2 == 0; }); // C++20

Ignoring the return value of erase

erase on sequence containers returns an iterator to the element following the erased position. Not using it forces an extra lookup and risks using a stale iterator:

std::vector<int> v = {1, 2, 3, 4, 5};

for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0)
        it = v.erase(it); // erase returns the next valid iterator
    else
        ++it;
}

Mixing insertion into std::unordered_map with iteration

Tree-based insertions never invalidate iterators, so concurrent iteration and insertion into std::map is well-defined:

std::map<int, int> m = {{1, 10}, {2, 20}, {3, 30}};
for (auto it = m.begin(); it != m.end(); ++it) {
    if (it->second > 15)
        m.insert({it->first + 100, it->second * 2}); // safe — no invalidation
}

The same code on std::unordered_map is undefined behavior: an insertion may trigger a rehash that invalidates it before the loop's increment.

Move semantics (C++11)

Moving a container transfers ownership of its storage. All iterators, pointers, and references into the moved-from object become invalid:

std::vector<int> a = {1, 2, 3};
auto it = a.begin();

std::vector<int> b = std::move(a); // C++11
// it is now invalid — using it is undefined behavior

This is commonly missed when containers are moved into function arguments or stored in other containers.

Best Practices

Minimise iterator lifetimes. Obtain iterators close to their point of use. The longer an iterator lives, the more code paths can inadvertently invalidate it between acquisition and use.

Reserve before bulk insertions into std::vector. A single reserve call eliminates all reallocation within the batch and preserves any iterators into the existing prefix.

Use std::erase_if (C++20) for conditional removal. It is correct by construction and eliminates the entire class of range-iteration invalidation bugs.

Prefer node-based containers when you need stable iterators. If your algorithm must hold iterators while simultaneously modifying the container, std::list or std::map eliminate the problem at the cost of cache locality.

Treat invalidation as a data race in multi-threaded code. The standard's invalidation rules are defined for single-threaded access. If one thread modifies a container while another thread holds an iterator into it, the result is a data race regardless of which container type is used. Protect with a mutex or use a purpose-built concurrent data structure.

See Also

• std::erase_if — C++20 free function for conditional element removal without manual iterator bookkeeping
• std::vector::reserve — pre-allocates capacity to eliminate reallocation and the invalidation it causes
• std::list::splice — transfers nodes between lists with no iterator invalidation on either side
• std::unordered_map::reserve — (C++11) pre-sizes the hash table to avoid rehash-triggered invalidation during bulk insertion