deque insert invalidation of iterators vs. pointers ( references)

Question

Based on citation from cplusplus.com

If the insertion happens at the beginning or the end of the sequence, all iterators related to this container are invalidated, but pointers and references remain valid, referring to the same elements they were referring to before the call.

Why the insert to the front or end invalidates the iterators but not pointers and references?

score 7 · Accepted Answer · edited Nov 02 '13 at 15:07

Basically, a deque can be thought of as a vector<array<T>*>.

In other words, it consistsof a small "index" vector containing pointers to a series of fixed-size arrays. When you insert at the beginning or end of a deque, it fills out the first/last array, and then adds another one when necessary, so it never needs to move existing elements. That is why pointers/references are not invalidated.

However, because this "index" is stored in something like a vector, it might be copied and reallocated when resized, so every time a new array is added to the index, the index might be copied to a different memory location.

An iterator needs to know enough about the container to be able to iterate over it. In other words, it is not enough to know where the specific element it is current pointing to is located, it also needs to know which array it is part of, and where the index is, so it can find the next/previous arrays.

And so an operation which risks invalidating the "index" also invalidates iterators, because while they might still point to a valid element, they are no longer able to iterate over the entire deque.

score 0 · Answer 2 · answered Nov 02 '13 at 14:23

0

Pointers still do have the right memory address of individual items but when you for example:

obtain an iterator pointing to the beginning of the sequence
instert new item to the front

Do you still have an iterator pointing to the beginning? In this example you'll miss the number 5 in output:

#include <deque>
#include <iostream>
using namespace std;

int main()
{
    deque<int> d;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);

    deque<int>::iterator it=d.begin();

    d.push_front(5);

    for(;it!=d.end();++it)
    {
        cout << *it << endl;
    }
}

answered Nov 02 '13 at 14:23

nio

5,141
2
24
35

There must be some other reason. `std::list::push_front()` does not invalidate the iterator returned by `std::list::begin()`. – Oswald Nov 02 '13 at 14:25
I believe based on the compiler vendor's implementation. The pointers might have the memory address. But the standard does not back up. I tested on gcc 5.4. The address stays the same after remove and insertion. But I think there is no guarentee that in the future verion the feature will be maintained. – r0n9 Jan 11 '18 at 04:30

deque insert invalidation of iterators vs. pointers ( references)

2 Answers2