在不使迭代器无效的情况下添加和删除项目

我有一个包含'observers'列表的对象。这些观察者会收到有关事情的通知，他们可能会通过向对象添加或删除自己或其他观察者来响应此更改。在不使迭代器无效的情况下添加和删除项目

我想要一个强大的，而不是不必要的缓慢的方式来支持这一点。

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_设置，重置我的迭代器，如果它得到无效，然后在每一个观察者或许是“一代”计数器，所以我知道如果我已经把它称为？

来源

2009-06-08 Will

只是说明：您多次拼写“观察者”为“obsever”。如果您在编译时没有注意到这可能会导致一些头部划伤。 – 2009-06-08 21:59:08

一个hacky修复将是使指针为NULL，然后在整个地方做NULL检查。这样你不需要删除它。 – Lodle 2009-06-09 08:10:51

Lodle - 使用[]运算符而不是迭代器来处理添加，这是一个实际的答案，并且我很有可能接受它！ O（n）sweet – Will 2009-06-09 17:50:16

管理这种混乱的理智方法是有一个标志，以便删除代码知道它是否迭代观察者。

在remove中，如果代码在迭代中，则指针设置为null而不是删除。该标志被设置为第三状态以指示发生了这种情况。

观察者必须迭代[]运算符，以防迭代过程中调用add，并重新分配数组。数组中的空值将被忽略。

迭代后，如果标志被设置为表示观察者在迭代中被移除，则可以压缩数组。

来源

2009-11-25 11:33:47 Will

无论是添加还是插入项目都会导致一些容器的迭代器无效，这完全取决于容器类型。

您可能想要调查std::list，因为这是关于迭代器验证的容忍度更高的容器之一。例如，在移除一个元素时，只有指向被移除元素的迭代器才会失效。所有其他迭代器保持有效。

你仍然需要决定什么样的操作是有效的。您可以考虑不允许在观察者列表上直接添加/删除操作，并在通知正在发生时排队添加和删除操作，并在完成通知后执行队列操作。

如果观察员只允许自行拆除或添加新的观察员，这可能是矫枉过正和一个回路，因为这将是足够安全：

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

来源

2009-06-08 21:59:40

你的意思是在remove_obsever（）方法中有一个'current_observer'成员来监视它？但是在返回到notify_observers（）循环之前，如何从它中恢复，或在添加到尾部/头之前删除列表的尾部/头部？ – Will 2009-06-08 22:02:58

你不能安全地添加和矢量删除项目，而不无效任何迭代器 ~~指向或移出您已删除的项目~~ 。如果这对你来说是一个问题，也许你应该使用不同的容器？您可以添加和删除列表或映射，只会使迭代器在受影响的位置无效。

您可以使用以下方法遍历。它允许在容器中任意插入和删除，因为我们正在一个副本：

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

来源

2009-06-08 22:01:12

有不会被无效是你的观察员存储在一个列表中，而不是在一个向量迭代器的最简单方法。列表迭代器不会因添加或删除项目而失效，除非它们指向要删除的项目。

如果你想坚持一个向量，我可以直接想到的最好方法是如果你添加一个项目（添加可以使向量中的EVERY项无效）减量循环遍历向量（因为删除只会使点之后的项无效，从不会在它之前）。

来源

2009-06-08 22:02:14 workmad3