Weird behaviour with vector::erase and std::remove_if with end range different from vector.end()

c++, stl

Solution

Edit: Sorry, the original version of this was incorrect. Fixed.

Here's what's going on. Your input to `remove_if` is:

1  2  3  4  5  6
      ^     ^
    begin  end

And the `remove_if` algorithm looks at all numbers between `begin` and `end` (including `begin`, but excluding `end`), and removes all elements between that match your predicate. So after `remove_if` runs, your vector looks like this

1  2  3  ?  5  6
      ^  ^
  begin  new_end

Where `?` is a value that I don't think is deterministic, although if it's guaranteed to be anything it would be `4`. And `new_end`, which points to the new end of the input sequence you gave it, with the matching elements now removed, is what is returned by `std::remove_if`. Note that `std::remove_if` doesn't touch anything beyond the subsequence that you gave it. This might make more sense with a more extended example.

Say that this is your input:

1  2  3  4  5  6  7  8  9  10
      ^              ^
    begin           end

After `std::remove_if`, you get:

1  2  3  5  7  ?  ?  8  9  10
      ^        ^
    begin      new_end

Think about this for a moment. What it has done is remove the 4 and the 6 from the subsequence, and then shift everything within the subsequence down to fill in the removed elements, and then moved the `end` iterator to the new end of the same subsequence. The goal is to satisfy the requirement that the (`begin`, `new_end`] sequence that it produces is the same as the (`begin`, `end`] subsequence that you passed in, but with certain elements removed. Anything at or beyond the `end` that you passed in is left untouched.

What you want to get rid of, then, is everything between the end iterator that was returned, and the original end iterator that you gave it. These are the `?` "garbage" values. So your erase call should actually be:

ints.erase(it, ints.begin()+4);

The call to `erase` that you have just erases everything beyond the end of the subsequence that you performed the removal on, which isn't what you want here.

What makes this complicated is that the `remove_if` algorithm doesn't actually call `erase()` on the vector, or change the size of the vector at any point. It just shifts elements around and leaves some "garbage" elements after the end of the subsequence that you asked it to process. This seems silly, but the whole reason that the STL does it this way is to avoid the problem with invalidated iterators that doublep brought up (and to be able to run on things that aren't STL containers, like raw arrays).

Problem

I need to remove elements from the middle of a std::vector. So I tried: ``` struct IsEven { bool operator()(int ele) { return ele % 2 == 0; } }; int elements[] = {1, 2, 3, 4, 5, 6}; std::vector<int> ints(elements, elements+6); std::vector<int>::iterator it = std::remove_if(ints.begin() + 2, ints.begin() + 4, IsEven()); ints.erase(it, ints.end()); ``` After this I would expect that the `ints` vector have: [1, 2, 3, 5, 6]. In the debugger of Visual studio 2008, after the `std::remove_if` line, the elements of `ints` are modified, I'm guessing I'm into some sort of undefined behaviour here. So, how do I remove elements from a Range of a vector?

Original source