More C++ Idioms/Erase-Remove

Erase-Remove

Intent

To eliminate elements from a STL container to reduce the size of it.

Also Known As

Remove-Erase (based on the order of execution, rather than the typed order on the source code line)

Motivation

The std::remove algorithm does not eliminate elements from a container; it simply moves the elements not being removed to the front of the container, leaving the contents at the end of the container undefined. This is because std::remove works only using a pair of forward iterators (Iterator Pair idiom), and the generic concept of forward iterators does not know how to eliminate data elements from an arbitrary data structure. Only container member functions can eliminate container elements, as only members know the details of the internal data structure. The Erase-Remove idiom is used to remove and eliminate data elements from a container.

Solution and Sample Code

The std::remove algorithm returns an iterator to the beginning of the range of "unused" elements. It does not change the end() iterator of the container, nor does it change the container's size. The erase() member function can be used to really eliminate the members from the container in the following idiomatic way.

template<typename T>
inline void remove(std::vector<T> & v, const T & item)
{
    // Be careful: if you omit the v.end() parameter to v.erase, the
    // code will compile but only a single item will be removed.
    v.erase(std::remove(v.begin(), v.end(), item), v.end());
}


std::vector<int> v;
// Fill it up somehow
remove(v, 99); // Really remove all elements with value 99

The order of evaluation of v.end() and invocation of std::remove is unimportant here because std::remove algorithm does not change end() iterator in any way.

Known Uses

http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/reference/algorithms/new/remove_erase.html

References

Effective STL, Item 32 - Scott Meyers