Custom Order: Comparators

sort knows one order for numbers, one for strings and one for pairs. Real rules are rarely that simple: more points first, then fewer games, then the name. And a struct has no order at all until you give it one. This lesson is about telling sort what "comes before" means.

A comparator: the rule as a function

n players took part in a tournament. Each has a name, a number of points and a number of games played. Print the ranking: more points first; among equal points, the player who played fewer games; among those, alphabetical order.

A player is a struct with three fields, and the rule has three levels. We write the rule as a bool function of two players that answers one question: must a come before b? Then we hand that function to sort as its third argument, where greater<int>() went in the last lesson:

For Zara 7 4, Ali 9 5, Timur 7 3, Bek 7 3 it prints Ali first (9 points), then Bek and Timur (7 points, 3 games each, so the name decides), then Zara (7 points, 4 games). Such a function is called a comparator, and every comparator has the same shape — a ladder:

The rules a comparator must obey

sort trusts the comparator completely, and a comparator that breaks the rules makes sort produce garbage or even crash. Two rules cover almost everything:

• Strict. cmp(x, x) must be false: an element doesn't come before itself. So compare with < or >, never <= or >=. The ladder above does this automatically — equal keys fall through, and the last line returns false for equal elements.
• Consistent. If a comes before b and b before c, then a must come before c. Rock–paper–scissors breaks this: rock beats scissors, scissors beat paper, and paper beats rock. With "the winner comes first" as the rule, the three go round in a circle, and sort can't sort a circle.

A comparator never changes the elements and never reads anything but the two it was given.

A lambda: the comparator written on the spot

For a short rule, a separate function is a lot of ceremony. C++ lets you write the function right inside the call: [](const string &a, const string &b) { … } is a function with no name — a lambda. Everything else is the same: two references in, a out.