Qual é a diferença entre contêineres STL deque e lista?

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

  •  07-07-2019
  •  | 
  •  

Pergunta

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

Isso está correto ??

Foi útil?

Solução

A partir do (datada, mas ainda muito útil) SGI STL resumo de deque :

Uma fila de dupla extremidade é muito parecido com um vector: como vector, que é uma sequência que suportes de acesso aleatório aos elementos, a inserção de tempo constante e remoção de elementos no final da sequência, e inserção de tempo linear e remoção de elementos do meio.

O principal modo pelo qual difere deque de vector é que também suporta fila de dupla extremidade de inserção e a remoção constante de tempo de elementos no início da sequência. Além disso, deque não tem nenhum membro funções análogas à capacidade do vector () e de reserva (), e não fornece nenhuma das garantias sobre iterador validade que estão associados com as funções de membro.

Aqui está o resumo na list do mesmo site:

A lista é uma lista duplamente ligada. Isto é, é uma sequência que suporta tanto para a frente e para trás de passagem, e (amortizado) inserção de tempo constante e remoção de elementos, no início ou no final, ou no meio. Listas têm a propriedade importante que a inserção e splicing não faça iterators Invalidate a elementos da lista, e que invalida remoção até mesmo apenas os iteradores que apontam para os elementos que são removidos. A ordenação dos iteradores podem ser alterados (isto é, a lista :: iterator pode ter um predecessor diferente ou sucessor depois de uma operação de lista do que antes), mas os iteradores próprios não serão invalidados ou feita para apontar para diferentes elementos, a menos que a invalidação ou mutação é explícita.

Em resumo, os recipientes podem ter rotinas compartilhado, mas as garantias tempo para essas rotinas diferem de recipiente para recipiente . Isto é muito importante quando se considera que destes recipientes de usar para uma tarefa: tendo em conta como o recipiente será mais utilizado (por exemplo, mais para a busca do que para inserção / deleção) vai um longo caminho em direcionando-o para o recipiente certo.

Outras dicas

Deixe-me lista as diferenças:

  • Deque administra seus elementos com um matriz dinâmica , fornece aleatória acesso , e tem quase o mesmo interface como um vector.
  • Lista administra seus elementos como um duplamente lista ligada e não faz fornecer acesso aleatório .
  • Deque fornece inserções rápidas e deleções em tanto o fim eo começo. Inserir e apagar dispositivos o meio é relativamente lento porque todos os elementos até, quer de ambos extremidades pode ser movido para a sala ou para fazer preencher uma lacuna.
  • Em Lista , inserir e remover elementos é rápido em cada posição, incluindo ambas as extremidades.
  • Deque : Qualquer inserção ou exclusão de elementos outra do que no início ou extremidade invalida todos os ponteiros, referências, e iteradores que se referem a elementos do deque.
  • Lista : Inserir e excluir elementos faz Não ponteiros invalidar 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 ligada.

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

No. Uma fila de dupla extremidade apenas suporta O (1) de inserção e eliminação na frente e para trás. Pode, por exemplo, ser implementado em um vetor com wrap-around. Uma vez que também garante (1) de acesso aleatório O, você pode ter certeza que não está usando (apenas) uma lista duplamente ligada.

Outra garantia importante é a forma como cada lojas diferentes contêineres seus dados na memória:

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

Note que o deque foi projetado para tentar equilibrar as vantagens de ambos vector e lista sem suas respectivas desvantagens. É um recipiente especialmente interessante em plataformas de memória limitada, por exemplo, microcontroladores.

A estratégia de armazenamento de memória é muitas vezes esquecido, no entanto, é frequentemente uma das mais importantes razões para selecionar o recipiente mais adequado para uma determinada aplicação.

As diferenças de desempenho foram bem explicados por outros. Eu só queria acrescentar que as interfaces semelhantes ou mesmo idênticos são comuns em programação orientada a objetos - parte da metodologia geral de escrever software orientado a objetos. Você deve em nenhuma maneira supor que duas classes funcionam da mesma maneira, simplesmente porque eles implementam a mesma interface, mais do que você deve assumir que um cavalo funciona como um cachorro porque ambos implementar ataque () e make_noise ().

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top