2009-06-08 19 views
2

「オブザーバー」のリストを持つオブジェクトがあります。これらのオブザーバーは物事を通知され、オブジェクトまたは他のオブザーバーをオブジェクトに追加または削除することによって、この変更に対応することができます。イテレータを無効にしないアイテムの追加と削除

私は強く、これをサポートするために不必要に遅くない方法を望んでいます。

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_によって設定されたフラグを、持っている、と可能性があり、各観測で、おそらく「世代」カウンタ私はすでにそれを呼ばれてきた場合、私は知っているので、 ?

+0

ちょうど注記:「オブザーバー」のスペルは2度以上「obsever」です。コンパイル時に気付かないと頭が痛いことがあります。 –

+0

ハッキーな修正は、ポインタをNULLにして、その場所全体にNULLチェックを行うことです。この方法では、削除する必要はありません。 – Lodle

+0

Lodle - 追加を処理するために反復子ではなく[]演算子を使用して実際の回答をしてください。それを受け入れる良い機会があります! O(n)sweet – Will

答えて

1

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

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

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

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

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(); 
} 
+0

あなたはremove_obsever()メソッドで監視する 'current_observer'メンバーを持つことを意味しますか?しかし、それを回復する方法、またはtail/headに追加する前にリストのtail/headを取り除く方法は、すべてnotify_observers()ループに戻る前に? – Will

+0

反復変数をクラスメンバーにすることは、アクションが可能であることを確認する1つの方法です。こうすることで、コールスタックにon_changeメソッドのaddまたはremove関数へのコールバックが含まれている場合は、そのコールスタックを変更して、反復変数が決して無効にならないようにすることができます。これは非常に珍しいデザインであり、おそらくあなたがこれを行う必要を避けるためにあなたのクライアントに置くことができるいくつかの賢明な制限があります。 –

0

あなたは安全に無効にすることなく、ベクターから項目を追加および削除することはできませんいずれかのイテレータ が、削除したアイテムを指しているか、それを超えています 。これが問題の場合は、おそらく別のコンテナを使用する必要がありますか?リストまたはマップを追加または削除し、影響を受けた位置のイテレータのみを無効にすることができます。

次の方法を使用して反復処理を行うことができます。

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

ベクトルを追加すると、ベクトルのすべてのイテレータがベクトルの新しいチャンクに再配置される可能性があります。 – workmad3

+0

バグですが、コピー内の各アイテムについて真のオブザーバーリストに残っていることを確認すると、 O(n^2) – Will

+0

@コードにバグがあるとは思わない:オブザーバーに通知するときは、通知前と同じように状況をフリーズしたいと思うかもしれません。 –

1

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

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

3

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

+0

+1。私はこれをやや失礼だと思った。その意味や考えられる解決策についてしばらく考えてみると、すべてのオブザーバーが自分自身や他のオブザーバーを追加したり削除したりすることを許可するという「すべてを自由にする」方針は、考慮すべき多くの意味を持っています。 notifyメソッドの結果は、実行者と実装の順序に依存します。たとえば、あるオブザーバが別のオブザーバ(たとえば、通知されていない)を削除することができます。おそらく、あなたは抽選会に戻り、あなたの本当の必要条件とそのような柔軟性が必要な理由を説明してください。 –

+0

複数のオブザーバーを追加する必要がある場合はどうすればよいですか? – Will

0

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

関連する問題