Sign in to follow this  

Moving nodes between lists using STL

This topic is 4337 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 am trying to move nodes between linked lists for the purpose of taking "asleep" nodes out of the collision detection loop. My lists and iterators are defined like this: list<C2DPoly*>::iterator poly_iter; list<C2DPoly*> poly_list; list<C2DPoly*>::iterator asleep_poly_iter; list<C2DPoly*> asleep_poly_list; C2DPoly* temp_poly; Elements are inserted into the list like this: temp_poly = new C2DPoly(); poly_list.push_back(temp_poly); So far, this is all working. However, when I try to move an element from one list to another, like so: poly_iter = poly_list.begin(); asleep_poly_list.push_back(*poly_iter); poly_list.erase(poly_iter); The exe crashes and gives me an illegal operation error. When I comment out the line poly_list.erase(poly_iter); it no longer crashes. I can't see why that would be though, it seems to be the proper syntax. The node to be deleted normally isn't the first one in the list (I have left the full loop out of this code), so I can't just use pop_front(); Oh, and while I'm on the topic, is this a sensible way to clear my lists and avoid memory leaks? while( poly_list.size() ) { delete (poly_list.back()); poly_list.pop_back(); } poly_list.clear(); Thanks for reading.

Share this post


Link to post
Share on other sites
You could just use poly_list.clear() to clear all elements. If you are allocating memory to pointers stored in the vector/list/whatever, though, you'll have to delete the elements manually and then call poly_list.clear(). The memory will be deallocated when the destructor for the list is called, too, so you don't really need to worry about this in many cases. Sorry I can't really help you with your problem, though, because I'm tired and don't think I can really think it though =)

Good luck.

Share this post


Link to post
Share on other sites
Quote:
Original post by CIJolly
So far, this is all working. However, when I try to move an element from one list to another, like so:

poly_iter = poly_list.begin();
asleep_poly_list.push_back(*poly_iter);
poly_list.erase(poly_iter);

The exe crashes and gives me an illegal operation error.


In and of itself, this should not - unless poly_list.empty(), in which case it should fail on the second line.

Is this your actual code? I would suspect this to be in a loop like so:

for ( poly_iter = poly_list.begin() ; poly_iter != poly_list.end() ; ++poly_iter ) {
if ( some_condition ) {
asleep_poly_list.push_back( *poly_iter );
poly_list.erase( poly_iter );
}
}


If this is the case, then the error is that std::list<T>::erase invalidates that iterator. It returns an iterator to the next element. The correct way to deal with this is:

for ( poly_iter = poly_list.begin() ; poly_iter != poly_list.end() ; ++poly_iter ) {
if ( some_condition ) {
asleep_poly_list.push_back( *poly_iter );
poly_iter = poly_list.erase( poly_iter );
} else {
++poly_iter;
}
}


Or more cleanly, make "some_condition" a member function of the removee, then one can use functors and their ilk to do this more simply:

bool C2DPoly::is_asleep( void ) const {
return ...;
}


list< C2DPoly* >::iterator asleep_begin, asleep_end;

asleep_begin = std::remove_if( poly_list.begin() , poly_list.end() , & C2DPoly::is_asleep );
/* ^^^ moves all the polys for which is_asleep returns true to the end of the
* list, and returns an iterator to the first one for which it returned true
*/

asleep_end = poly_list.end();

asleep_poly_list.splice( asleep_poly_list.begin() , asleep_begin , asleep_end );
/* ^^^ removes [asleep_begin..asleep_end) from their original container
* ( poly_list ) and inserts them into asleep_poly_list, right before
* asleep_poly_list.begin()
*/








Quote:
(I have left the full loop out of this code)


Yes, don't do this next time, it is relevant!!!

Quote:
Oh, and while I'm on the topic, is this a sensible way to clear my lists and avoid memory leaks?


Options:
1) A container of smart pointers such a boost::shared_ptr
2) boost::ptr_* containers which mimic their std::* counterparts, with some minor variations to deal with polymorphism.
3) Hold the items by value instead of by pointer.

Share this post


Link to post
Share on other sites
Thanks MaulingMonkey, your powers of deduction are prodigious. My code looked almost exactly like you assumed (some_condition was a bit more elaborate, but otherwise spot on).
I didn't realise that erase invalidated the iterator. I changed the loop to the one which incremented the iterator within the loop, and the error is gone.
I will post the exact code next time, I have learnt my lesson!

silverphyre673, thanks for the info. Deleting the elements and clearing the list seems to be working, so fingers crossed I've got it right.

Share this post


Link to post
Share on other sites

This topic is 4337 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this