Sequence Containers: Memory Layout of vector, deque, and list

01The Architecture of std::vector

In modern systems programming, std::vector<T> is the default sequence container. Internally, a std::vector consists of three raw 8-byte pointers (24 bytes total on 64-bit systems): 1. start (points to the first element). 2. finish (points one past the last active element). 3. end_of_storage (points to the end of the allocated capacity).

size() is computed in O(1) time as finish - start, and capacity() is end_of_storage - start. Elements are stored in contiguous memory, maximizing CPU cache locality.

When push_back() is called and size() == capacity(), the vector reallocates: it allocates a new buffer with a Geometric Growth Factor (typically 2x in GCC/Clang or 1.5x in MSVC), moves elements to the new buffer using noexcept move constructors, and frees the old buffer. Geometric growth guarantees Amortized O(1) insertion time.

02std::deque: The Chunked Array Architecture

std::deque (double-ended queue) provides fast insertions and deletions at BOTH the front and back in O(1) time, without reallocating existing elements.

Unlike std::vector which requires a single contiguous buffer, std::deque is implemented as a two-tiered data structure: an array of pointers (the 'map') where each pointer points to a fixed-size contiguous chunk of elements (typically 512 bytes).

When expanding at the front or back, std::deque simply allocates a new chunk and updates the map. Existing elements never move in memory! This means references and pointers to elements inside a std::deque remain valid across push_front and push_back operations.

03The Fallacy of std::list in Systems Code

Introductory textbooks often praise std::list (a doubly linked list) for O(1) insertions anywhere. In production systems code, however, std::list is almost never used.

First, Memory Bloat: Every node in std::list stores two 8-byte pointers (prev and next) alongside the data. Storing a 4-byte integer requires 24 bytes (16 bytes pointer overhead + 4 bytes data + 4 bytes padding)—a 500% memory overhead!

Second, Cache Thrashing: Every node is an independent heap allocation scattered across RAM. Traversing a linked list causes the CPU to stall on almost every node due to L1/L2/L3 cache misses. In real-world benchmarks, std::vector consistently outperforms std::list by 10x to 50x, even when performing middle insertions, due to raw cache locality.

04Sequence Container Performance Matrix

Performance characteristics of standard sequence containers:

Default to std::vector. Use std::deque when FIFO queue semantics are needed without vector reallocation costs.

+-----------------------+---------------------+-------------------+-------------------------+| Container             | Random Access       | Push Back         | Push Front              |+-----------------------+---------------------+-------------------+-------------------------+| std::vector<T>        | O(1) (Contiguous)   | Amortized O(1)    | O(N) (Requires shift)   || std::deque<T>         | O(1) (2 indirection)| Strict O(1)       | Strict O(1)             || std::list<T>          | O(N) (Linear walk)  | Strict O(1)       | Strict O(1)             |+-----------------------+---------------------+-------------------+-------------------------+

05Production Systems Architecture & Hardware Trade-Offs

From an operating system and hardware architecture perspective, systems software must account for physical execution realities that compiler abstractions intentionally hide. At the hardware level, instruction caches (I-Cache) and data caches (D-Cache) operate independently, and CPU pipeline front-ends rely heavily on branch target buffers (BTB) to minimize instruction fetch stalls. When code is organized into coherent, spatially contiguous blocks within translation units, binary code density increases, improving instruction cache hit rates across high-frequency execution loops.

Furthermore, modern linkers such as LLVM lld and mold perform Link-Time Optimization (LTO) across translation units. When LTO is enabled (-flto), the compiler writes LLVM bitcode into object files rather than final machine code, allowing the linker to perform cross-translation-unit function inlining, devirtualization, and dead-code stripping across the entire binary.