Custom comparators and strict weak ordering

Six contest teams sorted by problems solved, then penalty, then name came out in the same order with both compilers, whatever order they arrived in. A comparator tells std::sort, std::set and the other sorted algorithms and containers which of two elements comes first: comp(a, b) returns true when a must come before b, and false otherwise, including when the two tie. Custom comparators let you sort by several keys, by a key you compute, or in descending order.

They come with one requirement: the comparator must be a strict weak orderingstrict weak ordering: The rules a comparator of the ordered containers and of std::sort must follow: comp(a, a) is false, comp is transitive, and keys that neither go before the other form groups of equivalent keys. a < b qualifies; a <= b does not. More in “std::map, std::set and custom comparators”. No element comes before itself, two elements never both come first, “comes before” chains from a to b to c, and ties chain the same way. A comparator that breaks a rule is undefined behaviourundefined behaviour: What a program does when it breaks a rule for which the C++ standard sets no requirements, such as reading past the end of an array. The compiler may assume it never happens, so the result can change with the compiler and the optimisation level. More in “Object lifetime and undefined behaviour in C++”, and the damage ranges from a wrongly sorted result to a crash. Below, the four rules come first, then one order with three keys, written two ways and compared with two others.

A comparator answers one question, under four rules

The requirement comes down to four properties, as cppreference’s page on the Compare requirement lists them, and each one has a classic way of being broken:

• Irreflexive: comp(a, a) is false, so nothing comes before itself. a <= b breaks it.
• Asymmetric: comp(a, b) and comp(b, a) are never both true. a != b breaks it, because it says each of two different values comes first.
• Transitive: a before b and b before c means a before c. A circular order, like rock, paper, scissors, breaks it.
• Transitive ties: if a ties with b and b with c, a ties with c. “Close enough counts as equal”, with a tolerance, breaks it.

Two elements tie, or are equivalentequivalent keys: Two keys a and b are equivalent for a comparator comp when neither comp(a, b) nor comp(b, a) is true. Ordered containers keep one element per group of equivalent keys and find a key by equivalence, never by ==. More in “std::map, std::set and custom comparators”, when neither comes before the other. A strict weak ordering does not forbid ties: it sorts the elements into groups of ties and puts the groups in a line. std::abs(a) < std::abs(b) is a valid strict weak ordering in which 3 and -3 tie. The diagram shows the groups for the contest standings below, ordered by problems solved and penalty minutes only.

Sorted containers use the same rule to decide what a duplicate is. A std::set keeps one element per group of ties, so a set of teams whose comparator looks only at problems solved would keep a single team for each count and quietly drop the others. Give a set’s comparator enough keys to tell apart everything you mean to keep.

std::tie compares three keys in one line

Standings order teams by problems solved, more first, then by penalty minutes, fewer first, then by name. The program writes that order twice:

// standings.cpp: contest standings ordered by problems solved (more first), then penalty minutes (fewer first),
// then name (alphabetical), written two ways: with std::tie in a lambda, and with a projection.
#include <algorithm>
#include <cstdio>
#include <string>
#include <tuple>
#include <vector>

struct Team {
    std::string name;
    int solved;
    int penalty;
};

static void print(const char* title, const std::vector<Team>& teams) {
    std::printf("%s\n", title);
    for (const Team& t : teams) std::printf("  %-8s %d solved, %3d min\n", t.name.c_str(), t.solved, t.penalty);
}

int main() {
    const std::vector<Team> input = {
        {"Mei", 5, 210}, {"Asha", 5, 180}, {"Kofi", 4, 95}, {"Ravi", 5, 180}, {"Lena", 4, 95}, {"Omar", 3, 40},
    };

    // A comparator returns true when a must come before b. y.solved on the left makes "more solved" come first.
    std::vector<Team> a = input;
    std::sort(a.begin(), a.end(), [](const Team& x, const Team& y) {
        return std::tie(y.solved, x.penalty, x.name) < std::tie(x.solved, y.penalty, y.name);
    });
    print("with std::tie:", a);

    // The same order as a key: tuples compare member by member, and -solved puts larger counts first.
    std::vector<Team> b = input;
    std::ranges::sort(b, {}, [](const Team& t) { return std::tuple(-t.solved, t.penalty, t.name); });
    print("with a projection:", b);
}

from session import run

# The standings with both compilers: the two ways print the same order.
run("""
clang++ -std=c++23 -O2 -Wall -Wextra standings.cpp -o standings && ./standings
g++-16 -std=c++23 -O2 -Wall -Wextra standings.cpp -o standings-gcc && ./standings-gcc
""")

