Iterating over STL containers

[jfaust]

I'm wondering if anybody has come across this issue before. I seem to run into it about once a year. I have an STL container in which I want to call some method on each of the items in the container. Think event/callback mechanism (or Observer pattern if you are a pattern buff). The problem I run into is that the container can be modified during an iteration. For instance, if the event was that the item is destroyed, the observer (listener), may want to stop receiving events on that object, and so will remove itself.

Iterators don't like the container changing during iteration.

Has anyone else had this problem before? How did you handle it? I was able to solve this, but I'd like to know if there are better solutions, or maybe a better way to handle a system like this.

Jeff

[jwbarton]

If you are going to use a routine that modifies a container, you have to be aware of what can happen to the iterators due to the operations that you are using. This applies not only if you are removing elements from the container, but also if you are adding elements to the container.

Depending on the type of container, you may have just invalidated the current iterator, or you may have invalidated all iterators into that container. For instance, std::list will only invalidate the current iterator if you erase that element. This allows you to save the next iterator before your call that may erase an element, not using the current iterator after the call.

Example:

std::list<MyClass> myList;

std::list<MyClass>::iterator current;
current = myList.begin();

while ( current != myList.end() )
{
std::list<MyClass>::iterator next = current;
++next;
CheckItem( myList, current ); // remove item sometimes

current = next; // don't increment current after call
}


Depending on the container type, the above code may work. You have to be aware of the rules for the STL container type about what kind of operations can invalidate the iterators for the container. If the routine you are calling can invalidate the iterator passed to it, you need to do something like above. If the routine can invalidate all iterators, you will need some other approach.

Best regards,
John

[jfaust]

John,

That's a good approach. I didn't realize that only the current iterator is invalidated. Is this something guaranteed by STL, or is it a fluke of a particular implementation?

Even so, this is too restrictive. Conceptually, the person firing the event is blind, and the person listening to the event is free to do as he pleases.

Thanks for the idea!

Jeff

[jwbarton]

For the std::list type, STL does specify that erasing a single element will not invalidate any other iterators to the list.

For your specific example of wanting to call a routine for each element in the container, where the element may want to remove itself, I might consider flagging the item for removal, and only removing it after the loop:


typedef std::List<MyClass> MyList;


bool IsMarked( const MyClass& myClass )
{
return myClass.IsMarked();
}


{
// Process something on each item, mark items if they should be deleted
std::for_each( myList.begin(), myList.end(), DoSomething );

// remove all the items that are marked
MyList::iterator last = std::remove_if( myList.begin(), myList.end(), IsMarked );

// actually remove the items from the list
myList.erase( last, myList.end() );
}


I would think that this approach would be much easier to work with, as it will also work with other container types.

Best regards,
John

[cup]

Something I used to do with loop counters when working on vectors that can change in size: go through the list backwards. I've never done it with iterators though. eg

for (int i = mylist.size () - 1; i >= 0; i--)
{
// do whatever you want with mylist[i], including deleting it
}

This works well even if the loop body contains mylist.pop_back or mylist.push_back. The size of the loop is irrelevant since we're going from back to front. It doesn't work at all if it has mylist.push_front. But then again, I've never had to use it with mylist.push_front so it wasn't a problem.

[jfaust]

At one point I did start down the path of flagging the items similar to what you suggested. I remove the responsibility to the caller and made it more general to also handle insertions, etc. I created a new class that contained a container, and had logic that locked and unlocked it. When locked, all calls that could modify the container simply appended to a list of actions with arguments that would execute as soon as the container was unlocked. It was pretty slick. The class was templatized and worked on any STL container. I created another class responsible for locking that locked in the constructor and unlocked in the destructor. The locking was reference counted, so that it could be locked more than once. When finished, I was really proud of myself. Unfortunately, it didn't work. There was a problem with how one event kicked off another that ended up using an item in the container that should not have been there since it was deleted, all because some guy at an outer scope had the container locked.

How I ended up solving it my problem: I created a set of template methods, in the style of std::for_each that operated on a given container. I called it for_all, and it behaved like for_each from begin() to end() on the container. The difference is that I created a different for_all for each different number of arguments. In other words, I create a for_each for 1 argument, a for_each for 2 arguments, and so on. The reason I did this instead of how STL handled arguments: have you ever tried to use bnd1st or bnd2nd? Sheesh...

Then, I created a similar set of template methods, called for_all_safe that first makes a copy of the container and operated on that. This way, the original container is free to change. Then, with each iteration, I first make sure that the item is still in the original list. This checks that the pointer is still valid.

This has some overhead, but not too much. It's pretty quick to make a copy of a container of pointers. The check to see if the item still exists in the original container is also fast with the right container.

I struggled with this long enough and came across it often enough that I thought it would be worthwile discussing here. I thought maybe that there was some STL feature that I was not aware of, such as safe_iterator that would solve all my problems.

I'll post some code tomorrow from work. I'd do it from here, but I always have to relearn how to pass methods as arguments and don't feel like embarassing myself at the moment.

Thanks John and cup. I've learned something new!

Jeff

