std::remove doesn't behave as expected

Question

While I was debugging, I figured out that std::remove doesn't behave as I expected. For example:

std::vector<int> nums {0,1,2,2,3,0,4,2};
int val{2};
std::remove(nums.begin(), nums.end(), val);

nums vector changes to [0, 1, 3, 0, 4, 0, 4, 2]. Where does that extra 0 and 4 come from? I would expect [0, 1, 3, 0, 4, 2, 2, 2].

Another example:

std::vector<int> nums {3,2,2,3};
int val{3};
std::remove(nums.begin(), nums.end(), val);

nums vector changes to [2, 2, 2, 3]. One 3 has been changed to 2 somehow. Could you explain this behavior?

Answer 1

remove does not state that the elements past (and including) its return ending iterator will have any particular value. It does not necessarily swap anything to those values. It is perfectly legal for them to be untouched or to contain undefined values or whatever.

You should not be looking at the elements past the returned ending iterator. The only elements that matter are those on the half-open range of begin to the returned iterator.

Answer 2

Where does that extra 0 and 4 come from?

They come from you. (So does the 2 after them.) All std::remove does is shift elements. It does not swap elements; it must use move-assignment (which is the same as copy-assignment for int).

Before: {0,1,2,2,3,0,4,2}
                 | | |
             ----- | |
             | ----- | (assignment, not swaps)
             | | -----
             | | |
             V V V
After:  {0,1,3,0,4,0,4,2}
         ^^^       ^^^^^ -- unchanged

Since the integers after the new "last" element (the shifted 4) are expected to be erased, there is no need to waste CPU cycles changing their values. (If you were dealing with something more complex than int, there might be an efficiency gain from moving values rather than copying them; in that case the values would change to something "valid but unspecified" -- i.e. the "moved-from" state. Still not a swap.)

Similarly:

Before: {3,2,2,3}
           | |
         --- |
         | ---
         | |
         V V
After:  {2,2,2,3}
             ^^^ -- unchanged

---

See also STL remove doesn't work as expected? which is about the same phenomenon, but from a different flawed expectation. (As I understand the current guidelines, since the question is from a different perspective, it should not be treated as a duplicate.)

See also possible implementation @ cppreference.com. The algorithm is fairly simple. Iterate over the container. When a to-be-removed element is found, do nothing. Otherwise, assign that value to the first element that has not yet been assigned something. After iterating, return an iterator to the first element that has not yet been assigned something. There is no cleanup attempted for the elements not assigned something. The values there are just whatever was left after assigning from (or skipping) them.