CKTIS / C++
std::deque: dvostranska vrsta z naključnim dostopom
std::deque omogoča hitre operacije na obeh koncih in naključni dostop, vendar ne zagotavlja enega zveznega bloka za vse elemente.
Različica: C++23
Sintaksa
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> iz <deque> je zaporedni vsebnik z iteratorji random access. Vstavljanje ali brisanje enega elementa na katerem koli koncu ima konstanten čas, operacije na sredini pa so linearne. Za razliko od std::vector elementi niso nujno zvezni, zato &d[0] ni začetek polja, ki bi vsebovalo celotno deque.
Vstavljanje na sredini razveljavi vse iteratorje in reference. Vstavljanje na koncu razveljavi vse iteratorje, ohrani pa reference na obstoječe elemente. Brisanje zadnjega elementa razveljavi iterator past-the-end in dostope do izbrisanih elementov; brisanje prvega, vendar ne zadnjega elementa vpliva le na izbrisane, brisanje na sredini pa razveljavi vse. Zato pop_front() pri deque z enim elementom hkrati izbriše zadnji element in razveljavi end().
operator[] ne preverja indeksa, at() pa vrže std::out_of_range. front(), back() in pop_* zahtevajo neprazen vsebnik. Pogosto delo na obeh koncih je naravna uporaba; za zvezne podatke ali stabilne iteratorje po dodajanju je treba izbiro vsebnika znova presoditi.
Primeri
#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';
}
Rezultat
2 1 2
std::deque → 2 1 2