std::map vs std::unordered_map: The Iteration Contract Nobody Reads
90 Day C++ Challenge: Zero to Production -- Day 25
I broke a nightly report by making it faster. The data stayed correct; the rows just came out in a different order than the day before, and a golden-file test caught it. The single change responsible was swapping a std::map for a std::unordered_map to speed up a hot lookup. This post is about the contract I forgot to read.
The two containers are not interchangeable
std::map and std::unordered_map have nearly the same interface, so it is tempting to treat them as drop-in replacements. They are not. They are built on different data structures and they make different promises.
std::map is a balanced binary search tree (a red-black tree). Keys are stored in sorted order. find , insert , erase are O(log n) . Iteration is always in ascending key order , and that is guaranteed by the standard.
std::unordered_map is a hash table .…