C++ Iterator Invalidation: “vector iterators incompatible”, Safe erase, and erase–remove

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

Introduction: “Debug Assertion Failed: vector iterators incompatible”

“I erased in a loop and crashed”

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.

This article covers:

• Ten common invalidation patterns
• Per-container rules (vector, list, map, unordered_*, deque)
• Safe idioms: erase–remove, deferred deletion, index walks
• Debugging: MSVC iterator checks, ASan, clang-tidy

---

Table of contents

1. What is iterator invalidation?
2. Per-container rules
3. Ten bad patterns
4. Safe coding patterns
5. Debugging
6. Production patterns
7. Summary

---

1. What is iterator invalidation?

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.

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]

---

2. Per-container rules (high level)

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.

list / forward_list

Inserts do not invalidate other iterators. erase invalidates only the erased element.

map / set

Insert/erase behavior similar to list-like stability for non-erased iterators (tree structure).

unordered_map / unordered_set

Rehash invalidates iterators (and can change bucket structure). erase invalidates erased elements.

deque

Many operations invalidate all iterators (implementation-dependent details—treat as unstable for long-lived iterators).

---

3. Ten common bad patterns

1. Range-for + erase/remove inside the loop

Do not mutate the same container in a range-for in ways that invalidate its hidden iterators.

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;
    }
}

2. Range-for + push_back extending past original end

Save original_size and index [0, original_size), or build a separate container.

3. Iterator across insert without refresh

After insert, recompute iterators from fresh begin() + index or store indices instead of iterators.

4. reserve after saving iterators

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

5. map erase + ++it blindly

Use it = m.erase(it) (C++11+) or erase post-increment idiom in older code.

6. Nested loops erase inner vector wrong

Inner loop must also use erase return pattern.

7. Saved iterator + later push_back

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

8. Concurrent iteration + mutation without sync

One thread push_back while another iterates → invalidation + data races—use mutex or separate snapshots.

9. Passing iterators into functions that grow the vector

Pass index or ensure no reallocation (e.g. reserved capacity contract).

10. Cached end() iterator across push_back

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

---

4. Safe patterns

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()
);

Deferred deletion (mark + sweep)

Mark objects during update; erase(remove_if, end) after the traversal completes—common in games and event systems.

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.

---

5. Debugging

• MSVC Debug STL: iterator checks (_ITERATOR_DEBUG_LEVEL).
• ASan: often reports heap-use-after-free when iterators imply freed storage.
• clang-tidy: rules like bugprone-inaccurate-erase help certain mistakes.

---

6. Production patterns

• 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.

---

7. Summary tables

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
deque	often all	often 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.

---

Implementation checklist

• 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

---

Related posts (internal)

• vector guide
• Iterator basics
• Use-after-free
• Range-based for
• Template errors
• Beginner mistakes
• Segfault
• Undefined behavior
• Stack overflow

---

Keywords

iterator invalidation, vector iterators incompatible, erase remove, push_back during iteration, range-based for

---

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.

---

Practical tips

• Enable ASan on CI for iterator-heavy modules.
• Code review checklist: range-for + mutation is a red flag.
• Prefer algorithms that operate in one pass over ad-hoc erase loops when possible.