5

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).

Community
  • 1
  • 1
Satyabrat
  • 111
  • 5
  • 1
    Why do you think "mid" is still valid? I guess it's because (*mid) prints '6', but it's just a dangling iterator pointing to somewhere in free'd memory which hasn't changed the previous value yet. If you run valgrind, you'll get lots of invalid access to the memory. – Inbae Jeong Mar 30 '16 at 06:12

1 Answers1

3

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.

Zbynek Vyskovsky - kvr000
  • 18,186
  • 3
  • 35
  • 43
  • Is there any reason, why mid points to the previous element i.e 5 in the original code even after invalidation, but the value at mid appears to be changing with the modification till segmentation fault. Is it correct to say that the value of mid is some garbage value or the code result is unpredictable ? – Satyabrat Mar 30 '16 at 06:08
  • Using `*mid` after `mid` has been invalidated is undefined behavior. In such a situation you might get a value that looks reasonable, looks like garbage or crashes your program. – Michael Burr Mar 30 '16 at 06:17
  • @Satyabrat : It's specific to implementation. But generally `mid` contains a pointer which doesn't change. But the elements move forward when inserting so logically to the pointer from `mid` will be moved the previous element. But as I said, only as long as the backing array is not reallocated (i.e. capacity does not change). – Zbynek Vyskovsky - kvr000 Mar 30 '16 at 06:18