deque insert invalidation of iterators vs. pointers ( references) [duplicate]

Question

This question already has an answer here:

C++ deque's iterator invalidated after push_front() (1 answer)

Closed 8 years ago.

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?

Answer 1

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.

Answer 2

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

1. obtain an iterator pointing to the beginning of the sequence
2. 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;
    }
}