Don't understand results of std::remove in C++ STL

Question

I was reading Josuttis "The C++ Standard Library, 2nd ed.". In section 6.7.1 author explains that the code given below will give unexpected results. I still don't how std::remove() functions, and why I am getting this strange result. (Though I understood that you need to use std::erase() in order to actually remove elements, and it is actually better to use list::erase() rather than combination of std::remove() & `std::remove()).

list<int> coll;
// insert elements from 6 to 1 and 1 to 6
for (int i=1; i<=6; ++i) {
     coll.push_front(i);
     coll.push_back(i);
}

// print
copy (coll.cbegin(), coll.cend(), // source
      ostream_iterator<int>(cout," ")); // destination
      cout << endl;

// remove all elements with value 3
remove (coll.begin(), coll.end(), // range
        3); // value
// print (same as above)

and the results are

pre:  6 5 4 3 2 1 1 2 3 4 5 6
post: 6 5 4 2 1 1 2 4 5 6 5 6 (???)

@KarolyHorvath, I just added the code ! see the print function — newprint, Sep 26 '13 at 20:37
See the answers here: http://stackoverflow.com/questions/6456870/stl-remove-doesnt-work-as-expected — Jason B, Sep 26 '13 at 20:40
All element with value 3 is overwritten by the following elements. Didn't you see the figure ? — P0W, Sep 26 '13 at 20:40
@newprint Also note that in your case calling `list::remove` is [far better](http://stackoverflow.com/questions/15278108/remove-if-with-boostbind-is-slow/15281230#15281230) than using the erase-remove idiom. — Praetorian, Sep 26 '13 at 20:42
P.S. Improper use of the remove() function is very common phenomenon. This error can see in TortoiseSVN, IPP Samples, Chromium and so on. :) http://www.viva64.com/en/examples/V530/ — , Sep 27 '13 at 05:43

chrisaycock · Accepted Answer · 2013-09-26T20:47:45.270

This explanation should help:

Removing is done by shifting the elements in the range in such a way that elements to be erased are overwritten. Relative order of the elements that remain is preserved and the physical size of the container is unchanged. Iterators pointing to an element between the new logical end and the physical end of the range are still dereferenceable, but the elements themselves have unspecified values. A call to remove is typically followed by a call to a container's erase method, which erases the unspecified values and reduces the physical size of the container to match its new logical size.

Note that the return value from std::remove() is the iterator that represents the new end. Therefore, calling std::erase() on this new end and the old end will free your excess space.

Almost correct - if you call `erase` with only the new end, it will only erase one element. You need to call the two-parameter version, with the new end and the old end. — Mark Ransom, Sep 26 '13 at 20:46

score 4 · Answer 2 · answered Sep 26 '13 at 20:39

std::remove doesn't actually shorten the list. It can't - as it only gets iterators and not the container itself.

What it does is copies the remaining values so that you get them in the beginning of the container. But the final elements of the container (in your case - the last two: '5' and '6') are actually still there..

After using std::remove you have to shorten to container yourself to remove the remaining "junk" copies.

score 3 · Answer 3 · edited Sep 26 '13 at 20:48

To quote from everyone's favorite c++ website:

The function cannot alter the properties of the object containing the range of elements (i.e., it cannot alter the size of an array or a container): The removal is done by replacing the elements that compare equal to val by the next element that does not, and signaling the new size of the shortened range by returning an iterator to the element that should be considered its new past-the-end element.

So std::remove doesn't change the size of the list. It removes the matching elements and returns you an iterator that represents the new end of the list. To actually erase the extraneous elements, you then need to do:

auto it = remove(coll.begin(), coll.end(), 3);
coll.erase(it, coll.end());

score 2 · Answer 4 · answered Sep 26 '13 at 20:39

You asked the algorithm to remove "3" element. So, while enumerating the container the algo shifts the content if something is removed from the middle. Such shift occurs 2 times in your case, this is why you see "5 6" elements at the end (because actual end was moved to 2 items forward). Then, "std::erase" will fix the issue with tail zombies.

Don't understand results of std::remove in C++ STL

4 Answers4