Jump to content
  • Advertisement
Sign in to follow this  
GenuineXP

Removing Items from a List (std::set, std::vector) While Iterating Through It

This topic is 4251 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm having some trouble with lists, more specifically sets and vectors. The engine I'm working on is heavily event-driven and uses a listener system similar in use to Java listeners. A source of events can add and remove listeners who receive those events when they occur and handle them. To build this system, I created an EventSourceMulticaster template, the name of which I took from a small tutorial I found on the net some time ago. It acts as the private base to event sources and provides the basic functionality to broadcast events as well as add and remove listeners. For example, one event the engine works with are cycles. For each type of event, there are three objects: a source, a listener, and... an event! So for cycle events there's a CycleSource class, CycleListener class, and CycleEvent class. That's all well and good, but EventSourceMulticaster has a big flaw that I've been working around. If an object is removed from it's list of listeners (an std::set) during a broadcast of an event, the iterator used to traverse the set is invalidated and things fall apart. The first solution to this was to create a temporary set (a copy) and traverse that. The problem is that objects that remove themselves as listeners may still receive the event during that broadcast (they're still in the temporary set)! Sometimes object are removed because they are about to be deleted; big problem! EventSourceMulticaster will try to invoke an event handler on a deleted object! I've been trying a new solution but it's very messy and keeps giving me assert failures. The idea is to detect when a listener was removed during the broadcast adjust the list and reassign the iterator. It sounds simple, but it requires two more lists (std::vectors): a list of previously called listeners and a temporary list of listeners copied from the original set. This is necessary for a few reasons, but most importantly because set iterators are not random access and vector iterators are, so I can move 'em around as much as I like. Anyway, here's the offending code. It's messy, but it looks (to me) as if it should work. Unfortunately, it doesn't. (Actually, it's not unfortunate, because I'm sure I'm making some stupid mistakes and it would be unfortunate if such misconstrued code executed. :-) )
void broadcast(E* e, void (L::*func)(E*))
{
    ...
    vector<L*> called;
    vector<L*> toCall(listeners.size());
    copy(listeners.begin(), listeners.end(), toCall.begin());
    size_t size;
    for (vector<L*>::iterator i = toCall.begin(); i != toCall.end(); ++i)
    {
        size = listeners.size();
        if (called.end() + 1 == find(called.begin(), called.end() + 1, *i)) // If this listener wasn't already called...
            ((*i)->*func)(e);
        called.push_back(*i);
        if (size > listeners.size()) // Listener was removed during broadcast!
        {
            toCall.clear();
            toCall.resize(listeners.size());
            copy(listeners.begin(), listeners.end(), toCall.begin()); // Update toCall with the current listeners.
            i = toCall.begin(); // Start over again; it's the only way to be sure!
        }
    }
}


Here, the template parameters E and L are the event type and listener type, respectively. listeners is a set of registered listeners (a class member). What I'm trying to do is create a temporary vector of registered listeners and a vector of listeners that have previously been called/notified. I iterate through the temporary vector, first testing the size of the listeners set. The listener encountered in the temporary vector is not called unless it does not appear in the called vector. The size of the listeners set is tested again to see if it has changed. If it has, the temprary vector is cleared, resized appropriately, and copied into again. To avoid missing any uncalled listeners, the iterator i is set to the beginning again. Like I said, I get a whole lot of assertion failures and runtime errors with this code. Is there something I'm doing terribly wrong? Is my usage of copy() and find() correct? If there are big problems, how does one go about altering a list whilst iterating through it? Thanks!

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by GenuineXP
if (called.end() + 1 == find(called.begin(), called.end() + 1, *i))


What are you trying to do here? end iterators are one past the last valid element in a range. Adding 1 to the end iterator of a container is always going to return an invalid iterator. Just stop adding 1...

Also your code is pushing elements onto the back of the called list even if the element was just found to already be on the called list. For more efficiency, you could make the called list a set to more quickly find if an element was already called.

A more efficient solution may be to not remove elements as soon as they ask to be removed. Instead, maintain another list or set or whatever of elements that have asked to be removed. Then you can ensure that elements are only removed from the listeners list when it is safe to do so. When deciding whether to call a listener, you just check if it has asked to be removed. Whenever a listener asks to listen, you also need to make sure to remove it from the toRemove list if it was there.

There is also the subtle problem of listeners asking to listen to a broadcaster as a result of a message sent by that broadcaster. Would such a listener receive that same message, or would it start receiving at the next broadcast? it would also invalidate your "if (size > listeners.size())" check. Maybe a toAdd list could be added too.

Share this post


Link to post
Share on other sites
Checking the documentation for erase(), you'll find (MSDN version):
Quote:
MSDN std::vector::erase()
Return Value

An iterator that designates the first element remaining beyond any elements removed, or a pointer to the end of the vector if no such element exists.

Using this information you can see that you could continue on to the next element using the return value from erase. It'll be easier to do this, though if you switch from a for loop to a while loop, because you don't want to always increment. If you erase(), you'll already have an iterator to the next element.
vector<someType>::iterator i = someVector.begin();
while (i != someVector.end())
{
if (needToErase(*i))
{
i = someVector.erase(i);
}
else
{
++i;
}
}


Also, I'd definitely recommend using a list if you're going to be erasing a lot of elements in the middle. A vector would be rather inefficient. (Although there are tricks you can use, if you don't need the elements to maintain their order.)

Share this post


Link to post
Share on other sites
Taking it one step at a time, in this line:
if (called.end() + 1 == find(called.begin(), called.end() + 1, *i))
Why are you adding 1 to the return value of end()?

[Never mind, already covered in the previous posts.]

Share this post


Link to post
Share on other sites
Thanks for the replies. I just got in for the night, so I only skimmed them so far.

As for adding one to the iterator used in find(first, last, value), I did that because an online reference said that find() will search elements in the range [first, last), where last is non-inclusive. That means to search [first, last], I have to search the range [first, last + 1), no? Is this reference wrong? It said the last parameter is returned when value is not found.

Thanks again.

Share this post


Link to post
Share on other sites
The C++ STL idiom is for .end() to return one past the end of the vector/list/set/whatever. Even the copy algorithm expects the end iterator to be non-inclusive. Your use of copy is correct.

The C++ template algorithms idiom is:

start = first element in the container
end = one past the last element in the container

All of the template algorithms use these semantics in the arguments they take.

Share this post


Link to post
Share on other sites
I see. I thought it would make sense for semantics of copy() and find() to be the same. :-)

I fixed the function with some of the above suggestions. In fact, erase() was always being called, but from the method to remove a listener which could happen at any time during the broadcast (which is why I had to "detect" that event and use other containers to work around it). I stopped continually pushing items back into the called vector; that was a mistake I failed to notice.

I still got some runtime errors after working on the function, but it turns out it was a mistake elsewhere in the code I was using to test my engine. I forgot to register an important listener (an ObjectDeletedListener)!

It seems to be working now. Thanks again for the help. By the way, does anyone know any good STL books? I've sort of been learning the STL as I go and from the web, but I think a comprehensive reference would be much more helpful (along with a good starter guide to show me the basics I've most likely missed).

Share this post


Link to post
Share on other sites
Quote:
Original post by GenuineXP
I see. I thought it would make sense for semantics of copy() and find() to be the same. :-)


They are...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!