C++ Reference ยท Algorithms
Writing C++ comparators: strict weak ordering
How to write correct C++ comparison functions for sort, set and map: strict weak ordering rules, multi-key comparisons with tuples, the spaceship operator and typical bugs.
Sorting algorithms (std::sort, std::stable_sort, std::nth_element), ordered containers (std::set, std::map, std::priority_queue) and searching functions (std::lower_bound) all need to know the order of your elements. You provide it as a comparator: a callable comp(a, b) that returns true when a must come before b. The default is std::less<>, which uses operator<.
The rules for a valid comparator are called a strict weak ordering. Break them and the result is not just a wrong order: algorithms such as std::sort can read past the end of the array, crash, or loop forever, because they rely on the rules for their own correctness. Writing the comparator carefully is the whole job.
auto byLengthThenAlpha = [](const std::string& a, const std::string& b) { if (a.size() != b.size()) return a.size() < b.size(); return a < b; }; std::sort(words.begin(), words.end(), byLengthThenAlpha);
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
bool comp(const T& a, const T& b); // returns true if a goes before b // Function object / lambda auto comp = [](const T& a, const T& b) { return a.key < b.key; }; // Standard comparators in <functional> std::less<> std::greater<> std::less_equal<> std::greater_equal<> // C++20 constrained versions in <functional> std::ranges::less std::ranges::greater // C++20 three-way comparison auto operator<=>(const T&) const = default;
A comparator must satisfy, for all elements a, b, c (writing comp for the function):
| Rule | Meaning |
|---|---|
| Irreflexive | comp(a, a) is false. |
| Asymmetric | If comp(a, b) is true, then comp(b, a) is false. |
| Transitive | If comp(a, b) and comp(b, c), then comp(a, c). |
| Transitive equivalence | If a is equivalent to b and b to c (neither precedes the other), then a is equivalent to c. |
Returns: bool (or anything contextually convertible to bool).
Errors / undefined behavior: an invalid comparator is undefined behavior in std::sort, std::set and friends, not just a wrong result. Typical symptoms: crashes, infinite loops, or elements missing in a set. The comparator must also be deterministic and must not modify its arguments.
Usage notes
- Use
<, never<=.a <= breturnstruefor equal values, which violates irreflexivity. This is the most common comparator bug and often "works" for small inputs, then crashes on larger data. - Multi-key rule of thumb. Compare the first key; only when the keys are equal go on to the next:
if (a.x != b.x) return a.x < b.x; return a.y < b.y;. Writinga.x < b.x || a.y < b.yis wrong, as it is not transitive. std::tie/ tuples.std::tie(a.x, a.y) < std::tie(b.x, b.y)compares lexicographically, in one line. To reverse a key, swap theaandbsides for that key (as the example does with the salary).- Floating point and NaN. NaN compares false with everything, so
x < yis not a strict weak ordering on a range containing NaN (all NaNs are "equivalent" to everything). Remove NaNs first or usestd::strong_order/std::total_order(C++20,<compare>). - Pass by const reference and keep the comparator cheap: it is called O(n log n) times. Capturing a large object by value in a lambda copies it when the algorithm copies the comparator.
- Ordered containers.
std::set<T, Comp>andstd::map<K, V, Comp>treat two keys as the same when neither precedes the other. A comparator that ignores part of the key therefore silently drops elements. Usestd::less<>(transparent) to allow lookup bystring_viewor other types without constructing a key. - Priority queues are reversed.
std::priority_queuepops the largest element undercomp; to get the smallest usestd::greater<T>. - Spaceship operator (C++20).
auto operator<=>(const T&) const = default;generates<,<=,>,>=,==and!=comparing members in declaration order. It cannot express a mix of ascending and descending keys or case-insensitive text; write a comparator for that. - Stability. A comparator only defines the order; whether equal elements keep their relative order depends on the algorithm. Use
std::stable_sortor a tie-breaker. - Strict weak order for
lower_bound. The range must already be sorted with the same comparator you pass tolower_boundorbinary_search.