Pourquoi std :: stack utilise std :: deque par défaut?

91

Puisque les seules opérations requises pour qu'un conteneur soit utilisé dans une pile sont:

  • arrière()
  • repousser()
  • pop_back ()

Pourquoi le conteneur par défaut est-il un deque au lieu d'un vecteur?

Les réallocations deque ne donnent-elles pas un tampon d'éléments avant front () pour que push_front () soit une opération efficace? Ces éléments ne sont-ils pas gaspillés puisqu'ils ne seront jamais utilisés dans le contexte d'une pile?

S'il n'y a pas de surcharge pour utiliser un deque de cette façon au lieu d'un vecteur, pourquoi la valeur par défaut pour priority_queue est-elle un vecteur pas également un deque? (priority_queue nécessite front (), push_back () et pop_back () - essentiellement les mêmes que pour stack)

Mis à jour en fonction des réponses ci-dessous:

Il semble que la façon dont deque est généralement implémentée est un tableau de taille variable de tableaux de taille fixe. Cela rend la croissance plus rapide qu'un vecteur (qui nécessite une réallocation et une copie), donc pour quelque chose comme une pile qui consiste à ajouter et supprimer des éléments, deque est probablement un meilleur choix.

priority_queue nécessite une indexation importante, car chaque suppression et insertion vous oblige à exécuter pop_heap () ou push_heap (). Cela fait probablement du vecteur un meilleur choix, car l'ajout d'un élément est toujours amorti constant de toute façon.

c++ stl containers Greg Rogers
la source
1
Le raisonnement de votre «mise à jour» n'est pas tout à fait correct. vector ajoute et supprime normalement des éléments de la fin plus rapidement qu'un deque. deque est plus rapide pour augmenter la mémoire , pas pour pousser des éléments.
Mooing Duck

Réponses:

75

Au fur et à mesure que le conteneur grandit, une réallocation pour un vecteur nécessite de copier tous les éléments dans le nouveau bloc de mémoire. La croissance d'un deque alloue un nouveau bloc et le lie à la liste des blocs - aucune copie n'est requise.

Bien sûr, vous pouvez spécifier qu'un conteneur de support différent soit utilisé si vous le souhaitez. Donc, si vous avez une pile dont vous savez qu'elle ne va pas grandir beaucoup, dites-lui d'utiliser un vecteur au lieu d'un deque si c'est votre préférence.

Michael Burr
la source
1
Mais lorsque la liste des pointeurs vers les blocs augmente, cette liste doit parfois être réallouée comme un vecteur le doit; asymptotiquement, tout gain d'efficacité est au mieux d'un facteur constant. Et la manipulation d'itérateur nécessaire pour effectuer correctement push and pop est beaucoup plus compliquée std::dequequ'elle ne l'est pour std::vector, et ces opérations sont susceptibles d'être utilisées beaucoup plus fréquemment que les réallocations. J'ai du mal à croire que std::dequecela battrait un jour std::vectoren pratique.
Marc van Leeuwen
@Michael Burr: Alors pourquoi ne pas utiliser list, pourquoi deque?
bappak
@MarcvanLeeuwen à votre sujet dit que vous avez du mal à croire ... pourriez-vous s'il vous plaît faire un point de vue clair? voulez-vous dire que vous pensez maintenant std::dequeavoir une chance de battre std::vectordans la pratique, ou voulez-vous dire que vous en doutez encore? Merci.
aafulei
@fleix Je ne vois pas pourquoi il est si important que j'aie personnellement plus de facilité à croire que std::dequecela fonctionnera aussi bien que std::vectordans les applications pratiques. Mais pour ce que cela vaut, mon expérience personnelle est que j'ai besoin de structures de données de pile et de file d'attente non pas pour une tâche importante et cruciale, mais pour de nombreuses petites occasions parsemées dans mon code. En tant que tel, je me soucie plus du comportement des petits que des grands; et deque y brille particulièrement terne. Ma préférence est de n'utiliser ni l'un ni l'autre, mais (auto-implémenté) des listes liées individuellement. Mais votre kilométrage peut varier.
Marc van Leeuwen
12

Voir le gourou de la semaine 54 de Herb Sutter de pour les mérites relatifs du vecteur et de quel domaine ferait l'un ou l'autre.

J'imagine que l'incohérence entre priority_queue et queue est simplement que différentes personnes les ont implémentées.

James Hopkin
la source
2
priority_queue n'utilise pas réellement push / pop_front, et les références à des éléments en plus du premier sont invalidées par les opérations de tas. Ainsi, aucun des avantages de deque ne s'appliquerait, contrairement au cas d'une file d'attente régulière.
Potatoswatter
9
En outre, priority_queuedoit rester trié, de sorte que la surcharge plus élevée de l'accès aléatoire deque::iteratorest plus problématique.
Potatoswatter
1
@Potatoswatter: priority_queuea un "ordre magique" qui est maintenu, il n'est pas trié. Cependant, votre argument est valable.
Mooing Duck