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.

Complete Invalidation Reference Table

The table below consolidates the rules from the C++ standard (cppreference.com) for every standard container. "Iter" means iterators; "Ref" means pointers and references to elements. "N/A" means the operation does not exist on that container. Read-only operations (find, count, size, operator[] for map/set lookups, etc.) never invalidate anything.

Key observations from the table:

• std::deque is the only container where insertion invalidates all iterators but not all references: after a push_front or push_back, any pointer &d[i] still points to the correct element, but every pre-obtained iterator is poison.
• std::unordered_map is the inverse of its tree cousin: insertion can invalidate all iterators (on rehash) but never invalidates existing pointers or references to elements — because nodes are individually heap-allocated and do not move.
• std::flat_map / std::flat_set (C++23) offer O(log n) lookup with cache-friendly iteration but pay for it with vector-like invalidation on every mutation: treat them as sorted std::vector wrappers for invalidation purposes.
• swap for all containers is cheap (O(1)) and, per the standard, does not invalidate iterators or references — they simply now refer into the other container after the swap.

The vector::erase Return-Value Idiom

std::vector::erase — and erase on deque, string, and the unordered containers — returns an iterator to the element that now occupies the erased position (or end() if the last element was erased). This return value is the only valid way to advance through a sequence while erasing elements one at a time.

The classic bug

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

for (auto it = v.begin(); it != v.end(); ++it) {  // BUG
    if (*it % 2 == 0)
        v.erase(it);  // erase invalidates it; ++it on next iteration is UB
}

After erase(it), it is invalidated. The ++it at the top of the loop increments an invalid iterator — undefined behavior.

Correct solution 1: use the return value

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;              // only advance when NOT erasing
}
// v == {1, 3, 5}

The rule: ++it and it = v.erase(it) are mutually exclusive in any given loop iteration. Never do both.

Correct solution 2: std::erase_if (C++20)

#include <vector>
#include <algorithm>  // std::erase_if (free function, C++20)

std::vector<int> v = {1, 2, 3, 4, 5};
std::erase_if(v, [](int x) { return x % 2 == 0; });
// v == {1, 3, 5}

std::erase_if is defined for every standard container in C++20. It handles iterator management internally, uses the most efficient removal strategy for each container type, and reduces the conditional-erase pattern to a single readable statement.

Correct solution 3: index-based loop (vectors only)

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

for (std::size_t i = 0; i < v.size(); ) {
    if (v[i] % 2 == 0)
        v.erase(v.begin() + static_cast<std::ptrdiff_t>(i));
        // do NOT increment i; the next element has shifted into position i
    else
        ++i;
}

Index-based loops sidestep iterator invalidation for vectors, but they are O(n²) because each erase shifts all subsequent elements. Prefer the return-value idiom or std::erase_if for correctness and clarity; prefer erase(remove_if(...), end()) (the erase-remove idiom) for performance on large sequences.

std::list::erase — no special idiom needed

For std::list and std::forward_list, erasure only invalidates the erased iterator itself. All other iterators remain valid, so the return-value idiom still works but you do not need to worry about adjacent iterators being affected:

std::list<int> lst = {1, 2, 3, 4, 5};

for (auto it = lst.begin(); it != lst.end(); ) {
    if (*it % 2 == 0)
        it = lst.erase(it);  // same idiom, but only erased iter invalidated
    else
        ++it;
}

Reference Invalidation vs. Iterator Invalidation

The standard distinguishes three categories of handle: iterators, pointers, and references. Their invalidation rules are identical for most containers but diverge for std::deque and the unordered containers.

std::vector — references follow the same rules as iterators. A push_back that triggers reallocation invalidates not only every iterator but also every pointer and reference to elements:

std::vector<int> v = {10, 20, 30};
int& ref = v[0];   // reference to first element
int* ptr = &v[1];  // pointer to second element

v.push_back(40);   // may reallocate — ref and ptr are potentially dangling
// Reading ref or ptr here is undefined behavior if reallocation occurred
std::cout << ref;  // UB if capacity was exceeded

This is one of the most frequently overlooked forms of iterator invalidation because references look like ordinary C++ variables, not like iterator objects.

std::deque — the split guarantee. After push_front or push_back, all iterators are invalidated but all references and pointers to existing elements remain valid. After an insertion or erasure in the middle, both iterators and references are invalidated.

std::deque<int> d = {10, 20, 30};
int& ref = d[1];   // reference to middle element

d.push_back(40);   // invalidates all iterators; ref remains valid
std::cout << ref;  // OK — prints 20

