STL Containers Under the Hood
STL containers wear a high-level coat, but underneath they're concrete memory layouts wired to specific operations. This lesson cracks open std::vector, std::map, and std::unordered_map in memory and assembly so you can see what each operation actually costs.
The standard only specifies behaviour and complexity, not layout. Every struct, offset and size below is modelled on libstdc++ (GCC's standard library) on x86-64 Linux and simplified for reading. libc++ (Clang's) and MSVC's STL lay things out differently.
std::vector: The Pointer Triple
A std::vector<int> is exactly three pointers:
// Simplified internal structure of std::vector<T>:template<typename T>class vector { T *_begin; // Pointer to first element T *_end; // Pointer past last element T *_capacity; // Pointer past allocated space};You can verify this in assembly:
#include <vector>
int sum_vector(const std::vector<int> &v) { int total = 0; for (int x : v) { total += x; } return total;}sum_vector: ; rdi = pointer to vector (3 pointers on stack or heap) mov rax, QWORD PTR [rdi] ; rax = _begin mov rcx, QWORD PTR [rdi+8] ; rcx = _end xor edx, edx ; total = 0
.loop: cmp rax, rcx ; begin == end? je .done add edx, DWORD PTR [rax] ; total += *begin add rax, 4 ; begin++ (sizeof(int) = 4) jmp .loop
.done: mov eax, edx ; Return total retThe range-based for loop compiles to pointer iteration: start at _begin, bump by sizeof(T), stop at _end. Identical performance to walking a raw array. The vector abstraction costs you nothing on traversal.
vector::push_back: The Reallocation Path
void add_element(std::vector<int> &v, int val) { v.push_back(val);}add_element: mov rax, QWORD PTR [rdi+8] ; Load _end cmp rax, QWORD PTR [rdi+16] ; Compare _end with _capacity je .need_realloc ; If equal, buffer is full
; Fast path: just append mov DWORD PTR [rax], esi ; *_end = val add QWORD PTR [rdi+8], 4 ; _end += sizeof(int) ret
.need_realloc: ; Slow path: allocate larger buffer, copy everything, deallocate old buffer ; This calls into a complex library function push rdi push rsi ; ... allocate new buffer (usually 2x capacity) ... ; ... memcpy old data to new buffer ... ; ... update _begin, _end, _capacity ... ; ... deallocate old buffer ... ; ... append the new element ... retThe fast path — capacity available — boils down to two instructions: store the value, bump the end pointer. The slow path triggers an allocation, a copy, and a free. It hits rarely though, because capacity doubles each time, which is what gives you amortized O(1).
std::vector<bool>: The Special Case
vector<bool> is infamously special. It packs bits instead of using one byte per bool:
std::vector<bool> flags(8);flags[3] = true;; flags[3] = true - bit manipulation! mov rax, QWORD PTR [rdi] ; Load base pointer mov ecx, 3 ; Index = 3 mov edx, ecx shr edx, 6 ; edx = index / 64 (word index) and ecx, 63 ; ecx = index % 64 (bit position) mov rsi, 1 shl rsi, cl ; Create bit mask or QWORD PTR [rax+rdx*8], rsi ; Set the bitWhere you'd expect mov BYTE PTR [rax+3], 1, you get shifts and masks. That's why vector<bool> doesn't behave like its siblings: indexing hands you a proxy object that fiddles bits, not a real bool&.
std::map: The Red-Black Tree
std::map<int, string> is implemented as a red-black tree. Each node contains:
// libstdc++-like node structure, simplified:struct _Rb_tree_node { int _color; // Red or black (4 bytes) // 4 bytes padding _Rb_tree_node *_parent; // Parent pointer (8 bytes) _Rb_tree_node *_left; // Left child (8 bytes) _Rb_tree_node *_right; // Right child (8 bytes) pair<const int, string> _value; // Key-value pair};// Node overhead: 32 bytes BEFORE the actual dataA std::map object itself contains:
struct _Rb_tree { std::less<int> _compare; // Empty, but padded to 8 bytes here _Rb_tree_node_base _header; // Sentinel: color, root, leftmost, rightmost size_t _node_count; // Number of elements};// sizeof(std::map<int, string>) = 48 bytes in libstdc++ (varies by implementation)Looking up a key:
auto it = m.find(42);; Simplified find operation; rdi = pointer to map, esi = key (42)find: mov rax, QWORD PTR [rdi+16] ; Load root node pointer.loop: test rax, rax je .not_found ; Null = not found
cmp esi, DWORD PTR [rax+32] ; Compare key with node's key je .found jl .go_left mov rax, QWORD PTR [rax+24] ; Go right jmp .loop.go_left: mov rax, QWORD PTR [rax+16] ; Go left jmp .loop
.found: ; rax = pointer to matching node ret.not_found: ; return end iterator retEvery step follows a pointer to a child. Pointer chase: every mov rax, [rax+offset] can stall waiting on a cache miss. A map with a million entries costs you ~20 hops (log2 of a million), and each hop is a fresh chance to miss cache. Which is exactly why std::unordered_map tends to win in the wild.
std::unordered_map: The Hash Table
std::unordered_map uses a hash table with separate chaining (linked lists for collisions):
libstdc++ has a twist on the textbook design. All the nodes sit on one singly linked list, and each non-empty bucket points at the node before its first node (which makes insert-after and erase-after cheap):
// libstdc++-like structure, simplified:struct _Hash_node { _Hash_node *_M_nxt; // +0: next node in the single list std::pair<const int, V> _M_v; // +8: key first, then value};
struct unordered_map { _Hash_node **_buckets; // +0: each entry = node BEFORE the bucket's first node size_t _bucket_count; // +8 _Hash_node *_before_begin; // +16: head of the list of all nodes size_t _element_count; // +24 struct { float _max_load_factor; size_t _next_resize; } _rehash_policy; // +32 _Hash_node *_single_bucket; // +48: storage used when there's only one bucket}; // 56 bytesLooking up a key:
; Simplified lookup; rdi = pointer to map, esi = keylookup: ; Hash the key: std::hash<int> in libstdc++ is the value itself movsxd rax, esi ; Modulo bucket count xor edx, edx div QWORD PTR [rdi+8] ; rdx = hash % bucket_count mov r8, rdx ; Remember our bucket index ; Load bucket entry mov rax, QWORD PTR [rdi] ; _buckets array mov rax, QWORD PTR [rax+rdx*8] ; Node BEFORE the bucket's first node test rax, rax je .not_found ; Empty bucket mov rax, QWORD PTR [rax] ; Step to the bucket's first node ; Walk the chain.chain: cmp esi, DWORD PTR [rax+8] ; Compare key je .found mov rcx, QWORD PTR [rax] ; Next node in the list test rcx, rcx je .not_found ; End of the whole list ; The list runs straight on into other buckets, so stop ; once the next node hashes somewhere else movsxd rax, DWORD PTR [rcx+8] xor edx, edx div QWORD PTR [rdi+8] cmp rdx, r8 jne .not_found mov rax, rcx jmp .chainWith a decent hash and a low load factor, chains stay at 0-1 elements, so lookups land at O(1) in practice. Each node is still its own heap allocation though, so cache behaviour rides on whatever allocation pattern your code happens to produce.
Container Size Summary
sizeof on x86-64 with libstdc++: vector<T>: 24 bytes (3 pointers) deque<T>: 80 bytes (map pointer + iterators + block size) list<T>: 24 bytes (sentinel node with prev/next + size) map<K,V>: 48 bytes (tree root + sentinel + count) unordered_map<K,V>: 56 bytes (buckets + count + load factor) string (SSO): 32 bytes (short string optimisation buffer)Element Access Costs
| Operation | vector | map | unordered_map |
|---|---|---|---|
| Access by index | [base + i*sizeof(T)] 1 instruction | N/A | N/A |
| Find by key | O(n) scan | O(log n) pointer chases | O(1) hash + compare |
| Insert | Amortized O(1) at end | O(log n) + allocation | O(1) amortized + allocation |
| Cache behaviour | Excellent (contiguous) | Poor (scattered nodes) | Mixed (buckets contiguous, nodes scattered) |
That last row is easier to feel than to read. The simulator below is a toy direct-mapped cache (8 lines of 16 bytes) with an illustrative access sequence. The first eight addresses are a vector<int> walk, 0, 4, 8 ... 28, so four ints share each line. The last eight are list<int> nodes scattered 112 bytes apart, the way a heap hands them out over time. Run it and compare: two misses for the vector, eight for the list.
Cache Contents(Direct-Mapped, 8 lines, 16B/line)
| Index | V | Tag | Data |
|---|---|---|---|
| 0 | 0 | - | - |
| 1 | 0 | - | - |
| 2 | 0 | - | - |
| 3 | 0 | - | - |
| 4 | 0 | - | - |
| 5 | 0 | - | - |
| 6 | 0 | - | - |
| 7 | 0 | - | - |
Practical Assembly Inspection
You can examine any STL operation:
g++ -S -masm=intel -O2 -std=c++17 example.cpp -o example.scat example.s | c++filt | less # Demangle names for readabilityOr use Compiler Explorer (godbolt.org) for an interactive view.
Every STL container is a specific memory layout dictating specific access patterns. Picking the right one comes down to how your accesses land on the cache hierarchy, more than to complexity classes. For small collections, a vector's O(n) linear scan routinely outruns a map's O(log n) tree walk: the vector's contiguous memory means one cache miss brings in several elements and the prefetcher can see the next line coming, while each tree hop is a dependent load that might miss.