Erasing elements from a container

The erase-remove idiom is the preferred way to drop elements from vector, deque and string; for list we should call the member function remove(), that implements the erase-remove pattern.

For associative containers we have to pursue a different approach since the remove() algorithm does not work properly here and no remove() member function is available. So, the erase() member function should be used instead.

Here are going to remove all the even numbers from a vector, a list, and a set. First of all we need a function that could be used as predicate for remove_if(), and here it is:

bool even(int value)
{
return value%2 == 0;
}

We initialize a vector in this way:

std::vector<int> v;
v.reserve(10);
for(int i = 0; i < 10; ++i)
v.push_back(i);
dump(v);

And then we eliminate the even elements using the erase-remove (actually, remove_if) idiom:

v.erase(remove_if(v.begin(), v.end(), even), v.end());
dump(v);

Now a list. The job is done by the member remove_if() function:

std::list<int> l;
for(int i = 0; i < 10; ++i)
l.push_back(i);
dump(l);

l.remove_if(even);
dump(l);

Finally the set. The use the member erase(), but we should pay attention not to invalidate the iterator on which we are working. This lead to a piece of code that is a sort of delicate:

std::set<int> s;
for(int i = 0; i < 10; ++i)
s.insert(i);
dump(s);

for(std::set<int>::iterator it = s.begin(); it != s.end(); /* ! */)
{
if(even(*it))
s.erase(it++); // 1.
else
++it; // 2.
}
dump(s);

1. We eliminate an element, so we post-increment the iterator, in this way the invalidated iterator is just a copy used by erase(), we could safely go on looping on it.
2. Nothing to do, we use the more efficent pre-increment operator.

Many more details on this argument in Item 9 of Effective STL, one of the Effective C++ books by Scott Meyers.

No comments:

Post a Comment