Oversimplified: Getting rid of data in STL containers Summary of Item 9 in "Effective STL"

Unless deleting a known range of elements directly through iterators (no conditions to match), which rangeerase() 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 Step 1
(Use remove_?() method)
unordered*: cannot rearrange
(Use erase(key) directly)
erase(): trim tail Step 2 Step 2
(Use remove_?() method)
Use after find_?()
(Use erase(key) directly)

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).

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.

40 total views, 0 views today