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

Files changed (1) hide show

tmp/tmpr2rt8bzb/{from.md → to.md} +1097 -0

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

	@@ -0,0 +1,1097 @@

+#### 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`.
+Unordered associative containers conform to the requirements for
+Containers [[container.requirements]], except that the expressions
+`a == b` and `a != b` have different semantics than for the other
+container types.
+Each unordered associative container is parameterized by `Key`, by a
+function object type `Hash` that meets the *Cpp17Hash* requirements
+[[hash.requirements]] and acts as a hash function for argument values of
+type `Key`, and by a binary predicate `Pred` that induces an equivalence
+relation on values of type `Key`. Additionally, `unordered_map` and
+`unordered_multimap` associate an arbitrary *mapped type* `T` with the
+`Key`.
+The container’s object of type `Hash` — denoted by `hash` — is called
+the *hash function* of the container. The container’s object of type
+`Pred` — denoted by `pred` — is called the *key equality predicate* of
+the container.
+Two values `k1` and `k2` are considered equivalent if the container’s
+key equality predicate `pred(k1, k2)` is valid and returns `true` when
+passed those values. If `k1` and `k2` are equivalent, the container’s
+hash function shall return the same value for both.
+[*Note 1*: Thus, when an unordered associative container is
+instantiated with a non-default `Pred` parameter it usually needs a
+non-default `Hash` parameter as well. — *end note*]
+For any two keys `k1` and `k2` in the same container, calling
+`pred(k1, k2)` shall always return the same value. For any key `k` in a
+container, calling `hash(k)` shall always return the same value.
+An unordered associative container supports *unique keys* if it may
+contain at most one element for each key. Otherwise, it supports
+*equivalent keys*. `unordered_set` and `unordered_map` support unique
+keys. `unordered_multiset` and `unordered_multimap` support equivalent
+keys. In containers that support equivalent keys, elements with
+equivalent keys are adjacent to each other in the iteration order of the
+container. Thus, although the absolute order of elements in an unordered
+container is not specified, its elements are grouped into
+*equivalent-key groups* such that all elements of each group have
+equivalent keys. Mutating operations on unordered containers shall
+preserve the relative order of elements within each equivalent-key group
+unless otherwise specified.
+For `unordered_set` and `unordered_multiset` the value type is the same
+as the key type. For `unordered_map` and `unordered_multimap` it is
+`pair<const Key,
+T>`.
+For unordered containers where the value type is the same as the key
+type, both `iterator` and `const_iterator` are constant iterators. It is
+unspecified whether or not `iterator` and `const_iterator` are the same
+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 elements of an unordered associative container are organized into
+*buckets*. Keys with the same hash code appear in the same bucket. The
+number of buckets is automatically increased as elements are added to an
+unordered associative container, so that the average number of elements
+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.
+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)`,
+such that `is_permutation(Ea1, Ea2, Eb1, Eb2)` returns `true`. For
+`unordered_set` and `unordered_map`, the complexity of `operator==`
+(i.e., the number of calls to the `==` operator of the `value_type`, to
+the predicate returned by `key_eq()`, and to the hasher returned by
+`hash_function()`) is proportional to N in the average case and to N² in
+the worst case, where N is `a.size()`. For `unordered_multiset` and
+`unordered_multimap`, the complexity of `operator==` is proportional to
+$\sum E_i^2$ in the average case and to N² in the worst case, where N is
+`a.size()`, and Eᵢ is the size of the iᵗʰ equivalent-key group in `a`.
+However, if the respective elements of each corresponding pair of
+equivalent-key groups Eaᵢ and Ebᵢ are arranged in the same order (as is
+commonly the case, e.g., if `a` and `b` are unmodified copies of the
+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`, `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
+  qualify as an input iterator is deduced for that parameter.
+- It has an `Allocator` template parameter and a type that does not
+  qualify as an allocator is deduced for that parameter.
+- It has a `Hash` template parameter and an integral type or a type that
+  qualifies as an allocator is deduced for that parameter.
+- It has a `Pred` template parameter and a type that qualifies as an
+  allocator is deduced for that parameter.

Diff to HTML by rtfpessoa