Proposed resolution:

This wording is relative to N5032.

1. Modify [associative.reqmts.general] as indicated:

   -2- Each associative container is parameterized on `Key` and an ordering relation `Compare` that induces a strict weak ordering ([alg.sorting]) on elements of `Key`the values of `Key` in the container at any point in time. In addition, `map` and `multimap` associate an arbitrary mapped type `T` with the `Key`. The object of type `Compare` is called the comparison object of a container.

   […]

   -7- In this subclause,

   1. (7.1) — `X` denotes an associative container class,

   2. […]

   3. (7.7) — `a_eq` denotes a value of type `X` when `X` supports equivalent keys,

   4. (7.8) — `a_tran` denotes a value of type `X` or `const X` when the qualified-id `X::key_compare::is_transparent` is valid and denotes a type ([temp.deduct]),

   5. (7.9) — `i` and `j` meet the Cpp17InputIterator requirements and refer to elements implicitly convertible to `value_type`,

   6. […]

   7. (7.17) — `t` denotes a value of type `X::value_type`, and

   8. (7.18) — `k` denotes a value of type `X::key_type`, and

   9. (7.19) — `c` denotes a value of type `X::key_compare` or `const X::key_compare`;

   10. […]

   11. (7.23) — `kx` is a value such that

       1. (7.23.1) — `a` is partitioned with respect to `c(x, kx)` and `!c(kx, x)`, with `c(x, kx)` implying `!c(kx, x)` and with `x` the key value of `e` and `e` in `a`, and

       2. (7.23.2) — `kx` is not convertible to either `iterator` or `const_iterator`; and

       3. (7.23.?) — if qualified-id `X::key_compare::is_transparent` is not valid or does not denote a type ([temp.deduct]), then `kl`, `ku`, `ke` and `kx` are of type `X::key_type`;

   12. […]

   […]

   […]

   a_uniq.emplace(args)
   

   -47- Result: pair<iterator, bool>

   -48- Preconditions: `value_type` is Cpp17EmplaceConstructible into `X` from `args`. If `t` is a `value_type` object constructed with std::forward<Args>(args)..., `Compare` induces a strict weak ordering on the set of values comprising the key of `t` and all the keys in `a_uniq`.

   -49- Effects: Inserts a `value_type` object `t` constructed with std::forward<Args>(args)... if and only if there is no element in the container with key equivalent to the key of `t`.

   -50- Returns: The `bool` component of the returned pair is `true` if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key of `t`.

   -51- Complexity: Logarithmic.

   a_eq.emplace(args)
   

   -52- Result: iterator

   -53- Preconditions: `value_type` is Cpp17EmplaceConstructible into `X` from `args`. If `t` is a `value_type` object constructed with std::forward<Args>(args)..., `Compare` induces a strict weak ordering on the set of values comprising the key of `t` and all the keys in `a_eq`.

   -54- Effects: Inserts a `value_type` object `t` constructed with std::forward<Args>(args)....If a range containing elements equivalent to `t` exists in `a_eq`, `t` is inserted at the end of that range.

   -55- Returns: An iterator pointing to the newly inserted element.

   -56- Complexity: Logarithmic.

   […]

   a_uniq.insert(t)
   

   -61- Result: pair<iterator, bool>

   -62- Preconditions: If `t` is a non-const rvalue, `value_type` is Cpp17MoveInsertable into `X`; otherwise, `value_type` is Cpp17CopyInsertable into `X`. `Compare` induces a strict weak ordering on the set of values comprising the key of `t` and all the keys in `a_uniq`.

   -63- Effects: Inserts `t` if and only if there is no element in the container with key equivalent to the key of `t`.

   -64- Returns: The `bool` component of the returned pair is `true` if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key of `t`.

   -65- Complexity: Logarithmic.

   a_eq.insert(t)
   

   -66- Result: iterator

   -67- Preconditions: If `t` is a non-const rvalue, `value_type` is Cpp17MoveInsertable into `X`; otherwise, `value_type` is Cpp17CopyInsertable into `X`. `Compare` induces a strict weak ordering on the set of values comprising the key of `t` and all the keys in `a_eq`.

   -68- Effects: Inserts `t` and returns the iterator pointing to the newly inserted element. If a range containing elements equivalent to `t` exists in `a_eq`, `t` is inserted at the end of that range.

   -69- Complexity: Logarithmic.

   a.insert(p, t)
   

   -70- Result: iterator

   -71- Preconditions: If `t` is a non-const rvalue, `value_type` is Cpp17MoveInsertable into `X`; otherwise, `value_type` is Cpp17CopyInsertable into `X`. `Compare` induces a strict weak ordering on the set of values comprising the key of `t` and all the keys in `a`.

   -72- Effects: Inserts `t` if and only if there is no element with key equivalent to the key of `t` in containers with unique keys; always inserts `t` in containers with equivalent keys. `t` is inserted as close as possible to the position just prior to `p`.

   -73- Returns: An iterator pointing to the element with key equivalent to the key of `t`.

   -74- Complexity: Logarithmic in general, but amortized constant if `t` is inserted right before `p`.

   a.insert(i, j)
   

   -75- Result: void

   -76- Preconditions: `value_type` is Cpp17EmplaceConstructible into `X` from `*i`. Neither `i` nor `j` are iterators into `a`. `Compare` induces a strict weak ordering on the set of values comprising all the keys in `[i, j)` and all the keys in `a`.

   -77- Effects: Inserts each element from the range `[i, j)` if and only if there is no element with key equivalent to the key of that element in containers with unique keys; always inserts that element in containers with equivalent keys.

   -78- Complexity: N log(a.size() + N), where N has the value `distance(i, j)`.

   a.insert_range(rg)
   

   -79- Result: void

   -80- Preconditions: `value_type` is Cpp17EmplaceConstructible into `X` from *ranges::begin(rg). `rg` and `a` do not overlap. `Compare` induces a strict weak ordering on the set of values comprising all the keys in `rg` and all the keys in `a`.

   -81- Effects: Inserts each element from `rg` if and only if there is no element with key equivalent to the key of that element in containers with unique keys; always inserts that element in containers with equivalent keys.

   -82- Complexity: N log(a.size() + N), where N has the value `ranges::distance(rg)`.

   […]

   a_uniq.insert(nh)
   

   -84- Result: insert_return_type

   -85- Preconditions: `nh` is empty or `a_uniq.get_allocator() == nh.get_allocator()` is `true`. If `nh` is not empty, `Compare` induces a strict weak ordering on the set of values comprising the key of `nh` and all the keys in `a_uniq`.

   -86- Effects: If `nh` is empty, has no effect. Otherwise, inserts the element owned by `nh` if and only if there is no element in the container with a key equivalent to `nh.key()`.

   -87- Returns: If `nh` is empty, inserted is `false`, `position` is `end()`, and `node` is empty. Otherwise if the insertion took place, `inserted` is `true`, `position` points to the inserted element, and `node` is empty; if the insertion failed, `inserted` is `false`, `node` has the previous value of `nh`, and `position` points to an element with a key equivalent to `nh.key()`.

   -88- Complexity: Logarithmic.

   a_eq.insert(nh)
   

   -89- Result: iterator

   -90- Preconditions: `nh` is empty or `a_eq.get_allocator() == nh.get_allocator()` is `true`. If `nh` is not empty, `Compare` induces a strict weak ordering on the set of values comprising the key of `nh` and all the keys in `a_eq`.

   -91- Effects: If `nh` is empty, has no effect and returns `a_eq.end()`. Otherwise, inserts the element owned by `nh` and returns an iterator pointing to the newly inserted element. If a range containing elements with keys equivalent to `nh.key()` exists in `a_eq`, the element is inserted at the end of that range.

   -92- Postconditions: `nh` is empty.

   -93- Complexity: Logarithmic.

   a.insert(p, nh)
   

   -94- Result: iterator

   -95- Preconditions: `nh` is empty or `a.get_allocator() == nh.get_allocator()` is `true`. If `nh` is not empty, `Compare` induces a strict weak ordering on the set of values comprising the key of `nh` and all the keys in `a`.

   -96- Effects: If `nh` is empty, has no effect and returns `a.end()`. Otherwise, inserts the element owned by `nh` if and only if there is no element with key equivalent to `nh.key()` in containers with unique keys; always inserts the element owned by `nh` in containers with equivalent keys. The element is inserted as close as possible to the position just prior to `p`.

   -97- Postconditions: `nh` is empty if insertion succeeds, unchanged if insertion fails.

   -98- Returns: An iterator pointing to the element with key equivalent to `nh.key()`.

   -99- Complexity: Logarithmic.

   […]

   a.extract(k)
   

   -100- Result: `node_type`

   -101- Effects: Removes the first element in the container with key equivalent to `k`.

   -102- Returns: A `node_type` owning the element if found, otherwise an empty `node_type`.

   -103- Complexity: log(`a.size()`)

   a_trana.extract(kx)
   

   -104- Result: `node_type`

   -105- Effects: Removes the first element in the container with key `r` such that !c(r, kx) && !c(kx, r) is `true`.

   -106- Returns: A `node_type` owning the element if found, otherwise an empty `node_type`.

   -107- Complexity: log(a_trana.size())

   […]

   a.merge(a2)
   

   -112- Result: `void`

   -113- Preconditions: `a.get_allocator() == a2.get_allocator()` is `true`. `Compare` induces a strict weak ordering on the set of values comprising all the keys in `a` and all the keys in `a2`.

   -114- Effects: Attempts to extract each element in `a2` and insert it into `a` using the comparison object of `a`. In containers with unique keys, if there is an element in a with key equivalent to the key of an element from `a2`, then that element is not extracted from `a2`.

   -115- Postconditions: Pointers and references to the transferred elements of `a2` refer to those same elements but as members of `a`. If `a.begin()` and `a2.begin()` have the same type, iterators referring to the transferred elements will continue to refer to their elements, but they now behave as iterators into `a`, not into `a2`.

   -116- Throws: Nothing unless the comparison object throws.

   -117- Complexity: N log(`a.size()` + N), where N has the value `a2.size()`.

   a.erase(k)
   

   -118- Result: `size_type`

   -119- Effects: Erases all elements in the container with key equivalent to `k`.

   -120- Returns: The number of erased elements.

   -121- Complexity: log(`a.size()`) + `a.count(k)`

   a_trana.erase(kx)
   

   -122- Result: `size_type`

   -123- Effects: Erases all elements in the container with key `r` such that !c(r, kx) && !c(kx, r) is `true`.

   -124- Returns: The number of erased elements.

   -125- Complexity: log(a_trana.size()) + a_trana.count(kx)

   […]

   b.find(k)
   

   -141- Result: `iterator`; `const_iterator` for constant `b`.

   -142- Returns: An iterator pointing to an element with the key equivalent to `k`, or `b.end()` if such an element is not found.

   -143- Complexity: Logarithmic.

   a_tranb.find(ke)
   

   -144- Result: `iterator`; `const_iterator` for constant a_tranb.

   -145- Returns: An iterator pointing to an element with key `r` such that !c(r, ke) && !c(ke, r) is `true`, or a_tranb.end() if such an element is not found.

   -146- Complexity: Logarithmic.

   b.count(k)
   

   -147- Result: `size_type`

   -148- Returns: The number of elements with key equivalent to `k`.

   -149- Complexity: log(`b.size()`) + `b.count(k)`

   a_tranb.count(ke)
   

   -150- Result: `size_type`

   -151- Returns: The number of elements with key `r` such that !c(r, ke) && !c(ke, r).

   -152- Complexity: log(a_tranb.size()) + a_tranb.count(ke)

   b.contains(k)
   

   -153- Result: `bool`

   -154- Effects: Equivalent to: `return b.find(k) != b.end();`

   a_tranb.contains(ke)
   

   -155- Result: `bool`

   -156- Effects: Equivalent to: return a_tranb.find(ke) != a_tranb.end();

   b.lower_bound(k)
   

   -157- Result: `iterator`; `const_iterator` for constant `b`.

   -158- Returns: An iterator pointing to the first element with key not less than `k`, or `b.end()` if such an element is not found.

   -159- Complexity: Logarithmic.

   a_tranb.lower_bound(kl)
   

   -160- Result: `iterator`; `const_iterator` for constant a_tranb.

   -161- Returns: An iterator pointing to the first element with key `r` such that !c(r, kl), or a_tranb.end() if such an element is not found.

   -162- Complexity: Logarithmic.

   b.upper_bound(k)
   

   -163- Result: `iterator`; `const_iterator` for constant `b`.

   -164- Returns: An iterator pointing to the first element with key greater than `k`, or `b.end()` if such an element is not found.

   -165- Complexity: Logarithmic.

   a_tranb.upper_bound(ku)
   

   -166- Result: `iterator`; `const_iterator` for constant a_tranb.

   -167- Returns: An iterator pointing to the first element with key `r` such that `c(ku, r)`, or a_tranb.end() if such an element is not found.

   -168- Complexity: Logarithmic.

   b.equal_range(k)
   

   -169- Result: pair<iterator, iterator>; pair<const_iterator, const_iterator> for constant `b`.

   -170- Effects: Equivalent to: `return make_pair(b.lower_bound(k), b.upper_bound(k));`

   -171- Complexity: Logarithmic.

   a_tranb.equal_range(ke)
   

   -172- Result: pair<iterator, iterator>; pair<const_iterator, const_iterator> for constant a_tranb.

   -173- Effects: Equivalent to: return make_pair(a_tranb.lower_bound(ke), a_tranb.upper_bound(ke));

   -174- Complexity: Logarithmic.

