Erase-remove idiom

The remove() standard algorithm doesn't actually remove anything. It just doesn't know how to do it. It works on iterators and it has no access to the underlying container, so what it does it is just manipulating the container and returning an iterator to the new "end" iterator for the container. The elements from "new end" to "old end" are trash, and should be erased for good, using the container specific erase() method.

See what happens if I incorrectly use remove() assuming it works in a "natural" way, and not the actual one (the dump() function is described in a previous post):

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

v[3] = v[5] = v[9] = 99;
dump(v);

remove(v.begin(), v.end(), 99); // !! this is not enough !!
dump(v);

In my environment this is the (unexpected but correct) output:

0 1 2 99 4 99 6 7 8 99
0 1 2 4 6 7 8 7 8 99

As you see, remove() did its job, but we still have to get rid of the trash at the end of the container. And to do that, the best way is calling erase() on the result of remove(), that is an iterator to the "new end", and the iterator to the "current end":

// remove(v.begin(), v.end(), 99); // !! this is not enough !!
v.erase(remove(v.begin(), v.end(), 99), v.end());

It should be clear now why this is called "erase-remove" idiom.

So, the standard remove() algorithm and specialized container method do not actually remove anything. With an exception: the list::remove() method that does actually eliminates the element.
So, in this specific case, we use it in this way:

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

l.remove(7); // !! this works correctly !!
dump(l);

I often re-read the Effective C++ books by Scott Meyers. This post has been written while pondering on Item 32 of Effective STL.