Skip to content
Tutorials Center
My learning

Topics

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.

C++
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

C++ Multi-key comparators: manual, tuple and spaceship

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.

C++ Comparators for containers, and a rule violation

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

C++
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 <= b returns true for 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;. Writing a.x < b.x || a.y < b.y is 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 the a and b sides for that key (as the example does with the salary).
  • Floating point and NaN. NaN compares false with everything, so x < y is not a strict weak ordering on a range containing NaN (all NaNs are "equivalent" to everything). Remove NaNs first or use std::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> and std::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. Use std::less<> (transparent) to allow lookup by string_view or other types without constructing a key.
  • Priority queues are reversed. std::priority_queue pops the largest element under comp; to get the smallest use std::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_sort or a tie-breaker.
  • Strict weak order for lower_bound. The range must already be sorted with the same comparator you pass to lower_bound or binary_search.