skip to content

In C++, how does std::deque store its elements, and why do references survive push_front and push_back while iterators do not?

level: middleimportance: should knowfreq 55%

answer

  1. fixed-size blocks, not one buffer
  2. an array of block pointers
  3. elements never relocate on end pushes
  4. the pointer array can be reallocated

basics

~20 s

std::deque keeps elements in fixed-size blocks tracked by an array of block pointers. Pushing at either end fills or adds a block and never moves existing elements, so references stay valid; the pointer array may be reallocated, which invalidates iterators.

solid answer

~50 s

The standard specifies behaviour, not layout: random-access iterators, constant-time insertion and erasure at both ends, and the rule that an insertion at either end invalidates all iterators but has no effect on the validity of references. libc++ and libstdc++ meet it the same way. Elements live in fixed-size blocks, and a separate array of block pointers, usually called the map, records them in order. `push_back` constructs into the last block or allocates a new block; existing elements never move, so pointers and references to them survive. When the map runs out of slots it is reallocated, and an iterator records a position in that map (libstdc++'s iterator stores the element pointer, the block's bounds and a map pointer), so all iterators are invalidated. Block sizes are each library's choice: for small elements libc++ fills 4096 bytes per block and libstdc++ 512 bytes. A deque is not contiguous: there is no `data()`, `reserve()` or `capacity()`.

code

cpp · 22 lines
cpp
#include <cstdio>
#include <deque>
#include <string>

struct PrintJob { int id; std::string owner; int pages; };

int main() {
    std::deque<PrintJob> jobs;
    jobs.push_back({1, "ana", 3});
    PrintJob& first = jobs.front();          // a reference into the deque
    PrintJob* firstPtr = &jobs.front();

    for (int i = 2; i <= 10000; ++i)
        jobs.push_back({i, "bob", 1});       // grow at the back
    jobs.push_front({0, "urgent", 1});       // and at the front

    // Insertion at either end keeps references and pointers valid
    // (iterators are invalidated, so none are held across the pushes).
    std::printf("first.id=%d still at same address: %s\n", first.id,
                firstPtr == &jobs[1] ? "yes" : "no");
    std::printf("front=%d back=%d size=%zu\n", jobs.front().id, jobs.back().id, jobs.size());
}

go deeper

for a junior

Know that std::deque supports fast push and pop at both ends plus indexing, and that it is not one contiguous buffer.

for a middle

Describe blocks plus a map of block pointers, and explain why end insertions keep references valid but invalidate iterators.

for a senior

Use deque for stable references under growth, avoid holding iterators across pushes, and know the block-size differences between libc++ and libstdc++ for large elements.

for a principal

Decide where deque's stable references justify its indexing cost and per-instance overhead versus a vector of handles or indices, especially when thousands of small deques exist.

## What the standard promises `std::deque<T>` (header `<deque>`, "double-ended queue") is a sequence container with: - **random-access iterators** and `operator[]`, like `std::vector`; - **constant-time insertion and erasure at the beginning and the end**; inserting a single element at either end always takes constant time and calls exactly one constructor of `T`; - **linear-time insertion and erasure in the middle**, proportional to the lesser of the distances to the two ends. For insertions, the draft adds the rule this question is about: an insertion in the middle invalidates all iterators and references, while **an insertion at either end invalidates all the iterators to the deque but has no effect on the validity of references to its elements**. Erasing the first or last element invalidates only iterators and references to the erased element (plus the past-the-end iterator when the last one goes). ## The block-and-map layout The standard never says how to achieve this, but libc++ and libstdc++ use the same design: 1. Elements are stored in **fixed-size blocks** (libstdc++ calls them nodes or buffers). 2. A separate, contiguous **array of block pointers**, usually called the **map**, lists the blocks in order, with free slots kept at both ends. 3. `push_back` constructs into the free space of the last block; when that block is full, it allocates a new block and records it in the next map slot. `push_front` does the mirror image at the front. 4. When the map itself has no free slot at the needed end, the deque allocates a bigger map (or recentres the existing one) and copies the **block pointers**, never the elements. | Library | Elements per block | |---|---| | libc++ | 4096 / `sizeof(T)` when `sizeof(T)` < 256; otherwise 16 | | libstdc++ | 512 / `sizeof(T)` when `sizeof(T)` < 512; otherwise 1 | Both values are implementation choices; libstdc++ warns in its source that changing its buffer size breaks binary compatibility. The libstdc++ row has a practical consequence: a deque of 600-byte print jobs allocates one block per job. ## Why references survive and iterators do not - A **reference or pointer** names an element's address. End insertions never relocate elements, so the address stays good. - An **iterator** has to know how to step to the next block, so it records a position in the map. libstdc++'s iterator holds four members: the current element pointer, the block's first and last pointers, and a pointer into the map. libc++'s holds a map iterator and an element pointer. When the map is reallocated, those map positions dangle, and the standard therefore invalidates every iterator on any end insertion, whether or not the map actually moved this time. So in a print server, a status dashboard can keep a `PrintJob&` to a job while new jobs are pushed at the back and urgent ones at the front; keeping a `std::deque<PrintJob>::iterator` across those pushes is a bug. ## What the layout costs - **Indexing is two steps.** `operator[]` computes a block and an offset, then follows the map: constant time, but more work than a vector's single addition. - **No contiguity.** There is no `data()`, and a deque cannot be viewed as a `std::span`; algorithms work through its iterators. - **No capacity control.** There is no `reserve()` or `capacity()`; `shrink_to_fit()` exists and is non-binding. - **Middle insertion shifts elements** toward the nearer end and invalidates all references. - **Overhead for small deques.** Even one element costs a whole block plus a map, which matters when you keep thousands of small deques. ## When a deque is the right choice 1. You push and pop at **both ends**, such as a print queue where urgent jobs jump to the front. 2. You append at one end and need **stable references** to elements already present, without paying a node allocation per element as `std::list` would. 3. You want a growing sequence that **never reallocates and moves its elements**, for example for types that are expensive to move. For a pure FIFO, `std::deque` is also what `std::queue` uses by default, for exactly these reasons.

  • Which std::deque erasures leave references to the other elements valid?
    Erasing the first element, or the last one, invalidates only iterators and references to the erased element; erasing the last also invalidates the past-the-end iterator. `pop_front` and `pop_back` are such erasures. Erasing anything in the middle invalidates all iterators and references, because elements are shifted toward one end to close the gap.
  • Why does a std::deque have no reserve() member?
    Its storage is a set of fixed-size blocks plus a map of block pointers, so there is no single buffer whose capacity could be reserved, and end insertions never relocate elements anyway. The standard therefore gives it `shrink_to_fit()`, a non-binding request to release unused memory, but no `reserve()` or `capacity()`.

A ring binder of fixed-size pages with a separate contents sheet: adding a page at the front or back never moves the existing pages, so a finger on a line stays put, but the contents sheet may be rewritten onto a longer sheet, so a note saying "line 3 of entry 12 on the contents sheet" goes stale.

  • A std::deque stores all its elements in one contiguous buffer like a vector
  • push_back on a std::deque keeps iterators valid because elements do not move
  • push_front on a std::deque moves every element one slot to the right
  • std::deque is implemented as a doubly linked list of single elements
  • The C++ standard fixes the block size of std::deque at 512 bytes