Как указано в заголовке.
Мое понимание дека состояло в том, что он выделял "блоки". Я не вижу, как выделение большего количества пробелов делает недействительными итераторы, и, если угодно, можно подумать, что итераторы deque будут иметь больше гарантий, чем вектор, не менее.
В стандарте С++ не указывается, как выполняется deque. Не требуется выделять новое пространство, выделяя новый кусок и привязывая его к предыдущим, все, что требуется, - это то, что вставка на каждом конце будет амортизирована постоянным временем.
Итак, хотя легко увидеть, как реализовать deque, чтобы он дал гарантию, которую вы хотите [*], это не единственный способ сделать это.
[*] Итераторы имеют ссылку на элемент, а также ссылку на блок, чтобы они могли продолжать/отступать от концов блока, когда они достигают их. Кроме того, я полагаю, что ссылка на сам deque, так что operator+ может быть постоянным временем, как ожидалось, для итераторов с произвольным доступом - после цепочки ссылок от блока к блоку недостаточно.
Интересно, что push_back и push_front будут не аннулировать любые ссылки для элементов deque. Только итераторы считаются недопустимыми.
Стандарт, насколько мне известно, не указывает, почему. Однако, если был реализован итератор, который знал о его ближайших соседях - в качестве списка - то, что итератор стал бы недопустимым, если бы он указывал на элемент, который был как на краю deque, так и на краю блока.
Мое предположение. push_back/push_front может выделить новый блок памяти. Итератор deque должен знать, когда оператор increment/decment должен перейти в следующий блок. Реализация может хранить эту информацию в самом итераторе. Приращение/уменьшение старого итератора после push_back/push_front может не работать должным образом.
Этот код может или не может завершиться с ошибкой времени выполнения. На моей Visual Studio он вышел из строя в режиме отладки, но приступил к выводу в режиме выпуска. В Linux это вызвало ошибку сегментации.
#include <iostream>
#include <deque>
int main() {
std::deque<int> x(1), y(1);
std::deque<int>::iterator iterx = x.begin();
std::deque<int>::iterator itery = y.begin();
for (int i=1; i<1000000; ++i) {
x.push_back(i);
y.push_back(i);
++iterx;
++itery;
if(*iterx != *itery) {
std::cout << "increment failed at " << i << '\n';
break;
}
}
}
Главное, чтобы не делать какие-либо предположения, просто обрабатывать итератор, как будто он будет признан недействительным.
Даже если он отлично работает, более поздняя версия компилятора или компилятор для другой платформы может прийти и сломать ваш код. В качестве альтернативы, коллега может прийти и решить превратить ваш deque в векторный или связанный список.
Даже если вы выделяете куски, вставка приведет к перераспределению этого конкретного фрагмента, если пространства недостаточно (как в случае с векторами).
Итератор - это не просто ссылка на данные. Он должен знать, как увеличивать и т.д.
Чтобы поддерживать произвольный доступ, реализации будут иметь динамический массив указателей на куски. Итератор deque будет указывать на этот динамический массив. Когда дека растет, может потребоваться выделение нового фрагмента. Динамический массив будет расти, аннулировать его итераторы и, следовательно, итераторы deque.
Итак, это не то, что куски перераспределены, но массив указателей на эти куски может быть. Действительно, как отметил Йоханнес Шауб, ссылки не являются недействительными.
Также обратите внимание, что итератор deque гарантирует не меньше, чем вектор, который также недействителен, когда контейнер растет.
Потому что стандарт говорит, что может. Он не гарантирует, что deque будет реализован как список кусков. Он задает конкретный интерфейс с определенными предварительными и пост-условиями и определенными минимальными алгоритмическими сложностями.
Исполнители могут свободно реализовывать то, что они выбирают, если они соответствуют всем этим требованиям. Разумная реализация может использовать списки кусков или использовать другую технику с различными компромиссами.
Вероятно, невозможно сказать, что один метод строго лучше другого для всех пользователей во всех ситуациях. Именно поэтому стандарт дает разработчикам свободу выбора.