添加和删除项目而不使迭代器无效
我有一个包含“观察者”列表的对象。 这些观察者会收到有关情况的通知，并且他们可能会通过在对象中添加或删除自己或其他观察者来响应此更改。
我想要一种强大的、而不是不必要的缓慢的方式来支持这一点。
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_ 设置的标志，以便在迭代器失效时重置它，然后每个观察者中可能有一个“生成”计数器，这样我就知道我是否已经调用了它？
I have an object that has a list of 'observers'. These observers get notified of things, and they might respond to this change by adding or removing themselves or other observers from the object.
I want a robust, and not unnecessarily slow, way to support this.
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?
}
}
I could perhaps have a flag, set by add_ and remove_, to reset my iterator if it gets invalidated, and then perhaps a 'generation' counter in each observer so I know if I've already called it?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
也许你可以使用更好的（？）设计。 例如，您可以让通知函数根据其返回值删除它们（或执行任何其他操作），而不是让观察者自行删除。
Maybe you could use a better(?) design. For example instead of having the Observers remove themselves, you could have the notify function remove them (or do any other operation) based on their return value.
添加或插入项目是否会使容器中的某些迭代器失效完全取决于容器类型。
您可能需要研究
std::list因为这是对迭代器验证更宽容的容器之一。 例如，在删除元素时，只有指向已删除元素的迭代器才会失效。 所有其他迭代器仍然有效。您仍然需要决定哪种操作是有效的。 您可以考虑不允许在观察者列表上直接添加/删除操作，并在发生通知时对添加和删除操作进行排队，在通知完成时对队列进行操作。
如果观察者只允许删除自己或添加新的观察者，这可能是矫枉过正，像这样的循环将是足够安全的：
Whether adding or inserting items will invalidate some are all iterators into a container is entirely dependent on the container type.
You may want to investigate
std::listas this is one of the more tolerant containers with respect to iterator validation. For example, on removing an element, only iterators pointing at the removed element will be invalidated. All other iterators remain valid.You still need to decide what sort of operations are valid. You could consider not allowing direct add/remove operations on the Observers list and queuing add and remove actions while a notify is occurring, actioning the queue on completion of the notify.
If observers are only allowed to remove themselves or add new observers this may be overkill and a loop such as this would be sufficiently safe:
管理这种混乱的明智方法是使用一个标志，以便删除代码知道它是否正在迭代观察者。
在删除中，如果代码处于迭代中，则指针将设置为 null 而不是删除。 该标志被设置为第三状态以指示这已经发生。
观察者必须使用 [] 运算符进行迭代，以防在迭代期间调用 add 并重新分配数组。 数组中的空值将被忽略。
迭代后，如果设置标志以指示在迭代中删除了观察者，则可以压缩数组。
The sane way to manage this chaos is to have a flag so the remove code knows whether it's iterating the observers.
In the remove, if the code is in an iteration, then the pointer is set to null rather than removed. The flag is set to a third state to indicate that this has happened.
The observers must be iterated with [] operator in case an add is called during iteration, and the array is reallocated. Null values in the array are ignored.
After iteration, if the flag is set to indicate that observers were removed in the iteration, the array can be compacted.
拥有不会失效的迭代器的最简单方法是将观察者存储在列表中而不是向量中。 列表迭代器不会因添加或删除项目而失效，除非它们指向要删除的项目。
如果你想坚持使用向量，我能立即想到的最好方法是在添加一个项目时重置一个标志（添加可以使向量中的每个项目无效），然后使用预递减循环去通过向量（因为删除只会使该点之后的项目无效，而不会在该点之前）。
The simplest way to have iterators that won't be invalidated is to store your Observers in a list rather than in a vector. List iterators don't get invalidated by adding or removing items unless they are pointing to the item being removed.
If you want to stick with a vector, the best way I can think of straight away is to have a flag to reset if you add an item (adding can invalidate EVERY item in the vector) and then use a pre-decrement loop to go through the vector (as removing will only invalidate items after the point, never before it).
我认为你们几代人都走在正确的道路上。 您的问题不清楚的是观察者的变化是否需要应用于当前通知。 如果没有，那么我会将所有需要继续应用于下一代的观察者移动，并保留当前的迭代器。
I think you're on the right track with generations. What's not clear from your question is whether the change in observers needs to be applied to the current notification. If not, then I would move all observers that need to continue being applied to the next generation and leave the current iterator alone.
如果不使任何指向或超出已删除项的迭代器
无效，您就无法安全地从向量中添加和删除项。 如果这对您来说是个问题，也许您应该使用不同的容器？ 您可以添加和删除列表或映射，仅使受影响位置的迭代器无效。您可以使用以下方法进行迭代。 它允许在容器中任意插入和删除，因为我们正在制作副本：
You cannot safely add and remove items from a vector without invalidating any iterators
that are pointing at or beyond the item that you have removed. If this is a problem for you, perhaps you should use a different container? You can add and remove to a list or map, only invalidating the iterator at the position that was affected.You could use the following method to iterate through. It allows arbitrary insertions and deletions in the container since we are making a copy: