Knowledge baseExam Center
ENEnglish
Choose language13

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

Sources