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?

Answer 1

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.

Answer 2

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