Добавление и удаление элементов без аннулирования итераторов

Question

У меня есть объект, у которого есть список «наблюдателей». Эти наблюдатели получают уведомления о вещах, и они могут отреагировать на это изменение, добавив или удалив себя или других наблюдателей из объекта.

Я хочу надежный и не слишком медленный способ поддержать это.

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

Возможно, у меня может быть флаг, установленный с помощью add_ и remove_, для сброса моего итератора, если он будет признан недействительным, а затем, возможно, счетчик «генерации» в каждом наблюдателе, чтобы я знал, если я его уже вызывал?

Answer 1

Может быть, вы могли бы использовать лучший (?) Дизайн. Например, вместо того, чтобы Наблюдатели удаляли себя, вы могли бы заставить функцию уведомления удалить их (или выполнить любую другую операцию) на основе их возвращаемого значения.

Answer 2

Будет ли добавление или вставка элементов лишать законной силы некоторые из них - все итераторы в контейнере, полностью зависит от типа контейнера.

Возможно, вы захотите изучить std::list, поскольку это один из наиболее допустимых контейнеров в отношении проверки итератора. Например, при удалении элемента будут отменены только итераторы, указывающие на удаленный элемент. Все остальные итераторы остаются действительными.

Вам все еще нужно решить, какие операции являются действительными. Вы могли бы подумать о том, чтобы не разрешать прямые операции добавления / удаления в списке наблюдателей и ставить в очередь действия добавления и удаления, когда происходит уведомление, воздействуя на очередь по завершении уведомления.

Если наблюдателям разрешено удалять только себя или добавлять новых наблюдателей, это может быть излишним, и такой цикл будет достаточно безопасным:

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

Answer 3

Разумным способом управления этим хаосом является наличие флага, чтобы код удаления знал, выполняет ли он итерацию наблюдателей.

При удалении, если код находится в итерации, указатель устанавливается на ноль, а не удаляется. Флаг устанавливается в третье состояние, чтобы указать, что это произошло.

Наблюдатели должны быть повторены с оператором [], если во время итерации вызывается add, а массив перераспределяется. Нулевые значения в массиве игнорируются.

После итерации, если установлен флаг, указывающий, что наблюдатели были удалены в итерации, массив можно сжать.

Answer 4

Самый простой способ иметь итераторы, которые не будут аннулированы, - это хранить ваши наблюдатели в списке, а не в векторе. Итераторы списка не становятся недействительными при добавлении или удалении элементов, если они не указывают на удаляемый элемент.

Если вы хотите придерживаться вектора, лучший способ, о котором я могу сразу подумать, это иметь флаг для сброса, если вы добавляете элемент (добавление может сделать недействительным КАЖДЫЙ элемент в векторе), а затем использовать предварительный декремент цикл для прохождения вектора (поскольку удаление приведет к аннулированию элементов только после точки, а не до нее).

Answer 5

Я думаю, что вы на правильном пути с поколениями. Из вашего вопроса не ясно, нужно ли применять изменения в наблюдателях к текущему уведомлению. Если нет, то я бы переместил всех наблюдателей, которых необходимо продолжить применять к следующему поколению, и оставил бы текущего итератора в покое.

Answer 6

Вы не можете безопасно добавлять и удалять элементы из вектора без признания недействительными каких-либо итераторов , которые указывают на или за элемент, который вы удалили . Если это проблема для вас, возможно, вам следует использовать другой контейнер? Вы можете добавлять и удалять список или карту, делая недействительным только итератор в той позиции, на которую он воздействовал.

Вы можете использовать следующий метод для итерации. Это позволяет произвольные вставки и удаления в контейнере, так как мы делаем копию:

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