Iterator Invalidation in C++

There are many cases in which our iterator gets invalidated while we iterate any container. This can be due to many reasons including the change in size or shape of the container while iterating. So one should be careful while using them in C++. So in this article, we will learn about iterator invalidation and how to prevent it in C++.

What is Iterator Invalidation?

Iterator Invalidation happens when the container to which an iterator is pointing changes its size since this leads to change in the location of the element while the iterator still points to the old invalid location.

Program to understand iterator invalidation in C++

#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<int>a{3,6,9,5,7};

    // updating vector while iterating
    // this will cause iterator invalidation
    for(auto it=a.begin();it!=a.end();it++)
        if((*it)==5) a.push_back(-1);
    for(auto it=a.begin();it!=a.end();it++) cout<<*it<<" ";
}

Output

3 6 9 5 7 -1 -1

In the above example, when we try to replace element 5 with -1 while iterating the vector, it is possible that the size of the vector can get more than its actual size due to which all elements are copied to a new memory which is allocated to the vector. Since our iterator still points to the previous address, thus the iterator gets invalidated.

Rules for Iterator Invalidation

1) For Insertion:

  • deque:-In case of a deque, if the inserted elements are not at an end then the iterator is invalidated.
  • vector:-Before inserting all the iterators pointing to the respective element are unaffected while all others are invalidated.
  • list, set, map, multimap, multiset:-All iterators and references are unaffected.

2)  For Deletion:

  • deque:- In case of a deque, if the removed elements are not at an end then the iterator is invalidated.
  • vector:- After removing an element, every iterator is invalidated.
  • list, set, map, multimap, multiset:- Only the iterators or references to the removed element is invalidated.

3) For Resizing:

  • Vector, deque, and list:- As per the insert or delete.

Thank You for reading!!
I hope it helps!!

Leave a Reply

Your email address will not be published. Required fields are marked *