More C++ Idioms/Erase-Remove
From Wikibooks, the open-content textbooks collection
Contents |
[edit]
Erase-Remove
[edit] Intent
To eliminate elements from a STL container to reduce the size of it.
[edit] Also Known As
Remove-Erase (based on the order of execution, rather than the typed order on the source code line)
[edit] Motivation
std::remove algorithm does not eliminate elements from the container! It simply quarantines them at the end of the container. This is because std::remove algorithm works only using a pair of forward iterators (Iterator Pair idiom) and 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 internal data structure. Erase-Remove idiom is used to really eliminate data elements from a container.
[edit] Solution and Sample Code
std::remove algorithm returns an iterator to the beginning of the range of "removed" elements. It does not change the end() iterator of the container nor does the size of it. Member erase function can be used to really eliminate the members from the container in the following idiomatic way.
std::vector<int> v; // fill it up somehow v.erase(std::remove(v.begin(), v.end(), 99), v.end()); // 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 and therefore, order of evaluation does not matter.
[edit] Known Uses
[edit] Related Idioms
[edit] References
Effective STL, Item 32 - Scott Meyers
