Consider the following code example:

vector<int> v;

// Add some elements
for(int i=0; i<10; ++i)
  v.push_back(i);

int* my_favorite_element_ptr = &v[3];
cout << "My favorite element = " << (*my_favorite_element_ptr) << endl;
cout << "Its address = " <<  my_favorite_element_ptr  << endl;

cout << "Adding more elements…"<< endl;

// Adding more elements
for(int i=0; i<100; ++i)
  v.push_back(i*10);

cout << "My favorite element = " << (*my_favorite_element_ptr) << endl;
cout << "Its address = " <<  &v[3]  << endl;

What’s going on here? We create a vector containing 10 elements, and for some reason decide to save for later a pointer to element with index 3. Then we add more elements to the vector and try to reuse the pointer we’ve acquired before. What is wrong with this code? Let’s look at the output it produces:

My favorite element = 3 Its address = 0x1001000cc
Adding more elements
…
My favorite element = 3
Its address = 0x10010028c

Note that after we add more elements to the vector, the address of the element &v[3] has changed! The problem is that when we add new elements to the vector, the existing elements might move to a totally different location.

Here is how such code works. When we create a vector, it allocates by default some number of elements (usually about 16). Then if we try to add more elements than the capacity allows, the vector allocates a new, larger array, copies existing elements from the old location to a new one, and continues to add new elements until the new capacity is exceeded. The old memory is deallocated, and might be reused for other purposes.

Meanwhile, our pointer still points to the old location, which is now in the deallocated memory. So what would happen if we continue to use it? If no one has reused that memory yet, we might get “lucky” and not notice anything, as in the example above. Even in this best-case scenario, though, if we write (assign a value) into that location, it will not change the value of the element v[3] because it is already located elsewhere.

If we are less lucky and that memory was reused for some other purpose, the consequences could be pretty bad, ranging from changing an unrelated variable that was unlucky enough to occupy the same place, to a core dump.

The preceding example deals with a pointer. The exact same thing happens when you do it using a reference; for example, instead of:

int* my_favorite_element_ptr = &v[3];

suppose one writes:

int& my_favorite_element_ref = v[3];

The result would be exactly the same. The reason is that the reference is just a “dereferenced pointer.” It knows the address of a variable, but does not require an asterisk in front of the variable to reach the memory to which it points. So the syntax is different, but the result is the same.

And finally, the same thing is true when we use iterators. Consider the following example:

  vector<int> v;

  for(int i=0; i<10; ++i)
    v.push_back(i);

  vector<int>::const_iterator old_begin = v.begin();

  cout << "Adding more elements … "<< endl;

  for(int i=0; i<100; ++i)
    v.push_back(i*10);

  vector<int>::const_iterator new_begin = v.begin();
  if(old_begin == new_begin)
    cout << "Begin-s are the same." << endl;
  else
    cout << "Begin-s are DIFFERENT." << endl;

As you have probably already guessed, the output of this program is:

  Adding more elements ...
  
  Begin-s are DIFFERENT.

So if you were holding an iterator to some element (any element, not necessarily the one to which begin() points), it might be invalid after changing the contents of the vector because the internal array, and correspondingly the iterator begin(), might have moved to some other place.

Therefore, any pointers, references, or iterators pointing to the elements of a vector obtained before modifying the vector should not be used after one modifies the vector by adding new elements. Actually, the same is true for almost all STL containers and all operations modifying the size of the container, e.g., adding or removing elements. Some containers, such as hash_set and hash_map, do not formally belong to the STL, but they are STL-like, will probably be part of STL soon, and behave the same way as STL containers in the situation discussed in here: the iterators become invalid after modifying a container. And even if you are using an STL container that would preserve the iterator to its element after the addition or removal of some other elements, the whole spirit of the STL library is that one could replace one container with another and the code should continue to work. So it is a good idea not to assume that the iterators are still valid after any STL or STL-like container is modified.

Note that in the previous example we modified the container inside the same thread we used to access the pointer. The same and even more problems could be created if you hold a pointer, reference, or iterator in one thread while modifying the container from another thread, but as mentioned in the Preface, the discussion of multithreading is outside the scope of this book.

Interestingly, in the preceding example, the index would work where the pointer failed: if you have marked your element by holding a zero-based index to it (in the first example, something like int index_of_my_favorite_element = 3), the example would continue to work correctly. Of course, using an index is slightly more expensive (slower) than using a pointer because in order to access an element corresponding to this index, a vector must do some arithmetic, i.e., calculate the address of the variable every time you use the [] operator. The advantage is that it works. The disadvantage is that it works only for vectors. For all other STL containers, once you’ve modified the container, you must find the iterator pointing to the element you need again.

Rule for this chapter to avoid errors with invalid pointers, references, and iterators: