C++ Map Lookup Memoization

Memoization is an old technique. It’s basically caching outputs for giving inputs (usually in a map). But a map lookup itself is not free. How can we memoize map lookups?

I learned from my coworker this nifty trick recently. Let’s say we have a map (e.g. std::unordered_map<K,V>, for which the associations (key -> value mapping) don't change during the lifetime of the program. This is fairly common for things like settings and counters. Now every time you look up a certain key, you have to paid the lookup cost (more instructions, cacheline misses, memory accesses, you name it). How…