std::deque

Overview

std::deque (double-ended queue, pronounced "deck") is a sequence container optimized for efficient operations at both the front and back. Unlike std::vector, which efficiently grows only at the end, a deque supports push_front() and pop_front() in addition to push_back() and pop_back(), all with O(1) amortized complexity.

Internally, a deque is typically implemented as a sequence of fixed-sized memory blocks chained together. This architecture allows random access via operator[] and at() in O(1) time, similar to vectors, while avoiding the costly reallocations that vectors incur when growing in one direction only. The tradeoff is that the non-contiguous nature introduces potential cache misses during iteration—making a deque slightly less cache-friendly than a vector for sequential access patterns.

Deque is the default underlying container for std::queue and std::stack because it naturally supports FIFO and LIFO discipline with efficient operations at both ends. Choose a deque when your algorithm frequently adds or removes elements from both ends, when you need a queue-like data structure with random access, or when you want to model a double-sided buffer.

Syntax

#include <deque>

// Declaration and initialization
std::deque<int> dq;
std::deque<int> dq2(10);           // 10 default-initialized elements
std::deque<int> dq3(10, 42);       // 10 copies of 42
std::deque<int> dq4{1, 2, 3};      // Initializer list (C++11)

// Front operations
dq.push_front(value);              // O(1) insert at front
dq.pop_front();                    // O(1) remove from front
T& front_ref = dq.front();         // Reference to first element

// Back operations
dq.push_back(value);               // O(1) insert at back
dq.pop_back();                     // O(1) remove from back
T& back_ref = dq.back();           // Reference to last element

// Random access
T val = dq[i];                     // O(1) unchecked access
T val2 = dq.at(i);                // O(1) with bounds checking, throws std::out_of_range

// Iteration
for (auto it = dq.begin(); it != dq.end(); ++it) { /* ... */ }
for (auto elem : dq) { /* ... */ }  // Range-based for (C++11)

// Queries
bool is_empty = dq.empty();
size_t sz = dq.size();
dq.clear();                        // Remove all elements

// Middle insertion/deletion (O(n))
dq.insert(dq.begin() + 3, value);
dq.erase(dq.begin() + 2);

Examples

Basic Double-Ended Operations

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq;
    
    // Build from both ends
    dq.push_back(1);
    dq.push_back(2);
    dq.push_front(0);
    dq.push_front(-1);
    
    // dq: -1, 0, 1, 2
    
    // Random access
    std::cout << dq[2] << '\n';      // Output: 1
    std::cout << dq.front() << '\n'; // Output: -1
    std::cout << dq.back() << '\n';  // Output: 2
    
    // Remove from both ends
    dq.pop_front();
    dq.pop_back();
    // dq: 0, 1
}

FIFO Queue Pattern

#include <deque>
#include <iostream>
#include <string>

void process_requests(std::deque<std::string>& queue) {
    while (!queue.empty()) {
        std::string request = queue.front();
        queue.pop_front();
        std::cout << "Processing: " << request << '\n';
    }
}

int main() {
    std::deque<std::string> requests;
    requests.push_back("read_file");
    requests.push_back("write_log");
    requests.push_back("send_email");
    
    process_requests(requests);
}

LIFO Stack Pattern

#include <deque>

int main() {
    std::deque<int> call_stack;
    
    // Push function calls
    call_stack.push_back(100);
    call_stack.push_back(200);
    call_stack.push_back(300);
    
    // Pop (LIFO)
    while (!call_stack.empty()) {
        int frame = call_stack.back();
        call_stack.pop_back();
        // Handle frame
    }
}

Sliding Window

#include <deque>
#include <vector>

std::vector<int> max_in_windows(const std::vector<int>& arr, int k) {
    std::deque<int> indices;  // Store indices
    std::vector<int> result;
    
    for (int i = 0; i < arr.size(); ++i) {
        // Remove elements outside window
        if (!indices.empty() && indices.front() < i - k + 1) {
            indices.pop_front();
        }
        
        // Remove smaller elements from back
        while (!indices.empty() && arr[indices.back()] <= arr[i]) {
            indices.pop_back();
        }
        
        indices.push_back(i);
        
        // Add max to result
        if (i >= k - 1) {
            result.push_back(arr[indices.front()]);
        }
    }
    
    return result;
}

