{"id":744,"date":"2017-11-26T23:04:39","date_gmt":"2017-11-27T07:04:39","guid":{"rendered":"http:\/\/wonghoi.humgar.com\/blog\/?p=744"},"modified":"2021-10-29T00:06:27","modified_gmt":"2021-10-29T08:06:27","slug":"oversimplified-getting-rid-of-data-in-stl-containers","status":"publish","type":"post","link":"https:\/\/wonghoi.humgar.com\/blog\/2017\/11\/26\/oversimplified-getting-rid-of-data-in-stl-containers\/","title":{"rendered":"Oversimplified: Getting rid of data in STL containers"},"content":{"rendered":"\n

Unless deleting a known range of elements directly through iterators (no conditions to match), which range<\/strong>–erase()<\/code> method can be used directly, targeting specific key\/value\/predicate requires understanding of the container’s underlying data structure.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

\n\n\n\n

The words ‘remove<\/em>‘ and ‘erase<\/em>‘ has very specific meaning for STL that are not immediately intuitive.<\/p>\n\n\n\n

 <\/td>Lives in<\/td>Target to match<\/td>Purpose<\/td><\/tr>
remove_?()<\/code><\/td><algorithm><\/code><\/td>required<\/td>Rearrange<\/strong> wanted elements to front<\/td><\/tr>
erase()<\/code><\/td>container<\/td>not accepted<\/td>Blindly<\/strong> deleting range\/position given<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

There is a remove()<\/code> 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.<\/p>\n\n\n\n

The usage is easy to remember once you understand it with the right wording above:<\/p>\n\n\n\n

algorithm + container<\/td>contiguous<\/td>lists<\/td>associative<\/td><\/tr>
remove_?()<\/code>: move front<\/em><\/td>Step 1<\/td>Step 1
<\/del>(Use remove_?()<\/code> method<\/strong>)<\/td>		unordered<\/em>*: cannot rearrange
(Use erase(key)<\/code> directly)<\/td><\/tr>
erase()<\/code>: trim tail<\/em><\/td>Step 2<\/td>Step 2
<\/del>(Use remove_?()<\/code> method<\/strong>)
<\/del><\/td>		Use after find_?()<\/code><\/del>
(Use erase(key)<\/code> directly)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Note that there are two steps for sequential (contiguous+lists) containers , hence the erase-remove idiom<\/a>. It’s really two steps:<\/p>\n\n\n\n

auto tail = remove(c.begin(), c.end(), T); \nc.erase(tail, c.end());<\/pre>\n\n\n\n
but they can be combined in one line since the tail is only useful at one place. Hence<\/p>\n\n\n\n
c.erase( remove(c.begin(), c.end(), T), c.end() ); <\/pre>\n\n\n\n
Lists provides a efficient shortcut method (see table below) since linked-lists does not need to be rearranged (just short the pointers).<\/p>\n\n\n\n
one-shot methods<\/td>contiguous<\/td>lists<\/td>associative<\/td><\/tr>
by content<\/td>N\/A: use erase-remove<\/code> idiom<\/td>remove(T)<\/code><\/td>erase(key)<\/code><\/td><\/tr>
by predicate<\/td>N\/A: use erase-remove_if<\/code> idiom<\/td>remove_if(pred)<\/code><\/td>N\/A: Use for-loops for now
No erase_if() yet as of C++17.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
Never try range-based remove_?()<\/code> for associative containers. It is a data corruption trap if any attempt is made to use anything named remove<\/code> on associative containers.<\/p>\n\n\n\n
The trap used to be possible since <algorithms><\/code> and containers were separate, but newer C++<\/a> protects you from the trap by checking if the element you are moving is of a MoveAssignable<\/em> type. Since associative containers’ keys cannot be modified (without a rescan), the elements are not move-assignable<\/em>.<\/p>\n\n\n\n
\n\n\n\n
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<\/em> uniformly across all<\/strong> containers. This helps to preserve the running iterator that gets invalidated immediately after the erase through i=c.erase(i);<\/code><\/p>\n\n\n\n
\n\n\n\n
* For brevity, I twisted the term unordered<\/em> here to mean that the native (implementation) data order is dependent on the data involved.<\/p>\n\n\n\n
When I said ‘cannot rearrange’, I meant ‘cannot efficiently rearrange’, since there are no cheap O(1) next() or prev() traversal.<\/p>\n\n\n\n
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.<\/p>\n
<\/div>
<\/path><\/svg><\/i> \"Loading\"<\/p>
<\/div>","protected":false},"excerpt":{"rendered":"
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 … Continue reading →<\/span><\/a><\/p>\n
<\/div>\n
<\/path><\/svg><\/i> \"Loading\"<\/p>\n
<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"footnotes":""},"categories":[25,6,29],"tags":[],"class_list":["post-744","post","type-post","status-publish","format-standard","hentry","category-cpp","category-note-to-self","category-programming"],"_links":{"self":[{"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/posts\/744","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/comments?post=744"}],"version-history":[{"count":23,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/posts\/744\/revisions"}],"predecessor-version":[{"id":3004,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/posts\/744\/revisions\/3004"}],"wp:attachment":[{"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/media?parent=744"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/categories?post=744"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/tags?post=744"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}