Warum funktioniert std :: Stack Verwendung std :: deque standardmäßig?

Question

Da die einzigen Operationen für einen Behälter erforderlich ist, um in einem Stapel verwendet werden, sind:

• zurück ()
• push_back ()
• pop_back ()

Warum ist der Standardcontainer für sie ein deque anstelle eines Vektors?

Sie nicht deque Umverteilungen einem Puffer von Elementen vor Front geben (), so dass push_front () ist ein effizienter Betrieb? Sind diese Elemente nicht verschwendet, da sie nie im Rahmen eines Stapels verwendet werden?

Wenn es keinen Overhead ist ein deque diese Art und Weise statt ein Vektor für die Verwendung, warum ist die Standardeinstellung für priority_queue ein Vektor kein deque auch? (Priority_queue erfordert vorne (), push_back () und pop_back () - im Wesentlichen die gleichen wie bei Stack)

---

aktualisiert auf der Grundlage der Antworten unter:

Es scheint, dass die Art und Weise deque ist in der Regel eine variable Größe Array fester Größe Arrays implementiert. Dies macht wächst schneller als ein Vektor (die Umschichtung und Kopieren erfordert), so etwas wie ein Stapel, die alle über das Hinzufügen und Entfernen von Elementen ist, deque wahrscheinlich eine bessere Wahl ist.

priority_queue erfordert Indizierung stark, wie jedes Herausnehmen und Einsetzen erfordert, dass Sie pop_heap () oder push_heap () auszuführen. Dies ist wahrscheinlich macht Vektor, der eine bessere Wahl gibt da ein Element hinzugefügt wird noch sowieso konstant abgeschrieben.

Answer 1

Wenn der Behälter wächst, erfordert eine Neuverteilung für einen Vektor alle Elemente in den neuen Speicherblock zu kopieren. ordnet einen neuen Block ein deque wächst und verbindet sie mit der Liste der Blöcke -. keine Kopien erforderlich sind,

Natürlich können Sie festlegen, dass ein anderer Trägerbehälter verwendet werden, wenn Sie mögen. Also, wenn Sie einen Stapel, die Sie wissen, ist nicht viel los zu wachsen, es sagt, ein Vektor anstelle einer deque zu verwenden, wenn das Ihre Präferenz ist.

Answer 2

Siehe Herb Sutter Guru der Woche 54 für die relativen Vorteile von Vektor- und deque wo entweder tun würde.

Ich stelle mir die Inkonsistenz zwischen priority_queue und Warteschlange einfach ist, dass verschiedene Menschen implementiert sie.