Deleting elements from std::set while iterating
C++IteratorSetStdC++ Standard-LibraryC++ Problem Overview
I need to go through a set and remove elements that meet a predefined criteria.
This is the test code I wrote:
#include <set>
#include <algorithm>
void printElement(int value) {
std::cout << value << " ";
}
int main() {
int initNum[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
std::set<int> numbers(initNum, initNum + 10);
// print '0 1 2 3 4 5 6 7 8 9'
std::for_each(numbers.begin(), numbers.end(), printElement);
std::set<int>::iterator it = numbers.begin();
// iterate through the set and erase all even numbers
for (; it != numbers.end(); ++it) {
int n = *it;
if (n % 2 == 0) {
// wouldn't invalidate the iterator?
numbers.erase(it);
}
}
// print '1 3 5 7 9'
std::for_each(numbers.begin(), numbers.end(), printElement);
return 0;
}
At first, I thought that erasing an element from the set while iterating through it would invalidate the iterator, and the increment at the for loop would have undefined behavior. Even though, I executed this test code and all went well, and I can't explain why.
My question: Is this the defined behavior for std sets or is this implementation specific? I am using gcc 4.3.3 on ubuntu 10.04 (32-bit version), by the way.
Thanks!
Proposed solution:
Is this a correct way to iterate and erase elements from the set?
while(it != numbers.end()) {
int n = *it;
if (n % 2 == 0) {
// post-increment operator returns a copy, then increment
numbers.erase(it++);
} else {
// pre-increment operator increments, then return
++it;
}
}
Edit: PREFERED SOLUTION
I came around a solution that seems more elegant to me, even though it does exactly the same.
while(it != numbers.end()) {
// copy the current iterator then increment it
std::set<int>::iterator current = it++;
int n = *current;
if (n % 2 == 0) {
// don't invalidate iterator it, because it is already
// pointing to the next element
numbers.erase(current);
}
}
If there are several test conditions inside the while, each one of them must increment the iterator. I like this code better because the iterator is incremented only in one place, making the code less error-prone and more readable.
C++ Solutions
Solution 1 - C++
This is implementation dependent:
Standard 23.1.2.8:
> The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.
Maybe you could try this -- this is standard conforming:
for (auto it = numbers.begin(); it != numbers.end(); ) {
if (*it % 2 == 0) {
numbers.erase(it++);
}
else {
++it;
}
}
Note that it++ is postfix, hence it passes the old position to erase, but first jumps to a newer one due to the operator.
2015.10.27 update:
C++11 has resolved the defect. iterator erase (const_iterator position); return an iterator to the element that follows the last element removed (or set::end, if the last element was removed). So C++11 style is:
for (auto it = numbers.begin(); it != numbers.end(); ) {
if (*it % 2 == 0) {
it = numbers.erase(it);
}
else {
++it;
}
}
Solution 2 - C++
If you run your program through valgrind, you'll see a bunch of read errors. In other words, yes, the iterators are being invalidated, but you're getting lucky in your example (or really unlucky, as you're not seeing the negative effects of undefined behavior). One solution to this is to create a temporary iterator, increment the temp, delete the target iterator, then set the target to the temp. For example, re-write your loop as follows:
std::set<int>::iterator it = numbers.begin();
std::set<int>::iterator tmp;
// iterate through the set and erase all even numbers
for ( ; it != numbers.end(); )
{
int n = *it;
if (n % 2 == 0)
{
tmp = it;
++tmp;
numbers.erase(it);
it = tmp;
}
else
{
++it;
}
}
Solution 3 - C++
You misunderstand what "undefined behavior" means. Undefined behavior does not mean "if you do this, your program will crash or produce unexpected results." It means "if you do this, your program could crash or produce unexpected results", or do anything else, depending on your compiler, your operating system, the phase of the moon, etc.
If something executes without crashing and behaves as you expect it to, that is not proof that it is not undefined behavior. All it proves is that its behavior happened to be as observed for that particular run after compiling with that particular compiler on that particular operating system.
Erasing an element from a set invalidates the iterator to the erased element. Using an invalidated iterator is undefined behavior. It just so happened that the observed behavior was what you intended in this particular instance; it does not mean that the code is correct.
Solution 4 - C++
C++20 will have "uniform container erasure", and you'll be able to write:
std::erase_if(numbers, [](int n){ return n % 2 == 0 });
And that will work for vector, set, deque, etc.
See cppReference for more info.
Solution 5 - C++
Just to warn, that in case of a deque container, all solutions that check for the deque iterator equality to numbers.end() will likely fail on gcc 4.8.4. Namely, erasing an element of the deque generally invalidates pointer to numbers.end():
#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque<int> numbers;
numbers.push_back(0);
numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);
//numbers.push_back(4);
deque<int>::iterator it_end = numbers.end();
for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
if (*it % 2 == 0) {
cout << "Erasing element: " << *it << "\n";
numbers.erase(it++);
if (it_end == numbers.end()) {
cout << "it_end is still pointing to numbers.end()\n";
} else {
cout << "it_end is not anymore pointing to numbers.end()\n";
}
}
else {
cout << "Skipping element: " << *it << "\n";
++it;
}
}
}
Output:
Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is not anymore pointing to numbers.end()
Note that while the deque transformation is correct in this particular case, the end pointer has been invalidated along the way. With the deque of a different size the error is more apparent:
int main()
{
deque<int> numbers;
numbers.push_back(0);
numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);
numbers.push_back(4);
deque<int>::iterator it_end = numbers.end();
for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
if (*it % 2 == 0) {
cout << "Erasing element: " << *it << "\n";
numbers.erase(it++);
if (it_end == numbers.end()) {
cout << "it_end is still pointing to numbers.end()\n";
} else {
cout << "it_end is not anymore pointing to numbers.end()\n";
}
}
else {
cout << "Skipping element: " << *it << "\n";
++it;
}
}
}
Output:
Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is still pointing to numbers.end()
Skipping element: 3
Erasing element: 4
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
...
Segmentation fault (core dumped)
Here is one of the ways to fix this:
#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque<int> numbers;
bool done_iterating = false;
numbers.push_back(0);
numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);
numbers.push_back(4);
if (!numbers.empty()) {
deque<int>::iterator it = numbers.begin();
while (!done_iterating) {
if (it + 1 == numbers.end()) {
done_iterating = true;
}
if (*it % 2 == 0) {
cout << "Erasing element: " << *it << "\n";
numbers.erase(it++);
}
else {
cout << "Skipping element: " << *it << "\n";
++it;
}
}
}
}
Solution 6 - C++
This behaviour is implementation specific. To guarantee the correctness of the iterator you should use "it = numbers.erase(it);" statement if you need to delete the element and simply incerement iterator in other case.
Solution 7 - C++
I think using the STL method 'remove_if' from
This solution may be less efficient.
Let's say we have some kind of container, like vector or a list called m_bullets:
Bullet::Ptr is a shared_pr<Bullet>
'it' is the iterator that 'remove_if' returns, the third argument is a lambda function that is executed on every element of the container. Because the container contains Bullet::Ptr, the lambda function needs to get that type(or a reference to that type) passed as an argument.
auto it = std::remove_if(m_bullets.begin(), m_bullets.end(), [](Bullet::Ptr bullet){
// dead bullets need to be removed from the container
if (!bullet->isAlive()) {
// lambda function returns true, thus this element is 'removed'
return true;
}
else{
// in the other case, that the bullet is still alive and we can do
// stuff with it, like rendering and what not.
bullet->render(); // while checking, we do render work at the same time
// then we could either do another check or directly say that we don't
// want the bullet to be removed.
return false;
}
});
// The interesting part is, that all of those objects were not really
// completely removed, as the space of the deleted objects does still
// exist and needs to be removed if you do not want to manually fill it later
// on with any other objects.
// erase dead bullets
m_bullets.erase(it, m_bullets.end());
'remove_if' removes the container where the lambda function returned true and shifts that content to the beginning of the container. The 'it' points to an undefined object that can be considered garbage. Objects from 'it' to m_bullets.end() can be erased, as they occupy memory, but contain garbage, thus the 'erase' method is called on that range.
Solution 8 - C++
I came across same old issue and found below code more understandable which is in a way per above solutions.
std::set<int*>::iterator beginIt = listOfInts.begin();
while(beginIt != listOfInts.end())
{
// Use your member
std::cout<<(*beginIt)<<std::endl;
// delete the object
delete (*beginIt);
// erase item from vector
listOfInts.erase(beginIt );
// re-calculate the begin
beginIt = listOfInts.begin();
}