Issue 4572: Key ordering requirements of associative containers are poorly specified

This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of New status.

4572. Key ordering requirements of associative containers are poorly specified

Section: 23.2.7.1 [associative.reqmts.general], 23.4.3.4 [map.modifiers], 23.4.6.4 [set.modifiers] Status: New Submitter: Joaquin M López Muñoz Opened: 2026-04-19 Last modified: 2026-04-20

Priority: Not Prioritized

View other active issues in [associative.reqmts.general].

View all other issues in [associative.reqmts.general].

View all issues with New status.

Discussion:

23.2.7.1 [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:

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).
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 23.2.7.1 [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 concepts and pre-C++20 well-defined expression tables, collectively called named requirements). 16.3.2.3 [structure.requirements]/8 tries to provide some leeway for the specific case of concepts in a manner described by P2027R0, section "This is a special case of a much bigger problem", as "little more than handwaving".

Proposed resolution:

This wording is relative to N5032.

Modify 23.2.7.1 [associative.reqmts.general] as indicated:
-2- Each associative container is parameterized on Key and an ordering relation Compare that induces a strict weak ordering (26.8 [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 (13.10.3 [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 (13.10.3 [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.
Modify 23.2.7.2 [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).
Modify 23.4.3.4 [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.
Modify 23.4.6.4 [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.