Using erase-remove_if idiom

问题:

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?

回答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 around inside the vector in order to put all elements that do not match the predicate towards the beginning of the container.

  • It then returns the iterator that points to the first predicate-matching element.

  • std::vector::erase needs to erase the range starting from the returned iterator to the end of the vector, in order to remove all elements that match the predicate.

---

More information: Erase-remove idiom (Wikipedia).

回答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.