2. Modify [associative.reqmts.except] as indicated:

   -1- For associative containers, no `clear()` function throws an exception. erase(kkx) does not throw an exception unless that exception is thrown by the container's `Compare` object (if any).

3. Modify [map.modifiers] as indicated:

   template<class... Args>
     constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
   template<class... Args>
     constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
   

   -3- Preconditions: `value_type` is Cpp17EmplaceConstructible into `map` from `piecewise_construct`, `forward_as_tuple(k)`, forward_as_tuple(std::forward<Args>(args)...). `Compare` induces a strict weak ordering on the set of values comprising `k` and all the keys in `*this`.

   -4- Effects: If the map already contains an element whose key is equivalent to `k`, there is no effect. Otherwise inserts an object of type `value_type` constructed with `piecewise_construct`, `forward_as_tuple(k)`, forward_as_tuple(std::forward<Args>(args)...).

   -5- Returns: In the first overload, the `bool` component of the returned pair is `true` if and only if the insertion took place. The returned iterator points to the map element whose key is equivalent to `k`.

   -6- Complexity: The same as `emplace` and `emplace_hint`, respectively.

   template<class... Args>
     constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
   template<class... Args>
     constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
   

   -7- Preconditions: `value_type` is Cpp17EmplaceConstructible into `map` from `piecewise_construct`, `forward_as_tuple(std::move(k))`, forward_as_tuple(std::forward<Args>(args)...). `Compare` induces a strict weak ordering on the set of values comprising `k` and all the keys in `*this`.

   -8- Effects: If the map already contains an element whose key is equivalent to `k`, there is no effect. Otherwise inserts an object of type `value_type` constructed with `piecewise_construct`, `forward_as_tuple(std::move(k))`, forward_as_tuple(std::forward<Args>(args)...).

   -9- Returns: In the first overload, the `bool` component of the returned pair is `true` if and only if the insertion took place. The returned iterator points to the map element whose key is equivalent to `k`.

   -10- Complexity: The same as `emplace` and `emplace_hint`, respectively.

   template<class K, class... Args>
     constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args);
   template<class K, class... Args>
     constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
   

   -11- Constraints: The qualified-id `Compare::is_transparent` is valid and denotes a type. For the first overload, is_convertible_v<K&&, const_iterator> and is_convertible_v<K&&, iterator> are both `false`.

   -12- Preconditions: `value_type` is Cpp17EmplaceConstructible into `map` from `piecewise_construct`, forward_as_tuple(std::forward<K>(k)), forward_as_tuple(std::forward<Args>(args)...). `Compare` induces a strict weak ordering on the set of values comprising key_type(std::forward<K>(k)) and all the keys in `*this`.

   -13- Effects: If the map already contains an element whose key is equivalent to `k`, there is no effect. Otherwise, let `r` be `equal_range(k)`. Constructs an object `u` of type `value_type` with `piecewise_construct`, forward_as_tuple(std::forward<K>(k)), forward_as_tuple(std::forward<Args>(args)...). If `equal_range(u.first) == r` is `false`, the behavior is undefined. Inserts `u` into `*this`.

   -14- Returns: In the first overload, the `bool` component of the returned pair is `true` if and only if the insertion took place. The returned iterator points to the map element whose key is equivalent to `k`.

   -15- Complexity: The same as `emplace` and `emplace_hint`, respectively.

   template<class M>
     constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
   template<class M>
     constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
   

   -16- Mandates: is_assignable_v<mapped_type&, M&&> is `true`.

   -17- Preconditions: `value_type` is Cpp17EmplaceConstructible into `map` from `k`, std::forward<M>(obj). `Compare` induces a strict weak ordering on the set of values comprising `k` and all the keys in `*this`.

   -18- Effects: If the map already contains an element `e` whose key is equivalent to `k`, assigns std::forward<M>(obj) to `e.second`. Otherwise inserts an object of type `value_type` constructed with `k`, std::forward<M>(obj).

   -19- Returns: In the first overload, the `bool` component of the returned pair is `true` if and only if the insertion took place. The returned iterator points to the map element whose key is equivalent to `k`.

   -20- Complexity: The same as `emplace` and `emplace_hint`, respectively.

   template<class M>
     constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
   template<class M>
     constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
   

   -21- Mandates: is_assignable_v<mapped_type&, M&&> is `true`.

   -22- Preconditions: `value_type` is Cpp17EmplaceConstructible into `map` from `std::move(k)`, std::forward<M>(obj). `Compare` induces a strict weak ordering on the set of values comprising `k` and all the keys in `*this`.

   -23- Effects: If the map already contains an element `e` whose key is equivalent to `k`, assigns std::forward<M>(obj) to `e.second`. Otherwise inserts an object of type `value_type` constructed with `std::move(k)`, std::forward<M>(obj).

   -24- Returns: In the first overload, the `bool` component of the returned pair is `true` if and only if the insertion took place. The returned iterator points to the map element whose key is equivalent to `k`.

   -25- Complexity: The same as `emplace` and `emplace_hint`, respectively.

   -26- Constraints: is_assignable_v<mapped_type&, M&&> is `true`.

   -27- Mandates: is_assignable_v<mapped_type&, M&&> is `true`.

   -28- Preconditions: `value_type` is Cpp17EmplaceConstructible into `map` from std::forward<K>(k), std::forward<M>(obj). `Compare` induces a strict weak ordering on the set of values comprising `k` and all the keys in `*this`.

   -29- Effects: If the map already contains an element `e` whose key is equivalent to `k`, assigns std::forward<M>(obj) to `e.second`. Otherwise, let `r` be `equal_range(k)`. Constructs an object `u` of type `value_type` with std::forward<K>(k), std::forward<M>(obj). If `equal_range(u.first) == r` is `false`, the behavior is undefined. Inserts `u` into `*this`.

   -30- Returns: In the first overload, the `bool` component of the returned pair is `true` if and only if the insertion took place. The returned iterator points to the map element whose key is equivalent to `k`.

   -31- Complexity: The same as `emplace` and `emplace_hint`, respectively.

