[associative.reqmts] - C++20 → C++23

Files changed (1) hide show

tmp/tmpao4qhl2j/{from.md → to.md} +728 -38

tmp/tmpao4qhl2j/{from.md → to.md} RENAMED Viewed

@@ -1,10 +1,16 @@
 ### Associative containers <a id="associative.reqmts">[[associative.reqmts]]</a>
 Associative containers provide fast retrieval of data based on keys. The
 library provides four basic kinds of associative containers: `set`,
-`multiset`, `map` and `multimap`.
 Each associative container is parameterized on `Key` and an ordering
 relation `Compare` that induces a strict weak ordering [[alg.sorting]]
 on elements of `Key`. In addition, `map` and `multimap` associate an
 arbitrary *mapped type* `T` with the `Key`. The object of type `Compare`
@@ -42,50 +48,729 @@ type.
 [*Note 2*: `iterator` and `const_iterator` have identical semantics in
 this case, and `iterator` is convertible to `const_iterator`. Users can
 avoid violating the one-definition rule by always using `const_iterator`
 in their function parameter lists. — *end note*]
-The associative containers meet all the requirements of Allocator-aware
-containers [[container.requirements.general]], except that for `map` and
-`multimap`, the requirements placed on `value_type` in
-[[container.alloc.req]] apply instead to `key_type` and `mapped_type`.
 [*Note 3*: For example, in some cases `key_type` and `mapped_type` are
 required to be *Cpp17CopyAssignable* even though the associated
 `value_type`, `pair<const key_type, mapped_type>`, is not
 *Cpp17CopyAssignable*. — *end note*]
-In [[container.assoc.req]], `X` denotes an associative container class,
-`a` denotes a value of type `X`, `a2` denotes a value of a type with
-nodes compatible with type `X` ([[container.node.compat]]), `b` denotes
-a possibly `const` value of type `X`, `u` denotes the name of a variable
-being declared, `a_uniq` denotes a value of type `X` when `X` supports
-unique keys, `a_eq` denotes a value of type `X` when `X` supports
-multiple keys, `a_tran` denotes a possibly `const` value of type `X`
-when the *qualified-id* `X::key_compare::is_transparent` is valid and
-denotes a type [[temp.deduct]], `i` and `j` meet the
-*Cpp17InputIterator* requirements and refer to elements implicitly
-convertible to `value_type`, \[`i`, `j`) denotes a valid range, `p`
-denotes a valid constant iterator to `a`, `q` denotes a valid
-dereferenceable constant iterator to `a`, `r` denotes a valid
-dereferenceable iterator to `a`, `[q1, q2)` denotes a valid range of
-constant iterators in `a`, `il` designates an object of type
-`initializer_list<value_type>`, `t` denotes a value of type
-`X::value_type`, `k` denotes a value of type `X::key_type` and `c`
-denotes a possibly `const` value of type `X::key_compare`; `kl` is a
-value such that `a` is partitioned [[alg.sorting]] with respect to
-`c(r, kl)`, with `r` the key value of `e` and `e` in `a`; `ku` is a
-value such that `a` is partitioned with respect to `!c(ku, r)`; `ke` is
-a value such that `a` is partitioned with respect to `c(r, ke)` and
-`!c(ke, r)`, with `c(r, ke)` implying `!c(ke, r)`. `A` denotes the
-storage allocator used by `X`, if any, or `allocator<X::value_type>`
-otherwise, `m` denotes an allocator of a type convertible to `A`, and
-`nh` denotes a non-const rvalue of type `X::node_type`.
-The `insert` and `emplace` members shall not affect the validity of
-iterators and references to the container, and the `erase` members shall
-invalidate only iterators and references to the erased elements.
 The `extract` members invalidate only iterators to the removed element;
 pointers and references to the removed element remain valid. However,
 accessing the element through such pointers and references while the
 element is owned by a `node_type` is undefined behavior. References and
@@ -117,13 +802,18 @@ associative container is copied, through either a copy constructor or an
 assignment operator, the target container shall then use the comparison
 object from the container being copied, as if that comparison object had
 been passed to the target container in its constructor.
 The member function templates `find`, `count`, `contains`,
