Jump to content
  • Advertisement
Sign in to follow this  
hymerman

Erasing items from a vector whilst iterating through it.

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

Yup, that's right, it's that time again- time to answer Hymerman's simple question! I have a vector of 'Creature' objects, which I iterate through to check whether they should be dead each frame. If they are meant to be dead, they are removed from the vector. This works fine for a little while, but after about half of them are gone, the whole thing cocks up and generates a run-time error (Unhandled exception at xxx ... Access violation reading xxx). I'm sure it's something to do with the way I'm deleting creatures, though I can't figure out why it only happens after some have already been deleted... Perhaps it's because I'm not allowed to continue iterating after deleting an object, or maybe deleting one screws around with what the iterator points to, which only happens once the vector reaches half its size? Anyways, any help would be much appreciated :) Here's the offending piece of code (with irrelevant stuff removed):
// Check the status of creatures
for(std::vector<Creature>::iterator it = creatures.begin(); it!=creatures.end(); it++) {
	Creature& c = *it;

	if (c.health <= 0) {
		creatures.erase(it);
	}
}

Share this post


Link to post
Share on other sites
Advertisement
Strange... I got the idea roughly one millisecond after posting to put in a 'break;' after the erase command, and now it works fine... Is this a good way of fixing it, or is it a hack? And more importantly, why does it work? All that I have after the if statement in the actual app is an else block which won't get executed if the creature is erased anyway, and hence shouldn't generate an access violation!

Not only that, but stepping through the code, the access violation happens before the line with 'break;' on it would even be executed!

Confused!

Share this post


Link to post
Share on other sites
Erasure invalidates all current iterators - any behavior using such a stale iterator after the fact is most likely undefined. And unpredictable in this case it would seem. This is a bad thing (tm), leaving it as is, well, that's just asking for trouble.

EDIT: Actually, what you've got right now is perfectly defined behavior - the break statement means you'll just only remove at maximum 1 element at a time. This is, however, probably not what you want - if you accumulate more than 1 element before each time you call this function, you will eventually run out of memory.

Alternatives:

1) erase() returns a valid iterator to the next element.

if ( removing ) {
it = container.erase( it );
} else {
++it;
}


Notes: SLOOOW. SLOW. SLOOOOOOW. Every time erase() is called, everything preceeding that element has to be copied back once. SLOOOOOOW. It'd work much better for containers like std::list, but this is SLOOOOW. Also, making the increment of the iterator a conditional is just ugly.

2) std::remove_if.

container.erase( std::remove_if( container.begin() , container.end() , std::mem_fun_ref( &Creature::IsDead ) ) , container.end() );


Edit: Added missing brace.

Todo: Implement "bool Creature::IsDead( void )"

Notes: remove_if puts those elements at the back of the array, it does not actually erase them - it returns an iterator to the first "removed" element. This is why you also call container.erase( begin , end ), to actually chop that part off. Much less slow than #1.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The break statement escapes from the enclosing for, while, do, or switch statement, and does not escape from an enclosing if statement. Using break in an if construct causes it to end whatever loop or switch statement the if statement was inside of.

Your break statement is breaking out of your while loop.

The access violation is caused because erasing an element from a vector can invalidate iterators.

The break statement prevents the access violation because it breaks out of the loop which is using the iterators immediately after a single erase takes place.

The best way to remove the elements from the vector may be to partition the vector into elements to keep and elements to remove, putting the elements to keep in the front, then resizing the vector to only be large enough to have the elements you want to keep. The standard template library has a partitioning algorithm that can do the partitioning step for you (you need to write the predicate it uses to do the partitioning).

Share this post


Link to post
Share on other sites
since vector::erase() returns the following iterator to the element after te erased one you can just do:

if(c.health <= 0)
{
it = creatures.erase(it);
}

Share this post


Link to post
Share on other sites
Ah, excellent. Yes, I figured I was probably invalidating something somewhere along the way. Thanks MaulingMonkey, this is the second time you've helped me out this week :)

I'm going for the first option; although this is slow, the vector is relatively small (currently defaulted to 10 items, I don't anticipate it being more than 50-100), and items will not need to be erased very often. That, and the second option hurts my brain.

Share this post


Link to post
Share on other sites
Ah, and I actually did this:
if(c.health <= 0)
{
it = creatures.erase(it);
--it;
}


Since the iterator will be incremented at the beginning of the next loop anyway. Am I right in thinking that if I don't decrement it, the creature after the erased one will be skipped? I'm quite sure I'm right, but it's late and my brain's not really working as it normally does.

Share this post


Link to post
Share on other sites
Quote:
Original post by hymerman
Ah, and I actually did this:
if(c.health <= 0)
{
it = creatures.erase(it);
--it;
}


What happens if it == begin()?

First, you'll erase the first element, and assign it to the new begin() - all fine and dandy (except the part where every other creature needs to be shifted left 1 in the array, but I'm not focusing on that)

Then, you'll try to decrement before the beginning of the array.

This is undefined behavior. It may work with std::vector, but most containers have at least a good chance of blowing up in your face if you try to do this - meaning you'll suddenly get unexpected behavior just from changing container types in the future. This is a very bad thing (tm).

Sorry, but there's a reason I placed the increment in a conditional :-/.

(This is also the reason I put forth std::remove_if - I find it saner than trying to keep track of when/when not to increment stuff/having iterator advancement not part of the for loop's step statement)

Share this post


Link to post
Share on other sites
Quote:
Original post by hymermanThat, and the second option hurts my brain.

It's not that hard. Here's a quick working example
#include <list>
#include <algorithm>

class Creature
{
public:
Creature() {};
Creature(int l) { health=l; };
Creature(const Creature &o) { *this=o; };
~Creature() {};
Creature &operator=(const Creature &o) { health=o.health;return *this; };
bool IsDead() const { return (health==0); };
int health;
};

int _tmain(int argc, _TCHAR* argv[])
{
std::list<Creature> c;

c.push_back(Creature(5));
c.push_back(Creature(2));
c.push_back(Creature(0));
c.push_back(Creature(1));
c.push_back(Creature(0));
c.push_back(Creature(5));

c.erase(std::remove_if(c.begin(), c.end(), std::mem_fun_ref( &Creature::IsDead )), c.end());

return 0;
}

The part that you need to worry about is
// include list and algorithm
#include <list>
#include <algorithm>

class Creature
{
public:
// define this method in your Creature class
bool IsDead() const { return (health==0); };
};

void SomeFunctionSomewhere()
{
// implement your list of creatures as a list not a vector
std::list<Creature> c;

// use remove_if with erase
c.erase(std::remove_if(c.begin(), c.end(), std::mem_fun_ref( &Creature::IsDead )), c.end());
}

This is a faster and cleaner method.

*edit* took out that naughty "using namespace"

Share this post


Link to post
Share on other sites
Thanks again for the help above and beyond the call of duty!

Though I always prefer cleaner, more elegant solutions to problems, this won't work in my case. There are different ways a creature can die, and these different ways require different treatment, so unfortunately the problem isn't as simple as just pruning the creature vectors. Sorry, I didn't mention this :) As such, I'll have to go with the conditional advancement of the iterator (and put in some checks to avoid the undefined behaviours you speak of...). Thanks for the example though, I'll be sure to use this in future now that I know it exists :)

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!