Why adding to vector does not work while using iterator?

Question

I have two code sample, which do exactly same thing. One is in C++03 and C++11.

C++ 11

int main()
{
    vector<int> v = {1,2,3};

    int count = 0;

    for each (auto it in v)
    {
        cout << it<<endl;

        if (count == 0)
        {
            count++;
            v.push_back(4);//adding value to vector
        }
    }

    return 0;
}

C++ 03

int main()
{
    vector<int> v = {1,2,3};

    int count = 0;

    for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {

        cout << *it<<endl;

        if (count == 0)
        {
            count++;
            v.push_back(4);//adding value to vector
        }
    }

    return 0;
}

Both the codes are giving following exception.

Now when I see vector::end() implementation,

iterator end() _NOEXCEPT
{   
// return iterator for end of mutable sequence
return (iterator(this->_Mylast, this));
}

Here, inline function clearly takes _Mylast to calculate end. So, when I add, it pointer will be incremented to next location, like _Mylast++. Why I am getting this exception?

Thanks.

Answer 1

A vector stores its elements in contiguous memory. If that memory block needs to be reallocated, iterators become invalid.

If you need to modify the vector's size while iterating, iterate by index instead of iterator.

Another option is to use a different container with a different iterator behavior, for example a list will allow you to continue iterating as you insert items.

And finally, (dare I suggest this?) if you know the maximum size your vector will grow to, .reserve() it before iterating over it. This will ensure it doesn't get reallocated during your loop. I am not sure if this behavior is guaranteed by the standard though (maybe someone can chime in); I would definitely not do it, considering iterating by index is perfectly safe.

Answer 2

Your push_back is invalidating the iterator you're using in the for loop, because the vector is reallocating its memory, which invalidates all iterators to elements of the vector.

The idiomatic solution for this is to use an insert_iterator, like the one you get from calling std::back_insterter on the vector. Then you can do:

#include <iostream>
#include <iterator>
#include <vector>

int main()
{
  std::vector<int> v;
  auto inserter = std::back_inserter(v);
  for(int i=0; i<100; ++i)
    inserter = i;

  for(const auto item : v)
    std::cout << item << '\n';
}

And it will ensure its own validity even through reallocation calls of the underlying container.

Live demo here.