Hello everyone, I am Xiaokang.
Have you ever fallen into this pit? Why does my program, which is clearly very simple, always crash inexplicably!
Hey, C++ enthusiasts, today we are going to talk about a pitfall that almost all C++ programmers encounter—iterator invalidation. Whether you are a beginner or a seasoned coder with years of experience, this issue can cause your program to crash unexpectedly. But don’t worry, after reading this article, you will definitely have an epiphany: “Oh! So that’s how it is!”
👨💻 Hey, friends! First, follow “Learn Programming with Xiaokang“, then read the article, so that knowledge can form a complete system!
What is an Iterator?
Before we rush into discussing “invalidation”, let’s first understand what an iterator is.
Imagine an iterator as a “pointer” that points to an element in a container (like a vector or list). With an iterator, we can access and modify elements in the container, and we can also move within the container (forward or backward).
In simple terms, an iterator is a bridge between the container and algorithms, allowing you to easily traverse and manipulate elements in the container without worrying about the internal structure of the container.
vector<int> nums = {1, 2, 3, 4, 5};
// it is an iterator pointing to the first element of the vector
auto it = nums.begin();
cout << *it << endl; // outputs 1
</int>What is Iterator Invalidation?
Now we come to the key question: what is iterator invalidation?
In simple terms, when you perform certain operations on a container, the previously valid iterator becomes invalid, and using this iterator will lead to undefined behavior (usually a program crash), this is iterator invalidation.
It’s like you have a key (iterator) to open a door (access container elements), but someone changes the lock (the container structure changes) while you are not paying attention, and your key naturally becomes useless.
Common Scenarios of Iterator Invalidation
1. Iterator Invalidation in Vectors
Vectors are the most commonly used STL containers, and they are also the place where iterator invalidation is most likely to occur.
Scenario 1: Invalidation Caused by Adding Elements (push_back)
vector<int> nums = {1, 2, 3};
auto it = nums.begin(); // it points to 1
nums.push_back(4); // may cause iterator invalidation
cout << *it << endl; // dangerous operation! may crash
</int>Why does it become invalid? Because vectors store elements contiguously in memory, when there is not enough space, they will reallocate a larger block of memory and copy the original elements over. At this point, the original memory address changes, and the previous iterator naturally becomes invalid.
It’s like you are reading a book, and suddenly someone takes that book away and replaces it with a new one in its place—your finger position is naturally incorrect.
Scenario 2: Invalidation Caused by Insert Operations
When it comes to adding elements to a vector, we cannot forget another common operation—insert! This one is even trickier than push_back!
vector<int> nums = {1, 2, 3, 4, 5};
auto it = nums.begin() + 2; // it points to element 3
nums.insert(nums.begin(), 0); // insert 0 at the front
cout << *it << endl; // dangerous operation! it is already invalid
</int>Why is insert more likely to cause problems? Because insert has double the potential for disaster:
First, like push_back, if the vector’s capacity is insufficient, insert will cause a reallocation of memory, invalidating all iterators.
Second, even if there is no reallocation, insert will shift all elements from the insertion point and beyond, causing all iterators at those positions to become “misaligned”.
For example, it’s like you are in a queue, and suddenly someone cuts in front of you—both you and the people behind you are forced to move back one position—your previously recorded position information is all messed up!
Remember this simple rule:
- If insert causes a resize: all iterators are invalidated
- If insert does not cause a resize: iterators at the insertion point and beyond are invalidated
Scenario 3: Invalidation Caused by Deleting Elements
vector<int> nums = {1, 2, 3, 4, 5};
for (auto it = nums.begin(); it != nums.end(); ++it) {
if (*it == 3) {
nums.erase(it); // iterator invalidation
cout << *it << endl; // do not continue using it, dangerous operation! may crash
}
}
</int>What’s the problem? When you delete an element, all elements after that position will move forward, and the original iterator will point to an incorrect position.
2. Iterator Invalidation in Lists
Lists are doubly linked lists, and their iterator invalidation scenarios are simpler than those of vectors.
list<int> myList = {1, 2, 3, 4, 5};
auto it = myList.begin();
++it; // it points to 2
myList.erase(it); // delete 2, it becomes invalid
// cannot use it anymore
</int>For lists, only the iterator of the deleted node becomes invalid, while the iterators of other nodes remain valid. This is because lists are structured as linked lists, and deleting a node does not affect the memory positions of other nodes.
3. Iterator Invalidation in Maps/Sets
Maps and sets are implemented based on red-black trees, and their iterator invalidation rules are similar to those of lists.
map<int, string=""> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};
auto it = myMap.begin();
myMap.erase(it); // it becomes invalid
// cannot use it anymore
</int,>Similarly, only the iterator of the deleted element becomes invalid, while the iterators of other elements remain valid.
How to Avoid the Pitfalls of Iterator Invalidation?
Now that we know the problem, how can we avoid it? Here are some practical tips:
Tip 1: Use the Return Value of erase and insert
Most containers’ erase methods return the next valid iterator, and insert returns an iterator pointing to the newly inserted element, which we can take advantage of.
// return value of erase
vector<int> nums = {1, 2, 3, 4, 5};
for (auto it = nums.begin(); it != nums.end(); ) {
if (*it == 3) {
it = nums.erase(it); // erase returns the next valid iterator
} else {
++it;
}
}
// return value of insert
vector<int> nums2 = {1, 2, 3, 4};
auto it2 = nums2.begin();
it2 = nums2.insert(it2 + 2, 100); // it2 now points to the newly inserted 100
cout << *it2 << endl; // outputs 100
</int></int>This tip is especially useful when you need to perform consecutive operations on the container, keeping the iterator always valid.
Tip 2: Mark and Then Delete
vector<int> nums = {1, 2, 3, 4, 5};
vector<int> toRemove;
// first mark the elements to delete
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] == 3) {
toRemove.push_back(i);
}
}
// delete from back to front (to avoid index changes)
for (int i = toRemove.size() - 1; i >= 0; --i) {
nums.erase(nums.begin() + toRemove[i]);
}
</int></int>Tip 3: Use Stable Container Operations
Some container operations do not cause iterator invalidation, so prefer to use these operations.
// for list, splice operation does not cause iterator invalidation
list<int> myList = {1, 2, 3, 4, 5};
list<int> anotherList = {10, 20};
auto it = myList.begin();
++it; // it points to 2
myList.splice(myList.end(), anotherList); // will not cause it to become invalid
cout << *it << endl; // still 2
</int></int>Practical Case: Solving Common Iterator Invalidation Issues
Case 1: Deleting Even Numbers from a Vector
Incorrect Implementation:
vector<int> nums = {1, 2, 3, 4, 5, 6};
for (auto it = nums.begin(); it != nums.end(); ++it) {
if (*it % 2 == 0) {
nums.erase(it); // incorrect! iterator invalidation
}
}
</int>Correct Implementation:
vector<int> nums = {1, 2, 3, 4, 5, 6};
for (auto it = nums.begin(); it != nums.end(); ) {
if (*it % 2 == 0) {
it = nums.erase(it);
} else {
++it;
}
}
</int>Case 2: Adding Elements While Iterating
Incorrect Implementation:
vector<int> nums = {1, 2, 3};
for (auto it = nums.begin(); it != nums.end(); ++it) {
if (*it == 2) {
nums.push_back(4); // incorrect! may cause iterator invalidation
}
}
</int>Correct Implementation (using index):
vector<int> nums = {1, 2, 3};
int size = nums.size(); // first record the original size
for (int i = 0; i < size; ++i) {
if (nums[i] == 2) {
nums.push_back(4); // use index instead of iterator
}
}
</int>Conclusion
Iterator invalidation may seem complex, but as long as you remember a few simple rules, you can easily avoid this pitfall:
- Vector: After inserting or deleting elements, iterators at that position and beyond will become invalid; if memory is reallocated, all iterators will become invalid.
- List/Forward List: Only the iterator of the deleted element will become invalid.
- Map/Set/Multimap/Multiset: Only the iterator of the deleted element will become invalid.
- Unordered Map/Unordered Set: Insert operations may cause all iterators to become invalid (rehash); delete operations will only invalidate the iterator of the deleted element.
In actual programming, it is often more elegant to use modern C++ algorithms and container operations, such as the combination of <span>remove_if</span> and <span>erase</span>, to solve problems:
vector<int> nums = {1, 2, 3, 4, 5, 6};
// one line of code to delete all even numbers
nums.erase(remove_if(nums.begin(), nums.end(),
[](int x) { return x % 2 == 0; }),
nums.end());
</int>So, how about it? Do you now have a better understanding of the pitfall of iterator invalidation? Next time you write code, don’t forget to remind yourself: if the container changes, the iterator may not be reliable!
There’s More to Explore, Let’s Deep Dive into C++!
After reading this article, do you feel like you have a new understanding of iterator invalidation? In fact, the pitfalls of C++ are far more than this one; behind each pitfall lies fascinating technical principles and solutions.
Want to avoid more hidden traps in C++ development and master techniques that make your code more efficient and elegant? Feel free to follow my public account “Learn Programming with Xiaokang“!
Here, I will continue to unlock for you in the same down-to-earth language:
- Core knowledge of C/C++ that will impress interviewers
- Performance optimization secrets summarized from practical experience in large companies
- Fun interpretations of fundamental computer knowledge
- And more practical guides like “iterator invalidation”
Learning programming is like solving puzzles; every time you master a knowledge point, it’s a key to open a new world. I hope to work with you to simplify complex problems and make dull technology interesting!
If this article helped you, feel free to like, share, and forward, and also welcome you to share the C++ pitfalls you have encountered in the comments!
See you next time!👨💻
How to Follow My Public Account?
Click on the public account card below to follow.
Oh, by the way, I also created a technical exchange group where everyone can discuss technology and answer questions. Stuck? Don’t understand something? Feel free to ask in the group! Not just me, there are a bunch of technical experts in the group ready to help you. Learning together is the motivation!
Collection of Useful Resources:What can you actually do with C++? A complete guide to popular employment directions!60 practical Linux C/C++ projects, challenge a salary of 300,000+map vs unordered_map in C++: Choosing the wrong container can slow your program down by 10 times!The invisible killer of memory management in C++: Why senior developers never store raw pointers in STL containers!“The Evolution of Computers” from punched tape to 32-bit Linux: The past and present of C++ program memory layout!“Must-Read for C++ Interviews” Is the vector object on the heap or stack? Let’s clarify this once and for all!