イテレータを無効にしないアイテムの追加と削除

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

この混乱を管理するための純粋な方法は、削除コードがオブザーバを反復しているかどうかを知るようにフラグを設定することです。

削除では、コードが繰り返し処理されている場合、ポインタは削除されずにnullに設定されます。フラグは、これが起こったことを示す第3の状態に設定される。

反復中にaddが呼び出され、配列が再割り当てされる場合、オブザーバは[]演算子で反復されなければなりません。配列内のNULL値は無視されます。

反復後、反復でオブザーバーが削除されたことを示すフラグが設定されている場合は、配列を圧縮できます。

Answer 2

アイテムを追加または挿入するかどうかによって、コンテナ内のすべてのイテレータが完全にコンテナの種類に依存するかどうかが決まります。

std::listはイテレータの検証に関してより耐性のあるコンテナの1つですので、調査することをお勧めします。たとえば、要素を削除すると、削除された要素を指すイテレータのみが無効になります。その他のイテレータはすべて有効です。

有効な操作の種類を決定する必要があります。 Observersリストで直接追加/削除操作を許可しないで、通知が発生している間に追加と削除のアクションをキューに入れ、通知完了時にキューを処理することを検討できます。

オブザーバーは、これだけはやり過ぎかもしれそのものを削除したり、新たなオブザーバーを追加するために許可され、このようなループは、十分に安全であるかどう：

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

リストではなく、ベクトルであなたのオブザーバーを格納することで無効にされることはありませんイテレータを持ってする最も簡単な方法：我々はコピーを作っているので、それは、コンテナ内の任意の挿入および欠失を可能にします。リストイテレータは、削除されるアイテムを指していない限り、アイテムを追加または削除することによって無効になりません。

もしあなたがベクトルに固執したいのであれば、すぐに考えることができる最良の方法は、アイテムを追加すると（ベクトルにすべてのアイテムを無効にすることができる）リセットするフラグを設定し、ベクトルを通過するための減分ループ（削除すると、ポイントの後のアイテムは無効になります。

Answer 5

おそらく、より良い（？）デザインを使用することができます。たとえば、Observersを自分自身で削除する代わりに、通知関数で戻り値に基づいて削除する（または他の操作を行う）ことができます。

Answer 6

あなたは世代にふさわしいと思います。あなたの疑問からはっきりしないことは、現在の通知にオブザーバーの変更を適用する必要があるかどうかです。そうでなければ、私は次世代への適用を続ける必要があるすべてのオブザーバーを移動し、現在のイテレーターだけを残します。