Archived

This topic is now archived and is closed to further replies.

Deleting in STL List

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

Just got a quick question: I''ve got a list of balls. I iterate through the list of balls and get them to bounce. I now have pretty much what I want - lots of bouncing balls. The problem arises when one of the balls falls off the edge of the map. I want to delete it. I''ve grown accustomed, over the years (sounds grand, doesn''t it ), to pushing items that need to be deleted onto a stack or queue and then deleting them all when I''ve finished iterating. However, this solution is horribly inelegant, and I was wondering if anyone had a better one? Thanx --------------- I finally got it all together... ...and then forgot where I put it.

Share this post


Link to post
Share on other sites
''Cos when I do that on the iterator I''m using, it goes all screwy and crashes the program. I can make it work by pushing them on a stack then erasing them when I''m finished, but isn''t there an easier way? Thanx for the reply, sjelkjd (did I get that right? )

---------------

I finally got it all together...
...and then forgot where I put it.

Share this post


Link to post
Share on other sites
I believe erase should return a valid iterator to the element after the element you erased. However, it does invalidate all other existing iterators to that list structure.

So you''ll have to be a little careful, like so:

list::iterator it=mylist.begin();

while(it!=mylist.end())
{
dostuff(it);
if(need_to_erase(it))
{
it=mylist.erase(it);
}
else
it++;
}

And you did get my handle right =)

Share this post


Link to post
Share on other sites
quote:
Original post by sjelkjd
I believe erase should return a valid iterator to the element after the element you erased. However, it does invalidate all other existing iterators to that list structure.



Not totally correct. For lists, maps and sets, the other iterators are NOT invalidated. It is due to their internal structure and is the C++ standard behavior.

Share this post


Link to post
Share on other sites
quote:
Original post by sjelkjd
I stand corrected. Odd that AdmiralBinary''s code would crash though...it leads me to believe that he''s using some iterator after erasing it.


I said not totally correct because you were right for the rest.

Erase does return an iterator to the next valid element and the deleted iterator is in fact invalidated and is the cause of AdmiralBinary''s crash.


Share this post


Link to post
Share on other sites
I see! I feel such an idiot. I thought what you meant was that the erased iterator was set to the next element. Thanx for helping guys

---------------

I finally got it all together...
...and then forgot where I put it.

Share this post


Link to post
Share on other sites
Array based container do not have remove.

As you may know, remove is an algorithm which delete elements based on their values.

For the sake of performance, remove(and remove_if) does not change the size of the container.

So if you have a container with the following elements :

1 2 3 4 5 5 5 7 8 8 0

After doing a remove_if, if you print the elements in the container you will see :

1 2 3 4 7 8 8 0 8 8 0

remove and remove_if will return an iterator to the first invalid value of the array(in our case it is the 8 after the first 0.

To do a full memory clean up you will have to call erase.

    

whatevertype container;

container.erase( remove( container.begin(), container.end(), 5 ),
container.end() );



List on the other hand, provide a specialisation of remove and remove_if that immediatly frees the memory.



std::list<type> lst;

lst.remove(5);



List also has a few other specialisations.

Unique,
splice,
merge,
sort,
reverse

To move away from lists a bit
Maps and sets have specialiations for searching elements, but weirdly does not have a remove specialization.



Edited by - Gorg on February 18, 2002 1:40:25 AM

Share this post


Link to post
Share on other sites
remove doesn''t actually delete anything. It returns an iterator to the end of the new valid sequence...here''s an example.

Let''s say we have a vector vec:
1,2,3,3,2,3,4,5,x
(x is the end of the container,undefined)

and we call remove(vec.begin(),vec.end(),3)

we get:
1,2,2,4,5,(q),q,q,x
where the parenthesized q is the value returned by remove.
Calling vec.end() still returns the last value. The value of q is undefined, but in this case, it is probably 5(usually the value that gets copied over).
Typically you want to erase the elements you remove, so the complete call looks like this:
vec.erase(remove(vec.begin(),vec.end(),3),vec.end());

Share this post


Link to post
Share on other sites