Какая именно структура данных представляет собой deques в C ++ ?

Существует ли конкретная структура данных, которую должна реализовывать двухсторонняя очередь в C ++ STL, или же двухсторонняя очередь представляет собой лишь расплывчатое представление о массиве, растущем как спереди, так и сзади, которое должно быть реализовано независимо от реализации?

Раньше я всегда предполагал, что двухсторонняя очередь - это кольцевой буфер , но недавно я читал ссылку на C ++ здесь , и похоже, что двухсторонняя очередь - это своего рода массив массивов. Не похоже, что это простой старый кольцевой буфер. Значит, это буфер пробелов или какой-то другой вариант расширяемого массива , или он просто зависит от реализации?

ОБНОВЛЕНИЕ И РЕЗЮМЕ ОТВЕТОВ :

Похоже, что общее мнение таково, что двухсторонняя очередь - это такая структура данных, что:

• время для вставки или удаления элемента должно быть постоянным в начале или в конце списка и не более линейным в другом месте. Если мы интерпретируем это как истинное постоянное время, а не как амортизированное постоянное время, как кто-то комментирует, это кажется сложной задачей.Некоторые утверждали, что мы не должны интерпретировать это как неамортизированное постоянное время.
• «Двусторонняя очередь требует, чтобы любая вставка сохраняла действительной любую ссылку на элемент-член. Это нормально, если итераторы становятся недействительными, но сами элементы должны оставаться в одном и том же месте в памяти». Как кто-то комментирует: это достаточно просто, просто скопировав элементы куда-нибудь в куче и сохранив T * в структуре данных под капотом.
• «Вставка одного элемента в начало или конец двухсторонней очереди всегда занимает постоянное время и вызывает единственный вызов конструктора T.» Единственный конструктор T также будет достигнут, если структура данных хранит T * под капотом.
• Структура данных должна иметь произвольный доступ.

Кажется, никто не знает, как получить комбинацию 1-го и 4-го условий, если мы примем первое условие как «неамортизированное постоянное время». Связанный список достигает 1), но не 4), тогда как типичный кольцевой буфер достигает 4), но не 1). Я думаю, что у меня есть реализация, которая удовлетворяет обоим нижеприведенным. Комментарии?

Мы начинаем с реализации, которую предложил кто-то другой: мы выделяем массив и начинаем размещать элементы с середины, оставляя пространство как спереди, так и сзади. В этой реализации мы отслеживаем, сколько элементов находится от центра как в переднем, так и в обратном направлениях, называем эти значения F и B. Затем давайте дополним эту структуру данных вспомогательным массивом, который в два раза превышает размер оригинала. array (теперь мы тратим кучу места, но не меняем асимптотическую сложность).Мы также заполним этот вспомогательный массив от его середины и присвоим ему аналогичные значения F 'и B'. Стратегия такова: каждый раз, когда мы добавляем один элемент в первичный массив в заданном направлении, если F> F 'или B> B' (в зависимости от направления), до двух значений копируются из первичный массив во вспомогательный, пока F 'не догонит F (или B' с B). Таким образом, операция вставки включает в себя размещение 1 элемента в первичном массиве и копирование до 2 элементов из первичного во вспомогательный, но это по-прежнему O (1). Когда первичный массив заполняется, мы освобождаем первичный массив, делаем вспомогательный массив первичным массивом и делаем другой вспомогательный массив, который еще в 2 раза больше. Этот новый вспомогательный массив начинается с F '= B' = 0 и в него ничего не копируется (поэтому операция изменения размера равна O (1), если распределение кучи составляет O (1) сложность). Поскольку вспомогательные копируют 2 элемента для каждого элемента, добавленного к первичному, а первичный начинается максимум наполовину, для вспомогательного невозможно не догнать первичный к тому времени, когда первичный элемент снова исчерпает пространство. При удалении также нужно удалить 1 элемент из основного и 0 или 1 из вспомогательного. Итак, предполагая, что выделение кучи равно O (1), эта реализация удовлетворяет условию 1). Мы делаем массив из T * и используем new при вставке, чтобы выполнить условия 2) и 3). Наконец, 4) выполняется, потому что мы используем структуру массива и можем легко реализовать доступ O (1).