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

31
votes

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.

5
c++visual-c++vectoriteratorerase
Please tag your questions with the language/environment you are using so we know what you are using from the main page (and you will get many more views). - Zifre
But you don't know what he is doing with the vector in the rest of his code! In general, a vector should be the first choice container, other things being equal. - anon
In general, you should prefer STL algorithms to hand-written loops. - rlbond
I agree that this specific situation calls for a list, but without a priori knowledge of what else needs to be done with this loop, it's hard recommending moving to a list right now. The STL algorithm code I suggested is O(n). An explicit loop + list is also O(n), but you give up locality of reference and random access, which is a big deal and I would suggest trying to avoid that if possible. I disagree that the algorithm is less clear. It consists of a simple functor and three steps. If a programmer knows how to use <algorithm>, and really, every c++ programmer should, it is easy to read. - rlbond
Why for the f*** sake there is no simple "remove (Element)" method, instead everywhere we have to put this dumb begin() and end() calls? - luke1985

5 Answers

41
votes

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;
   }
}
11
votes

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).

2
votes
if((*it)->getXPos() > 1.5f)
{
   delete *it;
   it = Entities.erase(it);
}
0
votes

Once you modify the vector, all outstanding iterators become invalid. In other words, you can't modify the vector while you are iterating through it. Think about what that does to the memory and you'll see why. I suspect that your assert is an "invalid iterator" assert.

std::vector::erase() returns an iterator that you should use to replace the one you were using. See here.

0
votes

The main problem is that most stl container iterators do not support adding or removing elements to the container. Some will invalidate all iterators, some will only invalidate an iterator that is pointing at an item that is removed. Until you get a better feeling for how each of the containers work, you will have to be careful to read the documentation on what you can and can't do to a container.

stl containers don't enforce a particular implementation, but a vector is usually implemented by an array under the hood. If you remove an element at the beginning, all the other items are moved. If you had an iterator pointing to one of the other items it might now be pointing at the element after the old element. If you add an item, the array may need to be resized, so a new array is made, the old stuff copied over, and now your iterator is pointing to the old version of the vector, which is bad.

For your problem it should be safe to iterate through the vector backwards and remove elements as you go. It will also be slightly faster, since you wont be moving around items that you are going to later delete.

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