Qual é a diferença entre recipientes deque e list STL?

Qual é a diferença entre os dois? Quero dizer, os métodos são todos iguais. Portanto, para um usuário, eles funcionam de forma idêntica.

Isso está correto ??

Do resumo (datado, mas ainda muito útil) SGI STL de deque:

Um deque é muito parecido com um vetor: como um vetor, é uma sequência que suporta acesso aleatório a elementos, inserção e remoção de elementos em tempo constante no final da sequência e inserção e remoção de elementos em tempo linear no meio.

A principal maneira pela qual o deque difere do vetor é que o deque também suporta a inserção e remoção de elementos no tempo constante no início da sequência. Além disso, deque não tem funções-membro análogas à capacidade do vetor () e à reserva (), e não oferece nenhuma das garantias sobre a validade do iterador que estão associadas a essas funções-membro.

Aqui está o resumo listdo mesmo site:

Uma lista é uma lista duplamente vinculada. Ou seja, é uma Sequência que suporta travessias para a frente e para trás e inserção e remoção de elementos constantes (amortizados) no início ou no final, ou no meio. As listas têm a propriedade importante de que a inserção e o splicing não invalidam os iteradores para os elementos da lista e que mesmo a remoção invalida apenas os iteradores que apontam para os elementos removidos. A ordem dos iteradores pode ser alterada (ou seja, list :: iterator pode ter um predecessor ou sucessor diferente após uma operação de lista do que antes), mas os próprios iteradores não serão invalidados ou apontados para diferentes elementos, a menos que essa invalidação ou a mutação é explícita.

Em resumo, os containers podem ter rotinas compartilhadas, mas as garantias de tempo para essas rotinas diferem de container para container . Isso é muito importante ao considerar qual desses contêineres usar para uma tarefa: levar em consideração como o contêiner será usado com mais frequência (por exemplo, mais para pesquisa do que para inserção / exclusão) ajuda muito a direcioná-lo para o contêiner certo .

Deixe-me listar as diferenças:

• Deque gerencia seus elementos com uma matriz dinâmica , fornece acesso aleatório e tem quase a mesma interface de um vetor.
• Lista gerencia seus elementos como uma lista duplamente vinculada e não fornece acesso aleatório .

• O Deque fornece inserções e exclusões rápidas no final e no início. Inserir e excluir elementos no meio é relativamente lento porque todos os elementos até uma das duas extremidades podem ser movidos para abrir espaço ou preencher uma lacuna.
• Em List , inserir e remover elementos é rápido em cada posição, incluindo ambas as extremidades.

• Deque : qualquer inserção ou exclusão de elementos que não sejam no início ou no final invalida todos os ponteiros, referências e iteradores que se referem a elementos do deque.
• Lista : inserir e excluir elementos não invalida ponteiros, referências e iteradores para outros elementos.

Complexidade

             Insert/erase at the beginning       in middle        at the end

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

std::list é basicamente uma lista duplamente vinculada.

std::deque, por outro lado, é implementado mais como std::vector. Possui tempo de acesso constante por índice, bem como inserção e remoção no início e no final, o que fornece características de desempenho drasticamente diferentes de uma lista.

Outra garantia importante é a maneira como cada contêiner diferente armazena seus dados na memória:

• Um vetor é um único bloco de memória contíguo.
• Um deque é um conjunto de blocos de memória vinculados, onde mais de um elemento é armazenado em cada bloco de memória.
• Uma lista é um conjunto de elementos dispersos na memória, ou seja: apenas um elemento é armazenado por "bloco" de memória.

Observe que o deque foi projetado para tentar equilibrar as vantagens do vetor e da lista, sem suas respectivas desvantagens. É um contêiner especialmente interessante em plataformas de memória limitada, por exemplo, microcontroladores.

A estratégia de armazenamento de memória é freqüentemente esquecida, entretanto, é frequentemente um dos motivos mais importantes para selecionar o contêiner mais adequado para um determinado aplicativo.

Não. Um deque só suporta inserção e exclusão O (1) na frente e atrás. Pode, por exemplo, ser implementado em um vetor com wrap-around. Visto que também garante acesso aleatório O (1), você pode ter certeza de que não está usando (apenas) uma lista duplamente vinculada.

As diferenças de desempenho foram bem explicadas por outros. Eu só queria acrescentar que interfaces semelhantes ou mesmo idênticas são comuns na programação orientada a objetos - parte da metodologia geral de escrever software orientado a objetos. Você não deve DE MANEIRA nenhuma supor que duas classes funcionam da mesma maneira simplesmente porque implementam a mesma interface, mais do que você deve supor que um cavalo funciona como um cão porque ambas implementam attack () e make_noise ().

Aqui está uma prova de conceito de uso de um mapa de lista e não ordenado que fornece O (1) lookup e O (1) manutenção exata de LRU. Necessita dos iteradores (não apagados) para sobreviver às operações de apagamento. Planeje usar em um cache gerenciado por software arbitrariamente grande O (1) para ponteiros de CPU na memória da GPU. Acena para o agendador Linux O (1) (fila de execução LRU <-> por processador). O unordered_map tem acesso de tempo constante por meio da tabela hash.

#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;
} 

Entre as diferenças eminentes entre dequeelist

• Para deque:

  Itens armazenados lado a lado;

  Otimizado para adicionar dados de dois lados (frente, verso);

  Elementos indexados por números (inteiros).

  Pode ser navegado por iteradores e até mesmo pelo índice do elemento.

  O tempo de acesso aos dados é mais rápido.

• Para list

  Itens armazenados "aleatoriamente" na memória;

  Pode ser navegado apenas por iteradores;

  Otimizado para inserção e remoção no meio.

  O tempo de acesso aos dados é mais lento, lento para iterar, devido à sua localização espacial muito pobre.

  Lida muito bem com elementos grandes

Você pode verificar também o seguinte Link , que compara o desempenho entre os dois contêineres STL (com std :: vector)

Espero ter compartilhado algumas informações úteis.