I want to delete vector entries that meet some condition, after calling a function on them. I don't care about stable ordering, so I'd normally, in effect, move the final array element to replace the one I'm examining.

Question: what is the slickest idiom for doing this with iterators?

(Yes, erase-remove is the standard idiom if you want to preserve ordering, but in my case it's not needed and I think will be slower, thanks to those moves, than my version given here.)

With an int subscript I'd do it thusly, and this code works:

  for ( int i = (int) apc.size() - 1; i >= 0; i-- )
      if ( apc[i]->blah ) {
          MyFunc( apc[i] );
          apc[i] = apc.back();
          apc.pop_back();
      }

I try the same with a reverse iterator and it blows up in the ++ of the for loop after it's gone into the if block the first time. I can't figure out why. If were actually calling erase() on *it I know that would render it undefined, but I'm not doing that. I suppose that pop_back() would undefine rbegin(). I should check if it is going into the if block on first iteration and if it only crashes in that situation.

  for ( auto it = apc.rbegin(); it != apc.rend(); it++ )
      if ( (*it)->blah ) {
          MyFunc( *it );
          *it = apc.back();
          apc.pop_back();
      }

With forward iterator it seems to work, though I dislike the stutter effect of having the loop stop when it's finding elements with blah true. A reverse loop is a little ugly, but at least its a real loop, not this centaur-like half-loop-half-while concoction:

  for ( auto it = apc.begin(); it != apc.end(); )
      if ( (*it)->blah ) {
          MyFunc( *it );
          *it = apc.back();
          apc.pop_back();
      } else
          it++;

2 Answers

1
Serge Ballesta On

pop_back should normally only invalidate back() and end(). But you can be caught by a corner case if the last element of the array has to be deleted. With indices, no problem, you try to move an element on itself which should be a no-op and proceed on previous index. But with iterators, the current value is back() so it should be invalidated.

Beware, it may also be a problem in your implementation so it could make sense to provide that information so that others could try to reproduce with this or other implementations.

1
super On

I think the old and tested erase-remove idiom covers this nicely.

apc.erase(std::remove_if(apc.begin(), apc.end(), [](auto& v) {
    if (v->blah) {
        MyFunc(v);
        return true;
    }
    return false;
}), apc.end());

This idiom moves all the elements to be removed to the end of the container by std::remove_if, and then we remove all of them in one go with erase.

Edit: As pointed out by Marshall, the algorithm will move the elements to be kept to the front, which makes sense considering that it promises to preserve the relative ordering of the kept elements.

If the lambda needs to act on this or any variable other then the passed in v it needs to be captured. In this case we don't need to worry about lifetime, so a default capture by reference is a good choice.

[&](auto& v) {
    if (v->blah < x) { //captures x by reference
        MyFunc(v, member_variable); //current object is captured by reference, and can access member variables
        return true;
    }
    return false;
})

If MyFunc potentially could modify member_variable we additionally need to make the lambda mutable.

By default the lambda creates a function object with a operator() const but mutable removes the const.

[&](auto& v) mutable { ... }