Changing a Container while using Visitor

Question

Hi everyone,

I implemented the Visitor pattern in C++ using a STL-like iterator for storing the Visitor's current position in the container. Now I would like to change the container while I iterate over it, and I'm especially interested in deleting items from the container, even the one I'm currently visiting.

Now obviously this will invalidate the Visitors internal iterator, because it was pointing to exactly this item. Currently, I store a list of all iterators in the container and update them, as soon as anything is added to or removed from the list. So in a way this is similar to the Observer pattern applied to the iterator (as Observer) and the list (as Observable).

Alternatively I considered having the visitor() methods return some hint to the Visitor about what happend to the current item and how to proceed iterating, but that doesn't sound like such a good idea either, because the visit() implementation shouldn't really care about finding the next item.

So, my question is: What's the best way to keep a visitor working, even when items are added to the container or removed from it.

Regards, Florian

Update: There's one visitor running over the container, but inside of the visit() method any number of additional iterators might be used on the same container. I want the visitor to continue with the remaining items in the container, even after we returned from a call to visit() in which any one of the items in the container got deleted.

Answer 1

When mutating the container during traversal, iterators are hazardous, at best. It is safest to use an index and walk backwards.

Answer 2

I think your (first) implementation is pretty good if there are not so many iterators and delete operations. If this would be the case I would use a mark and sweep like algorithm like Eddy recommended. Also, I think the latter is easier and thus less error prone. Don't forget to skip nodes which are marked for deletion. On the other hand, if there are cases besides 'delete' where your iterators need to be updated, stick to your current implementation.

Answer 3

In these cases, if copying my container is not expensive, I just copy it and iterate on the copy. The original container holds objects by shared_ptr while the copy just holds weak_ptr.