Iterator Invalidation Rules for C++ Containers

C++ Iterator C++ Standard Library C++ Faq

Introduction

C++ containers, such as vectors, lists, and maps, provide a way to store and manage collections of elements. When working with containers, it is common to use iterators to navigate and access the elements. However, it is important to understand the iterator invalidation rules to prevent errors and undefined behavior.

Iterator Invalidation

An iterator is invalidated when any operation on the container modifies its structure in a way that the iterator's validity is lost. This can happen when elements are added, removed, or moved within the container.

Iterator Invalidation in Vector

In a vector, an iterator can become invalidated when elements are added or removed anywhere except at the end of the vector. Adding or removing elements at the end does not invalidate iterators, as long as the storage capacity of the vector is not exceeded, leading to a reallocation.

// Example of vector iterator invalidation
std::vector<int> vec = {1, 2, 3, 4};
std::vector<int>::iterator it = vec.begin();

vec.insert(vec.begin() + 2, 5); // Invalidates the iterator
vec.erase(vec.begin() + 1);     // Invalidates the iterator

// Accessing the invalidated iterator leads to undefined behavior
std::cout << *it << std::endl;

Iterator Invalidation in List

A list is different from a vector because iterators remain valid even if elements are added, removed, or moved anywhere within the list. The only exception is when an element is erased, and the iterator points to that element. In that case, the iterator becomes invalidated.

// Example of list iterator invalidation
std::list<int> myList = {1, 2, 3, 4};
std::list<int>::iterator it = myList.begin();

myList.insert(std::next(myList.begin()), 5); // Does not invalidate the iterator
myList.erase(++myList.begin());              // Invalidates the iterator

// Accessing the invalidated iterator leads to undefined behavior
std::cout << *it << std::endl;

Iterator Invalidation in Map

In a map, iterator invalidation depends on the kind of modification performed on the map. Modifications that do not affect the relative order of elements do not invalidate iterators. However, modifying the key of an element can result in an iterator becoming invalidated.

// Example of map iterator invalidation
std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};
std::map<int, std::string>::iterator it = myMap.begin();

myMap.insert({4, "four"});          // Does not invalidate the iterator
myMap.erase(++myMap.begin());       // Does not invalidate the iterator
myMap[2] = "new value";              // Invalidates the iterator (modifies the key)

// Accessing the invalidated iterator leads to undefined behavior
std::cout << it->second << std::endl;

Best Practices to Prevent Iterator Invalidation

  • Avoid storing iterators across container modification operations, as they are more likely to become invalidated. Instead, reacquire the iterator after the modification if using it is necessary.
  • If you need to track elements in a container, consider using indices (for vectors) or std::distance (for other containers) to keep track of the position without relying on iterators.
  • Be cautious when using iterator-based algorithms, such as std::find, as they may rely on valid iterators. If using them, ensure that the iterators passed to these algorithms are still valid.

Conclusion

Understanding iterator invalidation rules is crucial for writing correct and efficient C++ code. By following the rules and best practices, you can avoid iterator invalidation issues and minimize the risk of undefined behavior.

Related Questions