C++ Iterator Invalidation: “vector iterators incompatible”

Containers: std::vector · sequence basics: arrays and lists.

Introduction: “Debug Assertion Failed: vector iterators incompatible”

Messages like vector iterators incompatible, list iterator not dereferencable, or map/set iterator not incrementable usually mean iterator invalidation: you kept using an iterator after an operation that ended its validity. That is undefined behavior—often a crash. Iterator invalidation happens when a container reallocates, inserts, erases, clears, or rehashes such that old iterators no longer refer to valid elements.

Those messages come from MSVC’s debug-mode iterator checking, which tracks which container every iterator belongs to and whether the container has changed since. “incompatible” specifically means two iterators being compared or used together don’t belong to the same container, and invalidation is only one way to get there. The other classic cause is comparing iterators from two different copies:

std::vector<int> getItems();                         // returns by value
for (auto it = getItems().begin(); it != getItems().end(); ++it) { /* ... */ }
// each call returns a new temporary vector: begin() and end() belong to different objects

Here begin() points into one temporary that is destroyed at the end of the full expression, and end() into another. The fix is to store the result once (auto items = getItems();) or iterate with range-for, which binds the returned vector to a hidden reference for the duration of the loop. In release builds none of this is checked, which is why the same code “works” there until it doesn’t.

---

What iterator invalidation actually means

An iterator points at a container element. Operations that move or destroy storage can make old iterators stale—like a dangling pointer.

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin();
vec.push_back(6);  // may reallocate → it may be invalid
std::cout << *it << '\n';  // undefined behavior

Release builds may “work” until they do not—use Debug + ASan early.

Why it “works”: a vector iterator in a release build is typically just a raw pointer. After push_back reallocates, the old block is returned to the allocator but usually not given back to the operating system, so reading through the stale pointer still reads mapped memory, and it may even still contain the old values. The program prints the right number in testing and prints garbage, or corrupts some unrelated object, once the allocator reuses that block. Whether reallocation happens at all depends on the current capacity, which is why these bugs often appear only with larger inputs: a test with 5 elements never crosses the capacity boundary that a production batch of 5,000 crosses on every run.

flowchart TB
  subgraph Before[Before change]
    M1[Memory at 0x1000]
    I1[iterator → 0x1000]
  end
  subgraph After[After reallocation]
    M2[Memory at 0x2000]
    I2[iterator → 0x1000 ❌]
  end
  Before -->|push_back realloc| After
  I2 -.->|dangling| Crash[Crash / UB]

---

Which operations invalidate what, per container

vector

Operation	Invalidates
push_back / emplace_back	All iterators if reallocation
insert	iterators at/after insertion point; all if reallocation
erase	iterators at/after erase point; references/pointers similarly
clear	everything
reserve / resize	all if reallocation

Rule of thumb: treat vector iterators as fragile across any operation that can reallocate or shift elements.

The two mechanisms behind the table are different. Reallocation moves every element to a new block, so everything pointing into the old block is dangling. Shifting happens without reallocation: erase at position i moves elements i+1..n down by one, so an iterator to the old element i+1 now refers to what used to be i+2. Shifted iterators still point into valid memory, which is why tools that detect use-after-free don’t flag them; you silently process the wrong element or skip one. Whether push_back reallocates is observable: it reallocates exactly when size() == capacity() before the call.

list / forward_list

Inserts do not invalidate other iterators. erase invalidates only the erased element. Each element lives in its own node, and inserting or erasing only relinks neighboring nodes, which is the main reason to choose list when you must hold iterators long-term. splice moves nodes between lists without invalidating them; the iterators remain valid but now belong to the destination list.

map / set

Same node-based stability: insert invalidates nothing, erase invalidates only iterators to the erased elements. Tree rebalancing changes links between nodes, never the nodes’ addresses, so iterators, pointers and references to other elements remain valid.

unordered_map / unordered_set

Rehash invalidates iterators (and can change bucket structure) but not pointers or references to elements, because nodes are not moved. erase invalidates only the erased elements. An insert that doesn’t trigger a rehash invalidates nothing; one that does is governed by the load factor, so reserve up front makes it predictable.

deque

The rules are specified by the standard but are unusual, because a deque is a sequence of fixed-size blocks plus an index of block pointers:

• Insert at the front or back invalidates all iterators but no references to existing elements (the blocks stay put; the index may be reallocated).
• Insert in the middle invalidates all iterators and references.
• Erase at the front or back invalidates only the erased elements (plus end() when erasing the last element); erase in the middle invalidates everything.

