How to erase & delete pointers to objects stored in a vector?


Question

I have a vector that stores pointers to many objects instantiated dynamically, and I'm trying to iterate through the vector and remove certain elements (remove from vector and destroy object), but I'm having trouble. Here's what it looks like:

    vector<Entity*> Entities;
    /* Fill vector here */
    vector<Entity*>::iterator it;
    for(it=Entities.begin(); it!=Entities.end(); it++)
        if((*it)->getXPos() > 1.5f)
            Entities.erase(it);

When any of the Entity objects get to xPos>1.5, the program crashes with an assertion error... Anyone know what I'm doing wrong?

I'm using VC++ 2008.

1
30
6/13/2009 7:34:41 PM

Accepted Answer

You need to be careful because erase() will invalidate existing iterators. However, it will return a new valid iterator you can use:

for ( it = Entities.begin(); it != Entities.end(); ) {
   if( (*it)->getXPos() > 1.5f ) {
      delete * it;  
      it = Entities.erase(it);
   }
   else {
      ++it;
   }
}
40
3/25/2019 4:29:56 PM

The "right" way to do this is using an algorithm:

#include <algorithm>
#include <functional>

// this is a function object to delete a pointer matching our criteria.
struct entity_deleter
{
    void operator()(Entity*& e) // important to take pointer by reference!
    { 
        if (e->GetXPos() > 1.5f)
        {
            delete e;
            e = NULL;
        }
}

// now, apply entity_deleter to each element, remove the elements that were deleted,
// and erase them from the vector
for_each(Entities.begin(), Entities.end(), entity_deleter());
vector<Entity*>::iterator new_end = remove(Entities.begin(), Entities.end(), static_cast<Entity*>(NULL));
Entities.erase(new_end, Entities.end());

Now I know what you're thinking. You're thinking that some of the other answers are shorter. But, (1) this method typically compiles to faster code -- try comparing it, (2) this is the "proper" STL way, (3) there's less of a chance for silly errors, and (4) it's easier to read once you can read STL code. It's well worth learning STL programming, and I suggest you check Scott Meyer's great book "Effective STL" which has loads of STL tips on this kind of stuff.

Another important point is that by not erasing elements until the end of the operation, the elements don't need to be shuffled around. GMan was suggesting to use a list to avoid this, but using this method, the entire operation is O(n). Neil's code above, in contrast, is O(n^2), since the search is O(n) and removal is O(n).


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon