How to erase specific elements from an STL container - the C++ way.

STL iterators are tricky little fellows. One moment they act clean and the very next, they throw their hands up and say something cryptic. Consider this snippet that erases all elements whose values are 20 from a vector of integers.

typedef std::vector<int> IntVectorType;
IntVectorType vInt;

for(IntVectorType::const_iterator iter = vInt.begin();
iter != vInt.end(); ++iter)
{
 if( *iter == 20 )
 {
     vInt.erase(iter);
 }
}

Lo and behold! The program crashes! This is because when you erase an element from a container all iterators to its position are invalidated. This just happens to be our loop iterator. So, what is an innocent programmer to do?

Well, there are two ways to erase individual elements in an STL container.

Method 1: The crude way ( recommended for cavemen/barbarians/C -programmers ;) )

IntVectorType::iterator iter = vInt.begin();
while(iter != vInt.end())
{
 if( *iter == 20 )
 {
     iter = vInt.erase(iter);  // Get iterator to next element.
 }
 else
 {
     ++iter;  // Increment if not erased.
 }
}

The method vector::erase() returns an iterator to the element that subsequently follows the last element that was erased. So, we just use that iterator to continue looping. Good! Problem solved! Is there a better way?

Method 2: The modern C++ way (recommended for rockstars/you/me)

struct EraseFromVector
{
    // Functor
    bool operator ()(const int value) const
    {
        return (value == 20);       
    }
};

vInt.erase(std::remove_if(vInt.begin(), vInt.end(), EraseFromVector()), vInt.end());

Looks like g(r)eek, you say? Alright then, let me explain. Basically, std::remove_if() is a magical chap. He takes two iterators as a range within which to work. For each element within that range, he then checks the unary predicate(our third argument) to see whether the element should be removed or not. If the predicate returns true, the element is removed.

I did say "removed" but in actuality, remove_if() sends the doomed elements to the back of the container. He doesn't actually remove them. How could he? He doesn't know what kind of container he's working with. Only the container can remove elements.

The nice thing about remove_if() is that he is guaranteed by the standard to preserve the order of the elements that were not removed. So, if our vector contained the elements 10, 20, 30, 20, 40 in that order, it will now contain the elements 10, 30, 40, 20, 20.

Finally, remove_if() returns an iterator to the start of the sequence containing all those miserable elements just sitting there at the back waiting for the axe to fall. We pass this iterator as the first argument to vector::erase() and an iterator to the end of the vector as the second argument. In one full swoop, all elements in the range are erased.

Now, doesn't this seem a lot more fun than a boring old while loop? :)