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.^[1][2][3]

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.^[1][2][3]

The algorithm 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.^[1][4] Thus, no elements are actually removed from the container. Rather, all elements which don't fit the remove criteria are brought together to the front of the range, in the same relative order. The remaining elements are left in a valid, but unspecified, state. When this is done, remove returns an iterator pointing one element past the last unremoved element.^[4][5]

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

Limitation

Erase–remove idiom cannot be used for containers that return const_iterator (e.g.: set)^[6]

std::remove and std::remove_if do not maintain elements that are removed (unlike std::partition, std::stable_partition). Thus, erase–remove can only be used with containers holding elements with full value semantics without incurring resource leaks.

Example

// Use g++ -std=c++11 or clang++ -std=c++11 to compile.

#include <vector> // the general-purpose vector container
#include <iostream>
#include <algorithm> // remove and remove_if
 
bool is_odd(int i)
{
  return (i % 2) != 0;  
}

void print(const std::vector<int> &vec)
{
  for (const auto& i: vec) 
    std::cout << i << ' '; 
  std::cout << std::endl;
}
 
int main()
{
  // initialises a vector that holds the numbers from 0-9.
  std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  print(v);
 
  // removes all elements with the value 5
  v.erase( std::remove( v.begin(), v.end(), 5 ), v.end() ); 
  print(v); 
  
  // removes all odd numbers
  v.erase( std::remove_if(v.begin(), v.end(), is_odd), v.end() );
  print(v);

  return 0;  
}

/*
Output:
0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 6 7 8 9 
0 2 4 6 8 
*/

References

1. Meyers, Scott (2001). Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library. Addison-Wesley.
2. Sutter, Herb; Alexandrescu, Andrei (2004). C++ Coding Standards: 101 Rules, Guidelines, and Best Practices. Addison-Wesley.
3. C/C++ Users Journal, October 2001. STL Algorithms vs. Hand-Written Loops
4. Josuttis, Nicolai (1999). C++ Standard Library – A Tutorial and Reference. Addison-Wesley.
5. ISO/IEC 14882:2003(E): Programming Languages – C++. ISO/IEC. 2003.
6. "Erase–remove idiom with std::set". Retrieved 14 April 2013.