Sign in to follow this  
zer0sum

Why does erasing from this vector crash my program?

Recommended Posts

zer0sum    100
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
no such user    280
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
zer0sum    100
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
voodoohaust    122
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
Ariste    296
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
Washu    7829
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
DevFred    840
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
DevFred    840
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
Washu    7829
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
Zahlman    1682
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

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