Why does the mutation of STL List containers cause an iterator to be invalidated?

[vaderboi]

Why does mutating an STL container (such as a vector or a stack) cause an iterator to point to junk data? Why does the elements shifting left or right cause this iterator invalidation? Wouldn't the iterator just point to a different part of the vector (like the place in memory located before or after the itt)?

Here is some example code:

std::vector<int> vec = {1, 2, 4, 5, 7};
std::vector<int>::iterator itt = vec.begin();

while( itt != vec.end() )
{
    if( *itt == 4 )
    {
        delete vec[itt];
    }
}

[Ganado]

Your code is undefined behavior. You're calling delete on something that wasn't created with new. Reasoning about why a particular undefined behavior behaves the way it does can only be answered fully by looking at the assembly produced for your particular compiler, and for that I would invite you to check out goldbolt.org, which is an online compiler that will show you what the assembly produced is, in real-time.

Nevertheless: Under normal circumstances, an iterator is invalidated when the underlying data inside a vector is reallocated. When a reallocation is done, the new array could be in a completely different location, so it makes sense that an invalid iterator would now be pointing to complete junk.

[vaderboi]

Yeah that is what I needed clarified- whether a new array could be in a completely different location. And I will check out that site. Thank you!

[MikeyBoy]

Also, at line 8, that's not how you use an iterator to access an element. Iterators are not indices - they work more like pointers.

And, to reiterate Ganado's point - you cannot use delete on something you didn't allocate with new.

[coder777]

For line 8 i think you mean this:

vec.erase(itt); // Removes the element identified by itt

[JLBorges]

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    const auto print = [] ( const auto& seq ) // print the elements of a sequence
    { for( const auto& v : seq ) std::cout << v << ' ' ; std::cout << '\n' ; };

    {
        std::vector<int> seq { 0, 1, 4, 2, 3, 4, 5, 4, 6, 7, 8, 9 } ;
        print(seq) ;

        // erase all occurrences of 4
        for( auto iter = seq.begin() ; iter != seq.end() ; )
        {
            // erase: returns a valid iterator to the element immediately after
            //        the element that was removed
            if( *iter == 4 ) iter = seq.erase(iter) ;
            else ++iter ;
        }
        print(seq) ;
    }

    {
        std::vector<int> seq { 0, 1, 4, 2, 3, 4, 5, 4, 6, 7, 8, 9 } ;
        print(seq) ;

        // erase all occurrences of 4
        // erase-remove idiom: https://en.wikipedia.org/wiki/Erase-remove_idiom
        seq.erase( std::remove( seq.begin(), seq.end(), 4 ), seq.end() ) ;
        print(seq) ;
    }

    {
        std::vector<int> seq { 0, 1, 4, 2, 3, 4, 5, 4, 6, 7, 8, 9 } ;
        print(seq) ;

        // erase all occurrences of 4
        // C++20: https://en.cppreference.com/w/cpp/container/vector/erase2
        std::erase( seq, 4 ) ;
        print(seq) ;
    }
}

http://coliru.stacked-crooked.com/a/f823efc19dcb07cb

[dhayden]

There are specific rules for which iterators are invalidated by which methods of which containers. This is important stuff and it's often hard to find. If you modify the contents of a container while you have an iterator, you should check the documentation to be sure that your iterator remains valid.