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

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

Это верно??

Из (датированного, но все еще очень полезного) резюме SGI STLdeque :

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

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

Вот сводка listс того же сайта:

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

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

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

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

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

• Deque : любая вставка или удаление элементов, кроме начала или конца, делает недействительными все указатели, ссылки и итераторы, которые относятся к элементам 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. Он имеет постоянное время доступа по индексу, а также возможность вставки и удаления в начале и в конце, что обеспечивает кардинально отличные характеристики производительности от списка.

Еще одна важная гарантия - это способ хранения данных в памяти каждым контейнером:

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

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

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

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

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

Вот доказательство концепции использования кода списка, неупорядоченной карты, которая дает O (1) поиск и O (1) точное обслуживание LRU. Требуются (не стертые) итераторы, чтобы выдержать операции стирания. Планируйте использовать в O (1) произвольно большой программно управляемый кеш для указателей ЦП в памяти графического процессора. Указывает на планировщик Linux O (1) (LRU <-> очередь выполнения на процессор). Unordered_map имеет постоянный доступ по времени через хеш-таблицу.

#include <iostream> 
#include <list> 
#include <unordered_map>  
using namespace std; 

struct MapEntry {
  list<uint64_t>::iterator LRU_entry;
  uint64_t CpuPtr;
};
typedef unordered_map<uint64_t,MapEntry> Table;
typedef list<uint64_t> FIFO;
FIFO  LRU;        // LRU list at a given priority 
Table DeviceBuffer; // Table of device buffers

void Print(void){
  for (FIFO::iterator l = LRU.begin(); l != LRU.end(); l++) {
    std::cout<< "LRU    entry "<< *l << "   :    " ;
    std::cout<< "Buffer entry "<< DeviceBuffer[*l].CpuPtr <<endl;
  }  
}
int main() 
{ 

  LRU.push_back(0);
  LRU.push_back(1);
  LRU.push_back(2);
  LRU.push_back(3);
  LRU.push_back(4);

  for (FIFO::iterator i = LRU.begin(); i != LRU.end(); i++) {
    MapEntry ME = { i, *i}; 
    DeviceBuffer[*i] = ME;
  }

  std::cout<< "************ Initial set of CpuPtrs" <<endl;
  Print();

  {
    // Suppose evict an entry - find it via "key - memory address uin64_t" and remove from 
    // cache "tag" table AND LRU list with O(1) operations
    uint64_t key=2;
    LRU.erase(DeviceBuffer[2].LRU_entry);
    DeviceBuffer.erase(2);
  }

  std::cout<< "************ Remove item 2 " <<endl;
  Print();

  { 
    // Insert a new allocation in both tag table, and LRU ordering wiith O(1) operations
    uint64_t key=9;
    LRU.push_front(key); 
    MapEntry ME = { LRU.begin(), key };
    DeviceBuffer[key]=ME;
  }

  std::cout<< "************ Add item 9  " <<endl;
  Print();

  std::cout << "Victim "<<LRU.back()<<endl;
} 

Среди выдающихся различий между dequeиlist

• Для deque:

  Предметы хранятся рядом;

  Оптимизирован для добавления данных с двух сторон (спереди, сзади);

  Элементы индексируются числами (целыми числами).

  Может просматриваться итераторами и даже индексом элемента.

  Время доступа к данным быстрее.

• За list

  Элементы хранятся в памяти «случайным образом»;

  Доступен для просмотра только итераторами;

  Оптимизирован для вставки и извлечения посередине.

  Доступ по времени к данным медленнее, медленнее для итерации из-за очень плохой пространственной локализации.

  Очень хорошо справляется с крупными элементами

Вы также можете проверить следующую ссылку , в которой сравнивается производительность между двумя контейнерами STL (с std :: vector)

Надеюсь, я поделился полезной информацией.