В чем причина того, что у deque есть оператор индекса?

Question

Сегодня я разговаривал с другом, и он вспомнил, как странно, что элементы deque могут быть доступны оператору индекса, когда другие «похожие» DS, такие как очередь и стек, не могут. В конце концов, разве не означает, что deque означает двустороннюю очередь? Разве тот факт, что доступ к deque можно получить случайным образом, не разрушает саму целостность структуры данных deque?

Кроме того, с точки зрения производительности, разве deque просто вносит меньше в таблицу полностью с помощью оператора индекса, если вы на самом деле не используете методы deque (семейство передних и задних функций)? Я понимаю, что реализация, лежащая в основе deque, разбивает его на куски / блоки, и что обычно требуется две операции для фактического произвольного доступа к элементу, тогда как векторы гарантированно находятся в смежной памяти.

Спасибо!

Answer 1

Кроме того, с точки зрения производительности, разве не deque просто вносит меньше в таблицу с помощью оператора индекса, если вы на самом деле не используете методы deque (семейство передних и задних функций)? Я понимаю, что реализация, лежащая в основе deque, разбивает его на куски / блоки, и что для произвольного доступа к элементу обычно требуется две операции, тогда как векторы гарантированно находятся в смежной памяти.

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

Answer 2

Разве тот факт, что доступ к deque's можно получить случайным образом, не разрушает саму целостность структуры данных deque?

Нет. Вы просто одержимы именем. Мы имеем в виду четкое определение «очереди», так что, возможно, это плохой выбор слов, но структура данных не определяется ее именем.

Структура даты - это данные (дух) с определенным набором связанных операций. Стандартная библиотека определена deque с оператором индекса. Так что это структура данных. Было сделано все возможное, чтобы различные требования к операциям не вступали в противоречие, поэтому целостность deque как структуры данных поддерживается довольно хорошо.