Почему std:: deque не вектор с памятью, зарезервированной перед индексом 0?
Насколько я понимаю, мотивация deque заключается в том, чтобы предоставить контейнер произвольного доступа с эффективным push_front.
Обычно упоминаемые преимущества vector по сравнению с deque включают более быстрый обход и
at(), но в основном его совместимость C, так как он гарантирует непрерывную память. ДЭК этого не делает, поскольку он представляет собой набор фрагментов памяти, каждый из которых содержит ряд значений.Я в замешательстве. Почему deque не построен как вектор, но с памятью, зарезервированной перед индексом 0 в добавление к памяти, зарезервированной после индекса size-1 ? Это гарантировало бы непрерывную память, позволяло бы эффективно push_front и даже избегало бы дополнительных косвенных действий при разыменовании итераторов.
Чтобы минимизировать смещение во время вставки, содержащиеся значения, которые будут смещены, будут зависеть от точки вставки. Если вставка в индекс n находится перед size()/2, сдвиньте значения вверх до n влево. В противном случае сдвиньте вправо значения после n.
Что я пропустил такого важного, что ДЭК-это набор массивов значений, а не один большой массив ?
1 ответ:
Согласно Википедии , то, что вы описываете, действительно является одной из возможных реализаций, по крайней мере в целом.
Однако стандарт C++ предъявляет требования, которые по существу запрещают это как реализацию для
std::deque; [deque.модификаторы] состояния:Вставка на обоих концах дека ... не влияет на достоверность ссылок на элементы дека.
(Спасибо @BenjaminLindley!)
Comments