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

StackOverflow https://stackoverflow.com/questions/1436020

  •  07-07-2019
  •  | 
  •  

Вопрос

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

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

Это было полезно?

Решение

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

  

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

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

Вот краткое описание list из тот же сайт:

  

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

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

Другие советы

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

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

Сложность

             Insert/erase at the beginning       in middle        at the end

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top