32

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.

Tony R
  • 11,224
  • 23
  • 76
  • 101
  • 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 Jun 13 '09 at 19:31
  • 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. –  Jun 13 '09 at 20:11
  • 2
    In general, you should prefer STL algorithms to hand-written loops. – rlbond Jun 13 '09 at 20:36
  • 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 , and really, every c++ programmer should, it is easy to read. – rlbond Jun 13 '09 at 21:16
  • 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 Mar 16 '14 at 19:24

5 Answers5

43

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;
   }
}
elcortegano
  • 2,444
  • 11
  • 40
  • 58
  • 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? – Tony R Jun 13 '09 at 20:02
  • 4
    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. –  Jun 13 '09 at 20:05
  • 1
    @Gman I think you mean dreference the iterator, not the pointer. –  Jun 13 '09 at 20:07
  • Why aren't you just iterating backwards by index? – Tara Nov 11 '19 at 20:37
11

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

rlbond
  • 65,341
  • 56
  • 178
  • 228
  • 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. – rlbond Jun 13 '09 at 20:11
  • 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. – rlbond Jun 13 '09 at 20:25
  • I think your O(n) calculations are a bit off. –  Jun 13 '09 at 20:27
  • 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. –  Jun 13 '09 at 20:30
  • 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). – rlbond Jun 13 '09 at 20:33
  • And while I disagree with with what you say, I will defend to the death your right to say it! – rlbond Jun 13 '09 at 20:42
  • 1
    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* – Todd Gardner Jun 13 '09 at 21:04
  • 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. – rlbond Jun 13 '09 at 21:09
  • Why not use remove_if instead of foreach+remove – leiz Jun 14 '09 at 01:55
  • @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. – rlbond Jun 14 '09 at 02:43
  • 1
    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). – Ari Jun 14 '09 at 07:35
2
if((*it)->getXPos() > 1.5f)
{
   delete *it;
   it = Entities.erase(it);
}
lhahne
  • 5,909
  • 9
  • 33
  • 40
0

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.

i_am_jorf
  • 53,608
  • 15
  • 131
  • 222
  • erase actually only invalidates iterators pointing to the erased item and elements after, iterators pointing to lower elements are not invalidated. – Dolphin Jun 13 '09 at 20:08
0

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);
  }
}
Dolphin
  • 4,655
  • 1
  • 30
  • 25
  • 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. – rlbond Jun 13 '09 at 21:52
  • 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. – Dolphin Jun 14 '09 at 01:39