Jump to content
  • Advertisement
Sign in to follow this  
TaskyZZ

std::list question

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

A few days ago while playing with vectors, I got some great help from some of you guys. Now I am trying to learn lists, you would think it would be easier, but in dealing with iterators, I am getting confused. Say I had a list, and as I was iterating through it, I wanted to remove an element but continue to go through the list. Here is what I have: for (std::list<clsBullets>::iterator iBulletNum=Bullets.begin();iBulletNum != Bullets.end();iBulletNum++) { if (iBulletNum->Draw()) Bullets.erase(iBulletNum); } If I remove an item, then my iterator ends up pointing beyond the list and accessing memory it shouldn't. How exactly should I handle this? Thanks for any help!

Share this post


Link to post
Share on other sites
Advertisement
erase returns the iterator that follows the element beeing erased. You just have to modify your loop to use the return value in that case. You should find an example (for list or vector) if you search the forum.

Share this post


Link to post
Share on other sites

for (std::list<clsBullets>::iterator iBulletNum=Bullets.begin();iBulletNum != Bullets.end();)
{
if (iBulletNum->Draw())
Bullets.erase(iBulletNum++);
else
++iBulletNum;
}





The iterator post-increment operator will create a copy of the original pointer and return that to the erase method, while your original iterator is incremented and remains valid. Note that the 3rd expression in your for statement, where the iBulletNum++ was has been removed.

Also note that I'm using the pre-increment operator if the bullet is not removed from the list, this is because the pre-increment operator does not create the copy, and is therefore faster.

Share this post


Link to post
Share on other sites
Quote:
Original post by pragma Fury
*** Source Snippet Removed ***

The iterator post-increment operator will create a copy of the original pointer and return that to the erase method, while your original iterator is incremented and remains valid. Note that the 3rd expression in your for statement, where the iBulletNum++ was has been removed.

Also note that I'm using the pre-increment operator if the bullet is not removed from the list, this is because the pre-increment operator does not create the copy, and is therefore faster.


Works like a champ.

Thanks for the help. Also, the bit about post-increment and pre-increment operators was enlightening. I will keep that in mind from now on!

Share this post


Link to post
Share on other sites
Actually, here's even more performance help..

After thinking about how the erase() method returns the next valid iterator, it occurred to me that doing an erase(iter++) would cause more useless CPU wastage. Why? Because erase() also makes a copy internally.. so we're making an extra copy.

Did a quick test, and the following method is nearly twice as fast as the source I gave you earlier, in regards to processing done by the list and iterators.


for (std::list<clsBullets>::iterator iBulletNum=Bullets.begin();iBulletNum != Bullets.end();)
{
if (iBulletNum->Draw())
iBulletNum = Bullets.erase(iBulletNum);
else
++iBulletNum;
}





EDIT!: NOTE std::vector::erase() operates in a completely different method than std::list::erase(). It's actually twice as fast to use the erase(iterator++) syntax when working with vectors.

[Edited by - pragma Fury on June 6, 2005 6:41:51 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by pragma Fury
EDIT!: NOTE std::vector::erase() operates in a completely different method than std::list::erase(). It's actually twice as fast to use the erase(iterator++) syntax when working with vectors.
Wouldn't that simply not work properly with a vector? Because you'd end up skipping the element after the one you just erased. Or if you were erasing the last element, you'd be in a pickle, since your iterator would now be beyond .end(). With a list, all iterators remain valid except for the one being erased, so .erase(it++) is okay, but with a vector, the incremented iterator would be an iterator that comes after the erased element, and thus the erase function would invalidate the iterator. Thus, you'd have to use the return from .erase() to be proper and reliable and correct and all that.

Share this post


Link to post
Share on other sites
Quote:
Original post by Agony
Quote:
Original post by pragma Fury
EDIT!: NOTE std::vector::erase() operates in a completely different method than std::list::erase(). It's actually twice as fast to use the erase(iterator++) syntax when working with vectors.
Wouldn't that simply not work properly with a vector? Because you'd end up skipping the element after the one you just erased. Or if you were erasing the last element, you'd be in a pickle, since your iterator would now be beyond .end(). With a list, all iterators remain valid except for the one being erased, so .erase(it++) is okay, but with a vector, the incremented iterator would be an iterator that comes after the erased element, and thus the erase function would invalidate the iterator. Thus, you'd have to use the return from .erase() to be proper and reliable and correct and all that.


Oh .. woah.
Yeah, you're absolutely right. [blush]
It would skip every 2nd element in the vector.

Share this post


Link to post
Share on other sites
In fact, your first example was completely incorrect since once you have used erase() on it, an iterator becomes invalid (it's in the function description). And trying to increment an invalid iterator has undefined behaviour. For example, if you had a list, the old iterator would be pointing to memory that has been released. Incrementing the iterator would mean trying to read the address of the next element from that chunk of memory you do not own anymore. I'm afraid you can't do that.

That's the real reason why erase() does return an iterator to the element that follows the element you have erased. Short of getting that iterator prior to erasing, there is no way for you to get it (and even then, I wonder if there aren't containeres and cases when the next-element iterator would get invalidated too - unlikely, but heh, short of actually reading the specs for the containers, you won't know)

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!