Bad comparator bugs

Why this matters

A comparator is the small function you give to a sort. It answers one question: should item a come before item b? Most of the time you write one line and it works. Sometimes it does not. The sort returns the items in a strange order, or the program crashes in a place that has nothing to do with your sort line, or the bug appears only on some inputs. These bugs are hard to find because the comparator looks correct when you read it.

This lesson covers the cases where a comparator breaks the rules that the sort depends on. In C++ a broken comparator is not a clean error. It is undefined behaviour, which means the language standard makes no promise about what the program does after that point. The program may print the wrong result, print the right result by luck, or crash. The comparison lesson earlier in this module states the rules. Here you will see what happens when each rule is broken, with real output, and how to fix each case.

The rules a comparator must follow

A comparator is usually written as a lambda, a small unnamed function. It takes two items and returns true or false. The sort uses that answer to decide order. For the sort to work, the answers must describe one consistent order. In plain words, the rules are these:

1. Asking whether an item comes before itself must always give false. An item is never before itself.
2. If a comes before b, then b must not come before a.
3. If a comes before b, and b comes before c, then a must come before c.
4. Two items that are neither before the other count as equal. Equal must also behave consistently: if a and b are equal, and b and c are equal, then a and c must be equal too.

Computer scientists call a comparator that follows these rules a strict weak ordering. The name is not important for the code. What matters is that a comparator must describe a real ordering. The examples below break one rule each. You can check the rules by hand on small inputs before you trust a comparator on big ones.

Every example in this lesson was compiled with g++ -std=c++20 -Wall on g++ 15.2. Where a sample is only shown to fail, the failure is printed by the program itself. Where the output of a bad program is not sorted, the output is shown exactly as it printed.

Example 1: <= looks right and crashes

Suppose you want to sort numbers from smallest to largest, and you write the comparator with <= because it reads as "less than or equal". Here is the program:

#include <algorithm>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v = {5, 3, 5, 1, 3, 5, 2};
    std::sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

Run it on this small list and the output looks correct:

1 2 3 3 5 5 5 

This is the danger. A bug that shows up only on some inputs can pass every test you try by hand. The comparator breaks rule 1. When the sort asks whether 5 comes before 5, <= answers true, but an item must never come before itself. On a short list the wrong answer does no harm. On a longer list with repeated values, it does.

Running it with checks on

Two tools catch this bug on the first run. The first is a library check. If you add -D_GLIBCXX_DEBUG to the compile command, the C++ standard library that comes with g++ checks some of its own rules while the program runs. It slows the program down, so use it while testing only:

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

With that flag, the program stops and prints a longer report. The key line is:

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

The word "irreflexive" is the formal name for rule 1. The message says that the comparator returned true when given the same item twice. Your code has the bug on one line, and the message tells you which rule it broke.

The second tool is the address sanitizer. A sanitizer is a build option that checks memory accesses while the program runs. Add -fsanitize=address,undefined to the compile command. For a longer list of 64 values, each between 0 and 3, the program stops with this report. The output below is trimmed to the first lines and the top of the stack:

=================================================================
==167459==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x71428a9e0140 at pc 0x5edf861fd341 bp 0x7ffc54ad84d0 sp 0x7ffc54ad84c0
READ of size 4 at 0x783418be003c thread T0
    #0 0x64647cbee54d in operator()<...> /usr/include/c++/15/bits/predefined_ops.h:158
    #1 0x64647cbee0f5 in __unguarded_partition<...> /usr/include/c++/15/bits/stl_algo.h:1839
0x783418be003c is located 4 bytes before 256-byte region [0x783418be0040,0x783418be0140)

Process ids, addresses and line numbers change from run to run and between compiler versions. The line heap-buffer-overflow means the program read memory outside the vector's data. The line located 4 bytes before 256-byte region says the read was just before the first integer, so a walker ran off the front of the list. The code that did the read is inside the standard library, in the step that splits the list around a pivot. The <= comparator never stopped that step at the front, so it kept reading.

Why the crash happens

The sort works by picking one item as a pivot, which is a value used as a reference point, and then moving items so that smaller ones are on one side and larger ones on the other. The step that does this walks in from both ends. It moves a walker in from each end while the item under it comes before the pivot. With <, an item equal to the pivot stops the walker, because it does not come before the pivot. With <=, an item equal to the pivot keeps the walker going, because it does come "before or equal". When many values are equal, a walker can run past the first or last item. The library's fast version of this step does not check the ends, because the comparator is supposed to make those checks unnecessary.

The fix is to use < (or > for the opposite order). Here is the corrected comparator on the same input:

