Erase-remove idiom

The erase-remove idiom is a common C++ technique to eliminate elements that fulfill a certain criterion from a C++ Standard Library container.

Motivation

A common programming task is to remove all elements that have a certain value or fulfill a certain criterion from a collection. In C++, this could be achieved using a hand-written loop. It is, however, preferred to use an algorithm from the C++ Standard Library for such tasks.

The algorithms library provides the remove and remove_if algorithms for this. Because these algorithms operate on a range of elements denoted by two forward iterators, they have no knowledge of the underlying container or collection. Thus, the elements are not actually removed from the range, merely moved to the end. When all the removed elements are at the end of the range, remove returns an iterator pointing one past the last unremoved element.

To actually eliminate elements from the container, remove is combined with the container's erase member function, hence the name "erase-remove idiom".

Sample Code

#include <vector> // the general-purpose vector container
#include <algorithm> // remove and remove_if

bool is_odd(int i) // unary predicate returning true iff the argument is odd
{
  return i % 2;  
}
bool is_even(int i) // unary predicate returning true iff the argument is even
{
  return !is_odd(i);
}

int main()
{
  using namespace std;
  int elements[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  // create a vector that holds the numbers from 0-9.
  vector<int> v(elements, elements + 10); 
 
  // use the erase-remove idiom to remove all elements with the value 5
  v.erase(remove(v.begin(), v.end(), 5), v.end()); 
  
  // use the erase-remove idiom to remove all odd numbers
  v.erase( remove_if(v.begin(), v.end(), is_odd), v.end() );
  
  // use the erase-remove idiom to remove all even numbers
  v.erase( remove_if(v.begin(), v.end(), is_even), v.end() ); 
}