C++ STL Containers Deep Dive: vector, map, unordered_map, deque, set & Cache Performance

C++ STL Containers Deep Dive: vector, map, unordered_map, deque, set & Cache Performance

Table of Contents

• Why Cache Locality Beats Big-O Theory
• Container Selection Decision Tree
• std::vector: Cache-Friendly and Dominant
• vector Growth Strategy and Reserve
• std::array: Stack-Allocated Fixed Sequences
• std::deque: Growing at Both Ends
• std::list and std::forward_list: When Ordered Insertion Wins
• std::map: Sorted Key-Value (Red-Black Tree)
• std::unordered_map: O(1) Hash Table
• std::flat_map (C++23): Sorted Vector Map
• std::set and std::unordered_set
• Container Adapters: stack, queue, priority_queue
• Benchmarking Your Container Choice
• Frequently Asked Questions

Why Cache Locality Beats Big-O Theory

Modern CPUs have cache hierarchies (L1: 32KB, L2: 256KB, L3: 8-32MB) that fetch data in cache lines of 64 bytes. When you access one int in a vector, the CPU fetches the next 15 ints for free (they're in the same cache line). When you access one node in a linked list or tree, the next node is at a random memory address — cache miss, ~100ns penalty:

The lesson: For most data sizes (< 1M elements), std::vector outperforms theoretically superior structures because the CPU cache hides the O(n) linear scan cost.

Container Selection Decision Tree

std::vector: Cache-Friendly and Dominant

std::vector<T> stores elements in a contiguous heap buffer. It's the default container for ~90% of C++ use cases:

vector Growth Strategy and Reserve

When push_back exceeds capacity, std::vector reallocates to a new (typically 1.5-2×) larger buffer and moves all elements:

std::map: Sorted Key-Value (Red-Black Tree)

std::map<K, V> is a balanced binary search tree (red-black tree). Every element is a heap-allocated node — O(log n) for all operations, but significant memory overhead per element:

std::unordered_map: O(1) Hash Table

std::unordered_map<K, V> provides O(1) average lookup but no ordering, larger memory overhead (bucket array), and potential O(n) worst case on hash collisions:

std::flat_map (C++23): Sorted Vector Map

std::flat_map (C++23) implements a sorted map using two contiguous vectors (keys and values) instead of a tree. Cache-friendly iteration, but O(n) insert:

Container Adapters: stack, queue, priority_queue

Frequently Asked Questions

When should I use std::list over std::vector? Almost never in practice. Despite O(1) mid-insertion in theory, std::list suffers from cache misses on every element access. Benchmarks consistently show std::vector winning for iteration-heavy workloads even with O(n) insertion, because L1/L2 cache prefetching hides the shift cost. Use std::list only when you have hard requirements: stable iterators that must survive insertions, or genuinely need O(1) splice operations between lists.

Why does std::unordered_map sometimes perform worse than std::map? Hash collisions degrade unordered_map to O(n) worst case. Additionally, the hash bucket array has worse cache locality than a tree for small maps (< 64 elements). A third issue: hashing strings involves processing every character — for very short keys, map's string comparison can be faster than hashing. Always benchmark with your real data distribution.

What's the memory overhead of each container?

• std::vector: 3 pointers (24 bytes) + contiguous data. Most efficient.
• std::map/set: 3 pointers per node (24 bytes overhead per element). ~3-4× more memory than vector.
• std::unordered_map: bucket array + per-element linked list nodes. ~5-6× more memory than vector.
• std::flat_map: two vectors — similar to vector overhead, most memory-efficient for sorted maps.

Part of the C++ Mastery Course — 30 modules from modern C++ basics to expert systems engineering.