CODEWITHSUNDEEP
c++c++11stliterator
Satyabrat
Satyabrat

Reputation: 111

How do iterators update after vector reallocation

Here is a code snippet that I was looking at: 

vector<int> iv = {1,2,3,4,5,6,7,8,9,10};
auto iter = iv.begin(), mid = iv.begin() + iv.size()/2;
for(int count = 100; count; --count ) {
    iter = iv.insert(iter, - 1);
    cout << "capacity = " << iv.capacity() << "*mid = " << *mid << endl;

}

As per iterator invalidation rules:
vector: all iterators and references before the point of insertion are unaffected, unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)[23.2.4.3/1] Iterator invalidation rules

I understand that since I am reassigning the value of "iter" at each insert operation, perhaps I am able to maintain it's validity (please correct me if I am wrong). However, the iterator "mid" remain valid in this case even when I am not tampering with it in the loop and also when the capacity of the vector is changing.

So, how is "mid" able to update itself after reallocation ?

To know whether mid is changing at all or not, I changed line 4 in the code to:

iv.insert(iter, -1); // Did not assign it back to iter.

Printing the results of dereferencing the value at mid suggests the change and perhaps also that iter is invalidated. (Again, please correct me if I am wrong).

Upvotes: 5

Views: 1056

Answers (1)

Zbynek Vyskovsky - kvr000
Zbynek Vyskovsky - kvr000

Reputation: 18825

Your understanding is correct. Once the capacity increases, any iterator becomes invalid. The mid iterator becomes invalid even when capacity didn't changes but it basically points to the previous element.

So the original code would work at least for iter, however mid would become unusable upon first insertion. With the modification the code is completely invalid.

Usually the implementation of vector iterator is just a simple pointer that points to some element to backing array. Therefore when capacity changes and array is reallocated, any such iterator is no longer valid as the pointer points to no longer valid memory. As a result, you may see either garbage, you may get segmentation fault or randomly see correct values. When capacity doesn't change, the elements in the array may be moved forward so you could see the previous element in the iterators after the insert point, but only in case there was no empty elements at the beginning of array (e.g. start was greater then zero). But all those are specific to implementation and therefore standard clearly specifies that most of the above is undefined behavior.

Upvotes: 3

Related Questions