Take the 2-minute tour ×

What are recommended methods of avoiding errors, when iterating through a vector; where any number of elements in the vector may (directly, or indirectly) cause insertions or removals of elements - invaliding the iterators?

Specifically, I'm asking in relation to games programming, with elements in the vector being game objects; some of which can spawn other objects, and some of which will be killed and need removed when they are updated. Because of this, reserving a large capacity before iteration is also not possible, as it's entirely unknown how many elements can be expected to be added.

share|improve this question
Use std::list? –  Joachim Pileborg Dec 10 '12 at 13:24
It would definitely avoid the problem, but losing the performance characteristics of the vector means it's not particularly viable in this case. –  Bilkokuya Dec 10 '12 at 13:52

5 Answers 5

up vote 2 down vote accepted

It's not possible to say in general. Part of the reason that the iterators are invalidated is that there's no way to read your mind to know what element you would like the invalidated iterators to refer to.

For example, I have an iterator to element 3 of 5. I erase element 2. Should the iterator point to the new element 2 (because it's "the same value moved down"), or should it point to the new element 3 (because it's "the same element of the vector with a different value moved down into it")?

Practically, your options are:

  1. Do not insert/erase elements while someone else has iterators. This means altering your code to make the changes at another time.
  2. Use indexes instead of iterators. This results in the second option above ("index refers to the same element with a new value"). Beware that indexes can also become invalid, if you erase enough elements that the index is off the end.
  3. Use a different data structure with different iterator invalidation rules. For example a std::list would give you the first option above ("iterator refers to the same element in a new position")

The iterator that you're using to iterate should never be harmfully invalidated by insertions/erases of a single element at that position. It is invalidated, but both functions return a new iterator that you can use to continue iterating. See their documentation for what element that new iterator refers to. That's why the problem only arises when you're using multiple iterators on the same container.

share|improve this answer
Just to clarify, is the iterator returned by insertion always valid; even if the vector reallocates? –  Bilkokuya Dec 10 '12 at 13:54
@Bilkokuya: yes. –  Steve Jessop Dec 10 '12 at 14:03

Here are some ideas:

  1. Iterate over the vector using an integer index. This won't get invalidated, but you need to take care to adjust the current index when inserting/removing elements.
  2. Iterate over a copy of the vector.
  3. Instead of making changes to the vector as you go along, keep track of what needs to be inserted/removed, and apply the changes after you've finished iterating.
  4. Use a different container, for example a linked list.
share|improve this answer

Vector might not be the best container to support intensive insertion/removal (especially when the size is large). But if you have to use vector, IMHO the safest way would be to work not with an iterator but with an index and keep track (and adjust the index) of items being inserted/deleted before the current position. This way you will at least avoid problems with reallocations.

And recalculate v.size()/v.end() after each iteration.

share|improve this answer

Use a separate vector and std::move the elements which don't get removed to it along with any created new elements. Then drop the old vector.

This way you don't have to remove/insert anything from/to the original vector and the iterators don't get invalidated.

share|improve this answer

You can, of course, go around the problem by using a container that doesn't invalidate the iterators on insertion and removal.

I'd like to recommend a different approach. Essentially you're iterating over the vector to create a new state in the game world. Instead of changing the state of the world as you traverse the vector, store what needs to change in a new vector. Then, after you've completely examined the old state, apply the changes you stored in the new vector.

This approach has one conceptual advantage: every object's new state depends on the old state only. If you apply the changes as you traverse the old state, and decisions about one object can depend on other objects, the order of traversal can affect the outcome, which can give "earlier" or "later" objects an unfair advantage.

share|improve this answer

Your Answer


