[unord.req] - C++20 → C++23

Files changed (1) hide show

tmp/tmp0i551os4/{from.md → to.md} +945 -35

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

@@ -1,7 +1,9 @@
 ### Unordered associative containers <a id="unord.req">[[unord.req]]</a>
 Unordered associative containers provide an ability for fast retrieval
 of data based on keys. The worst-case complexity for most operations is
 linear, but the average case is much faster. The library provides four
 unordered associative containers: `unordered_set`, `unordered_map`,
 `unordered_multiset`, and `unordered_multimap`.
@@ -73,54 +75,956 @@ per bucket is kept below a bound. Rehashing invalidates iterators,
 changes ordering between elements, and changes which buckets elements
 appear in, but does not invalidate pointers or references to elements.
 For `unordered_multiset` and `unordered_multimap`, rehashing preserves
 the relative ordering of equivalent elements.
-The unordered associative containers meet all the requirements of
-Allocator-aware containers [[container.requirements.general]], except
-that for `unordered_map` and `unordered_multimap`, the requirements
-placed on `value_type` in [[container.alloc.req]] apply instead to
-`key_type` and `mapped_type`.
-[*Note 3*: For example, `key_type` and `mapped_type` are sometimes
-required to be *Cpp17CopyAssignable* even though the associated
-`value_type`, `pair<const key_type, mapped_type>`, is not
-*Cpp17CopyAssignable*. — *end note*]
-In [[container.hash.req]]:
 - `X` denotes an unordered 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`,
 - `a_uniq` denotes a value of type `X` when `X` supports unique keys,
 - `a_eq` denotes a value of type `X` when `X` supports equivalent keys,
-- `a_tran` denotes a possibly const value of type `X` when the
   *qualified-id*s `X::key_equal::is_transparent` and
   `X::hasher::is_transparent` are both valid and denote types
   [[temp.deduct]],
 - `i` and `j` denote input iterators that refer to `value_type`,
 - `[i, j)` denotes a valid range,
 - `p` and `q2` denote valid constant iterators to `a`,
 - `q` and `q1` denote valid dereferenceable constant iterators to `a`,
 - `r` denotes a valid dereferenceable iterator to `a`,
 - `[q1, q2)` denotes a valid range in `a`,
 - `il` denotes a value of type `initializer_list<value_type>`,
 - `t` denotes a value of type `X::value_type`,
 - `k` denotes a value of type `key_type`,
-- `hf` denotes a possibly const value of type `hasher`,
-- `eq` denotes a possibly const value of type `key_equal`,
 - `ke` is a value such that
-  - `eq(r1, ke) == eq(ke, r1)`
   - `hf(r1) == hf(ke)` if `eq(r1, ke)` is `true`, and
-  - `(eq(r1, ke) && eq(r1, r2)) == eq(r2, ke)`
   where `r1` and `r2` are keys of elements in `a_tran`,
 - `n` denotes a value of type `size_type`,
 - `z` denotes a value of type `float`, and
-- `nh` denotes a non-const rvalue of type `X::node_type`.
 Two unordered containers `a` and `b` compare equal if
 `a.size() == b.size()` and, for every equivalent-key group \[`Ea1`,
 `Ea2`) obtained from `a.equal_range(Ea1)`, there exists an
 equivalent-key group \[`Eb1`, `Eb2`) obtained from `b.equal_range(Ea1)`,
@@ -140,42 +1044,48 @@ same container), then the average-case complexity for
 `unordered_multiset` and `unordered_multimap` becomes proportional to N
 (but worst-case complexity remains 𝑂(N^2), e.g., for a pathologically
 bad hash function). The behavior of a program that uses `operator==` or
 `operator!=` on unordered containers is undefined unless the `Pred`
 function object has the same behavior for both containers and the
-equality comparison function for `Key` is a refinement[^1] of the
-partition into equivalent-key groups produced by `Pred`.
 The iterator types `iterator` and `const_iterator` of an unordered
 associative container are of at least the forward iterator category. For
 unordered associative containers where the key type and value type are
 the same, both `iterator` and `const_iterator` are constant iterators.
-The `insert` and `emplace` members shall not affect the validity of
-references to container elements, but may invalidate all iterators to
-the container. The `erase` members shall invalidate only iterators and
-references to the erased elements, and preserve the relative order of
-the elements that are not erased.
-The `insert` and `emplace` members shall not affect the validity of
-iterators if `(N+n) <= z * B`, where `N` is the number of elements in
-the container prior to the insert operation, `n` is the number of
-elements inserted, `B` is the container’s bucket count, and `z` is the
-container’s maximum load factor.
 The `extract` members invalidate only iterators to the removed element,
 and preserve the relative order of the elements that are not erased;
 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
 pointers to an element obtained while it is owned by a `node_type` are
 invalidated if the element is successfully inserted.
-The member function templates `find`, `count`, `equal_range`, and
-`contains` shall not participate in overload resolution unless the
-*qualified-id*s `Pred::is_transparent` and `Hash::is_transparent` are
-both valid and denote types [[temp.deduct]].
 A deduction guide for an unordered 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

 ### Unordered associative containers <a id="unord.req">[[unord.req]]</a>
+#### General <a id="unord.req.general">[[unord.req.general]]</a>
 Unordered associative containers provide an ability for fast retrieval
 of data based on keys. The worst-case complexity for most operations is
 linear, but the average case is much faster. The library provides four
 unordered associative containers: `unordered_set`, `unordered_map`,
 `unordered_multiset`, and `unordered_multimap`.
 changes ordering between elements, and changes which buckets elements
 appear in, but does not invalidate pointers or references to elements.
 For `unordered_multiset` and `unordered_multimap`, rehashing preserves
 the relative ordering of equivalent elements.
+In this subclause,
 - `X` denotes an unordered 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 of type `X` or `const X`,
 - `a_uniq` denotes a value of type `X` when `X` supports unique keys,
 - `a_eq` denotes a value of type `X` when `X` supports equivalent keys,
+- `a_tran` denotes a value of type `X` or `const X` when the
   *qualified-id*s `X::key_equal::is_transparent` and
   `X::hasher::is_transparent` are both valid and denote types
   [[temp.deduct]],
 - `i` and `j` denote input iterators that refer 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` and `q2` denote valid constant iterators to `a`,
 - `q` and `q1` denote valid dereferenceable constant iterators to `a`,
 - `r` denotes a valid dereferenceable iterator to `a`,
 - `[q1, q2)` denotes a valid range in `a`,
 - `il` denotes a value of type `initializer_list<value_type>`,
 - `t` denotes a value of type `X::value_type`,
 - `k` denotes a value of type `key_type`,
