Remove while iterating std::vector (indirectly)

Question

This question has been asked multiple times but mine is a slightly different case. Say I have a std::vector of observers which I notify when a certain event happens:

void SomeClass::doThing() {
    // do things ...
    // notify observers
    for (auto* o : mObservers) {
        o->thingHappened();
    }
}

What if in the implementation of thingHappened the observer calls a method in SomeClass to remove itself from the observers? What are some of the best ways to handle this?

One possibility is to make a copy of mObservers before the for loop and use it instead, but the extra copy can be wasteful.

Another possibility is to delegate changes to the array to be run after the loop is finished, perhaps setting a lock (just a boolean) before the loop starts and while this lock is set, the methods that mutate the vector delegate themselves to be called after the loop is done when lock is set to false (could be done with a vector of lambdas... quite cumbersome).

Answer 1

If you have control over the signature of thingHappened(), you can change it to return a bool indicating whether it should be removed. Then, you can remove all the values which return true (or false; depends on the semantics you want).

Luckily for us, std::remove_if and std::partition are guaranteed to call the predicate exactly once per object in the range.

void SomeClass::doThing() {
    // do things ...
    // notify observers
    auto newEnd = std::remove_if(mObservers.begin(), mObservers.end(), [](auto *o) {
        return o->thingHappened();
    });
    // assuming mObservers is a vector
    mObservers.erase(newEnd, mObservers.end());
}

Answer 2

One way to work around this is to change the data structure. With a std::list the removal of a element only invalidates iterators/references/pointers to that element. Since the rest of the list remains intact all we need to do is get an iterator to the next element before we process the current one. That would look like

for (auto it = the_list.begin(); it != the_list.end();)
{
    auto next = std::next(it);
    it->call_the_possibly_removing_function();
    it = next;
}