Erasing all appropriate elements from a vector
Author
This relates to a game situation but the question is really one of general programming.
So I have a vector of all the projectiles in my game. Right now I want to make it so that when a projectile goes off of the screen it's removed from the game and the vector. So I'm iterating through all of the projectiles and testing whether or not they should be removed. After that I encounter trouble.
How are you supposed to do this exactly?
I know that vectors aren't very good for removal and lists are better, but then I suppose for a simple game it probably doesn't matter for practical purposes what I use from an efficiency standpoint.
I know that use erase() on a vector invalidates iterators after that point.
So, if I'm iterating through the projectiles and discover that the current one should no longer exist, what should I do?
As soon as I remove one, that ruins everything because of the iterator.
I know roughly about how vectors work when something is erased, how it moves the elements, and that lists don't work that way.
Should I just use a list? Would I then be able to iterate through all objects, call erase() if necessary and continue without any problem? Is this even practical at all with a vector?
Sounds like you want to be using the remove-erase idiom. Though if the order of your projectiles doesn't matter you might want to consider swapping with the last element and popping the back of the vector.
Author
Quote:Original post by SiCrane
Sounds like you want to be using the remove-erase idiom. Though if the order of your projectiles doesn't matter you might want to consider swapping with the last element and popping the back of the vector.
Yes... swap and pop might be best... should've thought of that.
Trying some stuff now though and I'm having problems. This code here seems to remove projectiles fine until the last projectile leaves the screen:
//Remove out of bounds player projectiles for ( itProj = playerProjectiles.begin(); itProj != playerProjectiles.end(); itProj++ ) { if( (*itProj).getY() >= gameCamera.getY() + gameCamera.getH() ) { itProj = playerProjectiles.erase( itProj ); } }Then I get:
"Expression: list iterator not incrementable."
Why might removing the last one cause a crash when it works alright before any are put in?
Wait, is it that the iterator is being assigned to a non-existant element after the current one when there's only 1 left? That's strange though, there seems to be a lot of people recommending (IIRC) that same kind of solution on the web.
Whereas if I try to use swap at all, like this:
std::swap( (*itProj), (*playerProjectiles.end()) );
I get:
"Expression: list iterator not dereferencable;"
Crap, I just checked and realized that end() returns the element AFTER the end -_-. Trying it with back(), it seems to work. Christ, that took a long time to figure out. Thanks for the help. BTW, this code doesn't look dangerous does it?:
//Remove out of bounds player projectiles for ( itProj = playerProjectiles.begin(); itProj != playerProjectiles.end(); itProj++ ) { if( (*itProj).getY() >= gameCamera.getY() + gameCamera.getH() ) { std::swap( *itProj, playerProjectiles.back() ); playerProjectiles.pop_back(); } }
You either erase or increment at for loop, not both.
Reason being, erase() invalidates all iterators to the vector and returns an iterator for next element after the erased one. So itProj already points to next element when you erase, and if you dont you need to ++it.
//Remove out of bounds player projectilesfor ( itProj = playerProjectiles.begin(); itProj != playerProjectiles.end();){ if( (*itProj).getY() >= gameCamera.getY() + gameCamera.getH() ) { itProj = playerProjectiles.erase( itProj ); } else { ++itProj ; }}Reason being, erase() invalidates all iterators to the vector and returns an iterator for next element after the erased one. So itProj already points to next element when you erase, and if you dont you need to ++it.
Author
Ok, I just tested it a few times and when I keep firing projectiles for a while I sometimes get the same "Expression: list iterator not incrementable." problem from before.
Hmmm... that code seems to be working fine. At least it hasn't errored like my previous code yet. Looks like it's fixed. Thanks.
Why is it, though, that this doesn't work?
Is the iterator being invalidated? Does the pop_back() in the middle of iteration make it still go beyond the end of the vector?
Quote:Original post by Ftn
You either erase or increment at for loop, not both.
*** Source Snippet Removed ***
Hmmm... that code seems to be working fine. At least it hasn't errored like my previous code yet. Looks like it's fixed. Thanks.
Why is it, though, that this doesn't work?
//Remove out of bounds player projectiles for ( itProj = playerProjectiles.begin(); itProj != playerProjectiles.end(); ) { //If out of bounds if( (*itProj).getY() >= gameCamera.getY() + gameCamera.getH() ) { //Swap with last element std::swap( *itProj, playerProjectiles.back() ); //Remove last element playerProjectiles.pop_back(); } else itProj++; }Is the iterator being invalidated? Does the pop_back() in the middle of iteration make it still go beyond the end of the vector?
Erasing or inserting in middle of vector invalidates all iterators, becouse vector's memory must be contiguous. So erase/insert moves all remaining elements back/forth.
pop_back should only invalidate the last element and end iterator, and the for loop should work if you keep calling the end() at every comparison.
The pop_back version, it doesn't invalidate the current iterator, so you can keep the itProj++ in the for loop :)
pop_back should only invalidate the last element and end iterator, and the for loop should work if you keep calling the end() at every comparison.
The pop_back version, it doesn't invalidate the current iterator, so you can keep the itProj++ in the for loop :)
What I always do is the following:
It's probably a very inefficient way of removing certain parts of a vector, but somehow, I don't know any other way of doing this.
std::vector<unsigned int> veErase;unsigned int nCounter = 0;for (std::vector<Element>::iterator it = veElements.begin(); it != veElements.end(); it++) { if (it->ShouldBeRemoved()) { //note that I'm not incrementing the counter when an element //is actually being removed, this is due to the following, if my //vector looks like this {0, 1, 2, 3, 4} and I want to remove the //'2' and the '3', I have to call vector.erase(vector.begin() + 2) twice, //because the vector looks like this {0, 1, 3, 4} after the first erase //call veErase.push_back(nCounter); } else { nCounter++; }}for (std::vector<unsigned int>::iterator it = veErase.begin(); it != veErase.end(); it++) { veElements.erase(veElements.begin() + (unsigned int)(*it));}It's probably a very inefficient way of removing certain parts of a vector, but somehow, I don't know any other way of doing this.
Quote:Original post by MadMax1992
What I always do is the following:
*** Source Snippet Removed ***
It's probably a very inefficient way of removing certain parts of a vector, but somehow, I don't know any other way of doing this.
Which is why two proper, idiomatic methods were presented for erasing elements from both sorted and unsorted vectors. Or lists, deques, etc., since these methods don't require random access [smile]
Quote:Original post by Ftn
Erasing or inserting in middle of vector invalidates all iterators, becouse vector's memory must be contiguous.
erase() only invalidates iterators at or after the point of erasure and insert() invalidates all iterators if there isn't sufficient capacity remaining for the inserted elements. If there is sufficient capacity for the inserted elements insert() will only invalidate iterators at or after the point of insertion.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
