Question

In C++ please.

6. Define iterator invalidation. Explain the reason for this

invalidation. Point out the problem in the following code and correct it.

vector <int> v = {10, 20, 30, 40, 50, 60};

int i;

cout << "Enter number to remove from vector: "; cin >> i;

for(auto it = v.begin(); it != v.end(); ++it)

if(*it == i) v.erase(it);

Answer 1

iterator invalidation:

When iterating over a container(for example vector), if size/shape of the container changes due to addition or removing of elements, then iterator gets invalidated

Reason: When size of the container( vector ) crosses maximum size due to insertion or size of the vector reduces due to erasing of elements, then new memory is allocated and all the elements are moved to that location. This will cause ietrator pointing to a location where there ar no elements.

<int> v = {10, 20, 30, 40, 50, 60};

int i;

cout << "Enter number to remove from vector: "; cin >> i;

for(auto it = v.begin(); it != v.end(); ++it)

if(*it == i) v.erase(it);

The element next to the element chosen to be removed will get skipped from iteration. This is the problem

For example: if user enters 30. Then all the occurences of 30 should be removed from vector. Now when while iterating vector 30 is encountered in third iteration. So v.erase(it); will remove 30 from vector and changes iterator to point to 40 . Now due to ++it. iterator gets incremented and points to 50. So 40 gets skipped.

Fix: we need to decrement iterator after erasing element.

#include <iostream>
#include<vector>
using namespace std;
int main()
{
vector <int> v = {10, 20, 30, 30, 40, 60};
int i;
cout<<"Enter number to remove from vector: ";
cin>>i;
for(auto it = v.begin(); it != v.end(); ++it){
if(*it == i) {
v.erase(it);
it--;
}
}
for (auto it=v.begin();it!=v.end();it++)
cout << (*it) << " ";
return 0;
}