0

Can any one explain the following behavior of the std::remove algorithm ( which I find to be pretty unusual) :

here's a little program to demonstrate the issue

std::vector<int> Vec;

Vec.push_back(3);
Vec.push_back(7);
Vec.push_back(9);
Vec.push_back(6);
Vec.push_back(1);
Vec.push_back(6);
Vec.push_back(2);

std::vector<int>::iterator iter;

std::remove(Vec.begin(), Vec.end(), 6);

for (int i : Vec)
{
    std::cout << i;
}

now this is an excrept from http://www.cplusplus.com/reference/algorithm/remove/

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

elementS, as in plural.

now, I understand what the basic idea is - I'm not asking you to explain that. The algorithm should find all elements for which the comparison with the value passed as the third argument equals true, put them all into the back of the container and return an iterator to the new logical end of the container - the start of the sequence where the "removed" elements have been placed. As far as I understand, the next time you iterate through the container, the elements in that sequence should be ignored.

What I don't understand is, how then, the program I used here as an example has the following output:

3 7 9 1 2 6 2

Even more peculiar to me is the fact that if you add another entry with a value other than 6 between the 2nd 6 and the 2 at the end, the output no longer contains a 6.

Now, I am aware of the member erase/std::remove combo you can use to remove multiple elements from a range. I tried it on this code and (to my surprise, given the context) it produces the results you'd expect it to.

So, I'm not asking for a way to to remove multiple occurences of the same value from a container, I'm asking if anyone can explain just what in the world is going under the hood of this algorithm?

DForck42
  • 19,789
  • 13
  • 59
  • 84
fishyperil
  • 35
  • 6
  • 2
    `std::remove` alone does actually not remove anything from the container, [here](http://en.cppreference.com/w/cpp/algorithm/remove) you can see possible implementations, maybe this helps to understand – 463035818_is_not_an_ai Feb 16 '18 at 17:00
  • 1
    On a side note, a cppreference.com is a better reference than cplusplus.com. – Arnav Borborah Feb 16 '18 at 17:01
  • 1
    Not sure I understand your question. You tell us *"Now, I am aware of the member erase/std::remove combo you can use to remove multiple elements from a range.*", yet it seems that you expect the vector itself to have changed its size via `std::remove` alone. – Christian Hackl Feb 16 '18 at 17:04
  • 1
    The small example is nice ! It'd be even nicer if we didn't have to add the main and the #include directives though, but I may be nitpicking here ( https://ideone.com/vpSFL5 ). Otherwise, the answer was actually hidden in the link you gave `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 [...]` – Caninonos Feb 16 '18 at 17:05
  • By the way, http://en.cppreference.com/w/cpp/algorithm/remove has a possible example implementation of the algorithm. You can also look into the header files that come with your compiler to see what the algorithm does with your compiler, or just use your debugger. – Christian Hackl Feb 16 '18 at 17:05
  • I wasn't expecting it to have changed its size, I'm just asking why the second occurence of the value 6 wasn't moved to the section past the new logical end. – fishyperil Feb 16 '18 at 17:08
  • 1
    @fishyperil: But it was moved past the new logical end. It's no longer in [ begin, new_end ]. – Christian Hackl Feb 16 '18 at 17:09
  • @fishyperil The value of the removed elements is unspecified. The algorithm is implementation specific. You would observe [different results](http://coliru.stacked-crooked.com/a/8a311091c1a5a39c) were you on GCC and not Visual C++. – Ron Feb 16 '18 at 17:12
  • maybe I'm misunderstanding the concept of the logical end here or something - what I thought is that if you had a container with 7 values like in the example, and you use the std::remove on one of them, that value gets moved past the seventh one and the algorithm returns the iterator after the 7th(logical end) and the sequence of removed values follows after it – fishyperil Feb 16 '18 at 17:15
  • 1
    @Ron I think you're the only one here that actually understood my question, but oddly enough, the link you provided as an example still produces the same result – fishyperil Feb 16 '18 at 17:20
  • @fishyperil Yes, my bad, the results are the same in cl and gcc. Just use the erase/remove idiom and don't worry too much about the `std::remove` implementation. The last two digits are unspecified values. – Ron Feb 16 '18 at 17:23
  • `remove()` doesn't actually remove anything, it just shuffles the unwanted stuff to the end. To actually get rid of the elements you need to subsequently `erase()` from the new logical end to the *actual* end. Then the elements will be gone. This is commonly known as the "erase remove idiom". – Jesper Juhl Feb 16 '18 at 17:50

0 Answers0