The dangers of iterators

When working with STL containers we generally use iterators to access, manipulate and enumerate the contents. This almost becomes second nature and it’s very easy to go on auto-pilot and end up coding an innocuous looking bit of code that can contain a rather nasty surprise. This little quiz shows just one example of how such a surprise might come back to bite you.

Question: What’s wrong with this code?

typedef std::vector vec_t;
vec_t v(100);
vec_t::const_iterator i = v.begin() + 50;
v.push_back(5);
(*i) = 5;

Answer: We’re trying to dereference an (almost certainly) invalid iterator.

Why?

When we create vector v it is pre-sized with 100 elements. Line 3 gets an iterator to the 51st element (begin + 50). We then add something to the vector and after that use the iterator to change the 51st element to have the value 5. So, what’s the problem?

The problem is that when we add a new item to the vector there is a chance its internal memory will need to be reallocated. This is because when we originally created the vector we asked for 100 items and by adding another item the vector will need space for 101 items. The only way it can make this space is by allocating more memory.

So far so good. The problem is that the C++ Standard guarantees the internal memory layout of a vector has to be compatible with the memory layout of a C style array. This means that when a vector needs to allocate more memory it needs to completely replace its internal buffer with a completely new on. Our iterator references the original buffer, which is semantically the same as having a dangling pointer – oops!

To avoid this memory reallocation, we could have reserved more memory for the vector before starting to manipulate it. Providing the manipulations don’t cause the internal memory to be reallocated the iterator will not be invalidated.

typedef std::vector vec_t;
vec_t v;
v.reserve(200); // reserve enough memory for 200
v.size(100); // pre-size vector to contain and use the memory for 100 items
vec_t::const_iterator i = v.begin() + 50;
v.push_back(5); // now we're using memory for 101 items out of 200
(*i) = 5; // since there was no memory reallocation necessary this is now safe