std::deque

 

C++

Compiler-Unterstützung

Freestanding und gehostet

Sprache

Standardbibliothek

Header der Standardbibliothek

Benannte Anforderungen

Feature-Test-Makros (C++20)

Bibliothek für Sprachunterstützung

Konzepte-Bibliothek (C++20)

Diagnostik-Bibliothek

Speicherverwaltungsbibliothek

Metaprogrammierungsbibliothek (C++11)

Allgemeine Dienstprogramme-Bibliothek

Container-Bibliothek

Iterator-Bibliothek

Ranges-Bibliothek (C++20)

Algorithmen-Bibliothek

Bibliothek für Zeichenketten

Textverarbeitungsbibliothek

Numerik-Bibliothek

Datums- und Zeitbibliothek

Ein-/Ausgabe-Bibliothek

Dateisystembibliothek (C++17)

Unterstützung für nebenläufige Programmierung (C++11)

Ausführungssteuerungsbibliothek (C++26)

Technische Spezifikationen

Symbolverzeichnis

Externe Bibliotheken

 

Container-Bibliothek

Sequenz

array (C++11)

vector

vector<bool>

inplace_vector (C++26)

hive (C++26)

deque

forward_list (C++11)

list

Assoziativ

setzt

multiset

map

multimap

Ungeordnete assoziative

unordered_set (C++11)

unordered_multiset (C++11)

unordered_map (C++11)

unordered_multimap (C++11)

Adapter

stack

queue

priority_queue

flat_set (C++23)

flat_multiset (C++23)

flat_map (C++23)

flat_multimap (C++23)

Ansichten

span (C++20)

mdspan (C++23)

Tabellen

Iterator-Invalidierung

Mitgliedsfunktionstabelle

Nicht-Mitgliedsfunktionstabelle

 

std::deque

Membertypen
Memberfunktionen
deque::deque deque::~deque deque::operator= deque::assign deque::assign_range (C++23)   deque::get_allocator Elementzugriff deque::at deque::operator[] deque::front deque::back Iteratoren deque::begindeque::cbegin (C++11) deque::enddeque::cend (C++11) deque::rbegindeque::crbegin (C++11) deque::renddeque::crend (C++11)	Kapazität deque::empty deque::size deque::max_size deque::shrink_to_fit (DR*) Modifizierer deque::clear deque::insert deque::insert_range (C++23) deque::emplace deque::erase deque::push_front deque::emplace_front (C++11) deque::prepend_range (C++23) deque::pop_front deque::push_back deque::emplace_back (C++11) deque::append_range (C++23) deque::pop_back deque::resize deque::swap
Nicht-Member-Funktionen
operator==operator<=> (C++20) swap(std::deque) erase(std::deque)erase_if(std::deque) (C++20)(C++20)	operator!=operator<operator>operator<=operator>= (bis C++20)(bis C++20)(bis C++20)(bis C++20)(bis C++20)
Deduktionsleitfäden(C++17)

 

Definiert in Header <deque>
template<     class T,     class Allocator = std::allocator<T> > class deque;	(1)
namespace pmr {     template< class T >     using deque = std::deque<T, std::pmr::polymorphic_allocator<T>>; }	(2)	(seit C++17)

std::deque (double-ended queue) ist ein indizierter Sequenzcontainer, der schnelle Einfüge- und Löschoperationen sowohl am Anfang als auch am Ende erlaubt. Zusätzlich machen Einfüge- und Löschoperationen an beiden Enden eines Deque niemals Zeiger oder Referenzen auf die restlichen Elemente ungültig.

Im Gegensatz zu std::vector sind die Elemente eines Deque nicht zusammenhängend gespeichert: Typische Implementierungen verwenden eine Sequenz von einzeln allozierten Arrays fester Größe mit zusätzlicher Verwaltungsstruktur. Das bedeutet, dass der indizierte Zugriff auf ein Deque zwei Dereferenzierungen von Zeigern erfordert, verglichen mit dem indizierten Zugriff eines Vektors, der nur eine erfordert.

