Erase-remove idiom

From Seo Wiki - Search Engine Optimization and Programming Languages

Jump to: navigation, search

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 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[1][4]. 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[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".

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() ); 
}

References

  1. 1.0 1.1 1.2 Meyers, Scott (2001). Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library. Addison-Wesley. 
  2. 2.0 2.1 Sutter, Herb; Alexandrescu, Andrei (2004). C++ Coding Standards: 101 Rules, Guidelines, and Best Practices. Addison-Wesley. 
  3. 3.0 3.1 C/C++ Users Journal, October 2001. STL Algorithms vs. Hand-Written Loops
  4. 4.0 4.1 Josuttis, Nicolai (1999). C++ Standard Library - A Tutorial and Reference. Addison-Wesley. 
  5. ISO/IEC 14882:2003(E): Programming Languages - C++. ISO/IEC. 2003. 
Personal tools

Served in 0.225 secs.