Learn C++ STL

Lesson 5 of 9 · sort, Comparators and Lambdas: Tell the Algorithm What You Mean

Module 12 · sort, Comparators and Lambdas: Tell the Algorithm What You Mean

Under the Hood: Introsort, Comparator Calls and What a Lambda Costs

ProReading

Kenji ranks 20,000 players by score. He sorts their player numbers with a lambda that looks up each score, and he captured the score table by value, "to be safe". On Compiler Explorer that sort took 103 to 169 ms in eleven runs. The same lambda capturing by reference took 1.2 to 1.5 ms, with the same order at the end. That is more than 80 times faster. Maria asks the question this lesson answers: "But why would a copy matter, if the sort only reads the scores?"

Checking what this lesson needs for you…

What is inside Under the Hood: Introsort, Comparator Calls and What a Lambda Costs

  1. Introsort: three algorithms inside one sort
  2. One partition, step by step
  3. Unguarded: why the markers need no bounds check
  4. The finish: one insertion sort, mostly unguarded
  5. stable_sort: two halves, chunks of 7 and a buffer
  6. Counting the comparator's calls
  7. How often sort copies your comparator
  8. The performance lab: what a lambda costs