Strange behavior with vector :: erase and std :: remove_if with a finite range other than vector.end ()

Question

I need to remove elements from the middle of 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 that, I would expect the vector ints have: [1, 2, 3, 5, 6].

In the Visual studio 2008 debugger, after the line std::remove_if elements ints changed, I assume that I am entering some kind of undefined behavior here.

So how to remove elements from a vector range?

Answer 1

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

This is what happens. Your entry in remove_if :

 1 2 3 4 5 6 ^ ^ begin end 

And the remove_if algorithm remove_if through all the numbers between begin and end (including begin , but excluding end ), and removes all the elements between them that match your predicate. So after remove_if is executed, your vector is as follows

 1 2 3 ? 5 6 ^ ^ begin new_end 

Where ? is a value that I do not consider deterministic, although if it is guaranteed, it will be 4 . And new_end , which points to the new end of the input sequence you gave it, with matching elements removed, is what std::remove_if . Note that std::remove_if doesn't touch anything beyond the subsequence you gave it. This may be of greater importance in a more extended example.

Say this is your input:

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

After std::remove_if you will get:

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

Think about it for a moment. What he did is remove 4 and 6 from the subsequence, and then slide everything inside the subsequence down to fill in the deleted elements, and then move the end iterator to the new end of the same subsequence. The goal is to satisfy the requirement that the sequence ( begin , new_end ] that it produces matches the subsequence ( begin , end ] that you passed, but with some deleted elements. Or outside the end that you passed, remains untouched.

What you want to get rid of this is all between the returned final iterator and the original final iterator that you gave it. ? these values ? "trash". So your removal request should be:

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

The erase call that you just deleted because of the end of the subsequence that you performed the removal that you do not want here.

What complicates this is that the remove_if algorithm does not actually call erase() on the vector or does not change the size of the vector at any point. It simply moves the elements around and leaves some garbage items after the end of the subsequence that you asked to process. This seems silly, but the whole reason STL does it this way is to avoid the problem with invalid iterators that grew doublep (and be able to run on things that are not STL containers, such as raw arrays).

Answer 2

Erasing elements in std::vector cancels the iterators behind the deleted element, so you cannot use "alien" functions that accept ranges. You have to do it differently.

EDIT:

In general, you can use the fact that erasing one element “shifts” all elements in subsequent positions back. Something like that:

 for (size_t scan = 2, end = 4; scan != end; ) { if (/* some predicate on ints[scan] */) { ints.erase (ints.begin () + scan); --end; } else ++scan; } 

Note that std::vector not suitable for erasing elements in the middle. You should think about something else ( std::list ?) If you do this often.

EDIT 2:

As explained in the comments, the first paragraph is not true. In this case, std::remove_if should be more efficient than what I suggested in the first edit, so ignore this answer. (Keeping it for comments.)

Answer 3

The behavior is not strange - you delete the wrong range. std::remove_if moves the elements that it "removes" to the end of the input range. In this case, you will need to do the following:

 ints.erase(it, ints.begin() + 4 /* your end of range */); 

From C ++ in a nutshell:

The remove_if function template "removes" elements for which pred returns false from the range [first, last]. The return value passed the new end of the range. The relative order of items that are not removed is stable.

Nothing is actually erased from the base container; instead, items are assigned new positions to the right so that they overwrite items for which pred returns false. See Figure 13-13 (under remove_copy) for an example of the removal process.