6.3 Iterators and Iterator Invalidation Hazards

Iterators are generalized pointer wrappers that allow you to traverse and manipulate elements inside standard containers. While they look like pointers, iterators must follow container safety rules. In this lesson, we will examine iterators and look at one of C++'s most dangerous undefined behavior bugs: iterator invalidation.

Let's look at iterator syntax and container modification traps.

An iterator holds the address of an element inside a container and supports operators like ++ to advance, -- to step back, and to dereference. Every standard container provides begin() (pointing to the first element) and end() (pointing to the memory slot after* the last element):

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec{10, 20, 30};
    
    // Traverse using explicit iterators
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << '\n'; // Dereference iterator to get value
    }
    return 0;
}

Under the hood, a range based for loop (like for (int x : vec)) is translated by the compiler into an iterator loop identical to the code above.

If you store an iterator pointing to an element in a container and then modify that container, the iterator can become invalidated. If you attempt to dereference or increment an invalidated iterator, your program will crash or corrupt memory.

Let's look at the classic vector invalidation trap: pushing elements to a vector while looping over it:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers{1, 2, 3};
    
    // DANGER: Loop with iterators while modifying the container!
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        if (*it == 2) {
            // Pushing an element can trigger capacity reallocation!
            // If vector reallocates, the old heap block is deleted.
            // The iterator 'it' now points to dead, deleted memory!
            numbers.push_back(100);
        }
    }
    return 0;
}

When the vector reallocates its capacity, it deletes the old heap memory block. The iterator it continues to hold the old address, becoming a dangling pointer. To prevent this, never modify the size of a container inside loops that rely on standard iterators, or use the iterator values returned by insertion methods to reset your position.