在不使迭代器無效的情況下添加和刪除項目

Question

我有一個包含'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_設置，重置我的迭代器，如果它得到無效，然後在每一個觀察者或許是「一代」計數器，所以我知道如果我已經把它稱爲？

Answer 1

管理這種混亂的理智方法是有一個標誌，以便刪除代碼知道它是否迭代觀察者。

在remove中，如果代碼在迭代中，則指針設置爲null而不是刪除。該標誌被設置爲第三狀態以指示發生了這種情況。

觀察者必須迭代[]運算符，以防迭代過程中調用add，並重新分配數組。數組中的空值將被忽略。

迭代後，如果標誌被設置爲表示觀察者在迭代中被移除，則可以壓縮數組。

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

你不能安全地添加和矢量刪除項目，而不無效任何迭代器 指向或移出您已刪除的項目 。如果這對你來說是一個問題，也許你應該使用不同的容器？您可以添加和刪除列表或映射，只會使迭代器在受影響的位置無效。

您可以使用以下方法遍歷。它允許在容器中任意插入和刪除，因爲我們正在一個副本：

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

Answer 4

有不會被無效是你的觀察員存儲在一個列表中，而不是在一個向量迭代器的最簡單方法。列表迭代器不會因添加或刪除項目而失效，除非它們指向要刪除的項目。

如果你想堅持一個向量，我可以直接想到的最好方法是如果你添加一個項目（添加可以使向量中的EVERY項無效）減量循環遍歷向量（因爲刪除只會使點之後的項無效，從不會在它之前）。

Answer 5

也許你可以使用更好的（？）設計。例如，可以讓notify函數根據它們的返回值刪除它們（或者執行任何其他操作），而不是讓觀察者自行刪除它們。

Answer 6

我認爲你的世代正軌。你的問題不清楚的是觀察員的變化是否需要應用於當前的通知。如果不是，那麼我會移動所有需要繼續應用到下一代的觀察者，並保留當前的迭代器。