Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::deque: dvostrani red s nasumičnim pristupom

std::deque pruža brze operacije na oba kraja i nasumičan pristup, ali ne jamči jedan neprekinuti spremnik za sve elemente.

Verzija: 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> slijedni je spremnik s iteratorima random access. Umetanje ili brisanje jednog elementa na bilo kojem kraju ima konstantno vrijeme, a operacije u sredini linearne su. Za razliku od std::vector, elementi ne moraju biti neprekinuti, pa &d[0] nije početak polja koje sadrži cijelu deque.

Umetanje u sredinu poništava sve iteratore i reference. Umetanje na kraju poništava sve iteratore, ali čuva reference na postojeće elemente. Brisanje posljednjeg elementa poništava iterator past-the-end i pristupe obrisanim elementima; brisanje prvog, ali ne i posljednjeg elementa utječe samo na obrisane, dok brisanje u sredini poništava sve. Zato pop_front() na deque s jednim elementom ujedno briše posljednji element i poništava end().

operator[] ne provjerava indeks, dok at() baca std::out_of_range. front(), back() i pop_* zahtijevaju neprazan spremnik. Čest rad na oba kraja prirodna je primjena; ako trebaju neprekinuti podaci ili stabilni iteratori nakon dodavanja, treba ponovno procijeniti izbor spremnika.

Primjeri

#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

Izvori