Best Practices

• Prefer deque for bidirectional growth. If you frequently add or remove from both ends, deque is the natural choice over vector.
• Use std::queue and std::stack for discipline. When you need FIFO or LIFO semantics, use the adapter classes rather than managing a deque directly; they enforce the intended interface.
• Avoid middle insertions in loops. Inserting at arbitrary positions is O(n). If your algorithm repeatedly inserts in the middle, use std::list instead.
• Beware iterator invalidation. Operations that reallocate deque blocks (which can happen on front/back insertion) invalidate all iterators. Always re-obtain iterators after modifications if you need them afterward.
• Cache behavior matters in performance-critical code. For sequential iteration in tight loops, vectors may outperform deques despite algorithmic equivalence. Profile if latency is critical.

Common Pitfalls

• Forgetting push_front exists. Many developers reach for std::list when they need front insertion, unaware that deque provides O(1) front operations.
• Overusing insert/erase. Calling insert() or erase() repeatedly at arbitrary positions turns the algorithm into O(n²). Restructure to use front/back operations or switch to std::list.
• Assuming contiguous memory. Unlike vectors, deque elements are not guaranteed to be contiguous. Pointer arithmetic across deque elements is undefined behavior.
• Mixing deque with pointer-based access. Iterators are safe; raw pointers into a deque can become invalid after reallocations.

Memory Model: Segmented Storage

Unlike std::vector, a deque does not store its elements in a single contiguous array. Instead it maintains a small array of pointers — called the map internally — where each pointer points to a fixed-size block (also called a chunk or node) of contiguous memory.

deque<int> internal layout (libstdc++ / GCC)

  map (array of pointers)
  ┌──────┬──────┬──────┬──────┐
  │ blk0 │ blk1 │ blk2 │ blk3 │   ← map (8 entries initially)
  └──┬───┴──┬───┴──┬───┴──────┘
     │      │      │
     ▼      ▼      ▼
  ┌──────┐ ┌──────┐ ┌──────┐
  │ e e e│ │ e e e│ │ e e e│     ← fixed-size blocks (~512 B on GCC)
  └──────┘ └──────┘ └──────┘

Block sizes across implementations (sourced from Raymond Chen, The Old New Thing, 2023):

How O(1) front/back insertion works without reallocation:

When you call push_front(), the deque checks whether the current front block has free slots before its first element. If it does, the new element is placed there — no allocation needed. If not, a fresh block is allocated and prepended to the map. Because blocks are small and the map grows geometrically (2× each time), both allocations are rare. Critically, no existing elements are ever moved during a block-level growth, unlike a vector which must copy everything to a new contiguous buffer.

// push_front is O(1) amortized — no element relocation ever
std::deque<int> dq(1'000'000, 0);
dq.push_front(42);  // allocates at most one new block (~512 bytes)
                    // the million existing elements are untouched

Random access in O(1):

Given an index i, the deque computes block_index = i / block_size and offset = i % block_size, then performs two pointer dereferences: map[block_index][offset]. GCC's libstdc++ caches current_block_begin and current_block_end in each iterator to avoid recomputing this on every increment.

Iterator invalidation rules:

• push_back() / push_front(): invalidates all iterators (the map may be reallocated), but references/pointers to existing elements remain valid.
• pop_back() / pop_front(): invalidates only iterators to the removed element; all other iterators and references stay valid.
• insert() / erase() in the middle: invalidates all iterators and references.

Cache Behavior vs. std::vector

Within a single block, elements are laid out contiguously, so iterating across elements within that block is as cache-friendly as iterating through a vector slice. The penalty appears only when the iterator crosses a block boundary — the hardware prefetcher must chase an extra pointer indirection into the map.

Sequential iteration:

