Erase–remove idiom

From Wikipedia, the free encyclopedia
  (Redirected from Erase-remove idiom)
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[edit]

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]

erase can be used to delete an element from a collection, but for containers which are based on an array, such as vector, all elements after the deleted element have to be moved forward, to avoid "gaps" in the collection. Calling erase multiple times on the same container generates lots of overhead of moving the elements.

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]

These algorithms do not remove elements from the container, but move all elements which don't fit the remove criteria to the front of the range, keeping the relative order of the elements. This is done in a single pass through the data range. After the first element that should be removed, all elements are moved forward by one element, after the second element to be removed, all elements are moved forward by two elements and so forth.

As no elements are actually removed and the container has still the same size, there is a number of elements equal to the number of "removed" items left in the back of the range, having a valid but unspecified state. remove returns an iterator pointing to the first of these elements, so they can be deleted using a single call to erase.

Doing the same using only erase would result in as many passes as there are elements to remove. In each of that passes, all elements after the erased element would be moved by only one element forward.

Limitation[edit]

The erase–remove idiom cannot be used for containers that return const_iterator (e.g.: set)[5]

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[edit]

// 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[edit]

  1. ^ a b c Meyers, Scott (2001). Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library. Addison-Wesley. 
  2. ^ a b Sutter, Herb; Alexandrescu, Andrei (2004). C++ Coding Standards: 101 Rules, Guidelines, and Best Practices. Addison-Wesley. 
  3. ^ a b 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. ^ "Erase–remove idiom with std::set". Retrieved 14 April 2013.