Deque вставка недействительности итераторов против указателей (ссылки)

Question

на основе цитат из cplusplus.com

Если вставка происходит в начале или в конце последовательности, все итераторы, связанные с этим контейнером аннулируются, но указатели и ссылки остаются в силе, ссылаясь на те же элементы, на которые они ссылались до вызова.

Почему вставка спереди или конца отменяет итераторы, но не указатели и ссылки?

Answer 1

В принципе, deque можно рассматривать как vector<array<T>*>.

Другими словами, он состоит из небольшого «индексного» вектора, содержащего указатели на ряд массивов фиксированного размера. Когда вы вставляете в начале или конце дека, он заполняет первый/последний массив, а затем добавляет еще один, когда это необходимо, поэтому ему не нужно перемещать существующих элементов. Вот почему указатели/ссылки не являются недействительными.

Однако, поскольку этот «индекс» хранится в виде вектора, он может быть скопирован и перераспределен при изменении размера, поэтому каждый раз, когда новый индекс добавляется к индексу, индекс может быть скопирован в другое место памяти ,

Итератору необходимо достаточно знать о контейнере, чтобы иметь возможность перебирать его. Другими словами, недостаточно знать, где находится определенный элемент, на который указывает текущий элемент, он также должен знать, какой массив он является частью и где индекс, поэтому он может найти следующий/предыдущий массив.

И поэтому операция, которая рискует аннулировать «индекс», также делает недействительными итераторы, поскольку, хотя они все равно могут указывать на действительный элемент, они больше не могут выполнять итерацию по всему детексту.

Answer 2

Указатели по-прежнему есть правильный адрес памяти отдельных элементов, но если вы, например:

1. получить итератор, указывающий на начало последовательности
2. instert новый элемент к переднему

У вас все еще есть итератор, указывающий на начало? В этом примере вы пропустите номер 5 на выходе:

#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; 
    } 
}