Sequence Containers (vector, deque, list, forward_list, array)
std::vector is a train that doubles its carriage count every time it fills up. Appending is instant 99% of the time, but when full, it buys a brand new double-sized track and moves all passengers over in one go.
On 64-bit platforms (GCC libstdc++, Clang libc++, MSVC STL), std::vector<T> contains exactly three raw 8-byte pointers: T* _M_start (points to the first allocated element), T* _M_finish (points one past the last valid element), and T* _M_end_of_storage (points one past the end of the allocated capacity). $3 × 8 = 24$ bytes. size() is computed on the fly as _M_finish - _M_start, and capacity() is _M_end_of_storage - _M_start.
std::vector stores all elements in a single contiguous block of heap memory; expanding capacity requires allocating a larger block and migrating all elements, which invalidates all existing pointers. In contrast, std::deque stores elements in a segmented collection of fixed-size chunks indexed by a central pointer map. Pushing to the front or back simply allocates a new fixed-size chunk and adds its pointer to the map. Because the existing chunks remain at their original heap addresses, pointers and references to existing elements never move and are never invalidated.
reserve(N): Pre-allocates raw memory so capacity() >= N. It does not construct any objects and does not change size(). Iterators are invalidated if and only if $N > capacity$ (triggering a reallocation).
resize(N): Modifiessize()to equal N. If $N > size(), it default-constructs or copy-constructs N - size() new elements. If N < size()$, it destroys excess elements from the back. Likereserve, it reallocates and invalidates iterators if $N > capacity$.
Interviewer's lens
Interviewers probe sequence containers to quickly distinguish between textbook memorizers and engineers who understand physical computer hardware:
- Textbook trap: Weak candidates quote Big-O in a vacuum (e.g. claiming
std::listis faster because insertion is 'always O(1)'). - Hardware reality: Senior candidates know that contiguous L1/L2 cache line prefetching makes
std::vectordramatically outperform node-based lists in almost every real workload. - Key metrics expected: The exact 24-byte 3-pointer stack layout of
std::vector, how geometric growth factors (1.5x vs 2.0x) amortize allocation cost, whystd::deque's chunk-map gives pointer stability across pushes, and how to avoid the infamousstd::vector<bool>bitfield proxy reference trap in production.
Under the hood & memory layout
Think of sequence containers as three different physical storage systems:
std::vectoris a single expanding bench: Everyone sits shoulder-to-shoulder in one unbroken row. Its 24-byte stack frame holds three pointers:begin,end, andend_of_storage. When the bench is full, it builds a brand new bench twice as long (2.0x on GCC/Clang, 1.5x on MSVC), moves everyone over, and tears down the old one.std::dequeis a ring binder of paper pages: Instead of one giant page, it keeps an index of fixed-size chunks (typically 512 bytes). Adding at the front or back simply snaps in a new page into the binder—existing seats never move, so pointers and references stay permanently valid.std::listis a scavenger hunt of sticky notes: Every single item is a separate heap allocation holdingprevandnextpointers (24 bytes of overhead on 64-bit for just one value). Traversing it forces the CPU to chase pointers across scattered memory, destroying L1/L2 cache prefetching.std::arrayis a fixed egg carton: Sits directly on the stack with zero heap allocation and zero memory overhead.
Consists of three 64-bit pointers: T* _M_start (first element), T* _M_finish (one past last element, size() = _M_finish - _M_start), and T* _M_end_of_storage (capacity() = _M_end_of_storage - _M_start).
Stores a pointer-to-pointer map T** _M_map, a map size size_t, and two iterators (_M_start and _M_finish) each containing pointers to current element, first element of chunk, last element of chunk, and node pointer in map. Elements live in fixed-size buffers (typically 512 bytes).
Every element is wrapped in a distinct heap node: void* _M_next (8B), void* _M_prev (8B), plus alignment padding (8B) and T payload. Traversing nodes forces non-contiguous pointer chasing that defeats CPU L1/L2 prefetchers.
Does not store bool (1 byte each). Instead, packs 8 boolean flags into 1 byte (or 64 per uint64_t word). Indexing v[i] returns an ephemeral std::vector<bool>::reference proxy object instead of bool&.
Core concepts & syntax traps
std::vector Internal Memory, Geometric Growth & Amortized O(1)
std::vector Internal Memory, Geometric Growth & Amortized O(1)
Imagine packing a suitcase that cannot stretch: once full, you must buy a larger suitcase, move every shirt over, and throw the old one away.
When push_back() exceeds capacity(), std::vector runs a 3-step geometric migration:
- Allocate: Requests a brand new contiguous heap block scaled by a growth factor (2.0x in GCC libstdc++ and Clang libc++, 1.5x in MSVC STL).
- Migrate: Transfers elements to the new block using
std::move_if_noexcept(falling back to copying if the move constructor might throw, maintaining strong exception safety). - Deallocate: Destroys the old elements and frees the old heap buffer, immediately dangling all previous iterators and pointers.
Amortized vs Worst-Case Latency:
- Amortized O(1): Because capacity grows geometrically, reallocations become exponentially rarer. Populating N elements requires roughly 2N total writes across all expansions.
- Worst-case O(N) spike: The single
push_back()triggering reallocation halts execution to copy memory. Eliminate this latency spike upfront withreserve(N).
std::vector<int> v;
v.reserve(1000); // Allocates capacity for 1000 elements upfront without constructing them!
for (int i = 0; i < 1000; ++i) {
v.push_back(i); // Guaranteed ZERO reallocations and ZERO pointer invalidations
}
v.shrink_to_fit(); // Non-binding request to shrink capacity() down to match size()Always call reserve() when the final element count or an upper bound is known in advance.
reserve() vs resize() & The Default Construction Trap
reserve() vs resize() & The Default Construction Trap
Candidates often mix up reserve() and resize(), causing subtle crashes or wasted allocations:
-
reserve(n)reserves raw land without building houses:- Affects
capacity()only;size()remains strictly 0. - Allocates raw heap bytes for at least n elements without running constructors.
- The trap: Calling
v.reserve(10)then accessingv[0] = 42is Undefined Behavior because no element exists yet! Usepush_back()instead.
- Affects
-
resize(n)actually constructs the houses:- Modifies
size()directly. - If n > size(), it appends n - size() new value-initialized elements (e.g.
0forint), invoking constructors. - If n < size(), it truncates the vector by destroying excess elements from the back, leaving
capacity()unchanged.
- Modifies
std::vector<int> v1;
v1.reserve(5); // size=0, capacity=5. v1[0] is UNDEFINED BEHAVIOR!
std::vector<int> v2;
v2.resize(5); // size=5, capacity=5. Elements are initialized to 0: {0, 0, 0, 0, 0}
v2[0] = 42; // Perfectly legalUse reserve() when you plan to append elements with push_back()/emplace_back(); use resize() when you want to immediately index elements with operator[].
std::deque: Chunk Map Architecture & Pointer Invariance
std::deque: Chunk Map Architecture & Pointer Invariance
Instead of one long continuous bench like std::vector, std::deque is built like a train with fixed-size cars (chunks of 512 bytes in libstdc++):
- Chunk-Map Index: A central pointer table tracks each fixed-size page buffer scattered in heap memory.
- Stable Seat Addresses (Pointer Invariance): Pushing to the front or back simply allocates a new 512-byte chunk and attaches it to the map. Existing chunks never move in memory, meaning pointers and references to elements remain permanently valid!
- Double-Hop Indexing: Accessing
dq[i]runs in O(1) time using two pointer dereferences instead of one:- Chunk index:
chunk = i / CHUNK_ELEMS - Element offset:
offset = i % CHUNK_ELEMS
- Chunk index:
- Iterator Invalidation Nuance: While element references never die on front/back pushes, iterators can invalidate if the central pointer table expands.
std::deque<int> dq = {1, 2, 3};
const int* ptr = &dq[1]; // Points to '2'
dq.push_front(0); // Allocates front chunk if needed; DOES NOT move existing chunks!
dq.push_back(4); // Allocates back chunk if needed
// ptr is STILL 100% valid and still points to 2! (Vector would have dangled here)
assert(*ptr == 2);Choose std::deque over std::vector when you need O(1) push_front or when pointers to elements must survive insertions at both ends.
std::list vs std::forward_list: Splicing & Memory Overhead
std::list vs std::forward_list: Splicing & Memory Overhead
Linked lists decouple storage completely: every element lives inside its own isolated heap box.
The Splicing Superpower (O(1) Node Adoption):
std::list::splice()transfers entire node chains between lists in strictly O(1) time.- It only rewires boundary
prevandnextpointers. Zero heap allocations occur, zero elements are copied, and existing node memory addresses are 100% preserved (ideal for LRU caches).
The Memory & Cache Penalty:
- Node Overhead: On 64-bit systems, each
std::listnode needs 16 bytes for pointers (prev+next) plus alignment padding—totaling 24 bytes of overhead per element. Storing a 4-byteintwastes 600% extra memory! - Cache Annihilation: Nodes are scattered in RAM, turning iteration into pointer chasing that misses L1/L2 caches.
std::forward_list(Singly-Linked): Cuts overhead down to 8 bytes by droppingprev. It deliberately omits.size()to prevent developers from accidentally running an O(N) count in hot loops.
std::list<int> a = {1, 2};
std::list<int> b = {3, 4};
// Transfers all nodes of 'b' into 'a' at a.begin() in O(1) without any allocation!
a.splice(a.begin(), b);
// a is now {3, 4, 1, 2}, b is empty. Pointers to nodes 3 and 4 are UNCHANGED.Use std::list only when you need O(1) splice or zero-invalidation node insertions; for forward-only singly-linked chains with no size overhead, use std::forward_list.
The std::vector<bool> Proxy Reference Trap & Thread Safety
The std::vector<bool> Proxy Reference Trap & Thread Safety
In an attempt to conserve memory, C++ specialized std::vector<bool> to pack 8 boolean flags into each byte. This well-intentioned optimization breaks core language contracts:
- No True
bool&Exists: Hardware can only address whole bytes, never individual bits. Because the compiler cannot form a raw pointer or reference to a bit,operator[]returns a temporary proxy object (std::vector<bool>::reference). auto&Fails Compilation: Writingauto& flag = v[0];fails to compile because a non-const referencebool&cannot bind to an ephemeral proxy object.- Template Breakage: Generic templates expecting
T& ref = container[i];break when instantiated withbool. - Multithreaded Data Races: Writing to
v[0]andv[1]from separate threads simultaneously triggers a data race. The CPU cannot write a single bit in isolation; it issues a read-modify-write on the entire shared machine word!
The Production Fix: Use std::vector<uint8_t> for byte-addressable, thread-isolated booleans, or std::bitset<N> when sizes are known at compile time.
std::vector<bool> vb = {true, false};
// auto& bad = vb[0]; // COMPILE ERROR: cannot bind bool& to temporary proxy!
auto good = vb[0]; // Warning: 'good' is std::vector<bool>::reference, NOT bool!
// Clean production fix when byte-addressability is needed:
std::vector<uint8_t> safe_bools = {1, 0};
auto& ref = safe_bools[0]; // Real uint8_t&, completely safe and thread-isolated!Never use std::vector<bool> in generic code or multithreaded pipelines; use std::vector<uint8_t> or std::bitset instead.
Unlock Live Implementation & Interview Scenarios
The C++23 production code, live coding steps, scenario twist solutions, and common UB traps are part of Brute2Best Pro. Module 1 is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.