+- `hf` denotes a value of type `hasher` or `const hasher`,
+- `eq` denotes a value of type `key_equal` or `const key_equal`,
 - `ke` is a value such that
+  - `eq(r1, ke) == eq(ke, r1)`,
   - `hf(r1) == hf(ke)` if `eq(r1, ke)` is `true`, and
+  - if any two of `eq(r1, ke)`, `eq(r2, ke)`, and `eq(r1, r2)` are
+    `true`, then all three are `true`,
+  where `r1` and `r2` are keys of elements in `a_tran`,
+- `kx` is a value such that
+  - `eq(r1, kx) == eq(kx, r1)`,
+  - `hf(r1) == hf(kx)` if `eq(r1, kx)` is `true`,
+  - if any two of `eq(r1, kx)`, `eq(r2, kx)`, and `eq(r1, r2)` are
+    `true`, then all three are `true`, and
+  - `kx` is not convertible to either `iterator` or `const_iterator`,
   where `r1` and `r2` are keys of elements in `a_tran`,
 - `n` denotes a value of type `size_type`,
 - `z` denotes a value of type `float`, and
+- `nh` denotes an rvalue of type `X::node_type`.
+A type `X` meets the *unordered 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 `unordered_map` and `unordered_multimap`, the requirements
+placed on `value_type` in [[container.alloc.reqmts]] apply instead to
+`key_type` and `mapped_type`.
+[*Note 3*: For example, `key_type` and `mapped_type` are sometimes
+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 `unordered_map` and `unordered_multimap` only.
+``` cpp
+typename X::value_type
+```
+*Result:* `Key` for `unordered_set` and `unordered_multiset` only;
+`pair<const Key, T>` for `unordered_map` and `unordered_multimap` only.
+*Preconditions:* `value_type` is *Cpp17Erasable* from `X`.
+``` cpp
+typename X::hasher
+```
+*Result:* `Hash`.
+*Preconditions:* `Hash` is a unary function object type such that the
+expression `hf(k)` has type `size_t`.
+``` cpp
+typename X::key_equal
+```
+*Result:* `Pred`.
+*Preconditions:* `Pred` meets the *Cpp17CopyConstructible* requirements.
+`Pred` is a binary predicate that takes two arguments of type `Key`.
+`Pred` is an equivalence relation.
+``` cpp
+typename X::local_iterator
+```
+*Result:* An iterator type whose category, value type, difference type,
+and pointer and reference types are the same as `X::iterator`’s.
+[*Note 1*: A `local_iterator` object can be used to iterate through a
+single bucket, but cannot be used to iterate across
+buckets. — *end note*]
+``` cpp
+typename X::const_local_iterator
+```
+*Result:* An iterator type whose category, value type, difference type,
+and pointer and reference types are the same as `X::const_iterator`’s.
+[*Note 2*: A `const_local_iterator` object can be used to iterate
+through a single bucket, but cannot be used to iterate across
+buckets. — *end note*]
+``` cpp
+typename X::node_type
+```
+*Result:* A specialization of a *node-handle* class
+template [[container.node]], such that the public nested types are the
+same types as the corresponding types in `X`.
+``` cpp
+X(n, hf, eq)
+```
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hf` as the hash function and `eq` as the key equality predicate.
+*Complexity:* 𝑂(`n`)
+``` cpp
+X(n, hf)
+```
+*Preconditions:* `key_equal` meets the *Cpp17DefaultConstructible*
+requirements.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hf` as the hash function and `key_equal()` as the key equality
+predicate.
+*Complexity:* 𝑂(`n`)
+``` cpp
+X(n)
+```
+*Preconditions:* `hasher` and `key_equal` meet the
+*Cpp17DefaultConstructible* requirements.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hasher()` as the hash function and `key_equal()` as the key
+equality predicate.
+*Complexity:* 𝑂(`n`)
+``` cpp
+X a = X();
+X a;
+```
+*Preconditions:* `hasher` and `key_equal` meet the
+*Cpp17DefaultConstructible* requirements.
+*Effects:* Constructs an empty container with an unspecified number of
+buckets, using `hasher()` as the hash function and `key_equal()` as the
+key equality predicate.
+*Complexity:* Constant.
+``` cpp
+X(i, j, n, hf, eq)
+```
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `*i`.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hf` as the hash function and `eq` as the key equality predicate,
+and inserts elements from \[`i`, `j`) into it.
+*Complexity:* Average case 𝑂(N) (N is `distance(i, j)`), worst case
+𝑂(N^2).
+``` cpp
+X(i, j, n, hf)
+```
+*Preconditions:* `key_equal` meets the *Cpp17DefaultConstructible*
+requirements. `value_type` is *Cpp17EmplaceConstructible* into `X` from
+`*i`.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hf` as the hash function and `key_equal()` as the key equality
+predicate, and inserts elements from \[`i`, `j`) into it.
+*Complexity:* Average case 𝑂(N) (N is `distance(i, j)`), worst case
+𝑂(N^2).
+``` cpp
+X(i, j, n)
+```
+*Preconditions:* `hasher` and `key_equal` meet the
+*Cpp17DefaultConstructible* requirements. `value_type` is
+*Cpp17EmplaceConstructible* into `X` from `*i`.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hasher()` as the hash function and `key_equal()` as the key
+equality predicate, and inserts elements from \[`i`, `j`) into it.
+*Complexity:* Average case 𝑂(N) (N is `distance(i, j)`), worst case
+𝑂(N^2).
+``` cpp
+X(i, j)
+```
+*Preconditions:* `hasher` and `key_equal` meet the
+*Cpp17DefaultConstructible* requirements. `value_type` is
+*Cpp17EmplaceConstructible* into `X` from `*i`.
+*Effects:* Constructs an empty container with an unspecified number of
+buckets, using `hasher()` as the hash function and `key_equal()` as the
+key equality predicate, and inserts elements from \[`i`, `j`) into it.
+*Complexity:* Average case 𝑂(N) (N is `distance(i, j)`), worst case
+𝑂(N^2).
+``` cpp
+X(from_range, rg, n, hf, eq)
+```
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `*ranges::begin(rg)`.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hf` as the hash function and `eq` as the key equality predicate,
+and inserts elements from `rg` into it.
+*Complexity:* Average case 𝑂(N) (N is `ranges::distance(rg)`), worst
+case 𝑂(N^2).
+``` cpp
+X(from_range, rg, n, hf)
+```
+*Preconditions:* `key_equal` meets the *Cpp17DefaultConstructible*
+requirements. `value_type` is *Cpp17EmplaceConstructible* into `X` from
+`*ranges::begin(rg)`.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hf` as the hash function and `key_equal()` as the key equality
+predicate, and inserts elements from `rg` into it.
+*Complexity:* Average case 𝑂(N) (N is `ranges::distance(rg)`), worst
+case 𝑂(N^2).
+``` cpp
+X(from_range, rg, n)
+```
+*Preconditions:* `hasher` and `key_equal` meet the
+*Cpp17DefaultConstructible* requirements. `value_type` is
+*Cpp17EmplaceConstructible* into `X` from `*ranges::begin(rg)`.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hasher()` as the hash function and `key_equal()` as the key
+equality predicate, and inserts elements from `rg` into it.
+*Complexity:* Average case 𝑂(N) (N is `ranges::distance(rg)`), worst
+case 𝑂(N^2).
+``` cpp
+X(from_range, rg)
+```
+*Preconditions:* `hasher` and `key_equal` meet the
+*Cpp17DefaultConstructible* requirements. `value_type` is
+*Cpp17EmplaceConstructible* into `X` from `*ranges::begin(rg)`.
+*Effects:* Constructs an empty container with an unspecified number of
+buckets, using `hasher()` as the hash function and `key_equal()` as the
+key equality predicate, and inserts elements from `rg` into it.
+*Complexity:* Average case 𝑂(N) (N is `ranges::distance(rg)`), worst
+case 𝑂(N^2).
+``` cpp
+X(il)
+```
+*Effects:* Equivalent to `X(il.begin(), il.end())`.
+``` cpp
+X(il, n)
+```
+*Effects:* Equivalent to `X(il.begin(), il.end(), n)`.
+``` cpp
+X(il, n, hf)
+```
+*Effects:* Equivalent to `X(il.begin(), il.end(), n, hf)`.
+``` cpp
+X(il, n, hf, eq)
+```
+*Effects:* Equivalent to `X(il.begin(), il.end(), n, hf, eq)`.
+``` cpp
+X(b)
+```
+*Effects:* In addition to the container
+requirements [[container.requirements.general]], copies the hash
+function, predicate, and maximum load factor.
+*Complexity:* Average case linear in `b.size()`, worst case quadratic.
+``` cpp
+a = b
+```
+*Result:* `X&`
+*Effects:* In addition to the container requirements, copies the hash
+function, predicate, and maximum load factor.
+*Complexity:* Average case linear in `b.size()`, worst case quadratic.
+``` 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:* Average case linear in `il.size()`, worst case quadratic.
+``` cpp
+b.hash_function()
+```
+*Result:* `hasher`
+*Returns:* `b`’s hash function.
+*Complexity:* Constant.
+``` cpp
+b.key_eq()
+```
+*Result:* `key_equal`
+*Returns:* `b`’s key equality predicate.
+*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:* Average case 𝑂(1), worst case 𝑂(`a_uniq.size()`).
+``` 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)...`.
+*Returns:* An iterator pointing to the newly inserted element.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a_eq.size()`).
+``` cpp
+a.emplace_hint(p, args)
+```
+*Result:* `iterator`
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `args`.
+*Effects:* Equivalent to `a.emplace(std::forward<Args>(args)...)`.
+*Returns:* An iterator pointing to the element with the key equivalent
+to the newly inserted element. The `const_iterator` `p` is a hint
+pointing to where the search should start. Implementations are permitted
+to ignore the hint.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a.size()`).
+``` 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 indicates whether
+the insertion takes place, and the `iterator` component points to the
+element with key equivalent to the key of `t`.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a_uniq.size()`).
+``` 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`.
+*Returns:* An iterator pointing to the newly inserted element.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a_eq.size()`).
+``` 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:* Equivalent to `a.insert(t)`. The iterator `p` is a hint
+pointing to where the search should start. Implementations are permitted
+to ignore the hint.
+*Returns:* An iterator pointing to the element with the key equivalent
+to that of `t`.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a.size()`).
+``` 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:* Equivalent to `a.insert(t)` for each element in `[i,j)`.
+*Complexity:* Average case 𝑂(N), where N is `distance(i, j)`, worst case
+𝑂(N(`a.size()` + 1)).
+``` 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:* Equivalent to `a.insert(t)` for each element `t` in `rg`.
+*Complexity:* Average case 𝑂(N), where N is `ranges::distance(rg)`,
+worst case 𝑂(N(`a.size()` + 1)).
+``` 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()`.
+*Ensures:* 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:* Average case 𝑂(1), worst case 𝑂(`a_uniq.size()`).
+``` 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.
+*Ensures:* `nh` is empty.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a_eq.size()`).
+``` cpp
+a.insert(q, 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 iterator `q` is a hint pointing to where the search
+should start. Implementations are permitted to ignore the hint.
+*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:* Average case 𝑂(1), worst case 𝑂(`a.size()`).
+``` cpp
+a.extract(k)
+```
+*Result:* `node_type`
+*Effects:* Removes an element in the container with key equivalent to
+`k`.
+*Returns:* A `node_type` owning the element if found, otherwise an empty
+`node_type`.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a.size()`).
+``` cpp
+a_tran.extract(kx)
+```
+*Result:* `node_type`
+*Effects:* Removes an element in the container with key equivalent to
+`kx`.
+*Returns:* A `node_type` owning the element if found, otherwise an empty
+`node_type`.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`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:* Average case 𝑂(1), worst case 𝑂(`a.size()`).
+``` 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 hash function and key equality predicate 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 and all iterators referring to `a` will be
+invalidated, but iterators to elements remaining in `a2` will remain
+valid.
+*Complexity:* Average case 𝑂(N), where N is `a2.size()`, worst case
+𝑂(N`*a.size() + N`).
+``` cpp
+a.erase(k)
+```
+*Result:* `size_type`
+*Effects:* Erases all elements with key equivalent to `k`.
+*Returns:* The number of elements erased.
+*Complexity:* Average case 𝑂(`a.count(k)`), worst case 𝑂(`a.size()`).
+``` cpp
+a_tran.erase(kx)
+```
+*Result:* `size_type`
+*Effects:* Erases all elements with key equivalent to `kx`.
+*Returns:* The number of elements erased.
+*Complexity:* Average case 𝑂(`a_tran.count(kx)`), worst case
+𝑂(`a_tran.size()`).
+``` cpp
+a.erase(q)
+```
+*Result:* `iterator`
+*Effects:* Erases the element pointed to by `q`.
+*Returns:* The iterator immediately following `q` prior to the erasure.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a.size()`).
+``` cpp
+a.erase(r)
+```
+*Result:* `iterator`
+*Effects:* Erases the element pointed to by `r`.
+*Returns:* The iterator immediately following `r` prior to the erasure.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a.size()`).
+``` cpp
+a.erase(q1, q2)
+```
+*Result:* `iterator`
+*Effects:* Erases all elements in the range `[q1, q2)`.
+*Returns:* The iterator immediately following the erased elements prior
+to the erasure.
+*Complexity:* Average case linear in `distance(q1, q2)`, worst case
+𝑂(`a.size()`).
+``` cpp
+a.clear()
+```
+*Result:* `void`
+*Effects:* Erases all elements in the container.
+*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 key equivalent to
+`k`, or `b.end()` if no such element exists.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`b.size()`).
+``` cpp
+a_tran.find(ke)
+```
+*Result:* `iterator`; `const_iterator` for constant `a_tran`.
+*Returns:* An iterator pointing to an element with key equivalent to
+`ke`, or `a_tran.end()` if no such element exists.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a_tran.size()`).
+``` cpp
+b.count(k)
+```
+*Result:* `size_type`
+*Returns:* The number of elements with key equivalent to `k`.
+*Complexity:* Average case 𝑂(`b.count(k)`), worst case 𝑂(`b.size()`).
+``` cpp
+a_tran.count(ke)
+```
+*Result:* `size_type`
+*Returns:* The number of elements with key equivalent to `ke`.
+*Complexity:* Average case 𝑂(`a_tran.count(ke)`), worst case
+𝑂(`a_tran.size()`).
+``` cpp
+b.contains(k)
+```
+*Effects:* Equivalent to `b.find(k) != b.end()`.
+``` cpp
+a_tran.contains(ke)
+```
+*Effects:* Equivalent to `a_tran.find(ke) != a_tran.end()`.
+``` cpp
+b.equal_range(k)
+```
+*Result:* `pair<iterator, iterator>`;
+`pair<const_iterator, const_iterator>` for constant `b`.
+*Returns:* A range containing all elements with keys equivalent to `k`.
+Returns `make_pair(b.end(), b.end())` if no such elements exist.
+*Complexity:* Average case 𝑂(`b.count(k)`), worst case 𝑂(`b.size()`).
+``` cpp
+a_tran.equal_range(ke)
+```
+*Result:* `pair<iterator, iterator>`;
+`pair<const_iterator, const_iterator>` for constant `a_tran`.
+*Returns:* A range containing all elements with keys equivalent to `ke`.
+Returns `make_pair(a_tran.end(), a_tran.end())` if no such elements
+exist.
+*Complexity:* Average case 𝑂(`a_tran.count(ke)`), worst case
+𝑂(`a_tran.size()`).
+``` cpp
+b.bucket_count()
+```
+*Result:* `size_type`
+*Returns:* The number of buckets that `b` contains.
+*Complexity:* Constant.
+``` cpp
+b.max_bucket_count()
+```
+*Result:* `size_type`
+*Returns:* An upper bound on the number of buckets that `b` can ever
+contain.
+*Complexity:* Constant.
+``` cpp
+b.bucket(k)
+```
+*Result:* `size_type`
+*Preconditions:* `b.bucket_count() > 0`.
+*Returns:* The index of the bucket in which elements with keys
+equivalent to `k` would be found, if any such element existed. The
+return value is in the range `[0, b.bucket_count())`.
+*Complexity:* Constant.
+``` cpp
+b.bucket_size(n)
+```
+*Result:* `size_type`
+*Preconditions:* `n` shall be in the range `[0, b.bucket_count())`.
+*Returns:* The number of elements in the `n`ᵗʰ bucket.
+*Complexity:* 𝑂(`b.bucket_size(n)`)
+``` cpp
+b.begin(n)
+```
+*Result:* `local_iterator`; `const_local_iterator` for constant `b`.
+*Preconditions:* `n` is in the range `[0, b.bucket_count())`.
+*Returns:* An iterator referring to the first element in the bucket. If
+the bucket is empty, then `b.begin(n) == b.end(n)`.
+*Complexity:* Constant.
+``` cpp
+b.end(n)
+```
+*Result:* `local_iterator`; `const_local_iterator` for constant `b`.
+*Preconditions:* `n` is in the range `[0, b.bucket_count())`.
+*Returns:* An iterator which is the past-the-end value for the bucket.
+*Complexity:* Constant.
+``` cpp
+b.cbegin(n)
+```
+*Result:* `const_local_iterator`
+*Preconditions:* `n` shall be in the range `[0, b.bucket_count())`.
+*Returns:* An iterator referring to the first element in the bucket. If
+the bucket is empty, then `b.cbegin(n) == b.cend(n)`.
+*Complexity:* Constant.
+``` cpp
+b.cend(n)
+```
+*Result:* `const_local_iterator`
+*Preconditions:* `n` is in the range `[0, b.bucket_count())`.
+*Returns:* An iterator which is the past-the-end value for the bucket.
+*Complexity:* Constant.
+``` cpp
+b.load_factor()
+```
+*Result:* `float`
+*Returns:* The average number of elements per bucket.
+*Complexity:* Constant.
+``` cpp
+b.max_load_factor()
+```
+*Result:* `float`
+*Returns:* A positive number that the container attempts to keep the
+load factor less than or equal to. The container automatically increases
+the number of buckets as necessary to keep the load factor below this
+number.
+*Complexity:* Constant.
+``` cpp
+a.max_load_factor(z)
+```
+*Result:* `void`
+*Preconditions:* `z` is positive. May change the container’s maximum
+load factor, using `z` as a hint.
+*Complexity:* Constant.
+``` cpp
+a.rehash(n)
+```
+*Result:* `void`
+*Ensures:* `a.bucket_count() >= a.size() / a.max_load_factor()` and
+`a.bucket_count() >= n`.
+*Complexity:* Average case linear in `a.size()`, worst case quadratic.
+``` cpp
+a.reserve(n)
+```
+*Effects:* Equivalent to `a.rehash(ceil(n / a.max_load_factor()))`.
 Two unordered containers `a` and `b` compare equal if
 `a.size() == b.size()` and, for every equivalent-key group \[`Ea1`,
 `Ea2`) obtained from `a.equal_range(Ea1)`, there exists an
 equivalent-key group \[`Eb1`, `Eb2`) obtained from `b.equal_range(Ea1)`,
 `unordered_multiset` and `unordered_multimap` becomes proportional to N
 (but worst-case complexity remains 𝑂(N^2), e.g., for a pathologically
 bad hash function). The behavior of a program that uses `operator==` or
 `operator!=` on unordered containers is undefined unless the `Pred`
 function object has the same behavior for both containers and the
