CODEWITHSUNDEEP
c++visual-c++vectoriteratorerase
Tony R
Tony R

Reputation: 11524

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

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.

Upvotes: 32

Views: 90851

Answers (6)

AbePralle
AbePralle

Reputation: 992

Here's an alternative approach that, while unorthodox, is practical and efficient:

  1. Iterate through the vector, reading each Entity from a read index (the normal loop counter) and then either deleting it or writing it back to the vector at a separate write index that only gets incremented when a writeback occurs.
  2. At the end of the loop the write index will be the count of surviving entities, so you can .resize() the vector to that.
  3. Complexity is O(n).
uint32_t write_i = 0;
for (uint32_t read_i=0; read_i<Entities.size(); ++read_i)
{
  Entity* cur = Entities[read_i];
  if (cur->getXPos() > 1.5f)
  {
    delete cur;
  }
  else
  {
    Entities[write_i++] = cur;
  }
}
Entities.resize( write_i );

The caveat is that nothing called from within the loop can reliably iterate over the same vector, since there may be duplicate entries until the loop is finished and the vector is resized.

Upvotes: 0

anon
anon

Reputation:

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

Upvotes: 43

Dolphin
Dolphin

Reputation: 4762

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);
  }
}

Upvotes: 0

rlbond
rlbond

Reputation: 67749

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

Upvotes: 11

lhahne
lhahne

Reputation: 6029

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

Upvotes: 2

i_am_jorf
i_am_jorf

Reputation: 54600

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.

Upvotes: 1

Related Questions