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 .

#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