So holding a pointer to a deque element across push_back is fine, while holding an iterator is not, the opposite of what most people expect.

---

Ten loops that break their own iterators

Range-for + erase/remove inside the loop

Do not mutate the same container in a range-for in ways that invalidate its hidden iterators. A range-for is rewritten by the compiler into a loop over auto __begin = vec.begin(), __end = vec.end(), and those hidden iterators are computed once. Erasing inside the body shifts elements under __begin and leaves __end pointing past the new end, so the loop skips elements and then reads past the valid range. Safe: classic loop with it = vec.erase(it), or erase–remove.

for (auto it = vec.begin(); it != vec.end(); ) {
    if (*it % 2 == 0) {
        it = vec.erase(it);
    } else {
        ++it;
    }
}

erase returns an iterator to the element that followed the erased one, which is exactly where the loop should continue, so the loop must not also increment in that branch. Writing vec.erase(it); ++it; increments an invalidated iterator. This loop is correct but O(n²) in the worst case for a vector, because every erase shifts the remaining tail; for many removals, erase–remove below does the same work in one pass.

Range-for + push_back extending past original end

Save original_size and index [0, original_size), or build a separate container. A typical case is a work queue that discovers new work while processing, such as a breadth-first traversal appending neighbors. With indices (for (size_t i = 0; i < v.size(); ++i)) re-reading size() each iteration, it is well-defined and processes new items too; with iterators or range-for, the first reallocation breaks it.

Iterator across insert without refresh

After insert, recompute iterators from fresh begin() + index or store indices instead of iterators. vector::insert returns an iterator to the inserted element, which is the valid replacement for the iterator you passed in: it = vec.insert(it, value);.

reserve after saving iterators

Call reserve before taking iterators you intend to keep valid (or avoid storing iterators across reserve).

map erase + ++it blindly

Use it = m.erase(it) (C++11+) or erase post-increment idiom in older code. The old idiom is m.erase(it++);: the post-increment advances it to the next node and passes the old value to erase, so the iterator you keep was never invalidated. It works for node-based containers, but not for vector, where erase invalidates everything after the erased position, including the incremented iterator. Since C++20, std::erase_if(m, pred) handles the whole loop for all standard containers.

Nested loops erase inner vector wrong

Inner loop must also use erase return pattern.

Saved iterator + later push_back

Long-lived iterators into vector are unsafe across growth—store index.

Concurrent iteration + mutation without sync

One thread push_back while another iterates → invalidation + data races—use mutex or separate snapshots. This is the hardest variant to diagnose because the crash depends on timing: the reader may run for hours before its iteration happens to overlap a reallocation. ThreadSanitizer reports the underlying data race even on runs that don’t crash, which makes it the right tool here rather than ASan.

Passing iterators into functions that grow the vector

Pass index or ensure no reallocation (e.g. reserved capacity contract). A subtle version of this is passing a reference to an element to a function that appends to the same vector: vec.push_back(vec[0]); is required to work by the standard (implementations handle that aliasing), but your own void addCopy(std::vector<T>& v, const T& x) { v.reserve(v.size() + 1); v.push_back(x); } is not, because reserve may free the storage x refers to before it is copied.

Cached end() iterator across push_back

Call end() each iteration or compare against saved size for controlled algorithms.

---

erase–remove, deferred deletion, and other safe rewrites

erase–remove (bulk predicate erase)

#include <algorithm>
#include <vector>
std::vector<int> vec = {1, 2, 3, 4, 5, 6};
vec.erase(
    std::remove_if(vec.begin(), vec.end(),
        [](int x) { return x % 2 == 0; }),
    vec.end()
);

remove_if doesn’t remove anything, which is the source of the name confusion. It moves the elements to keep toward the front, preserving their order, and returns an iterator to the new logical end; the elements after it are in a valid but unspecified state. erase then chops off that tail. The whole operation is a single O(n) pass with no repeated shifting. Forgetting the second argument, vec.erase(std::remove_if(...)), compiles but erases only one element, the first one in the leftover tail, which is exactly the mistake clang-tidy’s bugprone-inaccurate-erase check flags. In C++20, std::erase_if(vec, pred) does both steps and returns the number of removed elements.

Deferred deletion (mark + sweep)

Mark objects during update; erase(remove_if, end) after the traversal completes—common in games and event systems. In a game loop, for example, an entity’s update() may decide that another entity has died. Removing it from the entity vector right away invalidates the loop that is calling update(). Setting a dead flag and sweeping all dead entities once after the loop keeps the traversal stable and turns many individual erases into one linear pass. The cost is that other code must check the flag during the frame, since dead entities are still present until the sweep.

