# Strict weak ordering and comparators

> Every sorting algorithm and ordered container assumes its comparator is a strict weak ordering, and a comparator that is not one gives undefined behavior rather than a merely odd order. Knowing the four laws, and the equivalence they define, explains which comparators are safe and why ordered lookup ignores operator==.

- **Source:** C++ Atlas (https://cppatlas.com/topics/strict-weak-ordering-and-comparators)
- **Track:** Iterators, algorithms and ranges
- **Estimated reading time:** 12 minutes
- **ISO C++ clauses:** [alg.sorting.general] (https://eel.is/c++draft/alg.sorting.general), [concept.strictweakorder] (https://eel.is/c++draft/concept.strictweakorder), [associative.reqmts.general] (https://eel.is/c++draft/associative.reqmts.general), [sort] (https://eel.is/c++draft/sort), [stable.sort] (https://eel.is/c++draft/stable.sort), [range.cmp] (https://eel.is/c++draft/range.cmp), [cmp.alg] (https://eel.is/c++draft/cmp.alg), [res.on.functions] (https://eel.is/c++draft/res.on.functions)
- **cppreference links:** [C++ named requirements: Compare](https://en.cppreference.com/w/cpp/named_req/Compare), [std::strict_weak_order](https://en.cppreference.com/w/cpp/concepts/strict_weak_order), [std::sort](https://en.cppreference.com/w/cpp/algorithm/sort), [std::stable_sort](https://en.cppreference.com/w/cpp/algorithm/stable_sort), [std::ranges::less](https://en.cppreference.com/w/cpp/utility/functional/ranges/less), [std::strong_order](https://en.cppreference.com/w/cpp/utility/compare/strong_order)
- **Prerequisites:** algorithms, three-way-comparison, associative-and-unordered-containers

## The one idea

A comparator answers one question: must `a` come before `b`? Algorithms like `std::sort` and containers like `std::set` never ask whether two elements are equal. They infer it. If neither has to come before the other, the two are treated as interchangeable, or **equivalent**. Everything the library does with a comparator, from partitioning around a pivot to rejecting a duplicate key, relies on that inference being consistent.

A **strict weak ordering** is precisely the condition under which the inference is consistent. It sorts the values into groups of equivalent elements and lines the groups up in a total order. If your comparator does not have that shape, the library is not obliged to produce a wrong-but-valid order. It is allowed to do anything, and real implementations read past the end of the array.

> **Mental model.** A strict weak ordering is a ranking with ties. Equivalent elements share a rank, every rank is strictly before or after every other, and `comp(a, b)` means "a's rank is lower".

## The four laws

For a comparator `comp`, define `equiv(a, b)` as `!comp(a, b) && !comp(b, a)`. [alg.sorting.general] requires, and the `strict_weak_order` concept documents, that `comp` is:

1. **Irreflexive.** `comp(a, a)` is false. Nothing comes before itself.
2. **Asymmetric.** If `comp(a, b)` then not `comp(b, a)`. This follows from the other laws but is the one most often broken directly.
3. **Transitive.** If `comp(a, b)` and `comp(b, c)` then `comp(a, c)`.
4. **Transitive in incomparability.** If `equiv(a, b)` and `equiv(b, c)` then `equiv(a, c)`.

The fourth law is what makes it *weak* rather than *partial*. Under the first three alone, incomparable elements can sit in no consistent position: `a` might tie with `b`, `b` with `c`, yet `a` come strictly before `c`. Law four rules that out, so equivalence is a genuine equivalence relation and the classes it forms are totally ordered.

> **Standardese.** [alg.sorting.general] says that, for every algorithm other than the binary searches, `comp` shall induce a strict weak ordering on the values, and defines equivalence as `!comp(a, b) && !comp(b, a)`. The binary searches only need the range to be partitioned with respect to the value sought. Breaking a library requirement placed on a user-supplied function object is undefined behavior by [res.on.functions].

## Comparators that break the laws

The usual suspects each break a specific law.

**Using `<=` or `>=`** breaks irreflexivity. `comp(x, x)` is true, so equal elements each claim to come first. In libstdc++, `std::sort` uses an unguarded insertion step that trusts `comp(x, x)` to be false as a stopping condition. With enough equal elements it walks off the front of the buffer. The debug mode, `-D_GLIBCXX_DEBUG`, checks irreflexivity and aborts with a diagnostic instead.

```cpp
#include <algorithm>
#include <vector>

void bad(std::vector<int>& v) {
  std::sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });
  // undefined behavior: comp(x, x) is true
}
```

**NaN** breaks transitivity of incomparability. With `<` on doubles, NaN is incomparable to every value, so `1.0` ties with NaN and NaN ties with `2.0`, yet `1.0 < 2.0`. One NaN in a `std::vector<double>` makes `std::sort` with the default comparator undefined behavior, and `std::set<double>` lookups unreliable.

**An inconsistent multi-key comparison** breaks asymmetry. The classic mistake reads like a reasonable rule.

```cpp
struct Pt { int x, y; };

bool wrong(const Pt& a, const Pt& b) {
  return a.x < b.x || a.y < b.y;
}
// wrong({1, 2}, {2, 1}) and wrong({2, 1}, {1, 2}) are both true
```

**State that changes between calls**, such as a comparator that consults a random number generator or a mutable cache keyed on call order, breaks all four at once. A comparator may count its calls, but its answer must depend only on the two arguments.

> **Pitfall.** Undefined behavior from a bad comparator rarely shows up in small tests. The out-of-bounds read in introsort needs runs of equal elements longer than the insertion threshold, typically more than sixteen, so a comparator using `<=` can pass every unit test and crash on production data.

## Writing multi-key comparators correctly

Compare the first key; only when it ties, move on to the next. `std::tie` builds tuples of references and their `<` does exactly that lexicographic walk.

```cpp
#include <string>
#include <tuple>

struct Person { std::string name; int age; };

bool by_age_then_name(const Person& a, const Person& b) {
  return std::tie(a.age, a.name) < std::tie(b.age, b.name);
}
```

`std::tie` needs lvalues. For a derived key such as `a.name.size()`, use `std::forward_as_tuple` or `std::make_tuple`, or spell out the comparison. Since C++20, three-way comparison makes the manual version compact, and `auto operator<=>(const Person&) const = default;` gives memberwise lexicographic ordering in declaration order without a comparator at all. The three-way-comparison topic covers the defaulting rules.

```cpp
#include <compare>
#include <string>

struct Person { std::string name; int age; };

bool by_age_desc_then_name(const Person& a, const Person& b) {
  if (auto c = b.age <=> a.age; c != 0) return c < 0;  // age descending
  return a.name < b.name;
}
```

For floating-point keys, choose what NaN means. `std::strong_order` on IEEE types is a total order that places NaNs consistently and also orders `-0.0` before `+0.0`, so `[](double a, double b) { return std::strong_order(a, b) < 0; }` is a valid comparator for any input. `std::partial_order(a, b) < 0` is not: it is `<` again, NaN problem included.

## Equivalence versus equality

Because ordered containers use equivalence, `operator==` plays no part in their lookup. A case-insensitive `std::set<std::string, CaseLess>` treats `"Apple"` and `"APPLE"` as the same key: inserting the second fails, and `find`, `count` and `contains` locate the first. Generic algorithms that search for a value, such as `std::ranges::find`, use `==` instead, so they disagree with the container.

```cpp
#include <algorithm>
#include <cctype>
#include <set>
#include <string>

struct CaseLess {
  bool operator()(const std::string& a, const std::string& b) const {
    auto lower = [](unsigned char c) { return std::tolower(c); };
    return std::ranges::lexicographical_compare(a, b, {}, lower, lower);
  }
};

void demo() {
  std::set<std::string, CaseLess> s{"Apple"};
  s.insert("APPLE");                        // not inserted: equivalent key
  bool a = s.contains("apple");             // true
  bool b = std::ranges::find(s, std::string("APPLE")) != s.end();  // false
  (void)a; (void)b;
}
```

A comparator that is not a strict weak ordering does more damage in a container than in a sort, because the damage persists. `std::set<int, std::less_equal<int>>` never sees two equal keys as equivalent, so it stores duplicates and then cannot find them. That is undefined behavior too, since [associative.reqmts.general] requires the container's comparator to induce a strict weak ordering on keys. Transparent comparators like `std::less<>` and heterogeneous lookup are covered in the node-handles-and-heterogeneous-lookup topic.

## sort, stable_sort, and what equivalent elements do

`std::sort` puts equivalent elements next to each other in an unspecified relative order. Since C++11 it performs O(N log N) comparisons in the worst case; before that only the average case was specified. `std::stable_sort` keeps equivalent elements in their original relative order. It is O(N log N) when it can allocate a buffer and O(N log² N) when it cannot. `std::list::sort` and `std::forward_list::sort` are stable too.

Stability is what lets you sort by several keys in passes, least significant key first, and it is the only reason to pay the extra cost. If the full sort key is a strict total order, the two algorithms give identical results.

Other algorithms also make promises about equivalent elements, and those promises are only as good as your comparator. `std::max(a, b)` and `std::min(a, b)` both return their first argument when the two are equivalent, so `std::min` and `std::max` of the same equivalent pair return the same object. `std::merge` takes from the first range before the second among equivalent elements, and `std::equal_range` returns exactly the run of elements equivalent to the value. Each of these is a statement about equivalence classes, and none means anything if the classes are not well formed.

## ranges::less, the concept, and projections

`std::ranges::less` is the default comparator for the constrained algorithms. Unlike `std::less<>`, it is constrained with `totally_ordered_with`, so comparing types with no `<` fails at the call rather than deep inside an algorithm. Both produce a strict total order over pointers, which built-in `<` does not guarantee for unrelated objects.

The `strict_weak_order<R, T, U>` concept, used by `std::sortable` through `indirect_strict_weak_order`, checks only syntax: `R` must be a predicate callable with every combination of `T` and `U`. The laws themselves are semantic requirements that no compiler checks. `std::strict_weak_order<std::ranges::less_equal, int, int>` is satisfied.

The constrained algorithms also take a **projection**, applied to each element before the comparator sees it. Projections replace most hand-written key comparators, and the comparator argument can be left as `{}` to keep `ranges::less`.

```cpp
#include <algorithm>
#include <functional>
#include <string>
#include <vector>

struct Person { std::string name; int age; };

void demo(std::vector<Person>& people) {
  std::ranges::sort(people, std::ranges::greater{}, &Person::name);
  std::ranges::sort(people, {}, &Person::age);                   // by age
  auto it = std::ranges::lower_bound(people, 30, {}, &Person::age);
  // it: the first person aged 30 or more
  (void)it;
}
```

In a binary search, the projection is applied to the elements only, never to the value searched for, which is why `lower_bound(people, 30, {}, &Person::age)` compares ages with `30`. The range must already be ordered by that same projected key. Had the two sorts run in the opposite order, the people would be ordered by name, and the search would violate its precondition.

## What to remember

- Library comparators must be strict weak orderings: irreflexive, asymmetric, transitive, and transitive in incomparability.
- Equivalence is `!comp(a, b) && !comp(b, a)`; ordered containers and sorts use it, never `==`.
- Violating the laws is undefined behavior, not an odd order; `<=` can make `std::sort` read out of bounds.
- NaN with `<` breaks transitivity of incomparability; use `std::strong_order` or remove NaNs first.
- Write multi-key comparisons with `std::tie`, `<=>`, or a defaulted `operator<=>`, never `a.x < b.x || a.y < b.y`.
- `std::sort` leaves equivalent elements in unspecified order; `std::stable_sort` and `list::sort` preserve it.
- The `strict_weak_order` concept is syntactic; `ranges::less_equal` satisfies it.
- Projections apply to elements, not to the searched value, and the range must be ordered by the projected key.

## Concept Map Outline

- **Strict weak ordering:** The shape every library comparator must have: a ranking with ties.
  - **The four laws:** Required by [alg.sorting.general] for sorting and ordered containers.
    - **Irreflexive:** comp(a, a) is false: nothing comes before itself.
    - **Asymmetric:** If comp(a, b) then not comp(b, a).
    - **Transitive:** comp(a, b) and comp(b, c) imply comp(a, c).
    - **Incomparability transitive:** Ties chain: equiv(a, b) and equiv(b, c) imply equiv(a, c); this makes it weak, not partial.
  - **Equivalence:** equiv(a, b) is !comp(a, b) && !comp(b, a); operator== is never consulted.
    - **Set lookup:** find, count and contains locate equivalent keys; a case-insensitive set rejects "APPLE" after "Apple".
    - **ranges::find differs:** Generic searches use ==, so they can disagree with the container's own lookup.
    - **min, max, merge:** On equivalent arguments min and max return the first; merge takes from the first range first.
  - **Broken comparators:** Violating the laws is undefined behavior, not an odd but valid order.
    - **<= or >=:** Breaks irreflexivity; libstdc++ sort can read out of bounds on long runs of equal values.
    - **NaN with <:** NaN ties with everything, so incomparability is not transitive.
    - **OR of two keys:** Breaks asymmetry: (1,2) and (2,1) each come before the other.
    - **Debug checking:** -D_GLIBCXX_DEBUG checks irreflexivity in std::sort; release builds check nothing.
  - **Writing them right:** Compare the next key only when the previous keys tie.
    - **std::tie:** tie(a.x, a.y) < tie(b.x, b.y) compares lexicographically; needs lvalues.
    - **<=> chains:** if (auto c = a.k <=> b.k; c != 0) return c < 0; then the next key.
    - **strong_order for doubles:** std::strong_order(a, b) < 0 is a total order that also orders NaN and signed zeros.
  - **sort vs stable_sort:** They differ only in what happens to equivalent elements.
    - **sort:** O(N log N) comparisons in the worst case since C++11; equivalent order unspecified.
    - **stable_sort:** Keeps equivalent elements in input order; O(N log^2 N) if no buffer is available.
  - **Ranges tools:** Constrained algorithms add concepts and projections.
    - **ranges::less:** Default comparator, constrained by totally_ordered_with; total order over pointers.
    - **strict_weak_order concept:** Purely syntactic: ranges::less_equal satisfies it.
    - **Projections:** Applied to elements, not to the searched value; ranges::sort(v, {}, &P::age).

## Standardese Quiz Questions

### Question 1 [warmup] ([associative.reqmts.general], [alg.sorting.general])

What does this program print?

```cpp
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <set>
#include <string>

struct CaseLess {
  bool operator()(const std::string& a, const std::string& b) const {
    auto lower = [](unsigned char c) { return std::tolower(c); };
    return std::ranges::lexicographical_compare(a, b, {}, lower, lower);
  }
};

int main() {
  std::set<std::string, CaseLess> s{"Apple"};
  auto [it, inserted] = s.insert("APPLE");
  std::printf("%zu %d %s\n", s.size(), inserted, it->c_str());
}
```

A. `2 1 APPLE`
B. `1 0 Apple`
C. `1 1 APPLE`
D. `1 0` followed by either spelling; which one is kept is unspecified

**Answer (B):** `1 0 Apple`

**Why:** `std::set` decides whether a key is already present by equivalence under its comparator, `!comp(a, b) && !comp(b, a)`, and the two strings are equivalent when compared case-insensitively. The insertion is rejected, `inserted` is false, and the returned iterator points at the existing element, which keeps its original spelling. `2 1 APPLE` is what you would expect if the set used `operator==`, which it never does. Which element survives is not unspecified: the existing element is never replaced by a rejected insertion.

### Question 2 [warmup] ([alg.sorting.general], [concept.strictweakorder])

Which strict weak ordering law does this comparator break?

```cpp
struct Pt { int x, y; };

bool comp(const Pt& a, const Pt& b) {
  return a.x < b.x || a.y < b.y;
}
```

A. Irreflexivity: `comp(p, p)` can be true
B. None; it is a valid lexicographic comparison
C. Only transitivity of incomparability
D. Asymmetry: `comp({1, 2}, {2, 1})` and `comp({2, 1}, {1, 2})` are both true

**Answer (D):** Asymmetry: `comp({1, 2}, {2, 1})` and `comp({2, 1}, {1, 2})` are both true

**Why:** With `a = {1, 2}` and `b = {2, 1}`, the first call is true because `1 < 2` on `x`, and the second is true because `1 < 2` on `y`, so each point claims to come before the other. Irreflexivity holds, since neither `p.x < p.x` nor `p.y < p.y` can be true. A real lexicographic comparison only looks at `y` when the `x` values tie, which is what `std::tie(a.x, a.y) < std::tie(b.x, b.y)` does.

### Question 3 [warmup] ([stable.sort], [alg.sorting.general])

What does this program print?

```cpp
#include <algorithm>
#include <cstdio>
#include <string>
#include <vector>

struct P { std::string name; int age; };

int main() {
  std::vector<P> ps{{"bo", 30}, {"al", 25}, {"cy", 30}, {"di", 25}};
  std::ranges::stable_sort(ps, {}, &P::age);
  for (auto& p : ps) std::printf("%s ", p.name.c_str());
}
```

A. `al di bo cy `
B. `al bo cy di `
C. `di al cy bo `
D. Any order with the 25s before the 30s

**Answer (A):** `al di bo cy `

**Why:** The projection makes the algorithm compare ages only, so `al` and `di` are equivalent, as are `bo` and `cy`. `stable_sort` keeps equivalent elements in their original relative order: `al` came before `di` and `bo` before `cy`. The last option describes `std::ranges::sort`, which makes no promise about the order within a group of equivalent elements.

### Question 4 [tricky] ([associative.reqmts.general], [alg.find])

What does this program print?

```cpp
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <set>
#include <string>

struct CaseLess {
  bool operator()(const std::string& a, const std::string& b) const {
    auto lower = [](unsigned char c) { return std::tolower(c); };
    return std::ranges::lexicographical_compare(a, b, {}, lower, lower);
  }
};

int main() {
  std::set<std::string, CaseLess> s{"Apple"};
  std::string key = "APPLE";
  bool a = s.contains(key);
  bool b = std::ranges::find(s, key) != s.end();
  std::printf("%d %d\n", a, b);
}
```

A. `1 1`
B. `0 0`
C. `1 0`
D. `0 1`

**Answer (C):** `1 0`

**Why:** `contains` searches the tree with the container's comparator, so it finds the element equivalent to `"APPLE"`. `std::ranges::find` knows nothing about the set's ordering and compares each element with `==`, and `"Apple" == "APPLE"` is false. The two answers disagree because one uses equivalence and the other equality.

### Question 5 [tricky] ([cmp.alg], [alg.sorting.general])

`v` is a `std::vector<double>` that may contain NaN. Which comparator makes `std::sort(v.begin(), v.end(), comp)` well-defined for every possible content of `v`?

A. `[](double a, double b) { return a < b; }`
B. `[](double a, double b) { return !(a >= b); }`
C. `[](double a, double b) { return std::partial_order(a, b) < 0; }`
D. `[](double a, double b) { return std::strong_order(a, b) < 0; }`

**Answer (D):** `[](double a, double b) { return std::strong_order(a, b) < 0; }`

**Why:** `std::strong_order` on IEEE floating-point types implements a total order over all values, including NaNs and signed zeros, so it is a strict weak ordering on any input. `a < b` and `std::partial_order(a, b) < 0` are the same relation, under which NaN is incomparable with everything, which breaks transitivity of incomparability. `!(a >= b)` is true in both directions when either operand is NaN, which breaks asymmetry, and for NaN against itself it breaks irreflexivity too.

### Question 6 [tricky] ([concept.strictweakorder], [concepts.equality])

What happens when this translation unit is compiled?

```cpp
#include <concepts>
#include <functional>

static_assert(std::strict_weak_order<std::ranges::less, int, int>);        // 1
static_assert(std::strict_weak_order<std::ranges::less_equal, int, int>);  // 2
```

A. Both assertions pass
B. Assertion 2 fails because `<=` is reflexive
C. Assertion 2 fails because `less_equal` is not a `relation`
D. It is ill-formed, no diagnostic required, and the compiler rejects it

**Answer (A):** Both assertions pass

**Why:** `strict_weak_order<R, T, U>` is defined as `relation<R, T, U>`: the irreflexivity and transitivity laws are semantic requirements that the compiler cannot check. `ranges::less_equal` is a predicate callable with two `int`s, so it satisfies the concept and the assertion passes. Passing it to `std::ranges::sort` would compile too, while still breaking the requirement the concept documents.

### Question 7 [standardese] ([associative.reqmts.general], [alg.sorting.general])

Given a set `s` with comparator `comp`, which element does `s.find(k)` locate according to the standard?

A. An element `e` with `e == k`
B. An element `e` with `!comp(e, k) && !comp(k, e)`
C. An element `e` with `!comp(k, e)`
D. The first element `e` with `!comp(e, k)`

**Answer (B):** An element `e` with `!comp(e, k) && !comp(k, e)`

**Why:** Associative containers look up keys by equivalence, which [alg.sorting.general] defines as `!comp(a, b) && !comp(b, a)`; `operator==` is never used, so a set with a case-insensitive comparator finds keys that are not equal. `!comp(k, e)` alone accepts any element that is not greater than `k`, and the first `e` with `!comp(e, k)` is what `lower_bound` returns, which may be greater than `k`. Only the two-sided test identifies an equivalent key.

### Question 8 [standardese] ([associative.reqmts.general], [res.on.functions])

What does the standard say about this program?

```cpp
#include <functional>
#include <set>

int main() {
  std::set<int, std::less_equal<int>> s;
  s.insert(1);
  s.insert(1);
  return static_cast<int>(s.size());
}
```

A. It is ill-formed: `std::less_equal` does not meet the requirements of `Compare`, so the declaration is rejected
B. It is well-defined and returns 2, because the keys are never equivalent
C. It is well-defined and returns 1
D. It has undefined behavior

**Answer (D):** It has undefined behavior

**Why:** [associative.reqmts.general] requires the comparator of an associative container to induce a strict weak ordering on the keys, and `<=` is not irreflexive. Breaking a requirement on a user-supplied template argument is undefined behavior by [res.on.functions], so no outcome is guaranteed. Mainstream implementations will happily store two 1s, which makes the second option tempting, but that is an observation about implementations, not a guarantee. Nothing in the type system checks the semantics, so the program does compile.
