Каково обоснование для deque иметь оператор подстрочного индекса?

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

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

Спасибо!

2 2
c++ vector deque

2 ответа:

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

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

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

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

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

0