stl · advanced

STL: std::deque Internals — Block Array, O(1) Both Ends, Cache vs vector

std::deque is a double-ended queue backed by an array of pointers to fixed-size blocks (chunks, ~512 bytes). Push/pop at both ends: O(1) no element movement — just fill/empty slots in first/last block; add new block when block is full. Random access: O(1) but 2 hops — block_idx = i/BS; elem = map[block_idx][i%BS]; worse cache than vector (no contiguous layout). Iterator invalidation: push_front/push_back → iterators invalid, raw pointers stable. Middle insert/erase: all invalid. vs vector: deque push_front O(1) vs vector O(n) — major advantage. vs list: deque O(1) random access vs list O(n). Use when: BFS queue, sliding window max (monotonic deque of indices), push_front in O(1), or need stable element addresses while growing. std::queue and std::stack default adapter is deque.

The code

// std::deque — double-ended queue backed by chunked block array
// NOT a circular buffer; NOT a contiguous array
// Structure: array of pointers to fixed-size blocks (chunks)
//            + front/back iterators into the block array

std::deque<int> dq;

// O(1) amortized at both ends:
dq.push_back(10);    // append at back  → fills last block or allocs new
dq.push_front(5);    // prepend at front → fills first block or allocs new
dq.pop_back();       // O(1) — no data move
dq.pop_front();      // O(1) — no data move

// O(1) random access (unlike list):
dq[2];               // block = idx / BLOCK_SIZE; offset = idx % BLOCK_SIZE
// → TWO pointer dereferences (vs vector's ONE)

// Insertion in middle: O(n)
dq.insert(dq.begin() + 2, 42);  // shifts half the elements

// vs vector:
// push_front: vector O(n) (shifts all); deque O(1) — no shift
// push_back:  vector O(1) amortized; deque O(1) amortized (similar)
// []:         vector O(1), 1 deref; deque O(1), 2 derefs (slower cache)
// middle insert: both O(n)
// memory:     vector = 1 contiguous block; deque = fragmented blocks

// Block size: implementation-defined (~512 bytes in libstdc++)
// Useful when: queue of large objects, frequent push_front/pop_front,
//              or don't want realloc copying (deque never moves existing elements)

What this lesson walks through

1. 01deque = a map of fixed-size blocks
2. 02push_front / push_back — O(1), no realloc
3. 03operator[] — O(1), but two pointer hops
4. 04Iterator invalidation — gentler than vector
5. 05deque vs vector vs list
6. 06When to reach for deque

A deque is NOT one contiguous array. It's an array of pointers (the 'map') to fixed-size blocks (chunks). Elements live inside the blocks; the map tracks which blocks are in use.