`std::vector` Iterator Invalidation: Insertions & Erasures

What is Iterator Invalidation?

In the previous lesson, we established that a std::vector holds its elements in a single, contiguous block of memory on the heap. An iterator (or a pointer or reference) to an element inside that vector is essentially a memory address pointing to a location within that block.

"Invalidation" means that the iterator no longer points to a valid element within the container. Using an invalidated iterator results in undefined behavior.

The primary cause of iterator invalidation in std::vector is the very reallocation mechanism we studied. When a vector reallocates:

1. It allocates a new block of memory at a completely different address.
2. It moves the elements from the old block to the new one.
3. It deallocates the old memory block.

Any iterator, pointer, or reference still holding an address within that old, deallocated block is now "dangling." It's pointing to freed memory.

As you saw, the iterator pos became invalid because the memory it pointed to was freed and its contents moved elsewhere. Any attempt to use pos after the reallocation is a serious bug.

The Rules of Invalidation

Let's codify this into a set of rules. The key question to ask is always: "Does this operation have the potential to change the vector's capacity or shift its elements?"

Rule 1: Operations that May Reallocate

Any operation that might cause the vector's capacity() to change will invalidate all iterators, pointers, and references to elements in that vector. This is because a change in capacity might require a reallocation.

Common Culprits:

• push_back() or emplace_back(): If size() == capacity(), a reallocation occurs. If size() < capacity(), no iterators are invalidated.
• reserve(): If the new capacity is greater than the old capacity, a reallocation occurs.
• shrink_to_fit(): If capacity() > size(), a reallocation might occur to release unused memory.
• resize(): If the new size is greater than the current capacity, a reallocation occurs.

The fundamental takeaway is that after any potentially capacity-changing operation, you cannot trust any old iterators. If you still need to refer to an element, you must re-acquire the iterator (e.g., by calculating its index and using v.begin() + index).

Rule 2: Insertion (insert())

Insertion is a bit more nuanced.

• If an insertion causes a reallocation (because size() becomes greater than capacity()), then Rule 1 applies: all iterators are invalidated.
• If the insertion does not cause a reallocation, then only iterators, pointers, and references at or after the insertion point are invalidated. This is because all those elements had to be shifted to the right to make space for the new element. Iterators before the insertion point remain valid.

Rule 3: Erasure (erase())

Erasing elements from a std::vector never causes a reallocation. However, it does invalidate iterators.

When you call v.erase(it):

• The element at it is destroyed.
• All elements after it are moved one position to the left to fill the gap.
• Therefore, the iterator it and all iterators, pointers, and references at or after the erasure point are invalidated. Iterators pointing to elements before the erasure point remain valid.

This rule is a frequent source of bugs when modifying a vector while iterating over it. Let's see this in action.

The correct idiom for removing elements while iterating is to use the return value of erase():

// A vector of integers
std::vector<int> v = {10, 20, 30, 40, 50, 30};

// Correctly erase all elements with the value 30
for (auto it = v.begin(); it != v.end(); /* no increment here! */) {
    if (*it == 30) {
        // erase() invalidates 'it' but returns a valid iterator 
        // to the next element. We re-assign 'it' to this new iterator.
        it = v.erase(it);
    } else {
        // Only increment if we didn't erase.
        ++it;
    }
}
// v now contains {10, 20, 40, 50}

std::vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin() + 2; // 'it' points to the element '3'

v.insert(v.begin() + 1, 99); // Insert 99 before element '2'

// What happens if we try to use 'it' here?
std::cout << *it << std::endl; 

Summary of Invalidation Rules

Here is a quick reference table summarizing the rules for std::vector:

Conclusion

You've now seen that while std::vector is incredibly efficient, its performance comes with strict rules you must follow. An iterator is not a magical handle; it's a direct view into the container's memory, and that view can become invalid when the memory layout changes.

Key Takeaways:

• Reallocation Invalidates Everything: Any operation that might reallocate the vector's storage (push_back on a full vector, reserve, etc.) invalidates all pointers, references, and iterators to its elements.
• Erasure Invalidates From That Point Onward: erase() invalidates the iterator pointing to the erased element and all subsequent iterators.
• The erase() Idiom: To safely erase from a vector in a loop, you must use the iterator returned by erase() to update your loop's iterator: it = v.erase(it);.

This deep understanding of memory behavior is precisely what separates a novice from an expert C++ developer. It allows you to write code that is not only correct but also avoids subtle performance pitfalls and hard-to-diagnose crashes.

What's Next?

We have now seen both the power and the perils of std::vector's contiguous memory model. But what if your primary use case involves frequent insertions and deletions in the middle of the sequence? The shifting of elements can become a performance bottleneck.

In our next lesson, we will compare std::vector to its node-based cousin, std::list. We will analyze std::list's completely different memory layout, its performance trade-offs, and, most importantly, its far more relaxed iterator invalidation rules. This will give you a clearer picture of how to choose the right tool for the job.