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

Question

В чем разница между двумя? Я имею в виду методы все одинаковы. Так что для пользователя они работают одинаково.

Это правильно ??

Answer 1

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

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

---

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

---

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

---

Сложность

             Insert/erase at the beginning       in middle        at the end

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

Answer 2

Из (от, но все еще очень полезного) SGI STL сводка deque:

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

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

Вот краткая информация о list с того же сайта:

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

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

Answer 3

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

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

Answer 4

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

Answer 5

Другой важной гарантией является то, как каждый отдельный контейнер хранит свои данные в памяти:

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

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

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

Answer 6

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