std::deque<T> is a double-ended queue: a sequence container that supports fast insertion and removal at both the front and the back. It's the container to choose when std::vector is almost right but the code also needs cheap front push and pop. This chapter covers how a deque is laid out in memory, the operations it offers, its complexity profile, and when to pick it over std::vector.

std::vector stores its elements in one contiguous block. That gives it a fast operator[] and the best cache behavior of any standard container, but it has one weakness: inserting or removing at the front is O(n), because every existing element has to shift down by one slot. Code that processes orders in arrival order and repeatedly pops the oldest order off the front uses a vector at the wrong shape.

That erase(begin()) is O(n). For three elements it's invisible, but for an order queue of a million it's expensive. std::deque is built so that the same operation runs in O(1).

The deque is the right container for vector-like random access plus cheap front operations. The trade-off is that its memory isn't contiguous, which costs a little on every element access and a lot when an algorithm depends on raw pointer arithmetic.

A deque doesn't sit in one block of memory. Internally it's a collection of fixed-size blocks (often called chunks or pages), each holding several elements, plus a small array of pointers, called the map, that records where each block lives. A d[k] access calculates which block holds the k-th element and which slot inside that block to read.

The map is the cyan box. Each orange box is one fixed-size block of element storage on the heap. The deque also remembers where the first element lives (the "front" position inside the first used block) and where the next free slot at the back is. A push_back writes into the next free slot. When that block fills up, the deque allocates a new block and adds it to the map. push_front does the symmetric thing at the other end.

The benefit is symmetry: both ends can grow without copying any existing elements. The cost is that two consecutive elements may live in different blocks, so iterating or indexing is slightly slower than over a vector. There's also a per-block overhead, which makes a deque slightly heavier per element than a vector.

The block size is implementation-defined. libstdc++ (g++) uses around 512 bytes per block, libc++ (clang++) uses larger blocks. There's no user-facing knob to tune it. The map itself grows when it runs out of pointer slots, which is the only time a deque ever reallocates the map.

A deque pays one extra indirection on every operator[] compared to a vector: first locate the block, then index into it. For most code this is a few extra cycles per access. For tight numerical loops, vector is still faster.

A std::deque<T> has the same family of constructors as std::vector<T>: an empty deque, a deque of a given size, a deque from an initializer list, or a copy of another deque.

The <deque> header provides the type. The element type can be anything copyable or movable, the same set of constraints as a vector. There's no reserve() because the segmented layout means there's nothing useful to pre-allocate; the deque doesn't need a single contiguous chunk, so it doesn't promise to avoid reallocation the way a vector does.

The deque's defining feature is that push_front, push_back, pop_front, and pop_back are all O(1). All four operations are members of std::deque.

push_front adds to the front, push_back adds to the back. pop_front and pop_back remove from those ends. None of these operations move existing elements, because the deque has spare room at both ends of its block layout, or allocates a fresh block when it runs out.

push_front on a std::deque is O(1) amortized. The same call on a std::vector is O(n) because every existing element shifts down by one slot. For front insertions in a hot loop, deque is the right choice.

pop_front and pop_back both have a quirk: they return void, not the removed element. To capture the value, read it with front() or back() first, then pop.

That's the canonical "drain a FIFO queue" pattern. The deque holds the pending work, front() peeks at the next item, and pop_front() removes it after the value has been grabbed.

emplace_front and emplace_back construct an element in place at the front or back, the same way vector::emplace_back does. They take the constructor arguments directly instead of a pre-built object to copy or move.

No temporary CartItem is built and copied. The constructor runs directly in the deque's storage. For heavyweight types this saves a move; for cheap types the difference is negligible, but the syntax is shorter either way.

A deque supports operator[] and at(i) for indexed access, like a vector. Both are O(1), because the deque can compute which block holds index i in constant time. The difference from vector is the extra indirection: one lookup in the map, then the actual element read.

operator[] is unchecked. Passing an out-of-range index is undefined behavior; the deque won't throw, and the read will pull from whatever memory happens to be there. at(i) is the checked version: it throws std::out_of_range if i >= size().

The exact wording of the error varies by implementation (g++'s message mentions vector because it shares the range-check code), but the exception type is always std::out_of_range.

deque::operator[] is O(1) but typically 2-3x slower than vector::operator[] due to the block lookup. For random-access heavy loops with no front insertions, vector is faster. For balanced front/back operations with occasional indexed reads, deque is the right shape.

front() and back() return references to the first and last elements. They're undefined behavior on an empty deque, so check empty() first when the state isn't obvious.

Both front() and back() return non-const references when called on a non-const deque, so they can sit on the left side of an assignment.

A deque supports insert and erase at arbitrary positions. Both are O(n), with one optimization: the deque only has to shift elements on the closer side of the insertion point. Inserting near the front shifts elements toward the front; inserting near the back shifts toward the back. On average that's half the work of the equivalent vector operation, though the asymptotic complexity is the same.

insert takes an iterator pointing to the position where the new element should land (so the new element sits before what that iterator pointed to) and returns an iterator to the inserted element. erase does the inverse, removing the element at the iterator and returning an iterator to the next surviving element.

The returned iterator is the usual way to keep iterating safely after an erase, since the iterator passed in is invalidated.

Mid-deque insert and erase are O(n). For workloads dominated by mid-sequence insertion, neither deque nor vector is ideal; std::list is built for that.

This is where deque surprises developers, because its rules differ from both vector and list. The rules:

The first row is the surprising one: push_back or push_front invalidates all iterators even though it doesn't move any existing elements. An iterator into a deque has to know enough to walk to the next block when it reaches a block boundary, and adding a new block may force the deque to reallocate its internal map, which moves the block pointers. References and pointers to elements stay valid, because the elements themselves don't move.

The contrast matters in practice.

The reference first still points at the same element, because that element didn't move. Reading *it after the push_back would be undefined behavior, because the iterator might be looking at stale block-pointer information.

This split between iterator validity and reference validity is unique to deque. In a vector, a reallocation moves the elements themselves, so references go bad along with iterators. In a list, neither push nor pop ever invalidates anything except an iterator to the removed element. Deque sits in the middle.

The cheat sheet for std::deque operations:

A deque is roughly as fast as a vector for back operations, much faster for front operations, slightly slower for indexed access, and the same big-O for mid-sequence operations. Two deque-specific costs: there's no data() function returning a contiguous pointer (because the data isn't contiguous), and a deque can't be passed to a C API that expects T*.

Choose std::deque when:

Choose std::vector when:

If the operations are almost all push_back and indexed read, vector is the default answer. If front operations matter, deque is the right call. The two containers' interfaces overlap enough that switching between them is a small code change.

A worked example that justifies a deque: an order processor that retries failed orders at the front of the queue, so they get attempted again before any new arrivals.

Every operation in that loop is O(1): the pop_front, the push_front, the empty check. With a vector, every push_front shifts the rest of the queue down by one slot. With a deque, the cost is constant.