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|
||required||Rearrange wanted elements to front|
||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|
||unordered*: cannot rearrange
Note that there are two steps for sequential (contiguous+lists) containers , hence the erase-remove idiom. e.g.
auto tail = remove(c.begin(), c.end(), T); c.erase(tail, c.end);. Lists provides a efficient shortcut method (see table below) since linked-lists does not need to be rearranged (just short the pointers).
|by content||N/A: use
|by predicate||N/A: use
||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
* 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.
895 total views, 1 views today