Sign in to follow this  
Sean_Seanston

Erasing all appropriate elements from a vector

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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();
}
}

Share this post


Link to post
Share on other sites
You either erase or increment at for loop, not both.

//Remove out of bounds player projectiles
for ( 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.

Share this post


Link to post
Share on other sites
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.

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?

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
What I always do is the following:

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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this