std:: deque

std::deque (Double-Ended-Queue) ist eine indizierte Sequenz-Container-Klasse, die schnelles Einfügen und Löschen an ihrem Anfang und Ende ermöglicht. Darüber hinaus machen Einfüge- und Löschoperationen an beiden Enden einer Deque Zeiger oder Referenzen auf die restlichen Elemente niemals ungültig.

Im Gegensatz zu std::vector sind die Elemente einer deque nicht zusammenhängend gespeichert: Typische Implementierungen verwenden eine Sequenz von einzeln allokierten Arrays fester Größe mit zusätzlicher Buchhaltung, was bedeutet, dass der indizierte Zugriff auf deque zwei Pointer-Dereferenzierungen durchführen muss, verglichen mit dem indizierten Zugriff von vector, der nur eine durchführt.

Die Speicherung eines Deque wird automatisch nach Bedarf erweitert und verkleinert. Die Erweiterung eines Deque ist kostengünstiger als die Erweiterung eines std::vector , da sie keine Kopie der vorhandenen Elemente an einen neuen Speicherort beinhaltet. Andererseits haben Deques typischerweise hohe minimale Speicherkosten; ein Deque, das nur ein Element enthält, muss sein vollständiges internes Array allokieren (z.B. 8-fache Objektgröße auf 64-Bit libstdc++; 16-fache Objektgröße oder 4096 Bytes, je nachdem was größer ist, auf 64-Bit libc++).

Die Komplexität (Effizienz) gängiger Operationen auf Deques ist wie folgt:

• Direktzugriff - konstant O(1) .
• Einfügen oder Entfernen von Elementen am Ende oder Anfang - konstant O(1) .
• Einfügen oder Entfernen von Elementen - linear O(n) .

std::deque erfüllt die Anforderungen von Container , AllocatorAwareContainer , SequenceContainer und ReversibleContainer .

Template-Parameter

Iterator-Invalidierung

Ungültigkeitshinweise

• Beim Einfügen an einem der beiden Enden der Deque werden Referenzen durch insert und emplace nicht ungültig.
• push_front , push_back , emplace_front und emplace_back machen keine Referenzen auf Elemente der Deque ungültig.
• Beim Löschen an einem der beiden Enden der Deque werden Referenzen auf nicht gelöschte Elemente durch erase , pop_front und pop_back nicht ungültig.
• Ein Aufruf von resize mit einer kleineren Größe macht keine Referenzen auf nicht gelöschte Elemente ungültig.
• Ein Aufruf von resize mit einer größeren Größe macht keine Referenzen auf Elemente der Deque ungültig.

Mitgliedertypen

Memberfunktionen

Nicht-Member-Funktionen

Hinweise

Beispiel

#include <deque>
#include <iostream>
int main()
{
    // Erstelle eine Deque mit Ganzzahlen
    std::deque<int> d = {7, 5, 16, 8};
    // Füge eine Ganzzahl am Anfang und Ende der Deque hinzu
    d.push_front(13);
    d.push_back(25);
    // Iteriere und gebe Werte der Deque aus
    for (int n : d)
        std::cout << n << ' ';
    std::cout << '\n';
}

13 7 5 16 8 25

Fehlerberichte

Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

Siehe auch