std::list question
Author
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!
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.
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.
Author
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!
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.
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]
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]
Quote:Original post by pragma FuryWouldn'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.
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.
Quote:Original post by AgonyQuote:Original post by pragma FuryWouldn'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.
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.
Oh .. woah.
Yeah, you're absolutely right. [blush]
It would skip every 2nd element in the vector.
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)
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)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
