Deque Layouts and the Cost of Push at Both Ends

A double-ended queue supports insertion and removal at both ends in constant time. A plain growable array supports one end cheaply: appending is amortized O(1), but prepending requires moving every element, which is Θ(n). The requirement that both ends be cheap is what forces every deque implementation away from a single contiguous block, and the cost of that departure is paid on the random-access path.

Why prepending cannot be made cheap in a flat array

In an array with n elements starting at index 0, inserting at the front means shifting elements 0 through n − 1 up by one position. That is n moves, or n * sizeof(T) bytes of memmove. There is no growth policy that avoids it, because the element that must occupy index 0 is currently occupied by another element, and contiguity requires every element to move.

A circular buffer solves the problem for a fixed capacity by letting the logical front sit at any physical offset. Prepending decrements the start index and writes; appending increments the end index and writes. Both are constant time as long as neither end crosses the other. The limitation is the fixed capacity: when the buffer fills, growing requires a new, larger allocation and a copy of the whole contents, and the copy is Θ(n). A deque that grows therefore has to combine the circular buffer’s two-ended cheapness with an allocation strategy that does not copy everything.

The array of blocks

The standard resolution, used by the common implementations of the C++ standard library’s std::deque, is an array of pointers to fixed-size blocks. The blocks are allocated individually; the pointer array is the map from logical position to block. Elements within a block are contiguous, so a scan of a few dozen consecutive elements touches few cache lines, and a block size that is a multiple of the cache line means an element never straddles a block boundary when the block itself is line-aligned.

Index i resolves in two steps: divide by the block size to find the block, take the remainder to find the offset within it. With a block size that is a power of two, the division becomes a shift and the remainder becomes a mask, both single instructions.

#define BLOCK 512                       /* elements per block, power of two */

typedef struct {
    size_t n;                           /* logical element count */
    size_t front;                       /* physical position of element 0 */
    void **map;                         /* array of block pointers */
    size_t map_len;
} deque;

static inline int *slot(deque *d, size_t i) {
    size_t pos = d->front + i;          /* physical position across blocks */
    return (int *)d->map[pos >> 9] + (pos & (BLOCK - 1));
}

The >> 9 and & 511 are the shift and mask for a block of 512 elements, and front is a position counted in elements across the whole map rather than an index within the first block. This is what makes prepending cheap. Rather than moving elements, the deque keeps slack before the first live element: prepending decrements front and writes into the vacated slot. When front would run past the low end of the map, a block is taken at the front and front is increased by the block size, which is why the map needs its own base offset or a pointer that can move backward as blocks are added; the code above omits that offset to keep the index arithmetic visible. Appending increments n and writes; when the last block is full, a new block is appended to the map.

The arithmetic is two operations more than a flat array’s single multiply-and-add, and the second operation is a dependent load: the block pointer must be fetched before the element address is known. That dependent load is what makes random access to a deque slower than to a vector, even when the deque’s total size is small enough to fit in cache.

Growing the map is the only Θ(n) operation, and it copies pointers rather than elements. For a deque of a million 4-byte elements with 512-element blocks, the map holds about 2000 pointers, so growing it copies about 16 KiB rather than the 4 MB of element data. That is the structural reason a deque’s growth is cheap: the expensive copy is of the index, not the data.

What the indirection costs

Three costs follow from the block map, and all three are on the access path rather than the update path.

An extra dependent load per access. A flat array’s address is base plus offset; a deque’s is map[pos >> shift] plus offset, where the map entry must be loaded. When the map entry is in L1 the load is a few cycles; when it is not, the access pays a full memory latency before it can even begin to fetch the element.

A fragmented footprint. The blocks are separate allocations, so their physical addresses are not related. A scan over the whole deque visits the blocks in map order but the map order does not imply physical adjacency. Each block is contiguous, so the scan gets the cache-line benefit within a block, but the prefetcher sees a discontinuity at each block boundary. The number of discontinuities is the number of blocks, which for a large deque is in the thousands.

Worse constant factors on iteration. An iterator over a deque must track a block pointer, a current position, and a position within the block, or recompute the block from a global index on each step. std::deque’s iterator is a heavier object than a pointer, and the standard does not require its elements to be contiguous, so std::sort on a deque works but cannot use the contiguous-range fast paths that a vector enables.