-`lower_bound`, `upper_bound`, and `equal_range` shall not participate in
-overload resolution unless the *qualified-id* `Compare::is_transparent`
-is valid and denotes a type [[temp.deduct]].
 A deduction guide for an associative container shall not participate in
 overload resolution if any of the following are true:
 - It has an `InputIterator` template parameter and a type that does not

 ### Associative containers <a id="associative.reqmts">[[associative.reqmts]]</a>
+#### General <a id="associative.reqmts.general">[[associative.reqmts.general]]</a>
 Associative containers provide fast retrieval of data based on keys. The
 library provides four basic kinds of associative containers: `set`,
+`multiset`, `map` and `multimap`. The library also provides container
+adaptors that make it easy to construct abstract data types, such as
+`flat_map`s, `flat_multimap`s, `flat_set`s, or `flat_multiset`s, out of
+the basic sequence container kinds (or out of other program-defined
+sequence containers).
 Each associative container is parameterized on `Key` and an ordering
 relation `Compare` that induces a strict weak ordering [[alg.sorting]]
 on elements of `Key`. In addition, `map` and `multimap` associate an
 arbitrary *mapped type* `T` with the `Key`. The object of type `Compare`
 [*Note 2*: `iterator` and `const_iterator` have identical semantics in
 this case, and `iterator` is convertible to `const_iterator`. Users can
 avoid violating the one-definition rule by always using `const_iterator`
 in their function parameter lists. — *end note*]
+In this subclause,
+- `X` denotes an associative container class,
+- `a` denotes a value of type `X`,
+- `a2` denotes a value of a type with nodes compatible with type `X` (
+  [[container.node.compat]]),
+- `b` denotes a value or type `X` or `const X`,
+- `u` denotes the name of a variable being declared,
+- `a_uniq` denotes a value of type `X` when `X` supports unique keys,
+- `a_eq` denotes a value of type `X` when `X` supports multiple keys,
+- `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]],
+- `i` and `j` meet the *Cpp17InputIterator* requirements and refer to
+  elements implicitly convertible to `value_type`,
+- \[`i`, `j`) denotes a valid range,
+- `rg` denotes a value of a type `R` that models
+  `container-compatible-range<value_type>`,
+- `p` denotes a valid constant iterator to `a`,
+- `q` denotes a valid dereferenceable constant iterator to `a`,
+- `r` denotes a valid dereferenceable iterator to `a`,
+- `[q1, q2)` denotes a valid range of constant iterators in `a`,
+- `il` designates an object of type `initializer_list<value_type>`,
+- `t` denotes a value of type `X::value_type`,
+- `k` denotes a value of type `X::key_type`, and
+- `c` denotes a value of type `X::key_compare` or
+  `const X::key_compare`;
+- `kl` is a value such that `a` is partitioned [[alg.sorting]] with
+  respect to `c(x, kl)`, with `x` the key value of `e` and `e` in `a`;
+- `ku` is a value such that `a` is partitioned with respect to
+  `!c(ku, x)`, with `x` the key value of `e` and `e` in `a`;
+- `ke` is a value such that `a` is partitioned with respect to
+  `c(x, ke)` and `!c(ke, x)`, with `c(x, ke)` implying `!c(ke, x)` and
+  with `x` the key value of `e` and `e` in `a`;
+- `kx` is a value such that
+  - `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
+  - `kx` is not convertible to either `iterator` or `const_iterator`;
+    and
+- `A` denotes the storage allocator used by `X`, if any, or
+  `allocator<X::value_type>` otherwise,
+- `m` denotes an allocator of a type convertible to `A`, and `nh`
+  denotes a non-const rvalue of type `X::node_type`.
+A type `X` meets the *associative container* requirements if `X` meets
+all the requirements of an allocator-aware container
+[[container.requirements.general]] and the following types, statements,
+and expressions are well-formed and have the specified semantics, except
+that for `map` and `multimap`, the requirements placed on `value_type`
+in [[container.alloc.reqmts]] apply instead to `key_type` and
+`mapped_type`.
 [*Note 3*: For example, in some cases `key_type` and `mapped_type` are
 required to be *Cpp17CopyAssignable* even though the associated
 `value_type`, `pair<const key_type, mapped_type>`, is not
 *Cpp17CopyAssignable*. — *end note*]