Der Speicher eines Deque wird bei Bedarf automatisch erweitert und verkleinert. Die Erweiterung eines Deque ist kostengünstiger als die Erweiterung eines std::vector, da sie kein Kopieren 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 komplettes internes Array allozieren (z. B. das 8-fache der Objektgröße auf 64-Bit libstdc++; das 16-fache der Objektgröße oder 4096 Bytes, je nachdem, welcher Wert größer ist, auf 64-Bit libc++).

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

• Zufälliger Zugriff - konstant O(1).
• Einfügen oder Entfernen von Elementen am Ende oder am 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.

Alle Memberfunktionen von std::deque sind constexpr: es ist möglich, std::deque-Objekte in der Auswertung eines konstanten Ausdrucks zu erstellen und zu verwenden. Jedoch können std::deque-Objekte im Allgemeinen nicht constexpr sein, da jeder dynamisch allozierte Speicher in derselben Auswertung des konstanten Ausdrucks freigegeben werden muss.

(seit C++26)

Template-Parameter

T	-	Der Typ der Elemente. T muss die Anforderungen von CopyAssignable und CopyConstructible erfüllen. (bis C++11) Die auf die Elemente angewendeten Anforderungen hängen von den tatsächlichen Operationen ab, die auf dem Container ausgeführt werden. Im Allgemeinen muss der Elementtyp ein vollständiger Typ sein und die Anforderungen von Erasable erfüllen, aber viele Memberfunktionen stellen strengere Anforderungen. (seit C++11)
Allocator	-	Ein Allokator, der zum Erwerb/Freigeben von Speicher und zum Erstellen/Zerstören der Elemente in diesem Speicher verwendet wird. Der Typ muss die Anforderungen von Allocator erfüllen. Das Verhalten ist undefiniert(bis C++20)Das Programm ist ill-formed(seit C++20), wenn Allocator::value_type nicht mit T übereinstimmt.

Iterator-Invalidierung

Operationen	Invalidiert
Alle schreibgeschützten Operationen.	Niemals.
swap, std::swap	Der End-Iterator kann ungültig werden (implementierungsabhängig).
shrink_to_fit, clear, insert, emplace, push_front, push_back, emplace_front, emplace_back	Immer.
erase	Beim Löschen am Anfang - nur die gelöschten Elemente. Beim Löschen am Ende - nur die gelöschten Elemente und der End-Iterator. Andernfalls - alle Iteratoren werden ungültig. Es ist nicht spezifiziert, wann der End-Iterator ungültig wird.(bis C++11) Der End-Iterator wird ebenfalls ungültig es sei denn, die gelöschten Elemente befinden sich am Anfang des Containers und das letzte Element wird nicht gelöscht. (seit C++11)
resize	Wenn die neue Größe kleiner als die alte ist - nur die gelöschten Elemente und der End-Iterator. Wenn die neue Größe größer als die alte ist - alle Iteratoren werden ungültig. Andernfalls - keine Iteratoren werden ungültig.
pop_front, pop_back	Auf das gelöschte Element. Der End-Iterator kann ungültig werden (implementierungsabhängig).(bis C++11) Der End-Iterator wird ebenfalls ungültig.(seit C++11)

Hinweise zur Invalidierung

• Beim Einfügen an beiden Enden des Deque werden Referenzen durch insert und emplace nicht ungültig.
• push_front, push_back, emplace_front und emplace_back machen keine Referenzen auf Elemente des Deque ungültig.
• Beim Löschen an beiden Enden des 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 des Deque ungültig.

Member-Typen

Mitgliedertyp	Definition
value_type	T
allocator_type	Allocator
size_type	Vorzeichenloser Ganzzahltyp (normalerweise std::size_t)
difference_type	Vorzeichenbehafteter Ganzzahltyp (normalerweise std::ptrdiff_t)
Referenz	value_type&
const_reference	const value_type&
Zeiger	Allocator::pointer (bis C++11) std::allocator_traits<Allocator>::pointer (seit C++11)
const_pointer	Allocator::const_pointer (bis C++11) std::allocator_traits<Allocator>::const_pointer (seit C++11)
iterator	LegacyRandomAccessIterator und ConstexprIterator(seit C++26) zu value_type
const_iterator	LegacyRandomAccessIterator und ConstexprIterator(seit C++26) zu const value_type
reverse_iterator	std::reverse_iterator<iterator>
const_reverse_iterator	std::reverse_iterator<const_iterator>