The comparison is not a matter of one being better. A vector is faster for random access and iteration and slower for front insertion; a deque is the reverse. The crossover point is where the number of front insertions times the element count exceeds the cost of the indirection on the accesses. The vector’s own growth behaviour, which the deque replaces with a map of blocks, is set out in Growth Policies in Dynamic Arrays.

Operation	Flat vector	Blocked deque
Append	amortized O(1)	amortized O(1)
Prepend	O(n)	amortized O(1)
Random access	one multiply-add	shift, mask, dependent load
Iteration	contiguous, prefetchable	contiguous within blocks
Growth	copies all elements	copies the block map

The circular variant inside a block map

A deque can also be built as a single circular buffer with a growth step, which is the layout used by many ring-buffer-backed deques. Capacity is a power of two, the front and back indices are masked, and growth doubles the capacity and copies the contents in two runs — the elements from front to the end, then the elements from the start to back — into a new buffer starting at index zero. That copy is Θ(n), but it happens geometrically often, so the amortized cost stays constant.

This layout has one contiguous region instead of many blocks, which is better for iteration and for prefetching. Its cost is that growth copies every element, so a deque that grows to hold millions of elements performs a large copy at each doubling. The blocked layout’s advantage is precisely that its growth copies pointers, not elements, so the largest copy is proportional to the number of blocks. The fixed-capacity version of the circular layout is the ring buffer, which has no growth step at all and therefore no copy.

Python’s collections.deque takes a different route to the same two-ended guarantee: a doubly linked list of fixed-size blocks, each block an array of object pointers. Prepending and appending are O(1) on the end blocks. Indexing is not: the implementation starts from the block at whichever end is nearer to the requested index and follows the block chain until it reaches the right one, so the cost is proportional to the index’s distance from the nearer end in blocks. An access to the middle of a large deque therefore traverses the most blocks the structure can put between an end and a position, which makes deque[i] linear in the worst case rather than the constant-time step the block arithmetic suggests. The block length is 64 pointers, so a block’s pointer array occupies eight 64-byte cache lines on a 64-bit build.

Where deques and rings meet

A ring buffer is a deque with a fixed capacity and no growth path. The full/empty distinction that a ring must resolve — the extra slot or the monotonic counter — is a consequence of the fixed capacity, and a growing deque does not have it because the length is a separate field. The concurrency properties differ too: a ring can be made lock-free for one producer and one consumer because the indices are the only shared state, while a growing deque reallocates and therefore needs exclusion around the growth.

The shared element is the modular index arithmetic. Both structures wrap an index around a power-of-two capacity, both rely on the mask to make the wrap cheap, and both are sensitive to the same failure: an index that is not masked, or masked with a value that is not a power of two, silently addresses the wrong slot. The ring’s version of this problem is worked through in Ring Buffers and the Cost of Telling Full From Empty.

Choosing a capacity policy

A deque with a block map has three size parameters: the block size, the initial map size, and the map growth factor. The block size trades iteration locality against map size and allocation count. A block large enough to hold several cache lines amortizes the per-block allocation and the dependent map load over a useful run of elements; a block much larger than the L1 data cache means a scan through it evicts its own beginning before the scan reaches the end, and it makes each block allocation a coarser commitment of memory that a short deque never uses.

The map growth is a separate geometric series. Doubling the map doubles the number of block pointers, which for a large deque is a small allocation, and it does not touch the blocks. The standard’s rule for insertion at either end is that it invalidates all iterators but leaves references to elements valid ([deque.modifiers]); for a blocked implementation the reason is that the elements stay in their blocks while the pointer a caller holds into their interior is unaffected. That distinction between reference invalidation and iterator invalidation is a common source of confusion in code that stores pointers into a deque and assumes they behave like pointers into a vector. The guarantee is a property of the standard container, not of every deque: std::deque is permitted to be a contiguous buffer, and an implementation that chooses that representation invalidates references as well.

Prepending into the reserved slack means a pointer to an element remains valid as long as that element is not erased. A pointer to the element at logical index 0 becomes a pointer to logical index 1 after a prepend, but the element itself has not moved. The stability of element addresses, not of indices, is what the block layout buys, and it is why a deque is a reasonable container for objects that other structures point at. Removal from the middle is the operation that breaks this stability, and the shift it forces on a flat array is covered in Erasing From the Middle.