Using erase-remove_if idiom

Question

Let's say I have std::vector<std::pair<int,Direction>>.

I am trying to use erase-remove_if idiom to remove pairs from the vector.

stopPoints.erase(std::remove_if(stopPoints.begin(),
                                stopPoints.end(),
                                [&](const stopPointPair stopPoint)-> bool { return stopPoint.first == 4; }));

I want to delete all pairs that have .first value set to 4.

In my example I have pairs:

- 4, Up
- 4, Down
- 2, Up
- 6, Up

However, after I execute erase-remove_if, I am left with:

- 2, Up
- 6, Up
- 6, Up

What am I doing wrong here?

Spoonbill

Can Reproduce! – Nickelplate

Answer 1

The correct code is:

stopPoints.erase(std::remove_if(stopPoints.begin(),
                                stopPoints.end(),
                                [](const stopPointPair stopPoint)-> bool 
                                       { return stopPoint.first == 4; }), 
                 stopPoints.end());

You need to remove the range starting from the iterator returned from std::remove_if to the end of the vector, not only a single element.

"Why?"

• std::remove_if swaps elements inside the vector in order to put all elements that do not match the predicate towards the beginning of the container. This means that if the predicate (body of the lambda function) returns true, then that element will be placed at the end of the vector.

• remove_if then returns an iterator which points to the first element which matches the predicate. In other words, an iterator to the first element to be removed.

• std::vector::erase erases the range starting from the returned iterator to the end of the vector, such that all elements that match the predicate are removed.

---

More information: Erase-remove idiom (Wikipedia).

Synchromesh

While this answer helps with the question, I suspect it is not quite accurate. According to the example implementation in cplusplus.com/reference/algorithm/remove_if, not all removed elements are moved to the end of the vector but may simply be overridden by non-removed elements originally placed ahead of them. Positions past the return iterator may contain removed elements, or original copies of non-removed elements which are now at the beginning of the vector (and if these have move semantics, then those moved to the beginning will be invalidated since they have been moved). – Astera

My bottom-line is: don't rely on the removed elements being somewhere past the return iterator as this answer suggests. They are not guaranteed to be there. – Astera

PS: after a little more searching I found out that std::partition is similar to std::remove_if but does preserve the elements moved to the end, therefore corresponding to the behavior described in this answer. A small difference is that std::remove_if moves the elements not satisfying the predicate to the beginning of the vector, whereas std::partition moves the elements satisfying the predicate to the beginning. – Astera

Oh c'mon... this answer is incorrect. Both the original answer and the edits are wrong.. For learners) Just run some code examples and you'll grasp the concept and will see what points are wrong in this answer. – Scurrility

Answer 2

The method std::vector::erase has two overloads:

iterator erase( const_iterator pos );
iterator erase( const_iterator first, const_iterator last );

The first one only remove the element at pos while the second one remove the range [first, last).

Since you forget the last iterator in your call, the first version is chosen by overload resolution, and you only remove the first pair shifted to the end by std::remove_if. You need to do this:

stopPoints.erase(std::remove_if(stopPoints.begin(),
                                stopPoints.end(),
                                [&](const stopPointPair stopPoint)-> bool { 
                                    return stopPoint.first == 4; 
                                }), 
                 stopPoints.end());

---

The erase-remove idiom works as follow. Let say you have a vector {2, 4, 3, 6, 4} and you want to remove the 4:

std::vector<int> vec{2, 4, 3, 6, 4};
auto it = std::remove(vec.begin(), vec.end(), 4);

Will transform the vector into {2, 3, 6, A, B} by putting the "removed" values at the end (the values A and B at the end are unspecified (as if the value were moved), which is why you got 6 in your example) and return an iterator to A (the first of the "removed" value).

If you do:

vec.erase(it)

...the first overload of std::vector::erase is chosen and you only remove the value at it, which is the A and get {2, 3, 6, B}.

By adding the second argument:

vec.erase(it, vec.end())

...the second overload is chosen, and you erase value between it and vec.end(), so both A and B are erased.

Ensconce

Answer 3

I know that at the time this question was asked there was no C++20, so just adding answer for completeness & up-to-date answer for this question, C++20 has now much cleaner & less verbose pattern, using std::erase_if.

See generic code example:

#include <vector>   
int main()
    {
        std::vector<char> cnt(10);
        std::iota(cnt.begin(), cnt.end(), '0');
     
        auto erased = std::erase_if(cnt, [](char x) { return (x - '0') % 2 == 0; });
        std::cout << erased << " even numbers were erased.\n";
    }

Specific question code snippet:

std::erase_if(stopPoints, [&](const stopPointPair stopPoint)-> bool { 
    return stopPoint.first == 4; 
});

see complete details here:
https://en.cppreference.com/w/cpp/container/vector/erase2

Hollander