Not using iterators into a resized vectors

Question

I read in The C++ Programming Language : Special Edition

Don't use iterators into a resized vector

Consider this example.

vector< int >::iterator it = foo.begin();

while ( it != foo.end() ) {
  if ( // something ) {
    foo.push_back( // some num );
  }
  ++it;
}

Is there a problem with this? After the vector was resized, would the foo.end() in the loop condition be pushed forward 1?

P.S. In addition, what if vector had reserved space for x number of ints. If push_back didn't violate this space, would it still be an issue ( I would assume so if it.end() points to one past the last element in the vector that contains something ).

Answer 1

Yes, there is a problem with it.

Any call to push_back has the potential to invalidate all iterators into a vector.

foo.end() will always retrieve the valid end iterator (which may be different to the value last returned by foo.end()), but it may have been invalidated. This means that incrementing it or comparing it may caused undefined behaviour.

Answer 2

Yes, there's a problem. Regardless of foo.end(), it may be invalidated by the push_back(). Edit: (i.e. it's not just that the end could change; it's possible that the whole buffer for the vector may be reallocated, so all iterators become invalid).

Answer 3

Yes, there's a problem with that. push_back invalidates any iterators for the vector you called it on. So after calling push_back, it is not even legal to execute ++it. This is a case of undefined behavior, so it may sometimes work and it may sometimes fail but you should never rely on it working.

Answer 4

As others have said, the push_back() may invalidate all iterators to the vector. The reason for this is that the data in a vector is stored in a region of contiguous memory. If the push_back() or any other operation that resizes the vector causes the size of the vector to go over the capacity of the allocated region that region will be reallocated and end up at a different place in memory, while all the iterators will still be referencing the old memory region.