Доступ двухсторонней очереди STL индексом является O (1)?
Я считал, что доступ к элементам индексом положения может быть сделан в постоянное время в двухсторонней очереди STL. Насколько я знаю, элементы в двухсторонней очереди могут быть сохранены в нескольких местоположениях, состоящих из нескольких несмежных участков, устранив безопасный доступ через адресную арифметику с указателями. Например:
abc-> defghi-> jkl-> mnop
Элементы двухсторонней очереди выше состоят из отдельного символа. Набор символов в одной группе указывает, что это выделяется в непрерывной памяти (например, abc находится в единственном блоке памяти, defhi расположен в другом блоке памяти, и т.д.). Кто-либо может объяснить, как доступ индексом положения может быть сделан в постоянное время, особенно если элемент, к которому получат доступ, находится во втором блоке? Или двухсторонняя очередь имеет указатель на группу блоков?
Обновление: Или есть ли какая-либо другая общая реализация для двухсторонней очереди?
2 ответа
Я нашел эту реализацию двухсторонней очереди из Википедии :
Хранение содержимого в нескольких меньших массивах, при необходимости выделяя дополнительные массивы в начале или в конце. Индексирование осуществляется путем сохранения динамического массива, содержащего указатели на каждый из меньших массивов.
Думаю, это отвечает на мой вопрос.
Если deque реализован как кольцевой буфер поверх std::vector, который перераспределяет себя при увеличении размера, то доступ по индексу действительно O(1).
Стандарт предоставляет доказательства того, что такая реализация имелась в виду - по крайней мере, она соответствует стандарту в оценках сложности. Пункты 23.2.1.3/4 и 23.2.1.3/5 требуют, чтобы
вставка в начало или в конец deque требовала постоянного времени, а вставка в середину - линейного времени размера deque
при стирании элементов из deque можно вызывать столько операторов присваивания, каково расстояние от стираемых элементов до конца deque.
И, конечно, следует полагаться на стандартные требования, а не на собственное видение того, как могут быть реализованы контейнеры и алгоритмы.
ЗАМЕЧАНИЕ, что стандарт требует больше, чем эти два пункта, перечисленные выше. Он также устанавливает требование, что ссылки на элементы должны оставаться действительными между вставками в заднюю или переднюю часть deque. Это требование может быть выполнено, если кольцевой буфер содержит указатели на фактические элементы, а не сами элементы. В любом случае, мой ответ просто демонстрирует идею о том, что несколько реализаций могут удовлетворять определенным требованиям.