std::sort(v.begin(), v.end(), [](int a, int b) { return a < b; });

Repeat the test with the 64-value list and the sanitizer reports nothing. Keep this habit: any comparator that you write with <= or >= is wrong for sorting, unless you have a very specific reason and you have read the rules for that reason. Use < or >.

Example 2: a subtraction that overflows

Many people write a comparator by subtracting: return a - b < 0;. It looks short, and for small numbers it works. For large numbers it breaks. An int in C++ holds values from about minus two billion to about plus two billion. If you subtract a large negative number from a large positive number, the result is larger than an int can hold. This is called signed integer overflow, and it is also undefined behaviour.

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v = {INT_MAX, -5, INT_MIN, 0, 7};
    std::sort(v.begin(), v.end(), [](int a, int b) { return a - b < 0; });
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

The output is wrong:

0 2147483647 -2147483648 -5 7 

2147483647 appears second, before -5 and 0. The sanitizer for undefined behaviour names the exact problem. Compile with -fsanitize=undefined and the program prints this line before the output:

sort_check.cpp:8:63: runtime error: signed integer overflow: -5 - 2147483647 cannot be represented in type 'int'

The fix is to compare the two values directly, with no subtraction:

std::sort(v.begin(), v.end(), [](int a, int b) { return a < b; });

The same program with this comparator prints -2147483648 -5 0 7 2147483647, which is the correct order. Comparing with < also reads more clearly. A subtraction only tells you the order when you know that the subtraction did not overflow, and that is a fact the comparator should not depend on.

Example 3: a rule that goes around in a circle

Rule 3 says that if a comes before b and b comes before c, then a comes before c. Some rules do not have this property. Think of rock, paper and scissors. Rock beats scissors, scissors beats paper, and paper beats rock. If you use "beats" as the comparator, then rock comes before scissors, scissors comes before paper, and paper comes before rock. Each pair is consistent with the rule on its own, but no single order can hold all three. Going around the circle always returns you to the start.

#include <algorithm>
#include <iostream>
#include <vector>
 
// Rock beats scissors, scissors beats paper, paper beats rock.
int beats(char a, char b) {
    return (a == 'R' && b == 'S') || (a == 'S' && b == 'P') || (a == 'P' && b == 'R');
}
 
int main() {
    std::vector<char> v = {'R', 'P', 'S', 'R', 'P', 'S', 'R', 'P'};
    std::sort(v.begin(), v.end(), [](char a, char b) { return beats(a, b); });
    for (char c : v) std::cout << c << ' ';
    std::cout << '\n';
}

The output is not sorted in any sense:

P R S P R S P R 

The debug library check does not stop this program. Rule 3 is broken, and the check does not report it, so the program runs to the end and prints a wrong answer without any message. This is the hardest kind of bug to find, because nothing reports it.

The fix is to give every symbol a number, and compare the numbers. A number comparison always follows the rules, because numbers have one order:

#include <algorithm>
#include <iostream>
#include <vector>
 
// Each symbol gets a fixed rank. Comparing ranks gives a plain sort order.
int rank(char c) {
    switch (c) {
        case 'R': return 0;
        case 'P': return 1;
        case 'S': return 2;
    }
    return -1;
}
 
int main() {
    std::vector<char> v = {'R', 'P', 'S', 'R', 'P', 'S', 'R', 'P'};
    std::sort(v.begin(), v.end(), [](char a, char b) { return rank(a) < rank(b); });
    for (char c : v) std::cout << c << ' ';
    std::cout << '\n';
}

This prints R R R P P P S S. The rule behind the new comparator is a plain order, so every symbol with the same rank is equal and the groups come out in order. If you need a "beats" rule for a game, do not use it as a sort order. Use it as a test that you call on pairs, and sort by something else.

Example 4: NaN values

C++ floating point numbers, such as double, have a special value called NaN, which stands for "not a number". A NaN appears when a calculation has no meaningful result, such as zero divided by zero. NaN breaks the rules quietly. Any comparison with NaN using < gives false, in both directions. That makes NaN "equal" to every number, and equal to every other NaN, which breaks rule 4 because equal must be consistent.

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<double> v = {2.0, NAN, 1.0, 3.0, NAN, 0.5};
    std::sort(v.begin(), v.end());
    for (double x : v) std::cout << x << ' ';
    std::cout << '\n';
}

The output places the NaN values in the middle of the list:

0.5 1 2 nan 3 nan 

The nan values are not at the end, and the debug library check does not report this either. The comparator used by std::sort on double is <, and it cannot order a NaN.

