std::vector vs std::deque Memory Layout in C++

This article examines the core architectural differences in memory layout between std::vector and std::deque in the C++ standard library. While both sequence containers offer dynamic sizing and constant-time random access, their underlying storage models differ fundamentally: std::vector relies on a single contiguous memory block, whereas std::deque uses a segmented collection of fixed-size chunks managed by an index map. Understanding these structural differences clarifies their trade-offs in cache performance, pointer stability, reallocation costs, and API compatibility.

std::vector: Contiguous Allocation

A std::vector stores all of its elements in a single, strictly contiguous array in dynamic memory. Internally, an implementation typically maintains three pointers: one to the beginning of the allocated storage, one to the end of the currently constructed elements (defining size()), and one to the end of the allocated storage (defining capacity()).

Because the elements reside back-to-back in memory:

  • Direct Pointer Compatibility: You can obtain a raw pointer to the underlying buffer using vec.data() or &vec[0], making std::vector directly compatible with C-style APIs and routines expecting contiguous arrays.
  • Cache Locality: Traversing a vector provides optimal spatial locality. Modern CPU cache prefetchers can easily detect and accelerate sequential access over its flat memory buffer.
  • Indexing Arithmetic: Element access via operator[] compiles down to a single base-pointer offset calculation: *(base_address + index).

The primary limitation of this layout occurs during expansion. When an insertion exceeds the container's capacity(), the vector must allocate an entirely new, larger block of contiguous memory, copy or move all existing elements to the new buffer, and deallocate the old buffer. This operation invalidates all existing pointers, references, and iterators to elements in the vector.

std::deque: Segmented Block Layout

A std::deque (double-ended queue) avoids full reallocations by using a segmented memory layout, often described as an array of arrays or a "map of chunks." Instead of one large buffer, a deque manages multiple fixed-size memory blocks (chunks) containing the actual elements, alongside a central control map (an array of pointers) where each pointer targets one chunk.

Because the memory is divided into discrete pages:

  • Non-Contiguous Overall: While elements within any single chunk are contiguous, the container as a whole is not. As a result, std::deque lacks a data() member function and cannot be passed directly to C-style APIs that require a contiguous buffer.
  • Two-Level Indexing: Random access via operator[] involves two steps of indirection rather than one. The container must compute which chunk contains the element (index / chunk_size) and then locate the element within that chunk (index % chunk_size).
  • Cache Performance: Iterating through a deque is slightly less cache-friendly than iterating through a vector due to pointer chasing across chunk boundaries, though locality remains high within the boundaries of an individual chunk.

Reallocation and Growth Characteristics

The differences in layout lead to distinct reallocation behaviors:

  1. Growth at the Ends: When expanding a std::vector, the entire array must move if capacity is exhausted. When expanding a std::deque at the front or back, the container merely allocates a new fixed-size chunk and adds its address to the central pointer map. Existing elements remain untouched at their original memory addresses.
  2. Pointer and Reference Stability: Inserting elements at either end of a std::deque never invalidates references or pointers to existing elements (though iterators may be invalidated due to updates in the chunk map). In contrast, inserting into a std::vector invalidates all references and pointers if a reallocation occurs.
  3. Internal Fragmentation and Overhead: A vector maintains unused memory solely as reserved capacity at the end of its single buffer. A deque introduces metadata overhead for the chunk pointer map, may waste memory in partially filled chunks at the front and back, and incurs heap allocation overhead each time a new chunk is requested from the runtime allocator.