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