Memberfunktionen

(Konstruktor)	konstruiert das deque (public member function)
(Destruktor)	destruiert das deque (public member function)
operator=	weist dem Container Werte zu (public member function)
assign	weist dem Container Werte zu (public member function)
assign_range (C++23)	weist dem Container einen Bereich von Werten zu (public member function)
get_allocator	gibt den zugehörigen Allocator zurück (public member function)
Elementzugriff
at	Greift mit Überprüfung auf ein bestimmtes Element zu (public member function)
operator[]	Greift auf ein bestimmtes Element zu (public member function)
front	Greift auf das erste Element zu (public member function)
back	Greift auf das letzte Element zu (public member function)
Iteratoren
begincbegin (C++11)	gibt einen Iterator zum Anfang zurück (public member function)
endcend (C++11)	gibt einen Iterator zum Ende zurück (public member function)
rbegincrbegin (C++11)	gibt einen Reverse-Iterator zum Anfang zurück (public member function)
rendcrend (C++11)	gibt einen Reverse-Iterator zum Ende zurück (public member function)
Kapazität
empty	prüft, ob der Container leer ist (public member function)
size	Gibt die Anzahl der Elemente zurück (public member function)
max_size	Gibt die maximal mögliche Anzahl von Elementen zurück (public member function)
shrink_to_fit (DR*)	reduziert den Speicherverbrauch durch Freigabe von ungenutztem Speicher (public member function)
Modifizierer
clear	leert den Inhalt (public member function)
insert	fügt Elemente ein (public member function)
insert_range (C++23)	fügt einen Bereich von Elementen ein (public member function)
emplace (C++11)	konstruiert Elemente direkt (in-place) (public member function)
erase	entfernt Elemente (public member function)
push_back	fügt ein Element am Ende hinzu (public member function)
emplace_back (C++11)	konstruiert ein Element direkt (in-place) am Ende (public member function)
append_range (C++23)	fügt einen Bereich von Elementen am Ende hinzu (public member function)
pop_back	entfernt das letzte Element (public member function)
push_front	fügt ein Element am Anfang ein (public member function)
emplace_front (C++11)	konstruiert ein Element im-place am Anfang (public member function)
prepend_range (C++23)	fügt einen Elementbereich am Anfang hinzu (public member function)
pop_front	entfernt das erste Element (public member function)
resize	ändert die Anzahl der gespeicherten Elemente (public member function)
swap	tauscht die Inhalte (public member function)

Nicht-Member-Funktionen

operator==operator!=operator<operator<=operator>operator>=operator<=> (entfernt in C++20)(entfernt in C++20)(entfernt in C++20)(entfernt in C++20)(entfernt in C++20)(C++20)	vergleicht die Werte zweier deques lexikographisch (function template)
std::swap(std::deque)	spezialisiert den Algorithmus std::swap (function template)
erase(std::deque)erase_if(std::deque) (C++20)	entfernt alle Elemente, die bestimmte Kriterien erfüllen (function template)

Deduction Guides

(seit C++17)

Notizen

Feature-Test-Makro	Wert	Std	Feature
__cpp_lib_containers_ranges	202202L	(C++23)	Bereichskonstruktion und -einfügung für Container
__cpp_lib_constexpr_containers	202502L	(C++26)	constexpr std::deque

Beispiel

Führen Sie diesen Code aus

#include <deque>
#include <iostream>
 
int main()
{
    // Create a deque containing integers
    std::deque<int> d = {7, 5, 16, 8};
 
    // Add an integer to the beginning and end of the deque
    d.push_front(13);
    d.push_back(25);
 
    // Iterate and print values of deque
    for (int n : d)
        std::cout << n << ' ';
    std::cout << '\n';
}

Ausgabe

13 7 5 16 8 25

Defect reports

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

DR	angewendet auf	Verhalten wie veröffentlicht	Korrigiertes Verhalten
LWG 230	C++98	T musste nicht CopyConstructible sein (ein Element vom Typ T konnte möglicherweise nicht konstruiert werden)	T muss auch CopyConstructible sein

Siehe auch

queue

passt einen Container an, um eine Queue (FIFO-Datenstruktur) bereitzustellen (Klassenvorlage)