Доступ к STL по индексу O (1)?

Question

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

abc-> defghi-> jkl-> MNOP

Элементы выше дека состоит из одного символа. Набор символов в одной группе указывает, что он выделен в непрерывной памяти (например, abc находится в одном блоке памяти, defhi находится в другом блоке памяти и т. Д.). Может ли кто-нибудь объяснить, как доступ по индексу позиции может выполняться в постоянное время, особенно если элемент, к которому нужно получить доступ, находится во втором блоке? Или у deque есть указатель на группу блоков?

Обновление: или существует ли какая-либо другая общая реализация для deque?

Answer 1

Я нашел эту реализацию из дека Wikipedia:

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

Я думаю, это отвечает на мой вопрос.

Answer 2

Если deque реализован как ring buffer поверх std::vector, который перераспределяет себя, когда он растет в размере, тогда доступ по индексу действительно является O (1).

Стандарт свидетельствует о том, что такая реализация была предусмотрена - по крайней мере, она соответствует стандартным оценкам сложности. Пункты 23.2.1.3/4 и 23.2.1.3/5 требуют, чтобы

• вставки в начало или конец дека требует постоянного времени, в то время как вставки в середине требуется линейное время размера Deque в

• при стирании элементов из deque он может вызывать столько операторов присваивания, сколько расстояния от стираемых элементов до конца deque.

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

ПРИМЕЧАНИЕ что стандарт требует больше, чем эти две точки, перечисленные выше. Он также требует, чтобы ссылки на элементы оставались действительными между вставками в спину или перед деком. Это может быть выполнено, если кольцевой буфер содержит указатели на фактические элементы, а не на сами элементы. В любом случае, мой ответ просто демонстрирует идею о том, что несколько реализаций могут удовлетворять определенным требованиям.

Answer 3

Одна из возможных реализаций может быть динамическим массивом массивов const-size; такой массив const-size может быть добавлен в любой конец, когда требуется больше места. Все массивы полны, за исключением, возможно, для первого и последнего, которые могут быть частично пустыми. Это означает, что зная размер каждого массива и количество элементов, используемых в первом массиве, можно легко найти позицию элемента по индексу.
http://cpp-tip-of-the-day.blogspot.ru/2013/11/how-is-stddeque-implemented.html