+``` cpp
+typename X::key_type
+```
+*Result:* `Key`.
+``` cpp
+typename X::mapped_type
+```
+*Result:* `T`.
+*Remarks:* For `map` and `multimap` only.
+``` cpp
+typename X::value_type
+```
+*Result:* `Key` for `set` and `multiset` only; `pair<const Key, T>` for
+`map` and `multimap` only.
+*Preconditions:* `X::value_type` is *Cpp17Erasable* from `X`.
+``` cpp
+typename X::key_compare
+```
+*Result:* `Compare`.
+*Preconditions:* `key_compare` is *Cpp17CopyConstructible*.
+``` cpp
+typename X::value_compare
+```
+*Result:* A binary predicate type. It is the same as `key_compare` for
+`set` and `multiset`; is an ordering relation on pairs induced by the
+first component (i.e., `Key`) for `map` and `multimap`.
+``` cpp
+typename X::node_type
+```
+*Result:* A specialization of the *node-handle* class
+template [[container.node]], such that the public nested types are the
+same types as the corresponding types in `X`.
+``` cpp
+X(c)
+```
+*Effects:* Constructs an empty container. Uses a copy of `c` as a
+comparison object.
+*Complexity:* Constant.
+``` cpp
+X u = X();
+X u;
+```
+*Preconditions:* `key_compare` meets the *Cpp17DefaultConstructible*
+requirements.
+*Effects:* Constructs an empty container. Uses `Compare()` as a
+comparison object.
+*Complexity:* Constant.
+``` cpp
+X(i, j, c)
+```
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `*i`.
+*Effects:* Constructs an empty container and inserts elements from the
+range \[`i`, `j`) into it; uses `c` as a comparison object.
+*Complexity:* N log N in general, where N has the value
+`distance(i, j)`; linear if \[`i`, `j`) is sorted with respect to
+`value_comp()`.
+``` cpp
+X(i, j)
+```
+*Preconditions:* `key_compare` meets the *Cpp17DefaultConstructible*
+requirements. `value_type` is *Cpp17EmplaceConstructible* into `X` from
+`*i`.
+*Effects:* Constructs an empty container and inserts elements from the
+range \[`i`, `j`) into it; uses `Compare()` as a comparison object.
+*Complexity:* N log N in general, where N has the value
+`distance(i, j)`; linear if \[`i`, `j`) is sorted with respect to
+`value_comp()`.
+``` cpp
+X(from_range, rg, c)
+```
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `*ranges::begin(rg)`.
+*Effects:* Constructs an empty container and inserts each element from
+`rg` into it. Uses `c` as the comparison object.
+*Complexity:* N log N in general, where N has the value
+`ranges::distance(rg)`; linear if `rg` is sorted with respect to
+`value_comp()`.
+``` cpp
+X(from_range, rg)
+```
+*Preconditions:* `key_compare` meets the *Cpp17DefaultConstructible*
+requirements. `value_type` is *Cpp17EmplaceConstructible* into `X` from
+`*ranges::begin(rg)`.
+*Effects:* Constructs an empty container and inserts each element from
+`rg` into it. Uses `Compare()` as the comparison object.
+*Complexity:* Same as `X(from_range, rg, c)`.
+``` cpp
+X(il, c)
+```
+*Effects:* Equivalent to `X(il.begin(), il.end(), c)`.
+``` cpp
+X(il)
+```
+*Effects:* Equivalent to `X(il.begin(), il.end())`.
+``` cpp
+a = il
+```
+*Result:* `X&`
+*Preconditions:* `value_type` is *Cpp17CopyInsertable* into `X` and
+*Cpp17CopyAssignable*.
+*Effects:* Assigns the range \[`il.begin()`, `il.end()`) into `a`. All
+existing elements of `a` are either assigned to or destroyed.
+*Complexity:* N log N in general, where N has the value
+`il.size() + a.size()`; linear if \[`il.begin()`, `il.end()`) is sorted
+with respect to `value_comp()`.
+``` cpp
+b.key_comp()
+```
+*Result:* `X::key_compare`
+*Returns:* The comparison object out of which `b` was constructed.
+*Complexity:* Constant.
+``` cpp
+b.value_comp()
+```
+*Result:* `X::value_compare`
+*Returns:* An object of `value_compare` constructed out of the
+comparison object.
+*Complexity:* Constant.
+``` cpp
+a_uniq.emplace(args)
+```
+*Result:* `pair<iterator, bool>`
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `args`.
+*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`.
+*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`.
+*Complexity:* Logarithmic.
+``` cpp
+a_eq.emplace(args)
+```
+*Result:* `iterator`
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `args`.
+*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.
+*Returns:* An iterator pointing to the newly inserted element.
+*Complexity:* Logarithmic.
+``` cpp
+a.emplace_hint(p, args)
+```
+*Result:* `iterator`
+*Effects:* Equivalent to `a.emplace(std::forward<Args>(args)...)`,
+except that the element is inserted as close as possible to the position
+just prior to `p`.
+*Returns:* An iterator pointing to the element with the key equivalent
+to the newly inserted element.
+*Complexity:* Logarithmic in general, but amortized constant if the
+element is inserted right before `p`.
+``` cpp
+a_uniq.insert(t)
+```
+*Result:* `pair<iterator, bool>`
+*Preconditions:* If `t` is a non-const rvalue, `value_type` is
+*Cpp17MoveInsertable* into `X`; otherwise, `value_type` is
+*Cpp17CopyInsertable* into `X`.
+*Effects:* Inserts `t` if and only if there is no element in the
+container with key equivalent to the key of `t`.
+*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`.
+*Complexity:* Logarithmic.
+``` cpp
+a_eq.insert(t)
+```
+*Result:* `iterator`
+*Preconditions:* If `t` is a non-const rvalue, `value_type` is
+*Cpp17MoveInsertable* into `X`; otherwise, `value_type` is
+*Cpp17CopyInsertable* into `X`.
+*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.
+*Complexity:* Logarithmic.
+``` cpp
+a.insert(p, t)
+```
+*Result:* `iterator`
+*Preconditions:* If `t` is a non-const rvalue, `value_type` is
+*Cpp17MoveInsertable* into `X`; otherwise, `value_type` is
+*Cpp17CopyInsertable* into `X`.
+*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`.
+*Returns:* An iterator pointing to the element with key equivalent to
+the key of `t`.
+*Complexity:* Logarithmic in general, but amortized constant if `t` is
+inserted right before `p`.
+``` cpp
+a.insert(i, j)
+```
+*Result:* `void`
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `*i`. Neither `i` nor `j` are iterators into `a`.
+*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.
+*Complexity:* N log (`a.size()` + N), where N has the value
+`distance(i, j)`.
+``` cpp
+a.insert_range(rg)
+```
+*Result:* `void`
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `*ranges::begin(rg)`. `rg` and `a` do not overlap.
+*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.
+*Complexity:* N log (`a.size()` + N), where N has the value
+`ranges::distance(rg)`.
+``` cpp
+a.insert(il)
+```
+*Effects:* Equivalent to `a.insert(il.begin(), il.end())`.
+``` cpp
+a_uniq.insert(nh)
+```
+*Result:* `insert_return_type`
+*Preconditions:* `nh` is empty or
+`a_uniq.get_allocator() == nh.get_allocator()` is `true`.
+*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()`.
+*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()`.
+*Complexity:* Logarithmic.
+``` cpp
+a_eq.insert(nh)
+```
+*Result:* `iterator`
+*Preconditions:* `nh` is empty or
+`a_eq.get_allocator() == nh.get_allocator()` is `true`.
+*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.
+*Ensures:* `nh` is empty.
+*Complexity:* Logarithmic.
+``` cpp
+a.insert(p, nh)
+```
+*Result:* `iterator`
+*Preconditions:* `nh` is empty or
+`a.get_allocator() == nh.get_allocator()` is `true`.
+*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`.
+*Ensures:* `nh` is empty if insertion succeeds, unchanged if insertion
+fails.
+*Returns:* An iterator pointing to the element with key equivalent to
+`nh.key()`.
+*Complexity:* Logarithmic in general, but amortized constant if the
+element is inserted right before `p`.
+``` cpp
+a.extract(k)
+```
+*Result:* `node_type`
+*Effects:* Removes the first element in the container with key
+equivalent to `k`.
+*Returns:* A `node_type` owning the element if found, otherwise an empty
+`node_type`.
+*Complexity:* log (`a.size()`)
+``` cpp
+a_tran.extract(kx)
+```
+*Result:* `node_type`
+*Effects:* Removes the first element in the container with key `r` such
+that `!c(r, kx) && !c(kx, r)` is `true`.
+*Returns:* A `node_type` owning the element if found, otherwise an empty
+`node_type`.
+*Complexity:* log(`a_tran.size()`)
+``` cpp
+a.extract(q)
+```
+*Result:* `node_type`
+*Effects:* Removes the element pointed to by `q`.
+*Returns:* A `node_type` owning that element.
+*Complexity:* Amortized constant.
+``` cpp
+a.merge(a2)
+```
+*Result:* `void`
+*Preconditions:* `a.get_allocator() == a2.get_allocator()`.
+*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`.
+*Ensures:* Pointers and references to the transferred elements of `a2`
+refer to those same elements but as members of `a`. Iterators referring
+to the transferred elements will continue to refer to their elements,
+but they now behave as iterators into `a`, not into `a2`.
+*Throws:* Nothing unless the comparison object throws.
+*Complexity:* N log(`a.size()+` N), where N has the value `a2.size()`.
+``` cpp
+a.erase(k)
+```
+*Result:* `size_type`
+*Effects:* Erases all elements in the container with key equivalent to
+`k`.
+*Returns:* The number of erased elements.
+*Complexity:* log (`a.size()`) + `a.count(k)`
+``` cpp
+a_tran.erase(kx)
+```
+*Result:* `size_type`
+*Effects:* Erases all elements in the container with key `r` such that
+`!c(r, kx) && !c(kx, r)` is `true`.
+*Returns:* The number of erased elements.
+*Complexity:* log(`a_tran.size())` + `a_tran.count(kx)`
+``` cpp
+a.erase(q)
+```
+*Result:* `iterator`
+*Effects:* Erases the element pointed to by `q`.
+*Returns:* An iterator pointing to the element immediately following `q`
+prior to the element being erased. If no such element exists, returns
+`a.end()`.
+*Complexity:* Amortized constant.
+``` cpp
+a.erase(r)
+```
+*Result:* `iterator`
+*Effects:* Erases the element pointed to by `r`.
+*Returns:* An iterator pointing to the element immediately following `r`
+prior to the element being erased. If no such element exists, returns
+`a.end()`.
+*Complexity:* Amortized constant.
+``` cpp
+a.erase(q1, q2)
+```
+*Result:* `iterator`
+*Effects:* Erases all the elements in the range \[`q1`, `q2`).
+*Returns:* An iterator pointing to the element pointed to by `q2` prior
+to any elements being erased. If no such element exists, `a.end()` is
+returned.
+*Complexity:* log(`a.size()`) + N, where N has the value
+`distance(q1, q2)`.
+``` cpp
+a.clear()
+```
+*Effects:* Equivalent to `a.erase(a.begin(), a.end())`.
+*Ensures:* `a.empty()` is `true`.
+*Complexity:* Linear in `a.size()`.
+``` cpp
+b.find(k)
+```
+*Result:* `iterator`; `const_iterator` for constant `b`.
+*Returns:* An iterator pointing to an element with the key equivalent to
+`k`, or `b.end()` if such an element is not found.
+*Complexity:* Logarithmic.
+``` cpp
+a_tran.find(ke)
+```
+*Result:* `iterator`; `const_iterator` for constant `a_tran`.
+*Returns:* An iterator pointing to an element with key `r` such that
+`!c(r, ke) && !c(ke, r)` is `true`, or `a_tran.end()` if such an element
+is not found.
+*Complexity:* Logarithmic.
+``` cpp
+b.count(k)
+```
+*Result:* `size_type`
+*Returns:* The number of elements with key equivalent to `k`.
+*Complexity:* log (`b.size()`) + `b.count(k)`
+``` cpp
+a_tran.count(ke)
+```
+*Result:* `size_type`
+*Returns:* The number of elements with key `r` such that
+`!c(r, ke) && !c(ke, r)`.
+*Complexity:* log (`a_tran.size()`) + `a_tran.count(ke)`
+``` cpp
+b.contains(k)
+```
+*Result:* `bool`
+*Effects:* Equivalent to: `return b.find(k) != b.end();`
+``` cpp
+a_tran.contains(ke)
+```
+*Result:* `bool`
+*Effects:* Equivalent to: `return a_tran.find(ke) != a_tran.end();`
+``` cpp
+b.lower_bound(k)
+```
+*Result:* `iterator`; `const_iterator` for constant `b`.
+*Returns:* An iterator pointing to the first element with key not less
+than `k`, or `b.end()` if such an element is not found.
+*Complexity:* Logarithmic.
+``` cpp
+a_tran.lower_bound(kl)
+```
+*Result:* `iterator`; `const_iterator` for constant `a_tran`.
+*Returns:* An iterator pointing to the first element with key `r` such
+that `!c(r, kl)`, or `a_tran.end()` if such an element is not found.
+*Complexity:* Logarithmic.
+``` cpp
+b.upper_bound(k)
+```
+*Result:* `iterator`; `const_iterator` for constant `b`.
+*Returns:* An iterator pointing to the first element with key greater
+than `k`, or `b.end()` if such an element is not found.
+*Complexity:* Logarithmic,
+``` cpp
+a_tran.upper_bound(ku)
+```
+*Result:* `iterator`; `const_iterator` for constant `a_tran`.
+*Returns:* An iterator pointing to the first element with key `r` such
+that `c(ku, r)`, or `a_tran.end()` if such an element is not found.
+*Complexity:* Logarithmic.
+``` cpp
+b.equal_range(k)
+```
+*Result:* `pair<iterator, iterator>`;
+`pair<const_iterator, const_iterator>` for constant `b`.
+*Effects:* Equivalent to:
+`return make_pair(b.lower_bound(k), b.upper_bound(k));`
+*Complexity:* Logarithmic.
+``` cpp
+a_tran.equal_range(ke)
+```
+*Result:* `pair<iterator, iterator>`;
+`pair<const_iterator, const_iterator>` for constant `a_tran`.
+*Effects:* Equivalent to:
+`return make_pair(a_tran.lower_bound(ke), a_tran.upper_bound(ke));`
+*Complexity:* Logarithmic.
+The `insert`, `insert_range`, and `emplace` members shall not affect the
+validity of iterators and references to the container, and the `erase`
+members shall invalidate only iterators and references to the erased
+elements.
 The `extract` members invalidate only iterators to the removed element;
 pointers and references to the removed element remain valid. However,
 accessing the element through such pointers and references while the
 element is owned by a `node_type` is undefined behavior. References and
 assignment operator, the target container shall then use the comparison
 object from the container being copied, as if that comparison object had
 been passed to the target container in its constructor.
 The member function templates `find`, `count`, `contains`,
+`lower_bound`, `upper_bound`, `equal_range`, `erase`, and `extract`
+shall not participate in overload resolution unless the *qualified-id*
+`Compare::is_transparent` is valid and denotes a type [[temp.deduct]].
+Additionally, the member function templates `extract` and `erase` shall
+not participate in overload resolution if
+`is_convertible_v<K&&, iterator> || is_convertible_v<K&&, const_iterator>`
+is `true`, where `K` is the type substituted as the first template
+argument.
 A deduction guide for an associative container shall not participate in
 overload resolution if any of the following are true:
 - It has an `InputIterator` template parameter and a type that does not

Diff to HTML by rtfpessoa