Iterator invalidation — when containers reshuffle under you
Scenario
You iterate through a vector to remove all negative numbers: `for (auto it = vec.begin(); it != vec.end(); ++it) { if (*it < 0) vec.erase(it); }`. The program immediately crashes with a segmentation fault.
Why does erasing an element inside a loop crash the program?
Mental model
An iterator is a bookmark. If you rip a page out of the book (`erase`), all the pages shift. Your bookmark is now pointing to the wrong page, or worse, hanging off the edge of the book.
Iterator invalidation is one of the most common and dangerous bugs in C++. When a container's internal memory layout changes (due to resizing or shifting elements), any iterators, pointers, or references pointing to the old memory locations become invalid.
Explanation
Iterators are glorified pointers used to traverse containers.
**The Vector Erase Trap:**
When you call `vec.erase(it)`, the vector removes the element and shifts all subsequent elements to the left to close the gap. The iterator `it` is now pointing to the *next* element naturally, but the `for` loop will execute `++it` anyway. You end up skipping elements! Worse, if you erased the *last* element, `it` becomes invalid. Calling `++it` on an invalid iterator causes Undefined Behavior (usually a crash).
**The Fix:**
`erase()` always returns a brand new, valid iterator pointing to the element immediately following the erased one. You must update your iterator using this return value: `it = vec.erase(it);` and *only* increment it if you did *not* erase anything.
**Global Invalidation (Reallocation):**
As learned previously, if `push_back()` triggers a vector to expand its capacity, it moves to a completely new heap allocation. **Every single iterator** for that vector is instantly invalidated. Similarly, adding elements to an `unordered_map` can trigger a **rehash** (rebuilding the entire hash table to maintain O(1) lookups), which destroys all active iterators for the map. `std::list`, on the other hand, never shifts or reallocates nodes, so inserting or erasing only invalidates iterators pointing to the specific node being erased.
**Real-world Engineering:** Iterating while erasing is mandatory in scenarios like cleaning up dead entities in a game loop, or filtering out expired network connections from a server's active connection list. Mastering the `it = erase(it)` pattern is essential to avoid crashes.
Code examples
The bug: Erasing inside a loop
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, -2, 3, -4, 5};
// BUG: This will crash or skip elements.
for (auto it = vec.begin(); it != vec.end(); ++it) {
if (*it < 0) {
vec.erase(it);
// 'it' is now invalid or pointing to the shifted next element.
// The loop will still run ++it, skipping an element or crashing.
}
}
return 0;
}Modifying the structure of a sequence container while traversing it using standard `for` loop mechanics corrupts the traversal state.
The fix: Update the iterator
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, -2, 3, -4, 5};
auto it = vec.begin();
while (it != vec.end()) {
if (*it < 0) {
// erase() returns a valid iterator to the NEXT element.
it = vec.erase(it);
} else {
// Only increment if we didn't erase anything.
++it;
}
}
// Alternatively, in modern C++20:
// std::erase_if(vec, [](int x){ return x < 0; });
return 0;
}By manually controlling the iterator advancement, we ensure we always possess a valid 'bookmark' into the container.
Key points
- Catch erase returns: Always assign the result of `.erase()` back to your iterator to keep it valid.
- Beware reallocation: Adding elements to `vector` or `unordered_map` can trigger global reallocation, destroying all active iterators.
Common mistakes
- Using range-based for loops to erase: Writing `for (int x : vec) { if (x < 0) vec.erase(...) }` is extremely dangerous. Range-based loops hide the iterator management. If you modify the container's size inside a range-based for loop, you will silently invoke Undefined Behavior.
Recall questions
- What does `std::vector::erase(it)` return?
- Why does `push_back` on a vector sometimes invalidate all existing iterators?
- Why doesn't erasing an element from a `std::list` invalidate iterators pointing to other elements?
Questions & answers
A function iterates through an `unordered_map` and inserts new key-value pairs based on existing data. The program occasionally enters an infinite loop or crashes. Why?
Inserting elements into an `unordered_map` can trigger a rehash if the load factor gets too high. A rehash rebuilds the entire hash table, completely invalidating all current iterators and corrupting the active loop.
Approach: Understand global iterator invalidation events across different container types.
How do you safely remove all even numbers from a `std::vector` in pre-C++20?
You use an iterator and a `while` loop, assigning the iterator to the result of `vec.erase(it)` if the number is even, and manually calling `++it` otherwise. (Or, you use the Erase-Remove idiom: `vec.erase(std::remove_if(...), vec.end());`).
Approach: Identify safe traversal patterns for mutating vectors.