Five small instruments for the ideas in CP01 that move. Change the values, predict what will happen before you press Step, then check. Everything runs in your browser; the race at the bottom times real code on your machine.
The loop is for (int x : v) if (x > best) best = x; and its promise is best is the largest value visited so far. Aqua cells keep the promise; orange cells break it. Then try all-positive values and see why the bug hides.
Step through the values. A new key is created at 0 and then counted (yellow); an existing key gains one (aqua). Then look up a key two ways and watch the size of the map.
| key | count |
|---|
The contract says: most frequent, and a tie goes to the smaller value. The standard does not promise the order in which a loop meets an unordered_map's pairs, so shuffle it and see which scans still keep the contract.
One pass with a memory of value → index. At position j the loop asks: have I already seen target − v[j]? Switch to store, then check and run {3, 2, 4} with target 6.
| value | index |
|---|
Slide n. Checking every pair costs n(n − 1)/2 checks; one pass costs about n map operations. The chapter's planning numbers are 10⁹ pair checks per second and 20 ns per map operation. Then predict, and race both in this browser.
The race times both methods on n = 1,000, then 4,000, then 16,000 random values. Each time n grows 4 times, how many times longer does each method take?
| n | every pair (ms) | one pass (ms) | pair ratio | one-pass ratio |
|---|---|---|---|---|
| Write your two predictions, then press Run the race. | ||||
This is JavaScript, not your C++, so the milliseconds differ from .\run.ps1 -Bench. The ratios are the point: they come from the shape of the work, which is the same in both languages. Small sizes are noisy because fixed costs dominate.