c++ std vector - invalidated iterator question

Question

I have a standard vector of pointers.

Under what circumstances might an iterator into this vector become invalidated?

I have reason to believe that when an object is deleted, any vector iterator referencing it is thereby invalidated. This does not seem correct to me, however. I do believe this would be the standard behavior of containers in Managed .NET, but this seems off to me in c++.

for (It = Vec.begin(); It != Vec.end(); It++){
  GoToOtherCode((*It));
}

function GoToOtherCode (ObjectType* Obj){
  delete Obj;
}

Should this invalidate the Iterator It? It doesn't seem to me that it should not, but then I'm stuck with a difficult issue to debug! (I'm scared of my workaround -- to iterate through the vector with via integer-index. (This works fine... I'm just afraid of why the above is causing invalidation issues).

Thanks in advance for your time.

Edit: Thanks for the advice. The general consensus is that the above code is dangerous, but that it will not invalidate the Iterator. I believe I encountered an error with Visual Studio 2008 debugger, because after opening the project the next day, this invalidate issue was gone. So -- as with many things in computers, if nothing else seems to work, try resetting the thing.

Answer 1

It won't invalidate the iterator, it's actually the way you would delete heap allocated objects that are owned by the vector, the clear() method won't do that for you. This is pretty common:

for (It = Vec.begin(); It != Vec.end(); It++)
  delete *It;

Vec.clear();

Perfectly fine if you don't attempt to use what you just deleted.

Answer 2

It doesn't invalidate the iterator, but the pointer itself is left pointing to the now deleted object, so really you would need to do something to make sure your code does not trip up on the now dangling pointer. For example, you could set the pointer to a null value, or use erase to remove the deleted item from the vector.

Answer 3

An iterator dereference *iter returns a reference if I'm not mistaken, so you could instead have the function receive a pointer-reference. This is probably not the best way to go about it, however.

for(It i = vec.begin(); i != vec.end(); i++)
{
    GoToOtherCode(*i);
}

void GoToOtherCode (ObjectType *& pref)
{
    // This *should* set the iterator's copy of the pointer to null
    delete pref;
    pref = 0;
}

Then you could check for nulls in your vector. Warning: untested code.

Answer 4

This shouldn't invalidate your iterator - but...

The danger here is that, although you've deleted your ObjectType instance, your Vec vector still contains a pointer to the original memory location. The Vector doesn't know that the instance has been deleted.

The vector itself should be fine - it'll just be pointing to a lot of locations that are no longer valid.

Answer 5

One thing that could cause some weirdness (and maybe corruption as well) is deleting a pointer to an instance to a class that derives from one that doesn't have a virtual destructor. I don't know if anyone has ever seen this cause corruption or not, but I can imagine it causing issues. I'm thinking of something like:

//----- base.h -----
// nothing declared as virtual here!!
class Base {
public:
  Base();
  ~Base();
};
Base* getPointer();

//----- derived.cpp -----
class Derived: public Base {
public:
  Derived();
  ~Derived();
};
Base* getPointer() {
    return new Derived();
}

//----- main.cpp -----
#include "base.h"
#include <vector>
int main() {
  std::vector<Base*> v;
  v.push_back(getPointer());
  for (std::vector<Base*>::iterator i=v.begin(); i!=v.end(); ++i) {
    delete *i; // Derived::~Derived() is not invoked here
  }
  v.clear();
  return 0;
}

This probably isn't the case, but I figured that I would mention it just in case.

Answer 6

As others have mentioned, when you call delete on the iterator, you remove the data it points to, but not the pointer itself. You should make sure that you set the pointer itself to NULL, or use the erase method on the vector to get rid of the pointer.

Problems can arise if your container is a container of pointers. You've just deleted a pointer to the pointer, but now what? How do we access or free that memory?

Answer 7

The iterator will not be invalidated (unless you modify the element order).

But I do have two other suggerstions/best practices:

1. Use pre-increment istead of post-increment to iterate through your vector. Post-increment will always create a temporary copy of your current element, which can be expensive! (well for pointers it does not matter..., but you should just always use pre-inc!).
2. Don't use a vector of plain pointers. Use a vector of reference counting smart-pointers. shared_ptr will be included in C++0x and nearly all current c++ implementations (VC8, gcc, intel, ...) already have it (it's also available trough boost). The smart pointer owns the object and therefore observes its lifetime (deletes it if not needed anymore. So you don't need to take care...

The performance impact is very minimal (just one level of calling indirection)..

typedef vector<shared_ptr<ObjectType> > MyObjVector;
MyObjVector Vec;

for (It = Vec.begin(); It != Vec.end(); ++It)
{
  GoToOtherCode(*It);
}

function GoToOtherCode (shared_ptr<ObjectType>& PObj)
{
  // no delete needed!
}

Answer 8

Actually iterator invalidates when the vector reallocation takes place. During initialization of vector , it actually reserves some memory initially but when you this memory is all used up by the vector , the whole of vector is reallocated int he memory and thus invalidating all the iterators.