c++vectoriteratorcontainers

Confusion about invalidated iterators


If vectors are stored contiguously, as long as they are not made smaller or reallocated, any iterator pointing to an element within it should be valid. The following code would be defined:

#include <iostream>
#include <vector>

int main()
{
    std::vector v = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 
    auto i = v.begin() + 7;
    v.insert(v.begin() + 5, 10);
    if(v.capacity() > v.size()) {
        std::cout << *i << '\n';
    }
}

This writes 7 to my console, which my logic would predict. However, it is wrong according to GeeksforGeeks:

All iterators which point to an element before the point of insertion are unaffected but all others are invalidated.

Why is it wrong? I ask because I cannot see how the code would fail.


Solution

  • A better reference to look at is https://en.cppreference.com/w/cpp/container/vector/insert which states:

    If after the operation the new size() is greater than old capacity() a reallocation takes place, in which case all iterators (including the end() iterator) and all references to the elements are invalidated. Otherwise, only the iterators and references before the insertion point remain valid.

    So the proper check is:

    #include <iostream>
    #include <vector>
    
    int main()
    {
        std::vector v = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 
        auto i = v.begin() + 7;
        size_t oldCapacity = v.capacity();
        v.insert(v.begin() + 5, 10);
        if(v.size() <= oldCapacity) {
            std::cout << *i << '\n';
        }
    }
    

    Although this code will generally work, i has still been invalidated, before the insert it pointed to 8, after the insert it points to 7 this means that the iterator has been invalidated, a valid iterator always points to the same item in a container. Dereferencing an invalidated iterator is undefined behaviour.