What must a custom comparator for std::map or std::set guarantee, and what goes wrong if it compares with <= instead of <?
answer
- irreflexive, not reflexive
- equivalence from two calls
- transitivity of both relations
- undefined behaviour, not a compile error
basics
~20 sIt must induce a strict weak ordering: comp(a, a) is false, comp is transitive, and equivalence, neither comp(a, b) nor comp(b, a), is transitive too. A <= comparator breaks irreflexivity, so using it is undefined behaviour and lookups silently fail.
solid answer
~40 s`std::map` and `std::set` never use `operator==` to find or deduplicate keys. They decide that two keys are the **same** when they are *equivalent*: `!comp(a, b) && !comp(b, a)`. For that to work the comparator must induce a **strict weak ordering**: irreflexive (`comp(a, a)` is false), transitive, and with transitive equivalence. A comparator written with `<=` returns `true` for `comp(a, a)`, so no key is ever equivalent to itself; the standard library places no requirements on the result, which means undefined behaviour. In practice duplicates can be stored and `find` can miss keys that are there. With Apple clang 21 and libc++ a `<=` set accepted `5` twice and then `find(5)` returned `end()`. The compiler cannot diagnose any of it. Build comparators from `<`, `std::tie` or `std::greater<>`.
code
cpp · 27 lines#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <tuple>
struct Order { int price; long seq; int qty; };
struct ByPriceThenSeq { // lexicographic: a strict weak ordering
bool operator()(const Order& a, const Order& b) const {
return std::tie(a.price, a.seq) < std::tie(b.price, b.seq);
}
};
struct ByPrice { // also strict weak, but orders with equal prices are "equivalent"
bool operator()(const Order& a, const Order& b) const { return a.price < b.price; }
};
int main() {
std::map<int, int, std::greater<>> bids{{10098, 4}, {10100, 1}, {10099, 7}};
std::cout << "best bid " << bids.begin()->first << '\n';
std::set<Order, ByPriceThenSeq> fifo{{10100, 2, 5}, {10100, 1, 3}};
std::cout << "fifo size " << fifo.size() << ", first seq " << fifo.begin()->seq << '\n';
std::set<Order, ByPrice> lossy{{10100, 2, 5}, {10100, 1, 3}};
std::cout << "lossy size " << lossy.size() << '\n';
}go deeper
Know that std::map and std::set use a less-than comparator, std::less by default, and that std::greater<> reverses the order.
Define a strict weak ordering, state that equivalence means neither comp(a, b) nor comp(b, a), and explain why a <= comparator breaks irreflexivity.
Diagnose silent failures from comparators: partial-field comparators dropping objects, NaN keys, non-transitive tiebreakers, and undefined behaviour that no compiler reports.
Decide how a codebase prevents comparator bugs: prefer std::tie or defaulted operator<=>, review hand-written comparators, and test ordering properties on representative keys.
## What the container asks of Compare Every ordered associative container (`std::set`, `std::map`, `std::multiset`, `std::multimap`) is parameterized on a **comparison object** `Compare`, `std::less<Key>` by default. The standard requires that it *induces a strict weak ordering* on the keys. Written out for a comparator `comp`: - **Irreflexive**: `comp(a, a)` is `false` for every `a`. - **Transitive**: `comp(a, b) && comp(b, c)` implies `comp(a, c)`. - **Transitive equivalence**: define `equiv(a, b)` as `!comp(a, b) && !comp(b, a)`; then `equiv(a, b) && equiv(b, c)` implies `equiv(a, c)`. - **Stable**: for two keys in the same container, `comp(k1, k2)` must always return the same value, so a comparator that reads mutable global state, or keys mutated in place, breaks it. From these the standard shows that `equiv` is an equivalence relation and that `comp` totally orders the equivalence classes. That is all a balanced search tree needs: at every node it asks "left, right, or here?" with at most two calls. ## Equivalence is not equality The containers decide uniqueness and lookup purely through `comp`; **`operator==` plays no part in either.** Two keys are the same key when neither orders before the other. This has a consequence that bites in real code: a comparator that looks only at part of an object makes objects that differ in the other parts **equivalent**. In an order book, a `std::set<Order, ByPrice>` comparing only `price` holds at most one order per price: the second order at 10100 is "already present" and `insert` returns `{existing, false}`. If the intent is price-time priority, the comparator must include the tiebreaker: `std::tie(a.price, a.seq) < std::tie(b.price, b.seq)`. `std::tie` builds tuples of references whose `operator<` is lexicographic, which is a strict weak ordering whenever each member's `<` is one. ## Why <= breaks it A comparator written as `return a <= b;` fails irreflexivity: `comp(a, a)` is `true`. Equivalence then never holds, not even for a key and itself, so the tree's "here" branch is unreachable. The standard's rule for program-supplied components (operations on types used to instantiate a library template must meet the applicable requirements) says that otherwise **the behaviour is undefined**. Nothing is diagnosed at compile time, because the requirement is semantic. What actually happens depends on the implementation. A run with Apple clang 21 and libc++ inserted `5` twice and `7` once into a `std::set<int, LessEq>`: `size()` reported 3, while `find(5)` returned `end()` and `count(5)` returned 0. That is one observed outcome of undefined behaviour, not a promise; another library, or another version, can loop, crash or corrupt the tree. libc++ even carries a macro, `_LIBCPP_ENABLE_LEGACY_TREE_LOWER_UPPER_BOUND`, that its source calls a compatibility escape hatch "for comparators that are not strict weak orderings"; its default lookup code relies on the requirement. Other common ways to break the ordering: 1. **Floating-point keys containing NaN** with `std::less<double>`: NaN is unordered with everything, so it is "equivalent" to every key while those keys are not equivalent to each other. 2. **Broken tiebreakers** that fall through to a second field incorrectly, such as returning `a.x < b.x || a.y < b.y`: for `(1, 2)` and `(2, 1)` both `comp(a, b)` and `comp(b, a)` are true, so it is not even asymmetric. 3. **Mutating a key** through a `const_cast` or a `mutable` member after insertion, so the stored order no longer matches `comp`. ## Writing comparators that are correct - For a **descending** map, such as bids where the best price comes first, use `std::greater<>` or `std::greater<int>`; do not write `>=`. - For **multi-field** keys, use `std::tie`, or in C++20 default `operator<=>` on the key type and keep `std::less<>`. - Keep the comparator **pure**: no state that changes while keys are stored. - If equality and ordering must agree, check that `equiv(a, b)` matches `a == b` for your type; when they differ, remember that the container follows `equiv`. Because no compiler diagnoses a broken ordering, test it: a unit test that feeds a hand-written comparator a few representative keys (equal ones, NaN-like edge values, mixed tiebreakers) and asserts `!comp(a, a)`, asymmetry and transitivity catches most mistakes before they reach a container. The same strict weak ordering requirement governs `std::sort`, `std::lower_bound` and the other sorting algorithms, which are covered with the algorithms material; here the cost of breaking it is a corrupted container that keeps running.
- Why can a std::set<double> misbehave once a NaN is inserted, even with the default comparator?`std::less<double>` returns `false` for every comparison involving NaN, so NaN is equivalent to every key while those keys are not equivalent to each other. Equivalence stops being transitive, the strict weak ordering requirement is violated and the behaviour is undefined. Filter NaN out before insertion or use a comparator that orders it, for example one based on `std::strong_order` (C++20) for floating-point values.
- How do you make a std::map iterate from the highest key down without reversing every loop?Declare it with a descending comparator: `std::map<int, int, std::greater<>>`. `begin()` is then the largest key, which suits a bid side where the best price is the highest. Iterating `rbegin()` to `rend()` on an ascending map also works, but the comparator choice documents intent and keeps `lower_bound` semantics aligned with that order.
- std::set calls operator== to decide whether a key is a duplicate
- A <= comparator is fine because it still sorts the keys
- The compiler rejects a comparator that is not a strict weak ordering
- Comparing only the price field keeps all orders in a std::set
- Reverse ordering needs a comparator that returns a >= b