tags:

views:

814

answers:

8

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.

+1  A: 

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.

Reed Copsey
+3  A: 

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.

1800 INFORMATION
+8  A: 

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.

John Cavan
Although `++It` would have been better...
xtofl
@xtfol It depends, though in general that's how I write it. I just happened to use his example rather than my own code, but normally I use the prefix operator when it's happening in a statement, otherwise I use either depending on the need.
John Cavan
yeah cuz, you're not trying to remove it from the vector.
bobobobo
+2  A: 

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.

Nick Bedford
Not entirely correct, the iterator would actually be a pointer to a pointer (in this case), so dereferencing it will still give you the pointer.
John Cavan
@John but when the destination type (in this case the function parameter) is a reference, the reference to the value (in this case, the pointer) is passed.
Nick Bedford
I'm not sure what you're suggesting. His original code would work fine as the vector would be declared as std::vector<ObjectType *> Vec and so the type returned by dereferencing the iterator would be an ObjectType *.
John Cavan
@John They are talking about the ramifications of a function elsewhere deleting an object that is owned by a vector. Merely deleting the pointer will leave a dangling pointer at the source (the vector).
Nick Bedford
@Nick Ah... I think I'm getting it now. To be honest, I have never seen someone try to do that kind of thing. However, like my example above, it's fine if you clear the vector immediately after the loop.
John Cavan
+1  A: 

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.

D.Shawley
There is a potential for a memory leak (not corruption) if the derived class has members because its destructor will not be called. In your current example, nothing "bad" will happen because the derived class is empty, but yeah, a class that is intended to be a base for others should declare a virtual destructor.
John Cavan
@John - That's what I had suspected. I couldn't come up with a scenario that would cause corruption. I figured that I would mention it since putting non-visible derived classes into a vector of pointers to the base has been known to cause grief.
D.Shawley
A: 

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?

ZachS
A: 

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!
}
fmuecke
A: 

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.

Vivek