Learn C++ STL

Lesson 5 of 9 · map and multimap: A Key Finds Its Value

Module 9 · map and multimap: A Key Finds Its Value

Under the Hood: A Pair in Every Node, and What a Miss Costs

ProReading

Kenji's game server keeps the scores of a million players in a map<int, int>. Many times a day it asks whether a player has played, with if (scores[id] > 0). One day a million questions came, every one about a new player. In one run on Compiler Explorer they took 2,032 ms, against 1,224 ms with find. The map grew from 1,000,000 players to 2,000,000, and the next walk over every player took 331 ms instead of 154. Kenji wants to know where the time and the bytes went.

Checking what this lesson needs for you…

What is inside Under the Hood: A Pair in Every Node, and What a Miss Costs

  1. A node: three links and a colour, then the pair
  2. The map object and its tree come from Module 8
  3. GCC 12's own operator[] and at
  4. What a miss leaves behind
  5. Why the key is const, and how extract changes it
  6. The performance lab: where Kenji's time and bytes went