$ clang++ -std=c++23 -O2 -Wall -Wextra standings.cpp -o standings && ./standings
with std::tie:
  Asha     5 solved, 180 min
  Ravi     5 solved, 180 min
  Mei      5 solved, 210 min
  Kofi     4 solved,  95 min
  Lena     4 solved,  95 min
  Omar     3 solved,  40 min
with a projection:
  Asha     5 solved, 180 min
  Ravi     5 solved, 180 min
  Mei      5 solved, 210 min
  Kofi     4 solved,  95 min
  Lena     4 solved,  95 min
  Omar     3 solved,  40 min
$ g++-16 -std=c++23 -O2 -Wall -Wextra standings.cpp -o standings-gcc && ./standings-gcc
with std::tie:
  Asha     5 solved, 180 min
  Ravi     5 solved, 180 min
  Mei      5 solved, 210 min
  Kofi     4 solved,  95 min
  Lena     4 solved,  95 min
  Omar     3 solved,  40 min
with a projection:
  Asha     5 solved, 180 min
  Ravi     5 solved, 180 min
  Mei      5 solved, 210 min
  Kofi     4 solved,  95 min
  Lena     4 solved,  95 min
  Omar     3 solved,  40 min

Both ways printed Asha, Ravi, Mei, Kofi, Lena and Omar with both compilers. std::tie builds tuples of references, and tuples compare member by memberlexicographic comparison: Comparing two sequences element by element from the first: the first pair of elements that differ decides, and a sequence that runs out first is the smaller. Tuples, pairs, std::array and strings compare this way, like words in a dictionary. More in “std::pair, std::tuple and structured bindings” from the left, so one comparison covers all three keys. For the descending key, y.solved stands where x.solved would, which reverses that key alone. The projectionprojection: A function that a range algorithm applies to each element before comparing or testing it, such as &Student::marks in std::ranges::sort(students, {}, &Student::marks): the comparison sees two numbers, and the sort moves whole students. More in “C++ range algorithms and projections” version gives std::ranges::sort a key for each team instead of a comparator, and -t.solved does the reversing; the default comparison then applies to the keys. The name breaks the last ties, so the order is the same whatever order the teams arrived in. Step through three of the comparisons the sort makes, with the teams’ own numbers:

For a whole range in descending order, pass std::greater<>{} to std::sort, or std::ranges::greater{} to std::ranges::sort. Negating a key works for most signed integers, but not for the smallest int, whose negation overflows, nor for unsigned types and strings; swapping the two sides of that key works for every type.

Four ways to write one multi-key order, and when each fits

The same three-key order can be written in four ways:

• Chained if statements: one comparison per key, returning at the first difference; swap a and b for a descending key. The easy mistake is a < where > was meant, in one branch. Best for keys that need special rules.
• std::tie: two tuples of the keys, compared with <; swap the two sides for a descending key. The easy mistake is mixing the sides of different keys. Best for most contest code.
• A defaulted operator<=>: the members, declared in the order of the keys; a descending key needs a negated or wrapped member. The easy mistake is members in the wrong order. Best for types that always sort the same way.
• A projection: a function from an element to its key; negate the key, or pass std::greater. The easy mistake is a key that allocates on every call. Best for sorting by one computed key.

Answer three questions about your order, and the table rules out the ways that cannot express it:

A defaulted operator<=> makes a type sortable everywhere, with its members compared in declaration order, while the other three describe one order at the place where you sort. Two more tools complete the set: std::stable_sortstable sort: A sort that keeps elements which compare equal in the order they had before it, as std::stable_sort does. std::sort promises nothing about equal elements, so a second sort by another key keeps the first sort's order among ties only when it is stable. More in “Essential C++ algorithms: find, sort, partition” keeps ties in their input order, and sorting a vector of indices moves small integers instead of large elements.

Practise: comparators, keys and ties

Practise the four rules, the three keys and the four ways; your weakest idea comes first, and each option explains itself.

Comparators that break the rules, reproduced and caught Pro: opens with a Pro, Premium or Ultimate pass

Index sorts, stable ties and five classic orders Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• A comparator returns true only when a must come before b; never use <=.
• Custom comparators must be strict weak orderings: irreflexive, asymmetric, transitive, with transitive ties.
• Use std::tie or a projection for several keys, and swap the sides of a key, or negate it, to sort it descending.
• Use std::stable_sort when ties must keep their input order.