fast deletion from vector with a reverse iterator

Question

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++;

Have a look at the erase-remove idiom. You can make the call to `MyFunc` after remove, and before erase, or you can bake the call to `MyFunc` into the comparator you pass to `remove_if`. — super, May 18 '19 at 08:46
answered [here](https://stackoverflow.com/a/40567406/2754510) — Constantinos Glynos, May 18 '19 at 09:29
Possible duplicate of [Iterating over and removing elements from a Vector. Error:Vector iterator not Incrementable](https://stackoverflow.com/questions/40566108/iterating-over-and-removing-elements-from-a-vector-errorvector-iterator-not-in) — Constantinos Glynos, May 18 '19 at 09:30

score 1 · Answer 1 · answered May 18 '19 at 08:41

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.

I think pop_back() would additionally invalidate rbegin(), and it's the corner case you mention that is surely giving me my crash. — Swiss Frank, May 18 '19 at 09:47

super · Answer 2 · 2019-05-18T14:21:23.917

1

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 { ... }

edited May 18 '19 at 14:21

answered May 18 '19 at 08:58

super

12,335
2
19
29

OK, that feels close! My "blah" is actually a comparison v->blah < x, and I'm getting an error 'x' cannot be implicitly captured because no default capture mode has been specified. And additionally, MyFunc takes a member of this, but compiler warns again "current default capture mode does not allow it." Any pointers? I know what lambda functions are in theory but have almost no experience with them. – Swiss Frank May 18 '19 at 09:44
@SwissFrank You can specify default capture by reference by using [&] instead of [] at the start of the lambda. – super May 18 '19 at 13:46
This code is correct, but the explanation is not quite right. `remove_if` does not "move all the elements to be removed to the end of the container". Instead, it "moves all the elements to be kept to the beginning of the container", and leaves whatever at the end of the container. – Marshall Clow May 18 '19 at 13:49
@MarshallClow That makes sense since it promises to preserve the relative order of the kept elements. Strictly speaking though, I assume that's implementation defined. I'll add a note in the answer. – super May 18 '19 at 14:11

fast deletion from vector with a reverse iterator

2 Answers2