Unless deleting a known range of elements directly through iterators (no conditions to match), which range–erase() method can be used directly, targeting specific key/value/predicate requires understanding of the container’s underlying data structure.
I’d like to give a summary of Item#9 in “Effective STL” by defining the names and concepts so the complicated rules can be sensibly deduced by a few basic facts.
The words ‘remove‘ and ‘erase‘ has very specific meaning for STL that are not immediately intuitive.
| Lives in | Target to match | Purpose | |
remove_?() | <algorithm> | required | Rearrange wanted elements to front |
erase() | container | not accepted | Blindly deleting range/position given |
There is a remove() method for lists, which is an old STL naming inconsistency (they should have called it erase() like for associative containers). Treat it as a historical mistake.
The usage is easy to remember once you understand it with the right wording above:
| algorithm + container | contiguous | lists | associative |
remove_?(): move front | Step 1 | remove_?() method) | unordered*: cannot rearrange (Use erase(key) directly) |
erase(): trim tail | Step 2 | remove_?() method) | find_?()(Use erase(key) directly) |
Note that there are two steps for sequential (contiguous+lists) containers , hence the erase-remove idiom. It’s really two steps:
auto tail = remove(c.begin(), c.end(), T); c.erase(tail, c.end());
but they can be combined in one line since the tail is only useful at one place. Hence
c.erase( remove(c.begin(), c.end(), T), c.end() );
Lists provides a efficient shortcut method (see table below) since linked-lists does not need to be rearranged (just short the pointers).
| one-shot methods | contiguous | lists | associative |
| by content | N/A: use erase-remove idiom | remove(T) | erase(key) |
| by predicate | N/A: use erase-remove_if idiom | remove_if(pred) | N/A: Use for-loops for now No erase_if() yet as of C++17. |
Never try range-based remove_?() for associative containers. It is a data corruption trap if any attempt is made to use anything named remove on associative containers.
The trap used to be possible since <algorithms> and containers were separate, but newer C++ protects you from the trap by checking if the element you are moving is of a MoveAssignable type. Since associative containers’ keys cannot be modified (without a rescan), the elements are not move-assignable.
As for erasing through for-loops (necessary if you want to sneak in an extra step while iterating), C++11 now returns an iterator following the last erased element uniformly across all containers. This helps to preserve the running iterator that gets invalidated immediately after the erase through i=c.erase(i);
* For brevity, I twisted the term unordered here to mean that the native (implementation) data order is dependent on the data involved.
When I said ‘cannot rearrange’, I meant ‘cannot efficiently rearrange’, since there are no cheap O(1) next() or prev() traversal.
It’s a mess to simply copy one element over another (during rearrangement), leaving orphans there, and re-balance a BST or re-hash a hash-map. Nobody wants to go through such pains to remove element when there are tons of more direct ways out there.
