What is the lifetime and validity of C++ iterators ?

Question

I'm planning to implement a list of Things in C++ where elements might be removed out of order. I don't expect that i'll need any kind of random access (i just need to sweep the list periodically), and the order of items isn't important either.

So I thought of std::list<Thing*> with this->position = insert(lst.end(), thing) should do the trick. I'd like the Thing class to remember the position of each instance so that i can later easily do lst.erase(this->position) in constant time.

However, i'm still a bit new to C++ STL containers, and i don't know if it's safe to keep iterators for such a long time. Especially, given that there will be other elements deleted ahead and after the inserted Thing before it's gone.

Answer 1

In list all iterators remain valid during inserting and only iterators to erased elements get invalid during erasing.

In your case keeping iterator should be fine even when other elements deleted ahead and after the inserted Thing*.

EDIT:

Additional details for vector and deque:

Vector:

• inserting --- All iterators get invalid if reallocation happens, otherwise its valid.
• erasing ---- All iterators after erase point get invalid.

deque:

• inserting --- All iterators get invalid.
• erasing ---- All iterators get invalid.

Answer 2

This depends on the container you use.

Check: http://www.sgi.com/tech/stl/
Look at each containers documentation at the end their will be a description on the conditions that iterators stay valid under.

For std::list<> they remain valid under all conditions until the element they actually refer to is removed from the container (at this point they are invalid).