Sign in to follow this  
zer0sum

Why does erasing from this vector crash my program?

Recommended Posts

I have pinpointed a crash to this bit of code.
               for(vector<Projectile*>::iterator Iter = ProjectileList.begin(); Iter != ProjectileList.end(); ++Iter)
               {
                    (*Iter)->Move(deltaT);
                    if (!(*Iter)->inBounds())
                    {
                       Projectile* temp = (*Iter);
                       ProjectileList.erase(Iter);
                       delete temp;
                    }
               }
If a projectile misses and moves out of bounds, then I want to delete it from my vector tracking the projectiles. I believe the crash occurs when I delete the last element of the vector, but I'm not sure. Who can enlighten me on the proper use of Vectors?

Share this post


Link to post
Share on other sites
The canonical loop for erasing while iterating over a vector looks like:

for (iterator i = vec.begin(); i != vec.end()) {
if (condition(i)) {
i = vec.erase(i);
} else {
++i;
}
}

Share this post


Link to post
Share on other sites
Thanks, that did it. Not sure why. I guess the elements are all shifted when I delete, so I shouldn't increment the iterator. If I do, then I'll increment into some undefined slot or something.

Anyway, code works now. Thanks.

Share this post


Link to post
Share on other sites
erasing from a vector invalidates all its iterators. Therefore after "ProjectileList.erase(Iter);" Iter is no longer valid.

That's why you need to reacquire a new one as shown in "no such user" sample.

Share this post


Link to post
Share on other sites
template <class T, class Pred> 
void EraseRemoveIf(vector<T>& vec, Pred pred)
{
vec.erase(remove_if(vec.begin(), vec.end(), pred), vec.end());
}
You can modify it to work with general iterator ranges instead of vectors if you like. See erase-remove idiom for more information.

[Edited by - Ariste on April 26, 2010 8:30:23 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by voodoohaust
erasing from a vector invalidates all its iterators.

Nope, invalidates all iterators AFTER the point of erasure. The problem is then that itor (which is still valid, as it points to where the erased element WAS, and hence is not AFTER the point of erasure) might equal end() and hence will be incremented by the for loop (which is illegal). A minor semantics issue, but a relatively important one to be sure.

Share this post


Link to post
Share on other sites
Erasing elements one-by-one from a vector is O(n*n). I suggest the following O(n) alternative:

#include <algorithm>
#include <functional>

std::for_each(
ProjectileList.begin(),
ProjectileList.end(),
std::bind2nd(
std::mem_fun(&Projectile::move),
deltaT
)
);

ProjectileList.erase(
std::remove_if(
ProjectileList.begin(),
ProjectileList.end(),
std::not1(
std::mem_fun(&Projectile::inBounds)
)
),
ProjectileList.end()
);

Share this post


Link to post
Share on other sites
Whoops, didn't see the delete...

template<class T>
struct delete_functor
{
void operator()(T* p)
{
delete p;
}
};

std::for_each(
ProjectileList.begin(),
ProjectileList.end(),
std::bind2nd(
std::mem_fun(&Projectile::move),
deltaT
)
);

std::vector<Projectile*>::iterator it = std::partition(
ProjectileList.begin(),
ProjectileList.end(),
std::mem_fun(&Projectile::inBounds)
);

std::for_each(
it,
ProjectileList.end(),
delete_functor<Projectile>()
);

ProjectileList.erase(it, ProjectileList.end());


It's starting to become a little silly even to my trained STL eyes, though. Just use a vector of smart pointers with my first solution ;)

[Edited by - DevFred on April 27, 2010 2:00:01 PM]

Share this post


Link to post
Share on other sites
or just wrap it all up in a single predicate...

projectiles.erase(std::remove_if(projectiles.begin(), projectiles.end(), [delta](Projectile* p) -> bool {
p->move(delta);
if(!p->inBounds()) {
delete p;
return true;
}
return false;
}),
projectiles.end()
);

Share this post


Link to post
Share on other sites
If you take advantage of C++0x features, you might as well go ahead and use a std::vector<std::unique_Pointer<Projectile>> ;-)

Share this post


Link to post
Share on other sites
I would make a separate named function for the update process - it seems important enough. And why not use a boost::ptr_vector<Projectile>? :) It seems clear that the purpose of the pointers here is to indirect for polymorphism, so that's the natural fit IMO.


struct Update {
float interval;
Update(float interval): interval(interval) {}
bool operator()(Projectile& p) {
p.Move(interval);
return !p.inBounds();
}
};

// ...
typedef boost::ptr_vector<Projectile> projectiles_t;
projectiles_t projectiles;

// ...
projectiles_t::iterator begin = projectiles.begin(), end = projectiles.end();
projectiles.erase(std::remove_if(begin, end, Update(deltaT)), end);



Writing things this way separates responsibilities: updating an object vs. applying the removal algorithm vs. memory management.

Share this post


Link to post
Share on other sites
I find predicates with side-effects disturbing, but maybe that's just the Haskell part of my brain speaking :)

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