CKTIS / C++
std::deque: a double-ended queue with random access
std::deque provides fast operations at both ends and random access, but contiguous storage for all of its elements is not guaranteed.
Version: C++23
Syntax
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> from <deque> is a sequence container with random-access iterators. Inserting or erasing a single element at either end is constant time, while middle operations are linear. Unlike std::vector, its elements need not be contiguous, so &d[0] must not be treated as the start of one array containing the whole deque.
A middle insertion invalidates all iterators and references. Insertion at either end invalidates all iterators but preserves references to existing elements. Erasing the last element invalidates the past-the-end iterator and handles to erased elements; erasing the first but not the last element affects only handles to erased elements, while a middle erasure invalidates everything. Therefore, pop_front() on a one-element deque also erases the last element and invalidates end().
operator[] does not check its index, whereas at() throws std::out_of_range. front(), back(), and pop_* require a nonempty container. Frequent work at both ends is a natural use; if a contiguous block or iterator stability after appending is required, reconsider the container choice.
Examples
#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';
}
Result
2 1 2
std::deque → 2 1 2