For sequential read-only traversal (e.g., std::accumulate), a vector is typically 10–30% faster than a deque of the same size on modern x86 hardware, because every block boundary in the deque incurs a potential cache miss on the map pointer. With GCC's 512-byte blocks, this boundary is crossed roughly every 128 int elements (or every 64 double elements).

// Tight loop: vector wins due to single contiguous region
std::vector<int> v(N);
std::deque<int>  dq(N);

// ~10-30% slower for small element types due to inter-block pointer chases
long sum = 0;
for (int x : dq) sum += x;

Large-element workloads:

When elements are large (128 bytes or more), the cache-miss penalty per element dominates in both containers, and the difference between vector and deque diminishes — benchmark data from Baptiste Wicht (2012) shows deque matching or beating vector for 4KB elements during sequential search.

Insertion at the front:

push_front on a vector is O(n) — it shifts every existing element one position right. On a deque it is O(1) amortized. The benchmark difference is stark: deque and std::list are essentially constant-time for push_front, while vector degrades linearly. Use deque any time your access pattern involves both ends.

std::queue and std::stack Adapters

std::queue and std::stack are container adapters: they wrap an underlying container and expose only the operations consistent with their discipline. Both default to std::deque as that underlying container.

// std::queue — FIFO, backed by std::deque by default
template<class T, class Container = std::deque<T>>
class queue;

// std::stack — LIFO, backed by std::deque by default
template<class T, class Container = std::deque<T>>
class stack;

Why std::stack uses std::deque instead of std::vector:

A stack only needs back(), push_back(), and pop_back() — operations that std::vector also provides. The standard chose std::deque because deque growth never copies existing elements, making worst-case push truly O(1) rather than amortized O(1). This matters for real-time or latency-sensitive code where you cannot afford the occasional vector reallocation spike. std::priority_queue, by contrast, defaults to std::vector because it needs heavy random indexing for heap operations.

#include <queue>
#include <stack>
#include <deque>
#include <list>

// Default: backed by std::deque
std::queue<int> q;
std::stack<int> s;

// Override the backing container
std::queue<int, std::list<int>>   q_list;   // valid: list has front()/pop_front()
std::stack<int, std::vector<int>> s_vec;    // valid: vector has back()/pop_back()

// Using deque directly gives iteration — adapters do not expose it
std::deque<int> dq_raw;
dq_raw.push_back(1);
dq_raw.push_back(2);
for (int x : dq_raw) { /* can iterate */ }

// std::queue does NOT support iteration
// for (int x : q) { } // compile error

Choosing between the adapter and raw deque:

Use std::queue when you want FIFO enforcement and do not need to iterate or access elements by index. Use std::stack for LIFO enforcement. Use std::deque directly when you need both-ends access and random access or iteration over the full sequence.

Container Decision Guide

Use this table to choose between std::deque and its common alternatives:

Rule of thumb: Start with std::vector. Reach for std::deque specifically when you need O(1) growth at the front or when you are implementing a FIFO queue and also need to inspect elements by index.

Iterator Invalidation Rules

Deque iterator invalidation is asymmetric, and more nuanced than vector. The segmented memory layout means that some mutations affect only the front or back of the internal map, while others restructure the whole container — and the standard distinguishes these cases explicitly.

The table below summarises which operations invalidate iterators, pointers, and references. "Iterators" means the iterator objects themselves (including begin() and end()); "references" means raw references and pointers to elements.

The asymmetry between iterators and references on push_back/push_front is intentional and unique to std::deque. Because no existing block is ever relocated during a back or front push, the memory addresses of elements do not change — only the internal map structure (and therefore iterators that cache block pointers) may be rebuilt.

// C++11
#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq{10, 20, 30};

    int& ref_front = dq.front();   // reference to first element (value 10)
    auto it = dq.begin() + 1;      // iterator to second element (value 20)

    dq.push_front(5);              // push_front: invalidates ALL iterators ...
                                   // ... but NOT references to existing elements

    // it is now invalid — do not dereference it
    // ref_front is still valid; dq.front() is now 5, but ref_front still points to 10
    std::cout << ref_front << '\n'; // OK: prints 10

    // Re-obtain the iterator before using it
    auto it2 = dq.begin() + 2;     // safe: freshly obtained
    std::cout << *it2 << '\n';      // prints 20
}

