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.

Runyan

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

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. – Awoke

In general, you should prefer STL algorithms to hand-written loops. – Atomy

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. – Atomy

Why for the f*** sake there is no simple "remove (Element)" method, instead everywhere we have to put this dumb begin() and end() calls? – Superfine

Answer 1

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

Awoke

Seems to work, although I wonder what is the difference between this and Keand64's answer? vector::erase() claims to call the object's destructor, so is the "delete * it;" necessary? – Runyan

Pointers do not have destructors. The destructor for the thing in the vector would only be called if it were a collection of Entity values. So the call to delete is essential if you wish to avoid a memory leak. – Awoke

@Gman I think you mean dreference the iterator, not the pointer. – Awoke

Why aren't you just iterating backwards by index? – Erasion

Answer 2

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

Atomy

I wasn't done, and wrote that the code on the top is if the pointers don't need to be deleted. Sometimes you want a container of pointers with shared ownership. – Atomy

Gman -- all the code in the answers above have two loops too. You just don't see the loop inside vector::erase(). What's worse, those two loops are nested. – Atomy

I think your O(n) calculations are a bit off. – Awoke

And I disagree with everything you said justifying your code. There is no "proper" STL way, only ideas put forward by certain authors. and the compilation speed will be totally compiler dependent. – Awoke

How so? for_each is O(n), erase is O(n), and remove is O(n), and they're sequential, meaning the entire operation is O(n). In your code, your loop is (obviously) O(n), but vector::erase() is linear in the number of elements after the erased element. This is an O(n) operation as well. That gives a final complexity of O(n^2). There are, of course, ways to get around this in your loop. But as it stands, it's O(n^2). – Atomy

And while I disagree with with what you say, I will defend to the death your right to say it! – Atomy

First, a templated deleter functor makes this code more generic (and every code base should have one of those anyway, they are useful in a lot of situations). But second, you should be careful to do a two pass approach; you are leaving invalid pointers in the array while deleting the other elements. If one of the objects destructors accesses the array -> kaboom – Ugo

That's a good point, Todd. In those cases this wouldn't work, however I would consider that a very unlikely possibility. And yes, a templated deleter is useful. The code could be written using Boost.Bind to make it a bit shorter too. I think the most important thing is to make more people aware of STL programming. – Atomy

Why not use remove_if instead of foreach+remove – Wellstacked

@leiz: you could do that, if the functor deleted the pointer first. I hadn't thought of that and I guess it's ok, but you'd have to be careful. – Atomy

I like this solution because: 1. It's O(n) vs O(n^2). 2. It is the "proper" way in the sense that it pushes as much of the logic as possible into the STL implementation, which is presumably well tested and debugged. 3. The remove_if approach, while faster, conflates the removal condition with the removal action, i.e., the functor deletes the object as a side effect of testing it. Not desirable in terms of readability/maintainability. Also, functors with actions are more likely to have a state (not the case here, though), making them unsuitable as predicates (see Josuttis pp. 302). – Vernal

Answer 3

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

Hematite

This is incorrect, because the iterator returned from erase() gets incremented after the erase. – Awoke

I don't see any loop here – Aec

Answer 4

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.

Bust

erase actually only invalidates iterators pointing to the erased item and elements after, iterators pointing to lower elements are not invalidated. – Batten

Answer 5

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

Batten

While backwards iteration is clever, you are going to run into two problems. First, vector::erase() invalidates all iterators, so your code above uses an invalid iterator. But, the more pressing problem is that vector::erase() doesn't accept a reverse_iterator! The code you've written above shouldn't compile. – Atomy

hmmm, erase not taking a reverse_iterator could be a problem :) But, erase doesn't invalidate iterators pointing to elements before the element erased. Either way, fixed with compiling and working code. – Batten

Answer 6

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.

Digger