4. Modify [set.modifiers] as indicated:

   template<class K> constexpr pair<iterator, bool> insert(K&& x);
   template<class K> constexpr iterator insert(const_iterator hint, K&& x);
   

   -1- Constraints: The qualified-id `Compare::is_transparent` is valid and denotes a type. For the second overload, is_convertible_v<K&&, const_iterator> and is_convertible_v<K&&, iterator> are both `false`.

   -2- Preconditions: `value_type` is Cpp17EmplaceConstructible into `set` from std::forward<K>(x). `Compare` induces a strict weak ordering on the set of values comprising `k` and all the keys in `*this`.

   -3- Effects: If the set already contains an element that is equivalent to `x`, there is no effect. Otherwise, let `r` be `equal_range(x)`. Constructs an object `u` of type `value_type` with std::forward<K>(x). If `equal_range(u) == r` is `false`, the behavior is undefined. Inserts `u` into `*this`.

   -4- Returns: In the first overload, the `bool` component of the returned pair is `true` if and only if the insertion took place. The returned iterator points to the set element that is equivalent to `x`.

   -5- Complexity: Logarithmic.

[associative.reqmts.general] mandates that `Compare` induce a strict weak ordering (SWO) on elements of `Key`. A strict reading of this requirement without further qualifications implies, for instance, that using a container such as std::set<double> is UB regardless of what elements go into it (because std::less<double> is not a SWO on all values of `double` due to NaN). Assuming that the intent of the standard is to allow for the use of std::set<double> and other containers where `Compare` does not induce a full SWO on all possible values of `Key`, there are (at least) two possible relaxations of the original requirement:

1. Let `K` be the set of keys in an associative container `a` at a given point in time: `Compare` induces a SWO on `K` and also on {`k`} ∪ `K` for any `k` involved in an attempted insertion into `a` (either successful or not).

2. `Compare` induces a SWO on `K` and also on {`k`} ∪ `K` for any `k` involved in an attempted insertion (either successful or not) or a lookup operation.

Now, consider the following code:

// (A)
std::set<double> s = {0.0, 1.0, 2.0, 3.0};
auto nan = std::numeric_limits<double>::quiet_NaN();
return s.upper_bound(nan) == s.end();

Under interpretation 1, (A) is correct and returns `true`, whereas under interpretation 2 the code is UB because std::less<double> does not induce a SWO on `{0.0, 1.0, 2.0, 3.0, NaN}`.

Currently, libstdc++, Microsoft's C++ Standard Library, and libc++ v21 or lower behave as if interpretation 1 is in effect. Starting with version 22, libc++ introduces optimizations that implicitly assume interpretation 2, and the code in fact returns `false`. See this godbolt link, where the different behaviors are shown side by side.

Note, however, that the following pieces of code are not UB:

// (B) Global binary search functions
std::vector<double> v = {0.0, 3.0, 2.0, 1.0};
std::sort(v.begin(), v.end());
return std::upper_bound(v.begin(), v.end(), nan) == v.end(); // returns true

