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

Question

Les seules opérations nécessaires à l'utilisation d'un conteneur dans une pile étant les suivantes:

• retour ()
• push_back ()
• pop_back ()

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

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

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

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

Il semble que deque soit généralement implémenté comme un tableau de taille variable constitué de tableaux de taille fixe. Cela accélère la croissance par rapport à un vecteur (ce qui nécessite une réallocation et une copie), donc pour quelque chose qui ressemble à une pile, qui consiste à ajouter et à supprimer des éléments, deque est probablement un meilleur choix.

priority_queue nécessite beaucoup d'indexation, car chaque suppression et insertion nécessite l'exécution de pop_heap () ou de push_heap (). Cela fait probablement du vecteur un meilleur choix car l’ajout d’un élément est quand même amorti de façon constante.

Answer 1

À mesure que le conteneur grandit, la réallocation d'un vecteur nécessite la copie de tous les éléments dans le nouveau bloc de mémoire. Développer 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 grossira pas beaucoup, dites-lui d'utiliser un vecteur au lieu d'un deque si c'est votre préférence.

Answer 2

Voir le Gourou de la semaine 54 de Herb Sutter pour les mérites relatifs de vector et deque où l'un ou l'autre ferait l'affaire.

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