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