+equality comparison function for `Key` is a refinement[^1]
+of the partition into equivalent-key groups produced by `Pred`.
 The iterator types `iterator` and `const_iterator` of an unordered
 associative container are of at least the forward iterator category. For
 unordered associative containers where the key type and value type are
 the same, both `iterator` and `const_iterator` are constant iterators.
+The `insert`, `insert_range`, and `emplace` members shall not affect the
+validity of references to container elements, but may invalidate all
+iterators to the container. The `erase` members shall invalidate only
+iterators and references to the erased elements, and preserve the
+relative order of the elements that are not erased.
+The `insert`, `insert_range`, and `emplace` members shall not affect the
+validity of iterators if `(N+n) <= z * B`, where `N` is the number of
+elements in the container prior to the insert operation, `n` is the
+number of elements inserted, `B` is the container’s bucket count, and
+`z` is the container’s maximum load factor.
 The `extract` members invalidate only iterators to the removed element,
 and preserve the relative order of the elements that are not erased;
 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
 pointers to an element obtained while it is owned by a `node_type` are
 invalidated if the element is successfully inserted.
+The member function templates `find`, `count`, `equal_range`,
+`contains`, `extract`, and `erase` shall not participate in overload
+resolution unless the *qualified-id*s `Pred::is_transparent` and
+`Hash::is_transparent` are both valid and denote types [[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 unordered 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