[masklinn]

> My intuition tells me unordered_map is better to iterate, and map is better to random access.

map is definitely not better for random access, with the possible exception of adversarial input: IIRC std::map pretty much requires an rbtree so you get an O(log2(n)) access, while unordered_map is a hashmap so has an O(1) best case but O(n) worst case.

unordered_map might have a better cache friendliness (though that's debatable as IIRC the standard requires closed-hashing), however iterating it is a long series of unpredictable branches (each bucket can be empty or full and the better your hash function the more random it is), std::map requires a lot of pointer-chasing instead but it's all completely predictable.