12. Map vs Hash
In a market-data hot path, we maintain counters keyed by 64-bit instrument IDs. Latency spikes from dynamic memory and rehashing can violate budgets. Choose container strategy and usage that keeps per-update latency predictable.
#include <unordered_map>
#include <map>
using U = std::unordered_map<uint64_t,int>;
using A = std::map<uint64_t,int>;
void bump(U& u, A& a, uint64_t k) {
u[k]++; a[k]++;
}
Part 1.
For random 64-bit keys and no ordering requirement, which container would you prefer for bump, and how would you eliminate latency spikes? Describe any initialization and update changes you’d make.
Part 2.
(1) Which iterator and reference invalidations occur on insert, erase, and rehash for both containers?
(2) How would you avoid rehash spikes and allocator jitter in the hot path?
(3) Compare u[k]++ versus find + try_emplace + increment for latency.
(4) How do iteration order and cache locality differ between map and unordered_map?
(5) When are custom allocators or pmr beneficial for these containers?
Answer
Answer (Part 1)
Prefer unordered_map for random IDs; avoid map unless sorted order is required. Pre-size and cap load: U u; u.reserve(N); u.max_load_factor(0.7f);. Update without surprise allocations: if (auto it = u.find(k); it != u.end()) ++it->second; else u.try_emplace(k, 1);. Avoid growing in the hot path; size once at startup and monitor the load factor.
Answer (Part 2)
(1) unordered_map: insert preserves iterators unless rehash; rehash invalidates all iterators but not references; erase invalidates erased. map: insert keeps iterators/references; erase invalidates only erased element’s iterator/reference.
(2) Call reserve(expected), set max_load_factor, and avoid growth after warm-up. Use pooled/arena allocators to amortize allocations and eliminate system-call jitter.
(3) u[k]++ does one lookup; on miss it default-constructs then increments and may allocate. find + try_emplace(k,1) avoids default construction and still keeps at most one lookup.
(4) map iterates in key order with pointer-chasing and branchy tree navigation (poor locality). unordered_map walks buckets (more sequential) but still node-based; better cache behavior on bucket array.
(5) When many small node allocations dominate latency and determinism. std::pmr or pool allocators reduce fragmentation, improve cache locality, and bound allocation cost.