CPP std::Vector and Iterator Invalidation Example

In the previous article, we have discussed about CPP Map: Erase by Value or Callback while Iterating | erase_if for Map. Let us learn std::Vector and Iterator Invalidation Example in C++ Program.

Vector:

Vectors are similar to dynamic arrays in that they can resize themselves when an element is added or removed, and the container takes care of their storage. Iterators can access and traverse vector elements since they’re stored in contiguous storage. Data is inserted at the top of vectors. Inserting at the end takes longer since the array may need to be extended at times. There is no resizing, and removing the final variable still takes the same amount of time. Inserting and erasing at the start or within the middle is linear in terms of your time .

Vector and Iterator Invalidation Examples

Iterator Invalidation
Iterator invalidation when deleting element from vector
Solution for iterator invalidation when deleting element from vector
Iterator invalidation when inserting element from vector
Solution for iterator invalidation when inserting element from vector

1)Iterator Invalidation

Iterators in C++ should be used with caution. When we use iterators to iterate over our container, it is possible that the iterator will be invalidated. This may be due to changes in the shape and size of the container when iterating.

When the container to which an Iterator points changes form internally, i.e. moves items from one location to another, the original Iterator always points to the old invalid location, the Iterator becomes invalid.

Vector iterator invalidation occurs when,

An element is added to the vector at any point.
A vector element is removed.

2)Iterator invalidation when deleting element from vector

Assume an iterator ‘it’ points to the vector position x. Assume that a deletion occurs on that vector, causing its elements to shift from one position to another. If the original iterator ‘it’ still points to the old position, it is invalidated.

For example, in the code below, we use the erase function to delete an element from a vector. The current pointer is invalidated by this erase operation. So, if the same invalidated iterator is used after calling the erase() method, it may result in undefined behaviour.

Implementation:

#include <bits/stdc++.h>
using namespace std;

int main()
{ // creating a vector of type integer
    vector<int> intvec;
    // using for loop to add elements from 1 to 8
    for (int i = 1; i <= 8; i++)
        intvec.push_back(i);
    // print the elements of the vector
    for (auto itr = intvec.begin(); itr != intvec.end();
         itr++)
        cout << (*itr) << "  ";

    cout << endl;

    // Erasing the elements with value 2.
    auto itr = std::find(intvec.begin(), intvec.end(), 2);
    if (itr != intvec.end())
        intvec.erase(itr);

    // Iterator 'itr' is now invalidated because it still
    // points to a deleted spot. So,
    // if you try to use the same iterator again, it can
    // exhibit undefined behaviour.

    for (; itr != intvec.end(); itr++)
        cout << (*itr) << "  ";

    return 0;
}

Output:

1  2  3  4  5  6  7  8  
3  4  5  6  7  8

3)Solution for iterator invalidation when deleting element from vector

Solution:

After calling the erase function, the value of iterator ‘it’ should be modified.
The erase() function, for example, returns an iterator pointing to the new position of the element that came after the last element erased by the same function. Also, if the deleted element was the container’s last element, it restores the container’s end.

// Erasing the elements with value 3.
    auto itr = std::find(intvec.begin(), intvec.end(), 2);
    if (itr != intvec.end())
        itr=intvec.erase(itr);

4)Iterator invalidation when inserting element from vector

When a new variable is added to a vector, it internally changes the components, rendering the old iterators null.

The following are the reasons for element shift:

If an element is added between the two, it shifts all of the right elements by one.
If the new vector size exceeds its current power, it relocates a larger chunk of memory and copies all of the elements there.
As a result, when a new element is added to a vector, the old iterator can become null. Using these old invalidated iterators can lead to unexpected behaviour i.e.

Implementation:

#include <bits/stdc++.h>
using namespace std;

int main()
{ // creating a vector of type integer
    vector<int> intvec;
    // using for loop to add elements from 1 to 8
    for (int i = 1; i <= 8; i++)
        intvec.push_back(i);
    // making iterator to point to first element of vector
    auto itr = intvec.begin();
    // Using for loop and iterator to traveerse and print
    // the elements of vector
    for (; itr != intvec.end(); itr++)
        cout << (*itr) << "  ";

    cout << endl;
    // making iterator to point to first element of vector
    auto itr = intvec.begin();

    // inserting eleemeent 3028 at index 3
    intvec.insert(itr + 3, 1, 3028);

    // Since the old iterator is no longer true, using it as
    // is can
    // result in undefined conduct.

    for (; itr != intvec.end(); itr++)
        cout << (*itr) << "  ";

    return 0;
}

5)Solution for iterator invalidation when inserting element from vector

After calling the insert function, change the value of iterator ‘itr,’ i.e. re-assign it.

// inserting element 3028 at index 3
    intvec.insert(itr + 3, 1, 3028);
// Reinitialize the invalidated iterator to its initial state.
itr = intvec.begin();

Related Programs: