CKTIS / C++
std::deque: dwustronna kolejka z dostępem losowym
std::deque zapewnia szybkie operacje na obu końcach i dostęp losowy, ale ciągłe ułożenie jego elementów w jednym buforze nie jest gwarantowane.
Wersja: C++23
Składnia
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> jest kontenerem sekwencyjnym z iteratorami random access. Wstawianie lub usuwanie pojedynczego elementu na początku i końcu ma stały czas, a operacje w środku są liniowe. W przeciwieństwie do std::vector elementy nie muszą być ciągłe w pamięci, więc nie wolno traktować &d[0] jako początku tablicy całego kontenera.
Wstawienie w środku unieważnia wszystkie iteratory i referencje. Wstawienie na którymkolwiek końcu unieważnia wszystkie iteratory, lecz zachowuje referencje do istniejących elementów. Usunięcie ostatniego elementu unieważnia iterator past-the-end oraz uchwyty do usuniętych elementów; usunięcie pierwszego, ale nie ostatniego elementu narusza tylko uchwyty do usuniętych elementów, a usunięcie w środku unieważnia wszystko. Dlatego pop_front() na jednoelementowym deque usuwa zarazem ostatni element i unieważnia end().
operator[] nie sprawdza indeksu, natomiast at() rzuca std::out_of_range. front(), back() i pop_* wymagają niepustego kontenera. Częste operacje na końcach są naturalnym zastosowaniem; jeżeli potrzebny jest ciągły blok danych albo stabilność iteratorów po dopisywaniu, wybór kontenera trzeba ponownie ocenić.
Przykłady
#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';
}
Wynik
2 1 2
std::deque → 2 1 2