Почему std:: deque не вектор с памятью, зарезервированной перед индексом 0?



Насколько я понимаю, мотивация deque заключается в том, чтобы предоставить контейнер произвольного доступа с эффективным push_front.



Обычно упоминаемые преимущества vector по сравнению с deque включают более быстрый обход и at(), но в основном его совместимость C, так как он гарантирует непрерывную память. ДЭК этого не делает, поскольку он представляет собой набор фрагментов памяти, каждый из которых содержит ряд значений.

Я в замешательстве. Почему deque не построен как вектор, но с памятью, зарезервированной перед индексом 0 в добавление к памяти, зарезервированной после индекса size-1 ? Это гарантировало бы непрерывную память, позволяло бы эффективно push_front и даже избегало бы дополнительных косвенных действий при разыменовании итераторов.



Чтобы минимизировать смещение во время вставки, содержащиеся значения, которые будут смещены, будут зависеть от точки вставки. Если вставка в индекс n находится перед size()/2, сдвиньте значения вверх до n влево. В противном случае сдвиньте вправо значения после n.



Что я пропустил такого важного, что ДЭК-это набор массивов значений, а не один большой массив ?

639   1  

1 ответ:

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

Однако стандарт C++ предъявляет требования, которые по существу запрещают это как реализацию для std::deque; [deque.модификаторы] состояния:

Вставка на обоих концах дека ... не влияет на достоверность ссылок на элементы дека.

(Спасибо @BenjaminLindley!)

Comments

    Ничего не найдено.