The fix is to remove the NaN values before you sort, if your data should not contain them. The function std::erase_if removes every item that matches a test:

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<double> v = {2.0, NAN, 1.0, 3.0, NAN, 0.5};
    std::erase_if(v, [](double x) { return std::isnan(x); });
    std::sort(v.begin(), v.end());
    for (double x : v) std::cout << x << ' ';
    std::cout << '\n';
}

This prints 0.5 1 2 3. If the NaN values are valid data that you need to keep, decide where they should go, and write a comparator that puts them there. The comparator then needs an explicit rule for NaN, for example "all NaN values come last". Do not rely on < to handle them.

Example 5: a two-key sort with a tie

Now a realistic case. Suppose you have a list of students with a name and a score, and you want the highest score first. A comparator with >= looks like the natural choice, but it is the same bug as Example 1.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
struct Student {
    std::string name;
    int score;
};
 
int main() {
    std::vector<Student> v = {{"Ana", 80}, {"Ben", 95}, {"Cy", 80}, {"Dee", 70}};
    std::sort(v.begin(), v.end(), [](const Student& a, const Student& b) { return a.score >= b.score; });
    for (const auto& s : v) std::cout << s.name << ' ' << s.score << '\n';
}

With -D_GLIBCXX_DEBUG, the program stops with the same message as in Example 1:

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

Without the debug flag, the program prints an order with no error. The fix is >, which means "higher score comes first":

std::sort(v.begin(), v.end(), [](const Student& a, const Student& b) { return a.score > b.score; });

This comparator has a second problem. Ana and Cy both have a score of 80, so the comparator says they are equal. The sort is allowed to put them in either order. If you want a clear rule for ties, add a second key. The common way is to compare the name when the scores are equal. The function std::tie builds a group of references, and the group comparison checks the first item, then the second:

#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>
 
struct Student {
    std::string name;
    int score;
};
 
int main() {
    std::vector<Student> v = {{"Ana", 80}, {"Ben", 95}, {"Cy", 80}, {"Dee", 70}};
    // Highest score first, then name A to Z for ties.
    std::sort(v.begin(), v.end(), [](const Student& a, const Student& b) {
        return std::tie(b.score, a.name) < std::tie(a.score, b.name);
    });
    for (const auto& s : v) std::cout << s.name << ' ' << s.score << '\n';
}

This prints Ben 95, Ana 80, Cy 80, Dee 70. Notice that b.score comes before a.score in the first group. That reverses the order for the score, so higher scores come first, while the name keeps the normal A to Z order.

Choosing a tie rule

A tie rule is a choice you make on purpose. Pick the second key that matches the task. If two students have the same score, you might sort them by name, by age or by student number. Whatever you choose, the rule must still be a single consistent order, and the tie key must be something that is never equal for two different students. If two students can share a name, add a third key, such as an id.

Common mistakes

Using <= or >= in a sort

This is the most common version of the bug. The symptom can be a crash deep inside the standard library, or a message that names rule 1. The message from -D_GLIBCXX_DEBUG is the fastest way to find it. The fix is to change the operator to < or >. A comparator that is only used with std::set or std::map has the same rule, so check those too.

Returning a number instead of a true or false answer

A comparator must return a value that means "comes before". Some people write return a - b;. C++ accepts this, because a number can be turned into a bool. Any number that is not zero becomes true, so the comparator answers true for both a before b and b before a whenever the two values differ. Here is the program:

#include <algorithm>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v = {3, 1, 2, 5, 4};
    std::sort(v.begin(), v.end(), [](int a, int b) { return a - b; });
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

The output is not sorted:

4 5 2 1 3 

The debug library check does not stop this program. The fix is to return a comparison, such as a < b, and never a number.

Subtracting unsigned values

An unsigned value cannot be negative. When you subtract a larger unsigned value from a smaller one, the result wraps around to a large positive number. So a - b < 0 is never true for unsigned values, and the comparator says nothing is ever before anything else. Compile the program below with -Wextra and g++ prints a warning:

#include <algorithm>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<unsigned> v = {3, 1, 2, 5, 4};
    std::sort(v.begin(), v.end(), [](unsigned a, unsigned b) { return a - b < 0; });
    for (unsigned x : v) std::cout << x << ' ';
    std::cout << '\n';
}

The warning from g++ is:

warning: comparison of unsigned expression in '< 0' is always false [-Wtype-limits]

The output is the original list, unchanged: 3 1 2 5 4. The fix is a < b.

Taking a reference to a temporary value

std::tie takes references, so it needs real variables, not values that the code creates on the spot. A call such as a.size() creates a number that has no name. Here is a comparator that tries to tie that number:

return std::tie(a.size(), a) < std::tie(b.size(), b);

