Контейнеры C++ STL: в чем разница между deque и list?

Question

Контейнеры C++ STL: в чем разница между deque и list?

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

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

847 6

c++stl list deque

6 ответов:

Comments

Ничего не найдено.

fbrereto · Accepted Answer · 2009-09-17 02:34:58

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

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

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

вот резюме на list С того же сайта:

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

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

aJ. · Accepted Answer · 2016-08-18 18:42:15

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

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

список управляет своими элементами как a двусвязный список и не обеспечьте произвольный доступ.

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

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

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

список: вставка и удаление элементов делает не аннулировать указатели, ссылки, и итераторы к другим элементам.

сложности
             Insert/erase at the beginning       in middle        at the end

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

Reed Copsey · Accepted Answer · 2009-09-17 02:36:52

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

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

Jonathan Graehl · Accepted Answer · 2009-09-17 02:25:27

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

jose.angel.jimenez · Accepted Answer · 2014-10-27 00:28:31

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

вектор-это один непрерывный блок памяти.

deque-это набор связанных блоков памяти, где в каждом блоке памяти хранится более одного элемента.

список представляет собой набор элементов, рассеянных в памяти, т. е. только один элемент хранится в памяти "блок".

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

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

Lee B · Accepted Answer · 2009-09-17 03:05:45

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