A common defensive pattern when building up a deque in a loop is to avoid storing iterators across push operations entirely — use index arithmetic instead, since operator[] always recomputes the block/offset pair from the current state of the map.

// C++11
#include <deque>

void safe_accumulate(std::deque<int>& dq, int count) {
    // Store size_t index, not an iterator — index stays correct after push_front
    size_t anchor = dq.size();
    for (int i = 0; i < count; ++i) {
        dq.push_front(i);
        // Using dq[anchor + i] would be wrong here (anchor shifts with push_front)
        // Use fresh dq.front() or recompute after the loop
    }
}

Deque as a Sliding Window

The O(1) complexity at both ends makes std::deque the canonical backing store for monotone sliding-window algorithms. A sliding window over an array maintains a window of the last k elements; at each step the oldest element falls off the front and a new element enters the back — exactly the pattern deque is built for.

The classic sliding window maximum problem illustrates this. A monotone deque of indices is maintained such that the front always holds the index of the current window's maximum. When a new element arrives it evicts all smaller elements from the back before being added, keeping the deque in decreasing order.

// C++11
#include <deque>
#include <vector>
#include <cassert>

// Returns the maximum value in each window of size k.
std::vector<int> sliding_window_max(const std::vector<int>& nums, int k) {
    std::deque<int> dq;  // stores indices; front = index of current max
    std::vector<int> result;
    result.reserve(nums.size() - k + 1);

    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        // Evict indices that have fallen outside the window
        if (!dq.empty() && dq.front() < i - k + 1)
            dq.pop_front();

        // Maintain decreasing order: evict smaller elements from the back
        while (!dq.empty() && nums[dq.back()] <= nums[i])
            dq.pop_back();

        dq.push_back(i);

        if (i >= k - 1)
            result.push_back(nums[dq.front()]);
    }
    return result;
}

int main() {
    auto r = sliding_window_max({1, 3, -1, -3, 5, 3, 6, 7}, 3);
    assert((r == std::vector<int>{3, 3, 5, 5, 6, 7}));
}

Each element is pushed once and popped at most once, giving an overall O(n) algorithm. Neither std::list (no O(1) random access) nor std::vector (O(n) pop_front) can match this combination cleanly.

A related pattern is the bounded sliding buffer used in stream processing: keep the last k samples for statistical summaries (mean, variance) and discard older ones. Because the window advances by one element per sample, the amortized cost per sample is O(1) with deque regardless of window size.

// C++11
#include <deque>
#include <numeric>

class RollingAverage {
    std::deque<double> window_;
    int capacity_;
    double sum_ = 0.0;
public:
    explicit RollingAverage(int k) : capacity_(k) {}

    void push(double v) {
        if (static_cast<int>(window_.size()) == capacity_) {
            sum_ -= window_.front();
            window_.pop_front();          // O(1) — drop oldest sample
        }
        window_.push_back(v);             // O(1) — add new sample
        sum_ += v;
    }

    double average() const {
        return window_.empty() ? 0.0 : sum_ / window_.size();
    }
};

Deque vs. Vector Performance

std::deque and std::vector have the same asymptotic complexity for back operations, but their constant factors differ in important ways. Choosing between them requires understanding which operations dominate in your workload.

For back-only growth, vector is consistently faster in practice. A single large allocation is more cache-friendly for sequential access, and push_back on a vector only writes one word of metadata (the size) versus the deque's potential map pointer update. Benchmark guidance from the libc++ documentation and Stephan T. Lavavej's STL notes suggests deque push_back carries roughly 1.5–2× more overhead per operation than vector push_back on typical workloads due to the block-boundary checks.

// C++11
#include <deque>
#include <vector>

