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

R Sahu's answer provides a flexible technique for solving this problem. The one thing that concerns me about it is the introduction of several variables that you have to manage. However, it's totally possible to wrap the functionality in a utility class.

Here's a sketch of what you could do:

#include <functional>
#include <utility>
#include <vector>

// Note that this is not threadsafe
template <typename Type>
class MutableLock {
    bool locked = false;
    Type value;
    // std::function gives us a more general action,
    // but it does come at a cost; you might want to consider using
    // other techniques.
    std::vector<std::function<void(Type&)>> actions;

public:
    class AutoLocker {
        MutableLock& lock;

        friend class MutableLock<Type>;

        explicit AutoLocker(MutableLock& lock)
            : lock{ lock }
        {
        }

    public:
        ~AutoLocker()
        {
            lock.unlock();
        }
    };

    MutableLock() = default;

    // The [[nodiscard]] is a C++17 attribute that
    // would help enforce using this function appropriately
    [[nodiscard]] AutoLocker lock()
    {
        locked = true;
        return AutoLocker{ *this };
    }

    void unlock()
    {
        for (auto const& action : actions) {
            action(value);
        }
        actions.clear();

        locked = false;
    }

    template <typename F>
    void action(F&& f)
    {
        if (!locked) {
            f(value);
        } else {
            actions.emplace_back(std::forward<F>(f));
        }
    }

    // There needs to be some way to expose the value
    // not under the lock (so that we can use it when
    // we call `lock()`).
    //
    // Even if your `Type` is not a range, this would
    // be fine, as member functions of a template class
    // aren't instantiated unless you call them.
    //
    // However, you may want to expose other ways to
    // access the value
    auto begin() { return std::begin(value); }
    auto end() { return std::end(value); }
    auto begin() const { return std::begin(value); }
    auto end() const { return std::end(value); }
};

Using it would look something like this:

#include <algorithm>
#include <iostream>

class Observer {
public:
    virtual void thingHappened() = 0;

protected:
    ~Observer() = default;
};

class SomeClass {
    MutableLock<std::vector<Observer*>> observers;

public:
    void addObserver(Observer* observer)
    {
        observers.action([observer](auto& observers) {
            observers.push_back(observer);
        });
    }

    void remove(Observer const* observer)
    {
        observers.action([observer](auto& observers) {
            observers.erase(std::remove(observers.begin(), observers.end(), observer), observers.end());
        });
    }

    void doSomething()
    {
        auto lock = observers.lock();
        for (auto* observer : observers) {
            observer->thingHappened();
        }
        // when `lock` goes out of scope, we automatically unlock `observers` and
        // apply any actions that were built up
    }
};

class Observer1 : public Observer {
public:
    SomeClass* thing;

    void thingHappened() override
    {
        std::cout << "thing 1\n";
        thing->remove(this);
    }
};

int main()
{
    SomeClass thing;
    Observer1 obs;
    obs.thing = &thing;

    thing.addObserver(&obs);
    thing.doSomething();
    thing.doSomething();
}

^{On Coliru}

Answer 2

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?

The following method has worked for me in the past.

1. Note that your are going to iterate over the observers.
2. When a client requests to remove an observer to be removed, check whether you are in the middle of iterating over the observers. If you are, set it aside in another vector. If not, remove it from the observers.
3. After you are done iterating over the observers, remove all the observers that need to be removed.
4. Note that you are done iterating over the observers.

---

void SomeClass::removeObserver(Observer* o) {
   if ( this->isIterating  )
   {
      observersToRemove.push_back(o);
   }
   else
   {
      // Code for real removal of the observer
   }
}

void SomeClass::doThing() {
   this->isIterating = true;
   for (auto* o : mObservers) {
      o->thingHappened();
   }

   for ( auto* o : observersToRemove )
   {
      // Code for real removal of the observer
   }

   observersToRemove.clear();

   this->isIterating = false;
}

Answer 3

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

Answer 4

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());
}