Por que std :: stack usa std :: deque por padrão?

91

Uma vez que as únicas operações necessárias para que um contêiner seja usado em uma pilha são:

  • costas()
  • retrocesso()
  • pop_back ()

Por que o contêiner padrão para ele é um deque em vez de um vetor?

As realocações deque não fornecem um buffer de elementos antes de front () para que push_front () seja uma operação eficiente? Esses elementos não são desperdiçados, já que nunca serão usados ​​no contexto de uma pilha?

Se não houver sobrecarga para usar um deque dessa maneira em vez de um vetor, por que o padrão para priority_queue é um vetor e não um deque também? (priority_queue requer front (), push_back () e pop_back () - essencialmente o mesmo que para pilha)

Atualizado com base nas respostas abaixo:

Parece que a maneira como o deque é geralmente implementado é uma matriz de tamanho variável de matrizes de tamanho fixo. Isso torna o crescimento mais rápido do que um vetor (o que requer realocação e cópia), então, para algo como uma pilha que envolve adicionar e remover elementos, o deque é provavelmente uma escolha melhor.

priority_queue requer muita indexação, já que toda remoção e inserção requer que você execute pop_heap () ou push_heap (). Isso provavelmente torna o vetor uma escolha melhor, já que adicionar um elemento ainda é uma constante amortizada de qualquer maneira.

c++ stl containers Greg Rogers
fonte
1
O raciocínio em sua 'atualização' não está certo. o vetor normalmente adiciona e remove elementos do final mais rápido do que um deque. deque é mais rápido para aumentar a memória , não empurrar elementos.
Mooing Duck

Respostas:

75

Conforme o contêiner cresce, uma realocação de um vetor requer a cópia de todos os elementos para o novo bloco de memória. Aumentar um deque aloca um novo bloco e o vincula à lista de blocos - nenhuma cópia é necessária.

Claro, você pode especificar que um contêiner de apoio diferente seja usado, se desejar. Portanto, se você tem uma pilha que sabe que não vai crescer muito, diga a ela para usar um vetor em vez de um deque, se essa for sua preferência.

Michael Burr
fonte
1
Mas quando a lista de ponteiros para blocos aumenta, essa lista deve ser realocada ocasionalmente, assim como um vetor deve; assintoticamente, qualquer ganho em eficiência ocorre por um fator constante, na melhor das hipóteses. E a manipulação do iterador necessária para fazer push e pop corretamente é muito mais complicada do std::dequeque para a qual é std::vector, e essas operações provavelmente serão usadas com muito mais frequência do que realocações. Eu tenho dificuldade em acreditar que std::dequealgum dia seria melhor std::vectorna prática.
Marc van Leeuwen
@Michael Burr: Então por que não usar list, por quê deque?
bappak
@MarcvanLeeuwen, a respeito de você, diz que acha difícil acreditar ... poderia, por favor, fazer um ponto de vista claro? quer dizer que agora você acredita std::dequeque tem uma chance de vencer std::vectorna prática, ou quer dizer que ainda duvida? obrigado.
aafulei
@fleix Não vejo por que isso é tão importante se eu pessoalmente acho mais fácil acreditar que std::dequefuncionará tão bem quanto std::vectorem aplicações práticas. Mas, para valer a pena, minha experiência pessoal é que preciso empilhar e enfileirar estruturas de dados não para uma tarefa grande e crucial para a complexidade, mas para muitas pequenas ocasiões espalhadas por meu código. Como tal, preocupo-me mais com o comportamento nas pequenas do que nas grandes; e deque brilha particularmente maçante lá. Minha preferência é não usar nenhum dos dois, mas apenas listas vinculadas individualmente (autoimplementadas). Mas sua milhagem pode variar.
Marc van Leeuwen
12

Consulte o Guru da Semana 54 de Herb Sutter para os méritos relativos do vetor e deque onde qualquer um deles serviria.

Imagino que a inconsistência entre priority_queue e queue é simplesmente que diferentes pessoas os implementaram.

James Hopkin
fonte
2
priority_queue não usa push / pop_front, e referências a elementos além do primeiro são invalidadas pelas operações de heap. Portanto, nenhum dos benefícios do deque se aplicaria, ao contrário do caso de uma fila normal.
Potatoswatter
9
Além disso, priority_queuedeve permanecer classificado, de forma que a maior sobrecarga do acesso aleatório deque::iteratorseja mais problemática.
Potatoswatter
1
@Potatoswatter: priority_queuetem uma "ordem mágica" que é mantida, não é classificada. No entanto, seu ponto permanece.
Mooing Duck