Diagnosing C++ Standard Container Iterator Invalidation

Recognizable condition

Your program crashes, produces corrupted output, or exhibits silent data corruption after a container modification (insert, erase, resize, reserve, rehash) while iterators, references, or raw pointers to elements remain in use. In release builds the failure often appears as a heap‑corruption error, an access violation, or simply wrong results. In debug builds the same code may abort with a clear "iterator invalidated" message.

Cause / diagnostic table

Container	Operations that invalidate iterators	Operations that invalidate references / pointers
std::vector, std::deque, std::string	Any insert/emplace/reserve that triggers reallocation; erase invalidates iterators at/after the erased position.	Same as iterators (contiguous storage).
std::list, std::forward_list	Only iterators to erased elements.	Only references/pointers to erased elements.
std::map, std::set	Only iterators to erased elements.	Only references/pointers to erased elements.
std::unordered_map, std::unordered_set	Rehash (when load_factor() > max_load_factor()) invalidates all iterators; erase invalidates only erased iterators.	References/pointers stay valid across rehash (since C++11).
std::array	Never.	Never.

Ordered debugging checks

1. Identify the container and modification. Look at the call stack for push_back, insert, emplace, erase, resize, reserve, or rehash.
2. Locate every live iterator/reference/pointer into that container across all threads. Search for variables of type iterator, const_iterator, T&, T* that are still in scope after the modification.
3. Check for reallocation or rehash. For vector‑like containers compare capacity() before and after the operation; for unordered containers compare bucket_count() or load_factor() against max_load_factor().
4. Verify absence of concurrent modification. A data race between iteration and modification is UB even if the container’s own rules would otherwise preserve validity.
5. Run with instrumentation. Compile with -fsanitize=address (AddressSanitizer) and/or enable the library debug mode (-D_GLIBCXX_DEBUG for GCC, -D_LIBCPP_DEBUG=1 for Clang). Invalidated iterator access will abort with a diagnostic.

Fixes tied to findings

• Reallocation invalidates iterators (vector, deque, string).
  • Call reserve() once before the first insertion so that capacity never grows.
  • Replace iterators with index‑based access (size_t i) when the container may grow.
  • Switch to std::list or std::forward_list if stable iterators are required.
• Erase invalidates iterators at/after the erased position.
  • Use the iterator returned by erase (C++11 onward): it = c.erase(it);.
  • Iterate with a while loop: while (it != c.end()) { if (cond) it = c.erase(it); else ++it; }.
• Rehash invalidates unordered‑container iterators.
  • Reserve bucket count up front: c.reserve(expected_elements); (note: this reserves elements, not buckets; compute buckets via ceil(n / max_load_factor()) if you need exact control).
  • Store keys or indices instead of iterators when the container may rehash.
• Concurrent access. Protect the container with a std::mutex (or a reader‑writer lock) or replace it with a thread‑safe alternative such as tbb::concurrent_unordered_map.

Escalation criteria

1. Third‑party library code. If the invalidation originates in a library you cannot modify, file a bug report with a minimal reproducer.
2. Heisenbug disappears under debugger/ASan. Suspect earlier undefined behavior. Use rr (record‑and‑replay) or Valgrind with watchpoints on the iterator address to capture the first invalid access.
3. Performance‑critical hot path prevents container change. Consider a custom allocator that guarantees stable addresses (e.g., a pool allocator) or an intrusive container such as boost::intrusive::list.
4. Cross‑translation‑unit lifetime issues. Encapsulate ownership with std::shared_ptr or redesign the API to avoid exposing iterators across module boundaries.

Concrete example: safe erase loop for std::vector

std::vector v = {1,2,3,4,5};
// BAD: for (auto it = v.begin(); it != v.end(); ++it) { if (*it % 2 == 0) v.erase(it); }
// GOOD:
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) it = v.erase(it);
    else ++it;
}

The bad version increments an iterator that has just been invalidated by erase, causing UB. The good version uses the iterator returned by erase, which points to the element following the erased one.

Practical verification steps

1. Add -fsanitize=address -fno-omit-frame-pointer to your compile flags and run the test suite. Any iterator invalidation typically surfaces as a heap‑use‑after‑free or global‑buffer‑overflow report.
2. Enable the standard library debug mode: -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC (GCC) or -D_LIBCPP_DEBUG=1 (Clang). Run the same tests; invalidated iterator access aborts with a descriptive message.
3. Integrate static analysis in CI: clang-tidy -checks=bugprone-iterator-invalidation,cppcoreguidelines-avoid-non-const-global-variables.
4. Write a regression test that performs the exact modification pattern (e.g., erase‑while‑iterating) and asserts that no sanitizer or debug‑mode abort occurs.
5. For non‑deterministic crashes, record execution with rr record ./my_program and replay with rr replay -M -c 'watch *iterator_address'.

Limitations & cautions

• Debug‑mode flags (_GLIBCXX_DEBUG) change the ABI and drastically reduce performance; never ship binaries built with them.
• reserve() only prevents invalidation while the size stays within the reserved capacity. Growth beyond that capacity still triggers reallocation.
• unordered_map::reserve(n) reserves buckets for n elements, not n buckets. Compute required bucket count as ceil(n / max_load_factor()) if you need precise control.
• std::string::data() and c_str() return pointers invalidated by the same operations that invalidate iterators (contiguous guarantee since C++11).
• Range‑based for loops cache end(); modifying the container inside the loop is UB even though the iterator is hidden.
• Boost containers (e.g., boost::container::stable_vector) have different guarantees; do not assume std:: rules apply.

How to confirm the fix

After applying a fix, re‑run the instrumented build (ASan + debug mode) and the regression test. Absence of aborts or sanitizer reports, together with a passing test suite, is the practical evidence that the iterator invalidation has been eliminated.