Comprehensive Guide to Iterator Invalidation Rules in C++ Containers: Evolution from C++03 to C++17 and Practical Insights

Introduction and Background

In C++ programming, iterators provide a generic interface for accessing container elements, but dynamic changes to container structures can lead to iterator invalidation, where iterators point to invalid memory or incorrect elements. Understanding iterator invalidation rules is crucial for writing correct and efficient code. This article systematically outlines these rules across different C++ standards (C++03, C++11, C++17), with a focus on the latest C++17 specifications, and offers practical guidance.

Basic Concepts of Iterator Invalidation

Iterator invalidation occurs when an iterator becomes invalid after a container operation, potentially causing undefined behavior such as accessing dangling pointers or incorrect data. Invalidation typically results from memory reallocation, element relocation, or structural changes in the container. For example, vector reallocates memory when capacity is exceeded, invalidating all iterators, while list's node-based structure generally preserves iterator validity. The standard defines rules to clarify the impact of operations on iterators, which developers must follow to avoid errors.

Evolution of Rules from C++03 to C++17

C++03 established foundational rules but had ambiguities, such as the treatment of end() iterators. C++11 introduced forward_list and unordered containers, refining rules and clarifying that swap() does not affect element iterators (though end() may be invalidated). C++17 further standardized rules, adding explicit guidelines for operations like extract and merge, and strengthening general requirements. This article focuses on C++17, with supplements from earlier versions.

Iterator Invalidation Rules for Sequence Containers

Sequence containers include vector, deque, list, forward_list, and array. The following analysis is based on C++17 standards.

Insertion Operations

vector::insert, emplace_back, and similar functions invalidate all iterators and references if reallocation occurs; otherwise, iterators before the insertion point remain valid. Example:

std::vector<int> vec = {1, 2, 3};
vec.reserve(5); // prevent reallocation
auto it = vec.begin() + 1;
vec.insert(it, 4); // it remains valid, pointing to element 2

deque insertion in the middle invalidates all iterators and references; insertion at ends invalidates all iterators but leaves references valid. list and forward_list insertion does not affect iterators. array iterators are never invalidated during their lifetime, but swap may change the pointed-to value.

Erasure Operations

vector::erase and pop_back invalidate iterators and references at or after the erasure point. Example:

std::vector<int> vec = {1, 2, 3, 4};
auto it = vec.begin() + 2; // points to 3
vec.erase(vec.begin() + 1); // erases 2, it becomes invalid

deque erasure of the last element invalidates only the erased elements and the end() iterator; erasure of the first element invalidates only the erased elements; erasure in the middle invalidates all iterators and references. list and forward_list erasure invalidates only iterators to the erased elements. clear invalidates all iterators for all sequence containers (except end() for forward_list).

Resizing and Other Operations

vector::resize follows insertion/erasure rules. assign invalidates all iterators. Special functions like list::remove invalidate only iterators to erased elements.

Iterator Invalidation Rules for Associative Containers

Associative containers include set, map, and their multi-versions.

Insertion and Erasure Operations

Insertion does not affect iterators or references. Erasure invalidates only iterators to the erased elements. C++17 introduces extract, which invalidates only the iterator to the extracted element, but pointers and references remain valid, enabling node transfer without copying. Example:

std::set<int> s = {1, 2, 3};
auto it = s.find(2);
auto node = s.extract(it); // it invalidated, but node holds element 2
s2.insert(std::move(node)); // transfer node

Iterator Invalidation Rules for Unordered Associative Containers

Unordered associative containers like unordered_set are based on hash tables, with more complex rules.

Insertion and Rehashing

Insertion may trigger rehashing, invalidating all iterators but not affecting references. Rehashing occurs if (N+n) > z * B, where N is the current size, n is the number of insertions, B is the bucket count, and z is the maximum load factor. Example:

std::unordered_set<int> us;
us.max_load_factor(0.7);
us.rehash(10); // preallocate buckets
auto it = us.begin();
us.insert(5); // if rehashing not triggered, it remains valid

Erasure and Merge Operations

Erasure invalidates only iterators to erased elements. In C++17, merge operations invalidate all iterators to transferred elements and the receiving container, but iterators to remaining elements in the source container remain valid.

Iterator Invalidation Rules for Container Adaptors

stack, queue, and priority_queue inherit rules from their underlying containers (default deque or vector). Developers must apply rules based on the actual container type used.

General Rules and Considerations

Unless specified otherwise, invoking a container member function or passing a container to a library function does not invalidate iterators or change element values (standard 26.2.1/12). swap() does not invalidate iterators to elements, but end() may be invalidated (26.2.1/11.6). Algorithms like transform and accumulate require not modifying elements or invalidating iterators.

Practical Recommendations and Common Mistakes

Use reserve() to preallocate memory for vector and avoid reallocation. When erasing elements in loops, update iterators or use the new iterator returned by erase. Avoid using invalidated iterators after operations. Example mistake:

std::vector<int> vec = {1, 2, 3};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (*it == 2) {
        vec.erase(it); // it invalidated, subsequent ++it undefined
    }
}

Correct approach:

for (auto it = vec.begin(); it != vec.end(); ) {
    if (*it == 2) {
        it = vec.erase(it); // update iterator
    } else {
        ++it;
    }
}

Conclusion

Iterator invalidation rules are fundamental to C++ container programming. From C++03 to C++17, rules have been refined to emphasize safety and clarity. Developers should understand container-specific behaviors and standard clauses, leveraging tools like reserve and extract to write robust code. Future C++ versions may further optimize these rules, so staying updated with standards is recommended.