Warum verwendet std :: stack standardmäßig std :: deque?

90

Da die einzigen Operationen, die erforderlich sind, damit ein Container in einem Stapel verwendet werden kann, folgende sind:

  • zurück()
  • push_back ()
  • Pop zurück()

Warum ist der Standardcontainer dafür eine Deque anstelle eines Vektors?

Geben Deque-Neuzuweisungen nicht einen Puffer mit Elementen vor front () an, sodass push_front () eine effiziente Operation ist? Werden diese Elemente nicht verschwendet, da sie niemals im Kontext eines Stapels verwendet werden?

Wenn es keinen Overhead für die Verwendung einer Deque auf diese Weise anstelle eines Vektors gibt, warum ist die Standardeinstellung für priority_queue ein Vektor und keine Deque? (priority_queue erfordert front (), push_back () und pop_back () - im Wesentlichen dasselbe wie für stack)

Aktualisiert basierend auf den folgenden Antworten:

Es scheint, dass die Art und Weise, wie deque normalerweise implementiert wird, ein Array variabler Größe von Arrays fester Größe ist. Dies macht das Wachstum schneller als ein Vektor (der eine Neuzuweisung und ein Kopieren erfordert). Für so etwas wie einen Stapel, bei dem es nur um das Hinzufügen und Entfernen von Elementen geht, ist deque wahrscheinlich die bessere Wahl.

priority_queue erfordert eine starke Indizierung, da Sie bei jedem Entfernen und Einfügen pop_heap () oder push_heap () ausführen müssen. Dies macht den Vektor dort wahrscheinlich zu einer besseren Wahl, da das Hinzufügen eines Elements sowieso immer noch konstant abgeschrieben wird.

c++ stl containers Greg Rogers
quelle
1
Die Argumentation in Ihrem 'Update' ist nicht ganz richtig. Der Vektor fügt normalerweise Elemente schneller als eine Deque hinzu und entfernt sie vom Ende . deque ist schneller, um das Gedächtnis zu vergrößern , ohne Elemente zu verschieben.
Mooing Duck

Antworten:

74

Wenn der Container wächst, müssen für eine Neuzuweisung eines Vektors alle Elemente in den neuen Speicherblock kopiert werden. Wenn Sie eine Deque vergrößern, wird ein neuer Block zugewiesen und mit der Liste der Blöcke verknüpft. Es sind keine Kopien erforderlich.

Natürlich können Sie festlegen, dass ein anderer Hintergrundcontainer verwendet werden soll, wenn Sie möchten. Wenn Sie also einen Stapel haben, von dem Sie wissen, dass er nicht viel wachsen wird, sagen Sie ihm, dass er einen Vektor anstelle einer Deque verwenden soll, wenn Sie dies bevorzugen.

Michael Burr
quelle
1
Wenn jedoch die Liste der Zeiger auf Blöcke wächst, muss diese Liste gelegentlich neu zugewiesen werden, genau wie ein Vektor. asymptotisch ist jeder Effizienzgewinn bestenfalls ein konstanter Faktor. Die Iteratormanipulation, die erforderlich ist, um Push und Pop korrekt auszuführen, ist viel komplizierter std::dequeals für std::vector, und diese Operationen werden wahrscheinlich viel häufiger verwendet als Neuzuweisungen. Es fällt mir schwer zu glauben, dass std::dequedas std::vectorin der Praxis jemals schlagen würde .
Marc van Leeuwen
@ Michael Burr: Warum dann nicht verwenden list, warum deque?
Bappak
@MarcvanLeeuwen in Bezug auf Sie sagen, es fällt Ihnen schwer zu glauben ... könnten Sie bitte einen klaren Standpunkt vertreten? Meinst du, du glaubst jetzt, dass std::dequedu eine Chance std::vectorhast, in der Praxis zu schlagen , oder meinst du, du zweifelst immer noch daran? Vielen Dank.
aafulei
@fleix Ich verstehe nicht, warum es so wichtig ist, ob es mir persönlich leichter fällt zu glauben, dass std::dequedies genauso gut funktioniert wie std::vectorin praktischen Anwendungen. Meine persönliche Erfahrung ist jedoch, dass ich Stapel- und Warteschlangendatenstrukturen nicht für eine große und komplexitätskritische Aufgabe benötige, sondern für viele kleine Gelegenheiten, die durch meinen Code gestreut werden. Als solches interessiert mich das Verhalten im Kleinen mehr als im Großen; und deque leuchtet dort besonders langweilig. Ich bevorzuge es, stattdessen keine, sondern (selbst implementierte) einfach verknüpfte Listen zu verwenden. Ihr Kilometerstand kann jedoch variieren.
Marc van Leeuwen
12

Siehe Herb Sutters Guru der Woche 54 für die relativen Vorzüge von Vektor und Deque, wo beides tun würde.

Ich stelle mir vor, dass die Inkonsistenz zwischen priority_queue und queue einfach darin besteht, dass verschiedene Personen sie implementiert haben.

James Hopkin
quelle
2
priority_queue verwendet nicht wirklich push / pop_front, und Verweise auf Elemente neben dem ersten werden durch die Heap-Operationen ungültig. Im Gegensatz zu einer regulären Warteschlange würde also keiner der Vorteile von deque zutreffen.
Potatoswatter
9
Auch priority_queuemuss bleiben sortiert, damit der höhere Aufwand für zufällig Zugriff auf deque::iteratormehr problematisch ist.
Potatoswatter
1
@Potatoswatter: priority_queuehat eine "magische Ordnung", die beibehalten wird, es ist nicht sortiert. Ihr Punkt steht jedoch.
Mooing Duck