In this article we will discuss the iterator invalidation with respect to std::vector in C++.

What is Iterator Invalidation?

An Iterator becomes invalidate when the container it points to changes its shape internally i.e. move elements from one location to another and the initial iterator still points to old invalid location.

Iterator invalidation in vector happens when,

  • An element is inserted to vector at any location
  • An element is deleted from vector.

Iterator Invalidation Example on Element Deletion in vector:

Suppose an iterator ‘it’ points to a location x in the vector. Now suppose some deletion happens on that vector, due to which it move its elements from one location to another. Now if initial iterator ‘it’ still points to old location then it becomes invalidated.

For example, in the below code we are deleting an element from vector using erase function. This erase function invalidates the current pointer. So if after calling the erase() function , if one uses the same invalidated iterator then it can result in undefined behavior.

Now, how to fix this ?

Solution:

After calling the erase function update the value of iterator ‘it’ i.e.

As, erase() function returns an iterator pointing to the new location of the element that followed the last element erased by the same function. Also, if the element deleted was the last element of the container then it returns the end of the container.

Iterator Invalidation Example on Element Insertion in vector:

When a new element is inserted in vector then it internally shifts its elements and hence the old iterators become invalidated.

Reasons for element shift are as follows,

  • If element is inserted in between then it shift all the right elements by 1.
  • If the new size of vector is more than its current capacity, then it relocates a bigger chunk of memory and copies all the elements there.

Therefore, when a new element is inserted in vector then its old iterator can become invalidated. Using this old invalidated iterators can result in undefined behavior i.e.

Now, how to fix this ?

Solution:

After calling the insert function update the value of iterator ‘it’ i.e. by re-assigning it.

 

Thanks.

 

Click Here to Subscribe for more Articles / Tutorials like this.