C++ Iterator Invalidation: Vector vs List

Understanding iterator invalidation rules is essential for writing safe, bug-free C++ code, as accessing an invalidated iterator results in undefined behavior. The primary difference between std::vector and std::list stems from their underlying memory layouts: std::vector stores elements contiguously in a dynamic array, making its iterators vulnerable to shifts and reallocations, whereas std::list is a doubly linked list composed of individually allocated nodes, granting its iterators exceptional stability during structural modifications.

Memory Architecture and Its Impact

The storage model directly dictates how each container manages iterators:

• std::vector: Elements reside sequentially in a single contiguous memory block. Inserting or deleting an element requires shifting subsequent elements, and exceeding current capacity triggers a reallocation of the entire memory block.
• std::list: Elements are stored in isolated, heap-allocated nodes connected via pointers. Inserting or removing an element simply involves relinking pointers without moving existing nodes in memory.

Insertion Invalidation Rules

std::vector

• If a reallocation occurs: If the new size exceeds vector::capacity(), a new, larger memory block is allocated, all elements are moved or copied, and the old memory is freed. Consequently, all iterators, pointers, and references to elements in the vector are invalidated.
• If no reallocation occurs: If the new size is less than or equal to capacity(), no reallocation happens. However, because elements must remain contiguous, all elements at and after the insertion point are shifted to the right. Therefore, iterators, pointers, and references at or after the insertion point are invalidated, while those before the insertion point remain valid.

std::list

• Inserting elements (via insert, emplace, push_back, or push_front) never invalidates any existing iterators, references, or pointers. The newly added node is simply linked to its neighbors without altering the memory addresses of existing nodes.

Deletion (Erasure) Invalidation Rules

std::vector

• When removing an element using erase, pop_back, or similar operations, the erased element and all elements positioned after it must be shifted left to close the gap.
• As a result, iterators, pointers, and references at or after the point of erasure are invalidated, including the end() iterator.
• Iterators and references pointing to elements before the erasure point remain completely valid.

std::list

• Erasing an element (via erase, pop_back, or pop_front) only invalidates iterators, references, and pointers pointing specifically to the erased element.
• Iterators pointing to any other element in the list—whether before or after the erased node—remain entirely valid.

Special Operations: Splicing and Swapping

• std::vector::swap: Swaps container contents in \(O(1)\) time. Iterators remain valid but now point to the same index within the other vector object (except end(), which invalidates).
• std::list::splice: Moves nodes between lists without copying. Iterators pointing to the moved elements remain valid, but they now refer to elements inside the destination list.

Quick Reference Summary