An iterator becomes invalidated when the life of the handle into a container comes to an end. The vector may contain exactly the same values after the operation while all stored addresses into its previous memory location are now unusable. First, you retrieve a particular score, save a reference to it in order to be able to modify it later, and then add a couple of new scores to the end of the list:
#include <iostream>
#include <vector>
int main() {
std::vector<int> scores{ 90, 85, 70, 60 };
// Get a reference to the third score (70)
int& third_score = scores[2];
std::cout << "Before update: " << third_score << "\n";
// Add several new scores, triggering a reallocation
scores.push_back(55);
scores.push_back(50);
scores.push_back(45);
// Attempt to use the reference
third_score += 5;
std::cout << "After update: " << third_score << "\n";
return 0;
}This code compiles successfully without giving any warnings. Nevertheless, running it may be extremely dangerous. Depending on your compiler and memory state of the system, it may output the wrong value, some garbage, or cause a crash of the whole program. The reference has been invalidated. This means that the memory location it refers to is now not managed by the vector anymore and, thus, accessing it leads to undefined behavior.
The iterator keeps the address of the element it referred to before with great certainty.
Why Does Invalidation Occur
In order to understand why do pointers, references and iterators become invalidated, it is necessary to have a look at how containers manage their memory. A contiguous container, such as a vector, allocates a piece of the continuous memory on the heap. When you add elements and a vector gets larger than its current capacity, it has to allocate a larger piece of memory somewhere else, copy or move all existing elements there and then deallocate the previous memory location.
Invalidation means that an iterator, a pointer or a reference do not refer to the element it referred to before. Checking whether the address stored in the handle remains the same will not solve the problem of using an invalidated handle. A vector reallocation invalidates all these handles, and deleting a single element of the vector invalidates all handles from and including it.
During this reallocation, all pointers, references and iterators that refer to elements located in the old memory location point now to the already deallocated memory. So, they become dangled pointers or dangled references. Even if a vector does not allocate new memory, inserting or deleting elements in the middle of the vector implies shifting all elements after it to preserve their contiguity. This shift means that while your reference or iterator may continue to refer to the memory location within the vector, it refers to the different element now rather than the element you were referring to.
Other containers use different memory layouts and, consequently, different invalidation scenarios. For example, a deque has a segmented layout, which consists of several independent memory locations. If you insert elements at the front or at the back of the deque, the old segments are not moved and, hence, pointers and references to the old elements stay valid. Nevertheless, since the central directory of segments may be reallocated, all iterators to the deque are invalidated anyway. In case of inserting or deleting elements in the middle of the deque, all iterators and references are invalidated immediately.
Node-based containers, such as lists, sets and maps, store each element in its own independent heap-allocated node. Since these nodes are never moved or reallocated in the process of adding or deleting other elements, they are the most stable ones. References, pointers and iterators to the elements of the node-based container are completely valid until you delete this element explicitly.
Invalidation rules and modification safe patterns
Rules depend on the container and modification operations. Usually, node-based containers keep references to untouched nodes valid but erased elements are always gone. Unordered containers may invalidate iterators during rehash operation while references to the elements remain valid. Safe patterns include reacquisition of positions after a structural modification or usage of the iterator provided by erase operation if the interface allows this.
In order to write the safe code, it is important to know the invalidation rules for your container. The standard library containers have these common behaviors during modification operations:
- vector: Any insertion, which causes the reallocation, invalidates all iterators, pointers and references. If reallocation does not occur, insertions and deletions invalidate all handles starting with the point of modification.
- deque: Insertions at the front or back positions invalidate all iterators, but pointers and references stay valid. Insertions or deletions in the middle invalidate all iterators, pointers and references.
- lists: Insertions and deletions never invalidate iterators, pointers and references to other elements. Only iterators and references to the erased elements are invalidated.
- maps, sets and unordered variants: Insertions never invalidate iterators, pointers and references. Deletions invalidate only iterators, pointers and references, which refer to the specific erased elements.
Quite common task in programming is the iteration through a container and erasing of the elements meeting certain criteria. Trying to perform this task in the naive loop will lead you to the invalidation bugs very quickly, since the erasure of the element invalidates the iterator, which is currently used for traversing the collection. The proper way of performing this task is to use the return value of the erasure member function, which returns the valid iterator, referring to the next element:
#include <iostream>
#include <vector>
int main() {
std::vector<int> numbers{ 1, 2, 3, 4, 5, 6 };
auto it = numbers.begin();
while (it != numbers.end()) {
if (*it % 2 == 0) {
// erase() removes the element and returns the next valid iterator
it = numbers.erase(it);
} else {
// Only increment if we did not erase an element
++it;
}
}
for (int n : numbers) {
std::cout << n << " ";
}
std::cout << "\n";
return 0;
}Quite a tricky invalidation bug is caused by using the range-based loop. Since a range-based loop compiles down to the standard loop, which caches the iterators to the beginning and the end of the container behind the scenes, adding, inserting or erasing of the elements within the body of the range-based loop immediately invalidates these iterators causing undefined behavior on the very next iteration. If you have to change the size of the container during the traversal, you have to use a standard loop and manually update the iterator as shown in the example above.
Exercise: Iterator and Reference InvalidationStarter code, hints and solutionOpenClose
Practice: Iterator and Reference Invalidation
Work through the mission, reveal hints only when needed, and compare your result with the model solution.
Your challenge
Add an 8 next to the existing 2 and log each even value just before erasing it. Predict the remaining values and show why the returned iterator must be reused.
Mission checklist
- Run the starter as a baseline, then predict the change requested in Your challenge.
- Make that change in your editor; use the lesson-specific hints if you need help.
- Compile and run your answer, then compare with the worked solution and explain the result.
Starter program
This is the working baseline, not the completed answer. Compile as C++20, then make the change described above.
#include <iostream>
#include <vector>
int main() {
std::vector<int> numbers{ 1, 2, 3, 4, 5, 6 };
auto it = numbers.begin();
while (it != numbers.end()) {
if (*it % 2 == 0) {
// erase() removes the element and returns the next valid iterator
it = numbers.erase(it);
} else {
// Only increment if we did not erase an element
++it;
}
}
for (int n : numbers) {
std::cout << n << " ";
}
std::cout << "\n";
return 0;
}Hints
numbers.erase(it) invalidates the erased position and returns an iterator to the following element. Assign that return value back to it before another dereference.
Only the non-erasing branch increments it. If you incremented after erase as well, you could skip the element that just shifted into the current position.
Worked solution
The added removal log reads each even value before erase invalidates the iterator. The returned iterator is assigned back to it, so consecutive even elements are handled correctly. Final values remain 1,3,5; no erased element is dereferenced afterward.
#include <iostream>
#include <vector>
int main() {
std::vector<int> numbers{ 1, 2, 8, 3, 4, 5, 6 };
auto it = numbers.begin();
while (it != numbers.end()) {
if (*it % 2 == 0) {
// erase() removes the element and returns the next valid iterator
std::cout << "Erasing " << *it << '\n';
it = numbers.erase(it);
} else {
// Only increment if we did not erase an element
++it;
}
}
for (int n : numbers) {
std::cout << n << " ";
}
std::cout << "\n";
return 0;
}
Example output
Erasing 2
Erasing 8
Erasing 4
Erasing 6
1 3 5
0 comments
No comments yet. Be the first.