STL Annoyance

If you are using the std::vector or std::deque containers and want to obtain an iterator to a location in your container, don't even think about doing this:



Or this:



So, you can't obtain a valid iterator if you try to obtain it before your container has any items. You also can't obtain a valid iterator if you obtain it while your container has an item, but then you add more items to it and try to use the original iterator afterward.

What gives?

Calls to insert() (or push_back()) when size() == capacity() will force the container to reallocate its memory (they double in size). A new block of memory is allocated and then the old block is copied to the new block, and the old block deleted. This is bad news if you've obtained an iterator to an item in the old block of memory because it still points there, but the data is no longer there.

It should be obvious why calls to reserve() have the same effect.

So, what can you do?

• Don't use an iterator obtained prior to a call to insert() or reserve()  on your std::vector or std::deque
• Keep the iterator updated

Keeping the iterator updated:



Note how the address of our iterator never changes, but the address of the item it points to does change. Therein lies the heart of the matter: When these containers reallocate memory, the data gets moved, but nobody tells the iterators to those pieces of data.

It should also be noted that calls to erase() invalidate any iterators that point to data positioned after the element(s) being erased. The reason should be obvious, as the data is no longer in the same location.

Moral of the story: Don't use an iterator that was obtained prior to calls on your std::vector or std::deque that will cause them to allocate or deallocate memory. Doing so will invalidate your iterators, and using them will yield undefined behavior, which is a nice way of saying "Garbage data at best, An explosion at worst."

For a full explanation of when your iterators will be invalidated (there's more situations than I've listed), consult chapter 23 of the Official C++ Standard (search for all occurrences of the word "valid"):