Removing from a list while iterating.
Author
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.
I can't explain it in words, so here's some code:
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]
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]
_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).
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).
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++;
}
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++;
}
Author
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.
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]
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());}
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?
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());}
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
