WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::deque: doppelseitige Warteschlange mit wahlfreiem Zugriff

std::deque bietet schnelle Operationen an beiden Enden und wahlfreien Zugriff, garantiert aber keinen zusammenhängenden Puffer für alle Elemente.

Version: C++23

Syntax

template<class T, class Allocator = std::allocator<T>>
class deque;

void push_front(const T& value);
void push_back(const T& value);
void pop_front();
void pop_back();

std::deque<T> aus <deque> ist ein Sequenzcontainer mit Random-Access-Iteratoren. Ein einzelnes Element an Anfang oder Ende einzufügen oder zu löschen benötigt konstante Zeit, Operationen in der Mitte sind linear. Anders als bei std::vector liegen die Elemente nicht zwingend zusammenhängend; &d[0] ist daher nicht der Anfang eines Arrays der gesamten deque.

Ein Einfügen in der Mitte macht alle Iteratoren und Referenzen ungültig. Einfügen an einem Ende invalidiert alle Iteratoren, erhält aber Referenzen auf bestehende Elemente. Löschen des letzten Elements invalidiert den Past-the-end-Iterator und Zugriffe auf gelöschte Elemente; Löschen des ersten, aber nicht letzten Elements betrifft nur gelöschte Elemente, während Löschen in der Mitte alles invalidiert. Daher löscht pop_front() bei einer deque mit einem Element zugleich das letzte Element und invalidiert end().

operator[] prüft den Index nicht, at() wirft dagegen std::out_of_range. front(), back() und pop_* verlangen einen nichtleeren Container. Häufige Arbeit an beiden Enden ist ein typischer Einsatz; für zusammenhängende Daten oder stabile Iteratoren nach dem Anhängen ist die Containerwahl neu zu prüfen.

Beispiele

#include <deque>
#include <iostream>

int main() {
    std::deque<int> values;
    values.push_back(2);
    values.push_back(3);
    values.push_front(1);
    values.pop_back();
    std::cout << values.size() << ' ' << values.front() << ' ' << values.back() << '\n';
}

Ergebnis

2 1 2

std::deque → 2 1 2

Quellen