Skip to main content
Be Bitwise
C++Assembly Equivalents of C++ Patterns

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:

cpp
// 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:

cpp
#include <vector>
int sum_vector(const std::vector<int> &v) {
int total = 0;
for (int x : v) {
total += x;
}
return total;
}
asm
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
ret

The 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

cpp
void add_element(std::vector<int> &v, int val) {
v.push_back(val);
}
asm
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 ...
ret

The 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:

cpp
std::vector<bool> flags(8);
flags[3] = true;
asm
; 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 bit

Where 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:

cpp
// 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 data

A std::map object itself contains:

cpp
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:

cpp
auto it = m.find(42);
asm
; 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
ret

Every 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):

cpp
// 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 bytes

Looking up a key:

asm
; Simplified lookup
; rdi = pointer to map, esi = key
lookup:
; 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 .chain

With 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

cpp
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

Operationvectormapunordered_map
Access by index[base + i*sizeof(T)] 1 instructionN/AN/A
Find by keyO(n) scanO(log n) pointer chasesO(1) hash + compare
InsertAmortized O(1) at endO(log n) + allocationO(1) amortized + allocation
Cache behaviourExcellent (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.

Sequence [0/16]:
500ms
048121620242896208320432544656768880
Hits: 0Misses: 0Rate: 0.0%

Cache Contents(Direct-Mapped, 8 lines, 16B/line)

IndexVTagData
00--
10--
20--
30--
40--
50--
60--
70--

Practical Assembly Inspection

You can examine any STL operation:

bash
g++ -S -masm=intel -O2 -std=c++17 example.cpp -o example.s
cat example.s | c++filt | less # Demangle names for readability

Or 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.