Jump to content
  • Advertisement
Sign in to follow this  
obhi

Removing from a list while iterating.

This topic is 3419 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

suppose i'm iterating over objects stored in a array and calling functions over the objects. now the object asks to get deleted from this array and it informs he class holding this array. the class has to comply, but since it is processing the object array it cannot directly delete from this array. My problem is i want to delete this object from this array while processing (storing it to later delete it wont do because the object is getting killed after its request) and i cannot use reference counting either. any suggestions how t do it or which data structure to use. Eg code: void Holder::Iterateover() { for each object in objectarray object->CallMe() } void Holder::Deleteobject(object) { remove object from objectarray } void KillerObject::CallMe() { Holder::Deleteobject(this) } this might be very trivial, i tried quite a few solutions but somehow it is not working (and my engine is crashing.) last bit of info - the 'objectarray' in question is rather sorted and we want it that way. thanks in advance.

Share this post


Link to post
Share on other sites
Advertisement
I can't explain it in words, so here's some code:


bool KillerObject::CallMe()
{
// Holder::Deleteobject(this);
return true; // return true on removal
}

for ( std::list<KillerObject>::iteartor it = thelist.begin(), end = thelist.end(); it != end; /* no inc */ )
if ( (*it).CallMe() )
it = thelist.erase( it );
else
++it;





Also, having the elements know about its container is bad mojo, and should be avoided if possible.

EDIT:
Nice catch there, Ravyne :)

[Edited by - _fastcall on June 4, 2009 12:28:05 PM]

Share this post


Link to post
Share on other sites
_fastcall has it right, except that it should be "it = thelist.erase(it);" instead of "it = thelist.remove(it);"

The reason this happens is because the iterator becomes invalid after you've erased it (much the same way as a pointer becomes invalid after deleting the memory held by it) so you cannot get the next element from it. The erase(iterator) method returns an iterator to the next element, allowing you to continue. If the erased item was the last in the list, then the method returns an iterator to the end of the list.

For erasing a range of elements, there is a ranged erase, erase(iterator first, iterator last), which erases all elements between the two iterators, and whose return value behaves identically to erase(iterator).

Share this post


Link to post
Share on other sites
a note on the previous example if you want to continue through the list you should use a copy of the iterator then increment the original before deleting. If you remove the item the iterator points to the iterator is invalid. So do like the following:

list<foo> List;
list<foo>::iterator i = List.Begin();
list<foo>::iterator Delete;
while(i != List.end())
{
if((*i).DeleteCondition())
{
Delete = i;
i++;
List.erase(Delete);
continue;
}
i++;
}

Share this post


Link to post
Share on other sites
thanks for the reply's...but the function 'CallMe in this eg' isn't really something that returns true or false or info about if the object should continue exiting or not...anyway probably that is the best way around the problem because you dont end up keeping a dangling pointer alive.

Share this post


Link to post
Share on other sites

list<foo> List;
list<foo>::iterator i = List.Begin();
list<foo>::iterator DeleteIt;
while ( i != List.end() )
{
if ( (*i).DeleteCondition() )
{
DeleteIt = i;
i++;
List.erase( DeleteIt );
continue;
}
i++;
}



... refactors into:


for ( list<foo>::iterator it = list.begin(), end = list.end(); it != end; /* no increment */ )
if ( (*it).DeleteCondition() )
it = list.erase( it );
else
++it;



Use whatever you find more readable. [smile]

Share this post


Link to post
Share on other sites
Removing based on a condition is part of the standard library. Use it.

#include <algorithm>
#include <functional>
#include <list>

void blah(std::list<foo>& L)
{
L.erase(std::remove_if(L.begin(), L.end(),
std::mem_fun_ref(&foo::deleteCondition)), L.end());
}

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
Removing based on a condition is part of the standard library. Use it.

#include <algorithm>
#include <functional>
#include <list>

void blah(std::list<foo>& L)
{
L.erase(std::remove_if(L.begin(), L.end(),
std::mem_fun_ref(&foo::deleteCondition)), L.end());
}


Just because someone put it in the library doesn't mean that it has to be used. I find the loop much more clear. It's also easier to modify in the future.

For instance, if the condition for deleting changes, I can do
for (list<foo>::iterator it = list.begin(), end = list.end(); it != end; /* no increment */ ) {
if ((*it).DeleteCondition() || AnotherCondition(*it))
it = list.erase( it );
else
++it;
}




Now let's say I want to log the event when one of these deletions happen:
for (list<foo>::iterator it = list.begin(), end = list.end(); it != end; /* no increment */ ) {
if ((*it).DeleteCondition() || AnotherCondition(*it)) {
log << "WARNING: Deleting foo " << *it << "\n";
it = list.erase( it );
}
else
++it;
}




Would you mind telling us what that would look like in the other style of coding?

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Would you mind telling us what that would look like in the other style of coding?

Sure.

bool condition(foo& f)
{
bool del = f.deleteCondition() || AnotherCondition(f));
if (del) log << "WARNING: Deleting foo " << f << "\n";
return del;
}

void blah(std::list<foo>& L)
{
L.erase(std::remove_if(L.begin(), L.end(), condition), L.end());
}

Share this post


Link to post
Share on other sites
The problem here is how you've structured your code. Eith the structure you are using now is that you are removing the object from the list through another funciton while iterating the list.

There are several solitions to this:

- have the CallMe function return true/false if the object should live and then use one of the many posted loop examples here and delete the object based on that.

- another solution could be to mark the object as "remove me later" so you at least dont invalidate your container/iterators while doing the CallMe functions.
and then at the end of your frame/process/run funciton remove all objects fromt he list that is marked as deleted.

- copy the entire list and (assuming list holds pointers) and then just keep code as you have it.

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!