В чем разница между deque и list STL контейнерами?

Ответ 1

Из (датированный, но все же очень полезный) SGI STL резюме deque:

Deque очень похож на вектор: подобно вектору, это последовательность, которая поддерживает произвольный доступ к элементам, постоянную вставку времени и удаление элементов в конце последовательности, а также линейную временную вставку и удаление элементов в средний.

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

Здесь сводка на list с того же сайта:

Список представляет собой двусвязный список. То есть, это последовательность, которая поддерживает как обратное, так и обратное перемещение и (амортизированное) постоянное время вставки и удаления элементов в начале или в конце или в середине. Списки имеют важное свойство, что вставка и сплайсинг не делают недействительными итераторы для перечисления элементов, и даже удаление исключает только итераторы, указывающие на удаляемые элементы. Порядок итераторов может быть изменен (т.е. Список:: итератор может иметь другого предшественника или преемника после операции списка, чем раньше), но сами итераторы не будут признаны недействительными или не будут указывать на разные элементы, если это недействительность или мутация явно.

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

Ответ 2

Позвольте мне перечислить различия:

• Deque управляет своими элементами с помощью динамический массив, обеспечивает случайную доступа, и имеет почти тот же интерфейс как вектор.
• Список управляет своими элементами как дважды связанный список и не обеспечивают произвольный доступ.

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

• Deque: любая вставка или удаление элементов кроме как в начале или в конце аннулирует все указатели, ссылки, итераторы, которые ссылаются на элементы от deque.
• Список. Вставка и удаление элементов не аннулировать указатели, ссылки, итераторы к другим элементам.

Сложность

             Insert/erase at the beginning       in middle        at the end

Deque:       Amortized constant                  Linear           Amortized constant
List:        Constant                            Constant         Constant

Ответ 3

std::list - это в основном двойной список.

std::deque, с другой стороны, реализовано больше как std::vector. Он имеет постоянное время доступа по индексу, а также вставку и удаление в начале и конце, что обеспечивает значительно отличающиеся характеристики производительности, чем список.

Ответ 4

Нет. Deque поддерживает только O (1) вставку и удаление спереди и сзади. Например, он может быть реализован в векторе с оберткой. Поскольку он также гарантирует произвольный доступ к O (1), вы можете быть уверены, что он не использует (просто) двунаправленный список.

Ответ 5

Еще одна важная гарантия заключается в том, как каждый отдельный контейнер хранит свои данные в памяти:

• Вектор представляет собой единый непрерывный блок памяти.
• Deque - это набор связанных блоков памяти, где в каждом блоке памяти хранится более одного элемента.
• Список представляет собой набор элементов, рассеянных в памяти, то есть только один элемент хранится в блоке памяти.

Обратите внимание, что deque был разработан, чтобы попытаться сбалансировать преимущества как вектора, так и списка без их соответствующих недостатков. Это особый интересный контейнер на платформах с ограниченной памятью, например, микроконтроллеры.

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

Ответ 6

Различия в производительности были хорошо объяснены другими. Я просто хотел добавить, что подобные или даже идентичные интерфейсы являются общими для объектно-ориентированного программирования - частью общей методологии написания объектно-ориентированного программного обеспечения. Вы не должны допускать, что два класса работают одинаково, просто потому, что они реализуют один и тот же интерфейс, больше, чем вы должны предположить, что лошадь работает как собака, потому что они оба реализуют атаки() и make_noise().

Ответ 7

IF (вы хотите вставить или удалить только в начале или в конце массива):

USE DEQUE  # is way faster

ELSE:

USE LIST 

УЗНАЙТЕ БОЛЬШЕ ОБ ЭТОМ: https://www.geeksforgeeks.org/deque-in-python/