Back to General and Gameplay Programming

Deleting in STL List

General and Gameplay Programming Programming

Started by AdmiralBinary February 17, 2002 10:11 PM

9 comments, last by AdmiralBinary 22 years, 1 month ago

AdmiralBinary

100

Author

February 17, 2002 10:11 PM

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.

sjelkjd

171

February 17, 2002 10:26 PM

if you''re using an stl list why don''t you just call list.erase()?

AdmiralBinary

100

Author

February 17, 2002 10:37 PM

''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.

sjelkjd

171

February 17, 2002 10:48 PM

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 =)

Gorg

248

February 17, 2002 10:51 PM

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.

sjelkjd

171

February 17, 2002 10:55 PM

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.

Gorg

248

February 17, 2002 11:02 PM

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.

AdmiralBinary

100

Author

February 17, 2002 11:06 PM

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.

Shannon Barber

1,684

February 18, 2002 12:13 AM

So do you only need to call remove on array based containers?

Magmai Kai Holmlor

"Oh, like you''ve never written buggy code" - Lee

- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara

Gorg

248

February 18, 2002 12:38 AM

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

Deleting in STL List

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Deleting in STL List

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines