Comparison contracts

Why it matters

A sort function does not know what "order" means. It only knows what you tell it. You tell it with a comparator, which is a small rule that takes two items and answers one question: should the first item come before the second?

The sort trusts that rule. It assumes the rule behaves like an ordinary "less than" with a few specific properties. If the rule breaks those properties, the sort does not stop with a clear error. It may give the wrong order, or it may read memory outside the list and crash. This lesson names those properties, shows what breaks without them, and gives you a checklist to run before you use a new comparator.

The earlier lesson on std::sort and comparators showed how to write the rule. This lesson is about what makes a rule safe to write.

The idea: a comparator makes a promise

Start with the simplest comparator. For numbers, the usual rule is a < b. It answers "is a smaller than b?" If the answer is yes, the sort puts a before b.

In C++, a comparator is any callable that takes two values and returns bool. A lambda is the usual choice:

auto by_size = [](int a, int b) { return a < b; };

The C++ standard calls a comparator of this kind a strict weak ordering. The name is a mouthful, so here is what it means in plain words. It is a "less than" rule that:

1. Never says an item comes before itself.
2. Never says two items come before each other.
3. Passes its answers along a chain: if a comes before b, and b comes before c, then a comes before c.
4. Treats "neither comes before the other" as a kind of equality, and that equality also passes along a chain.

Rule 4 matters for ties. If two students both have 90 points, neither one comes before the other, so the rule calls them tied. A sort that keeps ties in any order is fine. A sort that gets confused by ties is not.

Each of the four rules has a short name. You do not need the names to write good code, but they appear in error messages, so here they are:

• Irreflexive: comp(x, x) is false for every x. Nothing comes before itself.
• Asymmetric: if comp(a, b) is true, then comp(b, a) is false.
• Transitive: if comp(a, b) and comp(b, c) are both true, then comp(a, c) is true.
• Incomparability is transitive: if a and b are tied, and b and c are tied, then a and c are tied.

Asymmetry already follows from the first three rules, so it is often left out of formal lists. It is worth checking by hand anyway, because it is easy to break by accident.

The rest of this lesson is about what happens when a comparator breaks one of these rules.

Worked example 1: a checker that tests the rules

Reading the rules is not enough. You need a way to test a comparator on real values. The program below is a small checker. It takes a sample list and a comparator, then tests every pair and every triple from the sample. It returns the first rule it finds broken, or "ok" if none is broken.

The checker is slow for big lists, because it tests every triple. That is fine. You only run it on a sample of five to ten values while you are writing the rule.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
// Tests a comparator on a small sample and returns the first problem found, or "ok".
template <typename T, typename Comp>
string check_contract(const vector<T>& sample, Comp comp) {
    size_t n = sample.size();
    for (size_t i = 0; i < n; i++)
        if (comp(sample[i], sample[i]))
            return "irreflexive fails at index " + to_string(i);
 
    for (size_t i = 0; i < n; i++)
        for (size_t j = 0; j < n; j++)
            if (comp(sample[i], sample[j]) && comp(sample[j], sample[i]))
                return "asymmetry fails for " + to_string(i) + "," + to_string(j);
 
    // Two items are "equivalent" when neither comes before the other.
    auto equiv = [&](size_t i, size_t j) {
        return !comp(sample[i], sample[j]) && !comp(sample[j], sample[i]);
    };
    for (size_t i = 0; i < n; i++)
        for (size_t j = 0; j < n; j++)
            for (size_t k = 0; k < n; k++) {
                if (comp(sample[i], sample[j]) && comp(sample[j], sample[k]) && !comp(sample[i], sample[k]))
                    return "transitivity fails for " + to_string(i) + "," + to_string(j) + "," + to_string(k);
                if (equiv(i, j) && equiv(j, k) && !equiv(i, k))
                    return "equivalence is not transitive for " + to_string(i) + "," + to_string(j) + "," + to_string(k);
            }
    return "ok";
}
 
int main() {
    vector<int> nums = {3, 1, 4, 1, 5};
    cout << "a < b       : " << check_contract(nums, [](int a, int b) { return a < b; }) << "\n";
    cout << "a <= b      : " << check_contract(nums, [](int a, int b) { return a <= b; }) << "\n";
    cout << "a > b       : " << check_contract(nums, [](int a, int b) { return a > b; }) << "\n";
 
    vector<double> close = {0.0, 0.08, 0.16};
    cout << "b - a > 0.1 : " << check_contract(close, [](double a, double b) { return b - a > 0.1; }) << "\n";
 
    vector<string> words = {"pear", "fig", "banana", "kiwi"};
    cout << "by length   : " << check_contract(words, [](const string& a, const string& b) { return a.size() < b.size(); }) << "\n";
    return 0;
}

Compile and run it. The -Wall flag turns on the common warnings, and the -std=c++20 flag selects the C++ version this course uses.

g++ -std=c++20 -Wall -o checker checker.cpp
./checker

The output is:

a < b       : ok
a <= b      : irreflexive fails at index 0
a > b       : ok
b - a > 0.1 : equivalence is not transitive for 0,1,2
by length   : ok

Read each line. The < and > rules pass. The <= rule fails on the first irreflexive test, because 3 <= 3 is true. A number is "less than or equal to" itself, so the rule says 3 comes before 3. That breaks rule 1.

The last two lines are the more interesting ones. You will see the b - a > 0.1 case again in worked example 2.

Worked example 2: why <= breaks a sort

The checker found the problem in <=. Now look at what the sort itself does with that rule. The program below sorts forty copies of the number 7 with <=. Every value is equal, so a correct sort should leave the list unchanged.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> v;
    for (int i = 0; i < 40; i++) v.push_back(7);   // all equal values
    sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });
    cout << "done, first = " << v[0] << "\n";
    return 0;
}

Build it with the same command as before, then run it:

g++ -std=c++20 -Wall -o bad_le bad_le.cpp
./bad_le
echo "exit=$?"

The build prints no warnings. The run prints nothing and ends like this:

exit=139

Exit code 139 means the program was stopped by a segmentation fault. That is the operating system's message for "this program touched memory it does not own". The sort ran past the start of the list.

Why does this happen? When std::sort moves an item into place, it slides it left past bigger items. For speed, the inner loop does not check the left edge of the list. It relies on the comparator to stop the loop before the edge, at an item that is not greater than the one being moved. With <=, an equal item keeps the loop going, so the loop walks past the first element and reads memory it does not own. The C++ standard requires the comparator to follow the contract, so breaking it makes the program's behaviour undefined. The standard does not say what happens. The crash is one possible result.

The same bug does not always crash. This program sorts one thousand random values from 1 to 5 with <=. It draws the values from mt19937, a random number generator, using uniform_int_distribution, which picks whole numbers in a range:

#include <algorithm>
#include <iostream>
#include <random>
#include <vector>
using namespace std;
 
int main() {
    mt19937 gen(42);
    uniform_int_distribution<int> dist(1, 5);
    vector<int> v(1000);
    for (int& x : v) x = dist(gen);
    sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });
    cout << "sorted, first = " << v.front() << "\n";
    return 0;
}

It ran without a crash and printed:

sorted, first = 0

Zero is not in the input, because dist(1, 5) only makes values from 1 to 5. The sort read a value from outside the list and printed it. The program looked successful, and its answer is wrong. This is the most dangerous kind of comparator bug, because nothing tells you that anything went wrong.

A debug build finds the problem at once. Add -D_GLIBCXX_DEBUG to the compile command. This flag turns on the checks in the GNU C++ library (the library that ships with g++). Compile the program that sorts forty 7s with it:

g++ -std=c++20 -Wall -D_GLIBCXX_DEBUG -o bad_le_dbg bad_le.cpp
./bad_le_dbg

The program stops and prints a message. One line of it reads:

Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).

The message names the rule that failed (irreflexive), the expression that was checked (!(a < a)), and the comparator's type. The full message contains more lines about the objects involved, which are omitted here.

Use the debug flag while you test. It makes a broken comparator fail loudly instead of silently. The flag slows the program down, so you do not use it in a release build.

Worked example 3: tolerance and float values

People often write a comparator that treats two numbers as equal when they are close enough. This is common for floating-point values, the numbers with decimal points, because they cannot always be stored exactly. A typical attempt looks like this: two values are equal when they are within 0.1 of each other, and otherwise the smaller one comes first.

The checker's last test used a simpler tolerance rule: b - a > 0.1. It says that a comes before b only when b is more than 0.1 larger. Items within 0.1 of each other are treated as tied. Run it on three values, 0.0, 0.08 and 0.16:

b - a > 0.1 : equivalence is not transitive for 0,1,2

Here is what goes wrong, with the numbers written out. 0.0 and 0.08 are tied, because the gap is only 0.08. 0.08 and 0.16 are tied, for the same reason. But 0.0 and 0.16 are not tied, because the gap is 0.16, which is more than 0.1. So 0.0 is tied with 0.08, 0.08 is tied with 0.16, and yet 0.0 is not tied with 0.16. Ties must pass along a chain, so this breaks rule 4.

The final order now depends on which pairs the sort happens to compare. A different sort algorithm, or a different starting order of the same values, can give a different result. The fix is to compare exact keys, or to round the values to a fixed number of decimal places before the sort, so that equality means one thing everywhere.

Worked example 4: a multi-key comparator that is correct

Most real comparators compare more than one field. A student list might sort by score from high to low, then by name from A to Z. The safe way to write this is one if for each key, in order. Compare the first key, and only if the two items tie on that key, compare the second.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
struct Player {
    string name;
    int points;
};
 
int main() {
    vector<Player> players = {
        {"Asha", 14}, {"Ben", 22}, {"Chen", 9}, {"Dita", 22},
        {"Emil", 17}, {"Farah", 3}, {"Gus", 17}, {"Hana", 11}};
 
    sort(players.begin(), players.end(), [](const Player& a, const Player& b) {
        if (a.points != b.points) return a.points > b.points;
        return a.name < b.name;
    });
    for (const Player& p : players) cout << p.name << " " << p.points << "\n";
    return 0;
}

The output is:

Ben 22
Dita 22
Emil 17
Gus 17
Asha 14
Hana 11
Chen 9
Farah 3

Each rule in this comparator is safe. If the points differ, the answer depends only on points, and that answer is consistent. If the points are the same, the answer depends only on the names. Because the second rule only runs on ties, the two keys never contradict each other.

A common wrong version writes a.points >= b.points in place of a.points > b.points. It looks like the same rule, but >= makes an item come before itself, which is the same mistake as <=. Keep the strict form, with < or >, in every key.

Checking a result with the same comparator

After a sort, you can check the result with std::is_sorted. It takes the same comparator, and it returns true when each value is not after the next one in that order. This is a quick test that the sort did its job on your data.

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> scores = {72, 95, 61, 88, 90};
    cout << boolalpha;
    cout << "before sort: " << is_sorted(scores.begin(), scores.end(), greater<int>()) << "\n";
    sort(scores.begin(), scores.end(), greater<int>());
    cout << "after sort:  " << is_sorted(scores.begin(), scores.end(), greater<int>()) << "\n";
    return 0;
}

The output is:

before sort: false
after sort:  true

The check is only as good as the comparator. If the comparator breaks the contract, is_sorted can answer true for a list that is not really in order, because it asks the same broken question. Test the comparator on a sample first, as in worked example 1, and then use is_sorted on real data.

Common mistakes

Using <= or >= in a comparator. This is the most common contract error. The fix is to use < for "smaller first" and > for "larger first". If you need ties to be grouped together, you do not need <=. The sort already keeps tied items next to each other.

Writing descending order with >=. Descending order is a > b. Writing a >= b breaks irreflexivity in the same way as <=.

Using a float tolerance for equality. Rules such as abs(a - b) < 0.1 break transitivity, as worked example 3 showed. Compare the exact values, or use an explicit rounding step before the sort.

Reading a value that changes. A comparator should depend only on its two arguments. If it reads a global counter, a random number generator, or a value that changes during the sort, the same two items can get different answers. Keep comparators pure, which means they read only what they are given.

Comparing different kinds of data by accident. A comparator for a struct should compare fields of that struct. A comparator that mixes an int key with a string key, or that accidentally reads the wrong field name in one branch, breaks the chain of answers. Read each branch once, slowly, and check that both sides use the same field.

Testing only with the happy-path data. A comparator can pass on random data and fail on data with many equal values. Always test with a sample that has ties, duplicates and the smallest and largest values you can think of.

Checklist before you use a comparator

Run this list on every new comparator. It takes a minute and catches most contract bugs.

1. Does comp(x, x) return false for every value? Look for <= and >=.
2. For descending order, does the rule use >, not >=?
3. For more than one key, does the rule compare the first key, then the next key only on a tie?
4. Does the rule avoid tolerance checks such as abs(a - b) < eps for equality?
5. Does the rule depend only on its two arguments, with no global state and no random values?
6. Does the rule compare the same type and fields on both sides of every branch?
7. Did you run the checker on a sample with duplicates and ties?
8. Did you run the sort once in a -D_GLIBCXX_DEBUG build during testing?

Practice

Exercise 1: Is <= allowed?

Write one sentence explaining why [](int a, int b) { return a <= b; } is not a valid comparator for std::sort. Name the rule that it breaks.

Show the answer

It breaks the irreflexive rule, which says that comp(x, x) must be false. With a <= b, comp(3, 3) is true, so the rule says that 3 comes before itself. The checker reported irreflexive fails at index 0 for this rule on the sample 3, 1, 4, 1, 5.

Exercise 2: Is != a valid comparator?

Explain whether [](int a, int b) { return a != b; } is a valid comparator. Run the checker on the sample 1, 2, 3 to confirm your answer.

Show the answer

It is not valid. The asymmetry rule says that if comp(a, b) is true, then comp(b, a) must be false. With !=, both comp(1, 2) and comp(2, 1) are true. The checker prints asymmetry fails for 0,1, which means the items at index 0 and index 1 break the rule.

Exercise 3: Sort strings by length, then alphabetically

Write a comparator that puts shorter strings first. Strings of the same length should be in alphabetical order. Sort the list pear, fig, banana, kiwi, apple, date with it and show the output.

Show the answer

auto by_length_then_alpha = [](const string& a, const string& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
};

Sorted with this comparator, the list prints as:

fig date kiwi pear apple banana

The three-letter word fig comes first. The four-letter words date, kiwi and pear follow in alphabetical order. The five- and six-letter words come last.

Exercise 4: Name descending, id ascending

Write a comparator for records with a name and an id. Sort by name from Z to A, and when the names match, sort by id from smallest to largest. Test it on {"bo", 3}, {"al", 1}, {"bo", 1}, {"cy", 2}.

Show the answer

struct Item { string name; int id; };
 
auto by_name_desc_id_asc = [](const Item& a, const Item& b) {
    if (a.name != b.name) return a.name > b.name;
    return a.id < b.id;
};

The output is:

cy 2
bo 1
bo 3
al 1

The name cy comes first because it is the largest name. The two bo records come next, in id order (1, then 3). The name al comes last.

Exercise 5: Explain a tolerance failure

A comparator treats two numbers as equal when they differ by less than 0.1. Using the values 0.0, 0.08 and 0.16, explain in your own words why this breaks the sort's rules.

Show the answer

0.0 and 0.08 are within 0.1, so they are tied. 0.08 and 0.16 are also within 0.1, so they are tied. But 0.0 and 0.16 are not within 0.1, so they are not tied. A tie must pass along a chain: if a ties with b, and b ties with c, then a must tie with c. Here it does not. The checker reports equivalence is not transitive for 0,1,2.

Summary

• A comparator is a rule that answers "should this item come first?" The sort trusts the rule and does not check it.
• A valid comparator is a strict weak ordering: nothing comes before itself, two items never come before each other, and the answers pass along a chain.
• <= and >= break the rule that nothing comes before itself, and the result can be a wrong order or a crash.
• Tolerance checks for equality break the chain rule for ties, so use exact comparisons instead.
• Compare one key at a time, and only move to the next key when the first one ties.
• Test each new comparator with a small sample that has ties, and with a -D_GLIBCXX_DEBUG build, before you rely on it.