Pourquoi std::stack utilise-t-il std::deque par défaut ?

Question

Étant donné que les seules opérations requises pour qu'un conteneur puisse être utilisé dans une pile sont les suivantes

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

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

Les réallocations de deque ne donnent-elles pas un tampon d'éléments avant front() de sorte que push_front() est 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 surcoût à utiliser une deque de cette façon au lieu d'un vector, pourquoi la valeur par défaut de priority_queue est-elle un vector et non une deque ? (priority_queue nécessite front(), push_back(), et pop_back() - essentiellement la même chose que pour stack)

---

Mise à jour sur la base des réponses ci-dessous :

Il semble que la façon dont les deque sont habituellement implémentés est un tableau de taille variable de tableaux de taille fixe. Cela permet une 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 retrait ou insertion nécessite l'exécution de pop_heap() ou de push_heap(). Cela fait probablement de vector un meilleur choix puisque l'ajout d'un élément est de toute façon amorti de façon constante.

Answer 1

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

Bien entendu, vous pouvez spécifier l'utilisation d'un autre conteneur d'appui si vous le souhaitez. Ainsi, si vous avez une pile dont vous savez qu'elle n'augmentera pas beaucoup, dites-lui d'utiliser un vecteur au lieu d'un deque si c'est ce que vous préférez.

Answer 2

Voir l'article de Herb Sutter Gourou de la semaine 54 pour connaître les mérites relatifs de vector et deque lorsque l'un ou l'autre ferait l'affaire.

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