KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

std::deque: dubbelzijdige wachtrij met willekeurige toegang

std::deque biedt snelle bewerkingen aan beide uiteinden en willekeurige toegang, maar garandeert geen enkele aaneengesloten buffer voor alle elementen.

Versie: 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> uit <deque> is een sequentiecontainer met random-access-iterators. Eén element aan een uiteinde invoegen of wissen kost constante tijd; bewerkingen in het midden zijn lineair. Anders dan bij std::vector hoeven elementen niet aaneengesloten te liggen, dus &d[0] is niet het begin van één array die de hele deque omvat.

Invoegen in het midden maakt alle iterators en referenties ongeldig. Invoegen aan een uiteinde maakt alle iterators ongeldig maar behoudt referenties naar bestaande elementen. Het laatste element wissen invalideert de past-the-end-iterator en toegangen tot gewiste elementen; het eerste maar niet het laatste element wissen raakt alleen gewiste elementen, terwijl middenin wissen alles invalideert. Daarom wist pop_front() bij een deque met één element ook het laatste element en maakt het end() ongeldig.

operator[] controleert de index niet; at() werpt std::out_of_range. front(), back() en pop_* vereisen een niet-lege container. Veel werk aan beide uiteinden is een natuurlijke toepassing; voor aaneengesloten opslag of stabiele iterators na toevoegen moet de containerkeuze opnieuw worden bekeken.

Voorbeelden

#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';
}

Resultaat

2 1 2

std::deque → 2 1 2

Bronnen