Почему push_back или push_front делают недействительными итераторы deque?

Question

Как следует из названия.

Мое понимание deque было то, что он выделил "блоки". Я не понимаю, как выделение большего количества пространства делает недействительными итераторы, и, если что-нибудь, можно подумать, что итераторы deque будут иметь больше гарантий, чем вектор, а не меньше.

Answer 1

Стандарт C ++ не определяет, как реализован deque. Не требуется выделять новое пространство, выделяя новый блок и связывая его с предыдущими, все, что требуется, - это чтобы амортизация вставки на каждом конце была постоянным временем.

Итак, хотя легко понять, как реализовать deque, чтобы он гарантированно дал вам [*], это не единственный способ сделать это.

[*] Итераторы имеют ссылку на элемент, плюс ссылку на блок, в котором он находится, чтобы они могли продолжать идти вперед / назад с конца блока, когда достигают их. Кроме того, я полагаю, что ссылка на саму деку такова, что operator+ может быть постоянным временем, как и ожидалось для итераторов с произвольным доступом - проследить цепочку ссылок от блока к блоку недостаточно.

Answer 2

Что еще интереснее, push_back и push_front будут не лишать законной силы любые ссылки на элементы deque. Только итераторы считаются недействительными.

Стандарт, насколько мне известно, не устанавливает почему. Однако, если бы был реализован итератор, который знал о его непосредственных соседях - как список, - этот итератор стал бы недействительным, если бы он указывал на элемент, который находился как на краю очереди, так и на границе блока.

Answer 3

Мое предположение. push_back / push_front может выделить новый блок памяти. Итератор deque должен знать, когда оператор увеличения / уменьшения должен перейти в следующий блок. Реализация может хранить эту информацию в самом итераторе. Увеличение / уменьшение старого итератора после 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;
        }
    }
}

Answer 4

Главное не делать какие-либо предположения, просто обрабатывать итератор, как если бы он был признан недействительным.

Даже если сейчас это работает нормально, более поздняя версия компилятора или компилятора для другой платформы может прийти и сломать ваш код. В качестве альтернативы, коллега может прийти и решить превратить вашу деку в векторный или связанный список.

Answer 5

Итератор - это не просто ссылка на данные. Надо знать, как увеличивать и т. Д.

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

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

Также обратите внимание, что гарантии итератора deque не меньше, чем у вектора, которые также становятся недействительными по мере роста контейнера.

Answer 6

Даже если вы размещаете в чанках, вставка приведет к перераспределению этого конкретного чанка, если не хватает места (как в случае с векторами).

Answer 7

Потому что стандарт говорит, что может. Он не требует, чтобы deque был реализован как список кусков. Это требует определенного интерфейса с определенными условиями до и после и определенными минимальными алгоритмическими сложностями.

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

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