{"id":1056,"date":"2015-03-08T23:53:59","date_gmt":"2015-03-09T06:53:59","guid":{"rendered":"http:\/\/www.elbeno.com\/blog\/?p=1056"},"modified":"2015-06-30T21:16:23","modified_gmt":"2015-07-01T04:16:23","slug":"a-persistent-myth-about-stls-remove-and-friends","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/blog\/?p=1056","title":{"rendered":"A persistent myth about STL’s remove (and friends)"},"content":{"rendered":"

There seems to be a persistent myth about STL’s remove<\/code>, remove_if<\/code>, etc.
\nAsk even a relatively experienced C++ programmer to explain this code.<\/p>\n

\r\nvector v = { 1,2,3,4,5 };\r\nv.erase(remove_if(v.begin(), v.end(),\r\n                  [] (int i) { return (i & 1) == 0; }),\r\n        v.end());\r\n<\/pre>\n
They’ll recognize the erase-remove idiom<\/a> and correctly say that it’s removing even numbers from the vector<\/code> so that what’s left is { 1,3,5 }<\/code>. So then you ask them how it works, and likely as not, they say something like:<\/p>\n
“The remove_if<\/code> moves all the elements you want to remove to the end, then the erase<\/code> gets rid of them.”<\/p>\n
This isn’t what remove_if<\/code> does.<\/strong> (And likewise, the other remove*<\/code> algorithms.) If it did that – which is more<\/em> work than it does – it would in fact be partition<\/code>. What remove<\/code> does is move the elements that won’t<\/strong> be removed to the beginning<\/strong>. A suitable implementation of remove_if<\/code>, which you can see in the libc++ source<\/a>, is:<\/p>\n
\r\ntemplate \r\n_ForwardIterator\r\nremove_if(_ForwardIterator __first, _ForwardIterator __last, \r\n          _Predicate __pred)\r\n{\r\n    __first = _VSTD::find_if<\r\n        _ForwardIterator, \r\n        typename add_lvalue_reference<_Predicate>::type>\r\n            (__first, __last, __pred);\r\n    if (__first != __last)\r\n    {\r\n        _ForwardIterator __i = __first;\r\n        while (++__i != __last)\r\n        {\r\n            if (!__pred(*__i))\r\n            {\r\n                *__first = _VSTD::move(*__i);\r\n                ++__first;\r\n            }\r\n        }\r\n    }\r\n    return __first;\r\n}\r\n<\/pre>\n
The elements that got removed just got overwritten. They didn’t get moved to the end. After the call to remove_if<\/code> (before the erase<\/code> call), the vector<\/code> was { 1,3,5,4,5 }<\/code>. <\/p>\n
This means that remove<\/code> can potentially invalidate invariants, e.g. if we expect the sequence to contain unique values (the erase<\/code> restores the invariant, so erase-remove should always be paired in this case). And if this had been a container of pointers, in all likelihood, memory would have been leaked. Hence item 33 in Effective STL<\/a><\/em>, “Be wary of remove<\/em>-like algorithms on containers of pointers”.<\/p>\n
So remember, remove<\/code> doesn’t move things to the end<\/strong>. Next time you hear that, congratulate the programmer saying it – they’re one of today’s lucky 10,000<\/a>!<\/p>\n","protected":false},"excerpt":{"rendered":"
There seems to be a persistent myth about STL’s remove, remove_if, etc. Ask even a relatively experienced C++ programmer to explain this code. vector v = { 1,2,3,4,5 }; v.erase(remove_if(v.begin(), v.end(), [] (int i) { return (i & 1) == 0; }), v.end()); They’ll recognize the erase-remove idiom and correctly…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[22,8],"tags":[],"class_list":["post-1056","post","type-post","status-publish","format-standard","hentry","category-cpp","category-programming"],"_links":{"self":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1056","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1056"}],"version-history":[{"count":10,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1056\/revisions"}],"predecessor-version":[{"id":1066,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1056\/revisions\/1066"}],"wp:attachment":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1056"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1056"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1056"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}