Adding and removing items without invalidating iterators

Question

I have an object that has a list of 'observers'. These observers get notified of things, and they might respond to this change by adding or removing themselves or other observers from the object.

I want a robust, and not unnecessarily slow, way to support this.

class Thing {
public:
    class Observer {
    public:
     virtual void on_change(Thing* thing) = 0;
    };
    void add_observer(Observer* observer);
    void remove_observer(Observer* observer);

    void notify_observers();
private:
    typedef std::vector<Observer*> Observers;
    Observers observers;
};

void Thing::notify_observers() {

    /* going backwards through a vector allows the current item to be removed in
    the callback, but it can't cope with not-yet-called observers being removed */
    for(int i=observers.size()-1; i>=0; i--)
     observers[i]->on_change(this);

// OR is there another way using something more iterator-like?

    for(Observers::iterator i=...;...;...) {
     (*i)->on_change(this); //<-- what if the Observer implementation calls add_ or remove_ during its execution?
    }
}

I could perhaps have a flag, set by add_ and remove_, to reset my iterator if it gets invalidated, and then perhaps a 'generation' counter in each observer so I know if I've already called it?

Answer 1

Whether adding or inserting items will invalidate some are all iterators into a container is entirely dependent on the container type.

You may want to investigate std::list as this is one of the more tolerant containers with respect to iterator validation. For example, on removing an element, only iterators pointing at the removed element will be invalidated. All other iterators remain valid.

You still need to decide what sort of operations are valid. You could consider not allowing direct add/remove operations on the Observers list and queuing add and remove actions while a notify is occurring, actioning the queue on completion of the notify.

If observers are only allowed to remove themselves or add new observers this may be overkill and a loop such as this would be sufficiently safe:

for( std::list<Observer>::iterator i = observers.begin(); i != observers.end(); )
{
    std::list<Observer>::iterator save = i++;
    save->on_change();
}

Answer 2

You cannot safely add and remove items from a vector without invalidating any iterators that are pointing at or beyond the item that you have removed. If this is a problem for you, perhaps you should use a different container? You can add and remove to a list or map, only invalidating the iterator at the position that was affected.

You could use the following method to iterate through. It allows arbitrary insertions and deletions in the container since we are making a copy:

void Thing::notify_observers()
{
   Observers obscopy=observers;
   Observers::iterator i=obscopy.begin();
   while (i!=obscopy.end())
   {
       (*i)->on_change(this);
       ++i;
   }
}

Answer 3

The simplest way to have iterators that won't be invalidated is to store your Observers in a list rather than in a vector. List iterators don't get invalidated by adding or removing items unless they are pointing to the item being removed.

If you want to stick with a vector, the best way I can think of straight away is to have a flag to reset if you add an item (adding can invalidate EVERY item in the vector) and then use a pre-decrement loop to go through the vector (as removing will only invalidate items after the point, never before it).

Answer 4

Maybe you could use a better(?) design. For example instead of having the Observers remove themselves, you could have the notify function remove them (or do any other operation) based on their return value.

Answer 5

I think you're on the right track with generations. What's not clear from your question is whether the change in observers needs to be applied to the current notification. If not, then I would move all observers that need to continue being applied to the next generation and leave the current iterator alone.

Answer 6

The sane way to manage this chaos is to have a flag so the remove code knows whether it's iterating the observers.

In the remove, if the code is in an iteration, then the pointer is set to null rather than removed. The flag is set to a third state to indicate that this has happened.

The observers must be iterated with [] operator in case an add is called during iteration, and the array is reallocated. Null values in the array are ignored.

After iteration, if the flag is set to indicate that observers were removed in the iteration, the array can be compacted.