g++ stops with a compile error. The key part of the message is:

error: cannot bind non-const lvalue reference of type 'long unsigned int&' to an rvalue of type 'std::__cxx11::basic_string<char>::size_type'

The message is long because the standard library adds notes. The part you need is the phrase "rvalue of type". Use std::pair instead, which copies its values:

return std::pair(a.size(), a) < std::pair(b.size(), b);

This version compiles, and sorts the words pear, fig, apple, kiwi, date and banana into fig date kiwi pear apple banana. That order is by length first, then A to Z.

Assuming equal items keep their order

When two items are equal, std::sort may put them in any order. It does not promise to keep the original order. If you need equal items to stay in the order they came in, use std::stable_sort instead. It has the same comparator rules, and it keeps equal items in their original order.

Comparators that change while sorting

A comparator should only read its two inputs and return an answer. If it changes a counter, reads a global variable that another part of the code changes, or uses a random number, the answers can contradict each other. The sort relies on the answers being stable. Keep comparators as plain functions of their two inputs.

How to check a comparator

Use this short routine before you trust a new comparator.

1. Write the rules in one line: "comes before means smaller key, and ties break by name". Check that the comparator matches that line.
2. Check that comp(x, x) is false for a few values.
3. Check that a comparator that uses subtraction cannot overflow, or rewrite it with <.
4. Compile with -std=c++20 -Wall -Wextra. Read every warning.
5. Test with -D_GLIBCXX_DEBUG on a list with many repeated values. Test with -fsanitize=address,undefined too.
6. If the output must be sorted, call std::ranges::is_sorted on the result with the same comparator, and check that it returns true.

Step 6 is a useful test in real code. It does not catch every bad comparator, but it catches wrong output as soon as it happens.

Practice

Exercise 1. A student writes a comparator to sort a list of people from oldest to youngest. The code is [](const Person& a, const Person& b) { return a.age >= b.age; }. Describe the bug and write the fixed comparator.

Show the answer

The comparator uses >=, which says a person comes before themselves. That breaks rule 1, and the debug library check reports it. Change the operator to >: [](const Person& a, const Person& b) { return a.age > b.age; }. This puts the oldest person first.

Exercise 2. Write a comparator that sorts words by length, shortest first, and then from A to Z for words of the same length. Use the words pear, fig, apple, kiwi, date and banana. Predict the output, then run it.

Show the answer

Use std::pair so that the comparator compares the length, then the word: return std::pair(a.size(), a) < std::pair(b.size(), b);. The output is fig date kiwi pear apple banana. The words of length 4 are date, kiwi and pear, and they are in A to Z order because the second key is the word itself.

Exercise 3. The comparator [](unsigned a, unsigned b) { return a - b < 0; } leaves the list 3 1 2 5 4 unchanged. Explain why in one or two sentences.

Show the answer

For unsigned values, a - b never produces a negative result. When a is smaller than b, the subtraction wraps around to a very large positive number. So a - b < 0 is always false, and every pair of values counts as equal. For this 5-item list, the sort never moves anything, so the list stays the same. The compiler warns about this with -Wtype-limits.

Exercise 4. A list of measurements is {2.0, NAN, 1.0, 3.0, NAN, 0.5}. Remove the NaN values, then sort the rest with <. Write the code and state the output.

Show the answer

Use std::erase_if(v, [](double x) { return std::isnan(x); }); before std::sort(v.begin(), v.end());. The output is 0.5 1 2 3. The sort works on the values that remain, and the NaN values are gone.

Exercise 5. Rock, paper and scissors cannot be sorted with "beats" as the comparator. Give each symbol a number so that the comparator can use <. Write the rank function and state the output of sorting R P S R P S R P with it.

Show the answer

Use R as 0, P as 1 and S as 2, with a switch that returns those numbers. Sort with rank(a) < rank(b). The output is R R R P P P S S. The order groups the symbols by rank. It does not say anything about which symbol wins a game, because that rule is not an order.

Summary

• A comparator must describe one consistent order: nothing is before itself, the order is transitive, and equal items are consistently equal.
• <= and >= in a sort break rule 1. The result can be a read past the end of the vector, which is undefined behaviour. Use < or >.
• Subtraction can overflow, and a number returned as a bool is always true when it is not zero. Return a comparison, not a difference.
• A "beats" relation with cycles, and NaN values, have no consistent order. Use ranks, or remove the NaN values first.
• std::tie and std::pair build a two-key comparison. Use them for ties, and do not pass them values that have no name.
• Test new comparators with -D_GLIBCXX_DEBUG and -fsanitize=address,undefined, and check the result with std::ranges::is_sorted.