[Paul McKenzie]

Originally posted by jfaust
The difference is that I created a different for_all for each different number of arguments. In other words, I create a for_each for 1 argument, a for_each for 2 arguments, and so on. The reason I did this instead of how STL handled arguments: have you ever tried to use bnd1st or bnd2nd? Sheesh...
Try the boost bind. It may help you here:

http://www.boost.org/libs/bind/bind.html

Regards,

Paul McKenzie

[jfaust]

Paul,

Now that is really really cool. I can't wait to get in tomorrow and play with it. I had heard "boost" mentioned before, but I had no idea it was an improvement over the obnoxious std methods.

Thanks,

Jeff

[Graham]

If your arguments don't change over the iteration, you could provide a set of functors and supply the invariant arguments to the constructors, rather than have multiple "copies" of the same function.

Have you considered using the State pattern, rather than simply flagging the object. If "deletion" consisted of setting the object to an "invalid" state, then you could still postpone the actual deletion, but if anyone tried to use it, they'd get some sort of indication that it won't work.

Also, delete during iteration over a list is one of the few occasions where post-increment is useful:

std::list<MyClass> myList;

std::list<MyClass>::iterator current;
current = myList.begin();

while ( current != myList.end() )
{
CheckItem( myList, current++ ); // Safe over deletion.
}

[jfaust]

Graham,

I thought of having a separate class to handle the arguments, but I couldn't come up with a clean way to do it without clogging the interface. Maybe you can help me out here.

My container class publicly exposes begin() and end() of the STL container, so that it works with other algorithms. Indicating a state might be difficult. I'd have to wrap the type being contained in another class that contains the state information. Or possibly create a new iterator class that knows about state, although I've never written any iterator code. Any way it's done, the burden of checking the state would be with the caller. The state would also have to keep track of insertion, which complicates matters.

Here's the basic funtion with no arguments:

template<class T, class F, class R> inline
void for_all_safe(const T& container, R (F::* f)() )
{
T tempContainer(container);

for( T::const_iterator iter = tempContainer.begin(); iter != tempContainer.end(); ++iter )
{
if( std::find(container.begin(), container.end(), *iter) != container.end() )
{
((*iter)->*f)();
}
}
}


Here's the function with one argument:

template<class T, class F, class R, class A, class A1> inline
void for_all_safe(const T& container, R (F::* f)(A arg), A1& arg )
{
T tempContainer(container);

for( T::const_iterator iter = tempContainer.begin(); iter != tempContainer.end(); ++iter )
{
if( std::find(container.begin(), container.end(), *iter) != container.end() )
{
((*iter)->*f)(arg);
}
}
}


Notice that there are two template parameters for the argument. This is because the type passed into the template may be different than the type passed to the method. This can get burdensome, especially since a provide methods for up to five arguments.

This could be used like the following, where 'this' is the single argument passed in.


for_all_safe(m_listeners, &FooListener::onDestroyed, this);


Jeff

[Graham]

What I was suggesting won't relieve the "burden" of all those different arg types, but to move it to functors, so that you only have one copy of the function:

template<class T, class F>
void for_all_safe(const T& container, F f )
{
T tempContainer(container);

for( T::const_iterator iter = tempContainer.begin(); iter != tempContainer.end(); ++iter )
{
if( std::find(container.begin(), container.end(), *iter) != container.end() )
{
f(*iter);
}
}
}

template <typename R, class T>
class Func0Arg
{
R (T::*f_)();
public:
Func0Arg(R (T::*f)()) : f_(f) {}
void operator()(const T& obj) { obj.*f_(); }
};

template <typename R, class T, typename A, typename Arg>
class Func1Arg
{
R (T::*f_)(A);
Arg arg_;
public:
Func1Arg(R (T::*f)(A), Arg arg) : f_(f), arg_(arg) {}
void operator()(const T& obj) { obj.*f_(arg_); }
};

// etc for more args

//usage

for_all_safe(m_listeners, Func1Arg<Aagh>(FooListener::onDestroyed, this));

On second thoughts, that's not so wonderful, because you'd have to list all the template parameters to create the functor - unless you do what std::make_pair() does for std::pair. Hmm, it seems a bit round-about, but it does avoid duplicating code, and that's always a good thing to do.

As for the State suggestion, it would have to be the contained class that implements it, otherwise it's not worthwhile. It basically relies on the contained class doing nothing in response to the function call if it's been "destroyed". The advantage would be that you could use for_each and remove some of the inefficiency of your for_all_safe(). It may mean reorganising the class to accomodate the pimpl necessary for state to work, and I don't know how feasible that suggestion is for you. It also relies on a "disabled" state being able to do nothing sensibly (not always possible). It was just a thought.

There may be some other suggestions I could make, but it's going-home time here, so I don't really have the time. HTH

[jfaust]

Graham,

Ahh, cool. I could have both. The functions I have could simply turn around and call your functions with the correct functor, removing the burden of the template parameters from the caller. This would put all the logic in one place at least.

Please, let me know of your other suggestions. My strongest belief in programming is "there's always a better way."

Jeff