Index-based erase (note complexity)

Erasing by index can be O(n²) for many erases; prefer erase–remove for large removals.

unordered_map + reserve

Pre-size to reduce rehash iterator invalidation during growth.

References into vector

A reference to vec[i] is invalidated by reallocation—similar rules as iterators; reserve if you can bound growth.

---

Catching invalidation with Debug STL, ASan, and clang-tidy

• MSVC Debug STL: iterator checks (_ITERATOR_DEBUG_LEVEL).
• libstdc++ debug mode: compile with -D_GLIBCXX_DEBUG to get checked iterators on GCC; an invalidated iterator aborts with a message such as “attempt to dereference a singular iterator” and the offending container’s address.
• ASan: often reports heap-use-after-free when iterators imply freed storage.
• clang-tidy: rules like bugprone-inaccurate-erase help certain mistakes.

The tools catch different subsets, so it helps to know what each one sees. ASan detects accesses to freed memory, so it catches the reallocation cases (push_back, reserve, insert that grows the vector) with a report naming the push_back that freed the block. It does not catch shifted-but-valid memory after an erase, or reading past size() within capacity, because that memory is still allocated. Checked-iterator modes catch both, since they track logical validity rather than memory state, but they change the ABI: on GCC, everything that passes standard containers across library boundaries must be compiled with the same _GLIBCXX_DEBUG setting, otherwise you get link errors or crashes. -D_GLIBCXX_ASSERTIONS is a lighter, ABI-compatible alternative that adds bounds checks to operator[] and similar calls, but not iterator-validity tracking.

When I first switched a legacy test suite to _GLIBCXX_DEBUG, it failed in several places that had never crashed, nearly all of them erase loops that incremented after erasing. The loops had been skipping elements silently; the tests passed only because the skipped elements happened not to matter for the asserted results.

---

Entity managers, event buses, and shared containers

• Entity managers: mark pending_destroy, sweep after tick.
• Event buses: snapshot listeners (weak_ptr) or copy vector before notifying.
• Thread-safe wrappers: single mutex for all container mutations + separate snapshot reads if needed.

The event bus case is a textbook reentrancy bug. While emit() loops over its listener vector, a listener reacts to the event by unsubscribing itself (or subscribing a new listener), which erases from or appends to the vector being iterated. Nothing in the listener’s code looks wrong in isolation. Copying the listener list before the loop makes the iteration immune to changes; the trade-off is that a listener removed during the event may still receive that one event, so listeners should tolerate a final call, or the bus can check a “still subscribed” flag before each call.

---

Invalidation quick reference

Container quick reference

Container	insert	erase	rehash / realloc
vector	after pos + maybe all	after pos + maybe all	often all iterators
list	stable	erased only	N/A
map/set	stable	erased only	N/A
unordered_*	may rehash	erased only	rehash → invalidate iterators (not references)
deque	ends: all iterators, no references; middle: all	ends: erased only; middle: all	—

Rules of thumb

1. Do not modify a container in a range-for over that container unless the algorithm is proven safe.
2. erase: it = c.erase(it).
3. push_back: mind reallocation; reserve when you can bound size.
4. Avoid long-lived iterators into vector/deque across mutations—prefer indices.
5. If you must mutate during traversal, defer or work on a copy.

---

Review checklist for iterator-heavy code

• No range-for self-mutation without proof
• Erase loops use returned iterators
• reserve / size snapshots before growth loops
• No stored iterators across push_back without reserve contract
• Thread safety around shared containers
• ASan tests for iterator-heavy code

At the codebase level: enable ASan on CI for iterator-heavy modules, treat range-for + mutation as a red flag in review, and prefer algorithms that operate in one pass over ad-hoc erase loops when possible.

Closing: iterator invalidation is a top source of subtle crashes. Learn container rules, prefer erase–remove and deferred deletion, and validate with Debug STL + ASan.

---

Frequently Asked Questions (FAQ)

Q. Does calling reserve() keep my vector iterators valid?

A. Only if you call it before saving the iterators. A reserve that increases capacity reallocates and invalidates every iterator, pointer and reference into the vector. Once capacity is large enough, push_back does not reallocate, so iterators to existing elements stay valid, although end() is still invalidated. If you cannot bound the size in advance, store indices instead of iterators.

---

Related Articles

• std::vector in Practice
• Arrays and Lists
• C++ std::vector Basics — Initialization, Operations &
• C++ Use-After-Free (UAF)
• Range-based for
• Template errors
• Beginner mistakes
• Segfault
• Undefined behavior
• Stack overflow

---