// Prefer vector when growth is back-only and you iterate sequentially
void back_only_growth(int n) {
    std::vector<int> v;
    v.reserve(n);                // one allocation; zero reallocations
    for (int i = 0; i < n; ++i)
        v.push_back(i);          // fast: no block boundary checks

    std::deque<int> dq;
    for (int i = 0; i < n; ++i)
        dq.push_back(i);         // correct, but checks block capacity each time
}

For front insertion, the calculus reverses completely. std::vector::insert at position 0 moves every existing element one position to the right — an O(n) operation per call, making a loop that repeatedly prepends O(n²) overall. std::deque::push_front is O(1) amortized. The crossover point where deque wins is around 64–128 elements; beyond that, using vector for front insertion is always a performance mistake.

// C++11
#include <deque>
#include <vector>

// O(n) total with deque — O(n²) total with vector
void prepend_all(int n) {
    std::deque<int> dq;
    for (int i = n - 1; i >= 0; --i)
        dq.push_front(i);         // O(1) each time: total O(n)

    std::vector<int> v;
    for (int i = n - 1; i >= 0; --i)
        v.insert(v.begin(), i);   // O(n) each time: total O(n²) — avoid this
}

For sequential read, vector wins because all bytes live in one contiguous region that the hardware prefetcher can pipeline without interruption. The deque crosses a block boundary roughly every block_size / sizeof(T) elements; each crossing stalls the prefetch pipeline. For int (4 bytes) on GCC (512-byte blocks), that is a boundary every 128 elements — tolerable for large N but noticeable for N < 10 000.

The practical rule: start with vector, switch to deque only when you need front operations or when profiling identifies reallocation spikes that deque's non-copying growth would eliminate.

std::erase and std::erase_if with Deque (C++20)

C++20 adds free-function std::erase and std::erase_if for all sequence containers, replacing the longstanding erase-remove idiom with a single, expressive call. Before C++20, removing all elements satisfying a predicate from a deque required chaining std::remove_if with dq.erase() — a two-step pattern that was error-prone and visually noisy.

// C++17 — erase-remove idiom (verbose, easy to get wrong)
#include <deque>
#include <algorithm>

std::deque<int> dq{1, 2, 3, 4, 5, 6};
dq.erase(std::remove_if(dq.begin(), dq.end(),
                        [](int x){ return x % 2 == 0; }),
         dq.end());
// dq: {1, 3, 5}

// C++20 — std::erase_if: idiomatic and concise
#include <deque>
#include <algorithm>

std::deque<int> dq{1, 2, 3, 4, 5, 6};
std::erase_if(dq, [](int x){ return x % 2 == 0; });
// dq: {1, 3, 5}

std::erase (non-predicate form) removes all elements equal to a given value, equivalent to the old erase(remove(...)) pattern with a value comparison:

// C++20
#include <deque>

std::deque<std::string> words{"cat", "dog", "cat", "bird", "cat"};
auto removed = std::erase(words, "cat");
// words: {"dog", "bird"}
// removed == 3 (number of elements erased)

Both functions return the number of elements erased, which was not available from the old idiom without extra bookkeeping. The internal implementation calls std::remove/std::remove_if followed by erase — the same operations as before — so there is no algorithmic change, only a cleaner API. Both functions work with any sequence container that supports erase, including std::vector, std::list, and std::string.

// C++20
#include <deque>
#include <string>
#include <cctype>

// Real-world example: strip control characters from a token buffer
std::deque<char> buf{'\x01', 'h', 'e', '\x00', 'l', 'l', 'o', '\x1b'};
std::erase_if(buf, [](unsigned char c){ return std::iscntrl(c); });
// buf: {'h', 'e', 'l', 'l', 'o'}

See Also

• std::vector — contiguous sequence container, optimized for back operations
• std::list — doubly-linked list with O(1) insertion at any position
• std::forward_list — singly-linked list with minimal memory overhead
• std::queue — FIFO adapter (uses std::deque by default)
• std::stack — LIFO adapter (uses std::deque by default)