Pourquoi ne std::stack utiliser std::deque par défaut?

Car les seules opérations nécessaires pour un conteneur pour être utilisé dans une pile sont:

  • back()
  • push_back()
  • pop_back()

Pourquoi le conteneur par défaut pour un deque au lieu d'un vecteur?

Ne pas deque réallocations de donner un tampon d'éléments avant (front), de sorte que push_front() est une exploitation efficace? Ne sont pas ces éléments perdre car ils ne pourront jamais être utilisé dans le contexte d'une pile?

Si il n'y a pas de frais généraux pour l'utilisation d'un deque de cette façon, au lieu d'un vecteur, pourquoi est la valeur par défaut pour priority_queue un vecteur non d'un deque aussi? (priority_queue nécessite l'avant(), push_back(), et pop_back() - essentiellement les mêmes que pour la pile)

Mis à jour sur la base des Réponses ci-dessous:

Il semble que l'deque est généralement mis en œuvre est une variable tableau de taille fixe, la taille des tableaux. Cela rend à croissance plus rapide qu'un vecteur (qui nécessite la réaffectation et à la reproduction), donc quelque chose comme une pile, ce qui est tout au sujet de l'ajout et la suppression d'éléments, deque est probablement un meilleur choix.

priority_queue nécessite d'indexation fortement, comme chaque retrait et l'insertion de vous oblige à exécuter pop_heap() ou push_heap(). C'est probablement ce qui fait vector un meilleur choix, il y depuis l'ajout d'un élément est toujours amorti constant de toute façon.

  • Le raisonnement suivi dans votre "mise à jour" n'est pas tout à fait droit. vecteur normalement ajoute et supprime des éléments à partir de la fin plus rapide qu'un deque. deque est plus rapide pour la culture de la mémoire, non pas de pousser des éléments.
InformationsquelleAutor Greg Rogers | 2008-09-19
  1. 71

    Que le conteneur se développe, une réaffectation pour un vecteur nécessite la copie de tous les éléments dans le nouveau bloc de mémoire. La croissance d'une deque alloue un nouveau bloc et les liens à la liste des blocs - pas de copies sont nécessaires.

    Bien sûr, vous pouvez spécifier qu'un autre support de conteneur être utilisé si vous le souhaitez. Donc, si vous avez une pile que vous savez ne va pas croître beaucoup, de lui dire d'utiliser un vecteur lieu d'une deque si c'est votre préférence.

    • Mais quand la liste de pointeurs vers les blocs se développe, cette liste doit parfois être réaffecté comme un vecteur doit; asymptotiquement, le gain en efficacité est par un facteur constant, au mieux. Et itérateur de manipulation nécessaires pour faire des push et pop correctement est beaucoup plus compliqué pour std::deque que c'est pour std::vector, et ces opérations sont susceptibles d'être utilisées beaucoup plus fréquemment que les réaffectations. J'ai du mal à croire que std::deque serait jamais battu std::vector dans la pratique.
    • Bavure: Alors pourquoi ne pas utiliser list, pourquoi deque?
    • quant à vous dire que vous avez un moment difficile de croire ... pourriez-vous s'il vous plaît faire un point de vue clair? voulez-vous dire maintenant, vous êtes croyant std::deque n'ont une chance de battre std::vector dans la pratique, ou voulez-vous dire que vous encore en douter? merci.
    • Je ne vois pas pourquoi il est si important de savoir si personnellement, je n'ai plus de facilité à croire que std::deque feront aussi bien std::vector dans des applications pratiques. Mais pour ce que sa vaut le coup, mon expérience personnelle est que j'ai besoin de pile et file d'attente des structures de données non pas pour une grande et de la complexité des tâches essentielles, mais pour de nombreuses petites occasions répandue à travers mon code. En tant que tel je me soucie plus sur le comportement dans les petites que dans les grandes; et deque brille particulièrement ennuyeux il. Ma préférence est de ne pas utiliser, mais (auto-mis en œuvre), isolés des listes liées à la place. Mais vous le kilométrage peut varier.
    InformationsquelleAutor Michael Burr
  2. 12

    Voir Herb Sutter est Gourou de la Semaine 54 pour les mérites relatifs de vecteur et deque où l'un et l'autre n'.

    J'imagine que l'incohérence entre priority_queue et la file d'attente est tout simplement que des personnes différentes mises en œuvre.

    • priority_queue ne fait pas les utiliser push/pop_front, et les références à des éléments en plus de la première sont invalidés par le segment des opérations. Ainsi, aucun des avantages de la deque s'appliquerait, contrairement au cas d'une file d'attente régulière.
    • Aussi, priority_queue doit rester triés, de sorte que la hausse des frais généraux de l'accès au hasard deque::iterator est plus problématique.
    • a une "magie de l'ordre" qui est maintenu, il n'est pas triée. Cependant, votre point de stands.
    InformationsquelleAutor James Hopkin