Does modifying a std::vector invalidate an iterator?

Question

Consider this piece of code:

#include <vector>
#include <iostream>

int main(int argc, char** args)
{
    std::vector<int> vec;
    vec.push_back(0);

    for (auto iter = vec.begin(); iter != vec.end(); iter++)
    {
        vec.push_back((*iter) + 1);
        std::cout << *iter << std::endl;
    }
}

I expected this to print all the numbers to Infinite. But what it did was to print a LOT of zeros (and an occasional -256, WHAT?) only to run into a segfault.

My assumtion is that iter still points to the old array after the call to vec.push_back moves the internal data to a new array.

What exactly is the problem here? Is my assumption correct, that the push_back call invalidates the iterator?

Interestingly, when I substitute std::vector for a std::list, the code works as expected. Is it save to use a std::list instead? Or is that just working correctly by accident?

*Is it save to use a std::list instead?* -- Yes it is safe to use `std::list`, but don't rely on contiguous data in memory, and be wary of the extra memory used and speed reduction (maybe these won't be an issue with your application). — PaulMcKenzie, Jul 01 '20 at 14:09
*What exactly is the problem here?* -- A `std::list` is basically a doubly-linked list. Removing or adding elements to a linked list does not change the addresses of the existing links, which is why there is no iterator invalidation occurring. All that happens is that the existing link(s) get their respective "next" and "previous" pointers updated to point to different / new links. — PaulMcKenzie, Jul 01 '20 at 14:15
rather than using `std::list`, you can `reserve` a large number. You will need to stop the loop when you reach that capacity — Caleth, Jul 01 '20 at 14:19
[iterator invalidation](https://en.cppreference.com/w/cpp/container) can be a useful reference. — Eljay, Jul 01 '20 at 19:07

score 3 · Accepted Answer · answered Jul 01 '20 at 14:07

std::vector::push_back invalidates all iterators on that vector if the new vector size is greater than the previous capacity. (The reason is due to the reallocation of the vector).

The behaviour of using an invalidated iterator is undefined.

std::list::push_back does not invalidate any iterators.

Does modifying a std::vector invalidate an iterator?

1 Answers1