Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C++

std::deque: oboustranná fronta s náhodným přístupem

std::deque poskytuje rychlé operace na obou koncích a náhodný přístup, ale nezaručuje jediný souvislý blok pro všechny prvky.

Verze: C++23

Syntaxe

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> z <deque> je sekvenční kontejner s iterátory random access. Vložení či odstranění jednoho prvku na kterémkoli konci má konstantní čas, operace uprostřed jsou lineární. Na rozdíl od std::vector nemusí prvky ležet souvisle, takže &d[0] není začátek pole obsahujícího celou deque.

Vložení uprostřed zneplatní všechny iterátory a reference. Vložení na konci zneplatní všechny iterátory, ale zachová reference na existující prvky. Smazání posledního prvku zneplatní iterátor past-the-end a přístupy ke smazaným prvkům; smazání prvního, ale ne posledního prvku ovlivní jen smazané prvky, zatímco mazání uprostřed zneplatní vše. Proto pop_front() u deque s jedním prvkem zároveň smaže poslední prvek a zneplatní end().

operator[] index nekontroluje, kdežto at() vyhodí std::out_of_range. front(), back() a pop_* vyžadují neprázdný kontejner. Častá práce na obou koncích je přirozené použití; pro souvislá data či stabilní iterátory po přidání je třeba volbu kontejneru přehodnotit.

Příklady

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

Výsledek

2 1 2

std::deque → 2 1 2

Zdroje