auto it = d.begin();
d.push_front(0);   // it is now invalid
// *it is UB — but ref is still OK

std::unordered_map — references survive rehash, iterators do not. Because elements are stored in individually heap-allocated nodes, a rehash only restructures the bucket array — the nodes themselves do not move. All iterators are invalidated (they embed bucket information), but pointers and references to elements survive:

std::unordered_map<int, std::string> m;
m.reserve(2);  // set up for exactly 2 elements

m[1] = "one";
const std::string& ref = m[1];  // reference to the mapped value
m[2] = "two";
m[3] = "three";  // may trigger rehash — ref still valid, iterators are not

std::cout << ref;  // OK — "one" is still there, node did not move

std::list and std::map — neither iterators nor references are ever invalidated by insertion. Only the iterator and reference to an erased element itself become invalid.

std::string and std::string_view Invalidation

std::string follows the same invalidation rules as std::vector<char>. The standard states: references, pointers, and iterators into a basic_string may be invalidated by any call to a non-const member function or any standard library function that takes a reference to a non-const basic_string.

In practice this means: treat any string mutation — append, insert, replace, +=, resize, reserve — as potentially invalidating all iterators and references, even when no reallocation visibly occurred, because the standard deliberately leaves implementation latitude here.

std::string_view magnifies this hazard. A string_view points into the underlying string buffer but holds no ownership stake. If the string reallocates (or is destroyed), the string_view becomes a dangling pointer with no runtime indication:

#include <string>
#include <string_view>

std::string s = "hello";
std::string_view sv = s;  // sv points into s's buffer

s += " world";  // may reallocate — sv is now potentially dangling
// sv.data() may point to freed memory; using sv is undefined behavior
std::cout << sv;  // UB

Safe pattern: produce a string_view only from a string whose lifetime and content are stable for the duration of the view's use, and never store a string_view across an operation that modifies the source string.

std::span and Vector Reallocation

std::span (C++20) is a non-owning view over a contiguous sequence. Its own iterators are invalidated whenever any pointer in the range [data(), data() + size()) is invalidated. For a span observing a std::vector, that means every vector reallocation silently invalidates the span:

#include <vector>
#include <span>

std::vector<int> v = {1, 2, 3};
std::span<int> s = v;  // s.data() == v.data()

v.push_back(4);  // reallocation likely — s.data() is now dangling
// iterating s, or calling s[0], is undefined behavior

for (int x : s)          // UB if v reallocated
    std::cout << x;

The bug is insidious because s itself still looks well-formed — it still holds the old pointer and size with no runtime flag to signal invalidation. The corrective approach is to either reconstruct the span after each mutation, or ensure no reallocation can occur (via reserve) for the span's lifetime:

std::vector<int> v;
v.reserve(100);  // guarantee: no reallocation while size() <= 100

std::span<int> s = v;

v.push_back(1);  // no reallocation — s is still valid (but size is stale!)
v.push_back(2);
// Note: s.size() == 0 (captured at construction time when v was empty)
// Reconstruct the span to see current elements:
s = v;  // now s.size() == 2, s.data() == v.data()

Note that even without reallocation, s.size() reflects the vector's size at the time the span was constructed. A span is not a live view of the vector's logical size — it is a fixed-length window into memory. Always reconstruct the span to pick up new elements.

A std::span over a std::array or a raw array with static extent is immune to this class of bug because neither of those underlying storage types ever reallocates:

std::array<int, 4> arr = {1, 2, 3, 4};
std::span<int, 4> s = arr;  // static-extent span; arr cannot reallocate

arr[0] = 99;  // mutation in place — s[0] sees 99, no invalidation possible

Detecting Invalidation Bugs at Runtime

Iterator invalidation bugs are undefined behavior and produce no guaranteed runtime signal. Two tools are particularly effective at catching them:

AddressSanitizer (ASan) — compile with -fsanitize=address. ASan tracks heap allocation lifetimes and will report use-after-free when code dereferences an iterator that pointed into a reallocated vector buffer. Enable with:

// Compile: clang++ -fsanitize=address -g -O1 myfile.cpp

libstdc++ Debug Mode / libc++ debug mode — both standard library implementations ship an instrumented debug mode that validates iterator state on every dereference:

// GCC / libstdc++: compile with -D_GLIBCXX_DEBUG
// Clang / libc++:  compile with -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG

In libstdc++ debug mode, invalidated iterators are tracked at runtime and dereferencing one produces an immediate assertion failure with a helpful diagnostic — far more informative than a crash from raw undefined behavior. Use debug mode during testing and development; strip it for release builds where performance matters.

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