// (C) Heterogeneous lookup
std::set<double, std::less<>> s = {0.0, 1.0, 2.0, 3.0};
return s.upper_bound(std::cref(nan)) == s.end(); // returns true

because `upper_bound` in (B) and (C) only requires that the passed key partition the range where lookup happens, and ¬( · < NaN) partitions the range `R` = [0.0, 1.0, 2.0, 3.0] into `R` and [] (see upper.bound and [associative.reqmts.general]/167. The fact that (C) is well defined is an argument against interpretation 2, given that (C) can be seen as a mere syntactic variation of (A).

The status quo (`Compare` must induce a full SWO on all possible values of `Key`) is unacceptably strict and hardly the intent of the standard. As reasonable interpretation is left open, we're beginning to see observable divergences between C++ standard library implementations.

Arguments in favor of partition-based lookup semantics

We posit that interpretation 1, supplemented with partition-based requirements for non-heterogeneous lookup:

Let `K` be the set of keys in an associative container `a` at a given point in time: `Compare` induces a SWO on `K` and also on {`k`} ∪ `K` for any `k` involved in an attempted insertion into `a` (either successful or not). Non-heterogeneous lookup for `k` only requires that `k` partition the range [`a.begin()`, `a.end()`).

is the most useful and reasonable interpretation. Some arguments in favor of this thesis:

• Partition-based lookup semantics is maximally aligned and consistent with current requirements for global lookup algorithms and associative container heterogeneous lookup. In particular:

  • It makes (A) and (C) equivalent, which is a reasonable assumption any non-expert user could make.

  • It makes flat container adaptors truly equivalent to the manually-sorted vectors they are meant to replace:

    // (D)
    std::vector<double> v = {3.0, 1.0, 0.0, 2.0};
    std::sort(v.begin(), v.end());
    auto nan = std::numeric_limits<double>::quiet_NaN();
    return std::upper_bound(v.begin(), v.end(), nan) == v.end();
    

    // (E) only well defined and equivalent to (D) if partition-based lookup is adopted
    std::flat_set<double> s = {3.0, 1.0, 0.0, 2.0};
    auto nan = std::numeric_limits<double>::quiet_NaN();
    return s.upper_bound(nan) == s.end();
    

• In the N1313 foundational paper where partition-based semantics was first introduced, David Abrahams states that "[s]trict weak ordering is a great concept for sorting, but maybe it's not appropriate for searching".

  N1313 informed the resolution of LWG 270 ("Binary search requirements overly strict"), whose rationale states that "[t]he proposed resolution reinterprets binary search. Instead of thinking about searching for a value in a sorted range, we view that as an important special case of a more general algorithm: searching for the partition point in a partitioned range".

• In N2882 and N3465, early versions of the paper upon which heterogeneous lookup for associative containers was defined (N3657), the wording for non-heterogeneous lookup was indeed partition-based in accordance with Abrahams's conceptual setup (though this exact wording didn't make it into the standard as is, for reasons unknown to the author).

• For a unique associative container `a`, if `Compare` induces a strict partial order on all its possible key values, then partition-based lookup is well defined everywhere. Formally, if `Compare` is a SPO and a set `K` of keys is totally ordered wrt `Compare` (i.e., `K` is a chain, which the range [`a.begin()`, `a.end()`) always satisfies), then `K` is partitioned by any arbitrary `k` (proof trivial).

• Beyond admittedly corner cases such as that of NaN, there are partial orders that directly benefit from partition-based semantics. For instance, if we have a set `s` of non-overlapping interval objects ordered by their natural interval order (such as supported by Boost.ICL, then `s.equal_range(i)` simply returns the range of intervals in `s` that are contained in `i`. Boost.ICL, in fact, implicitly relies on the interpretation of lookup semantics we're proposing here.

On a related note, it may be worth mentioning that the standard text has some general formulation problems regarding the extent of applicability of semantic requirements (both for C++20 `concept`s and pre-C++20 well-defined expression tables, collectively called named requirements). [structure.requirements]/8 tries to provide some leeway for the specific case of `concept`s in a manner described by P2027R0, section "This is a special case of a much bigger problem", as "little more than handwaving".