tmp/tmp0nbwqq5q/{from.md → to.md}
RENAMED
|
@@ -5,31 +5,31 @@ of data based on keys. The worst-case complexity for most operations is
|
|
| 5 |
linear, but the average case is much faster. The library provides four
|
| 6 |
unordered associative containers: `unordered_set`, `unordered_map`,
|
| 7 |
`unordered_multiset`, and `unordered_multimap`.
|
| 8 |
|
| 9 |
Unordered associative containers conform to the requirements for
|
| 10 |
-
Containers
|
| 11 |
`a == b` and `a != b` have different semantics than for the other
|
| 12 |
container types.
|
| 13 |
|
| 14 |
Each unordered associative container is parameterized by `Key`, by a
|
| 15 |
-
function object type `Hash` that meets the
|
| 16 |
-
[[hash.requirements]]
|
| 17 |
-
|
| 18 |
-
|
| 19 |
-
`
|
| 20 |
-
|
| 21 |
|
| 22 |
The container’s object of type `Hash` — denoted by `hash` — is called
|
| 23 |
the *hash function* of the container. The container’s object of type
|
| 24 |
`Pred` — denoted by `pred` — is called the *key equality predicate* of
|
| 25 |
the container.
|
| 26 |
|
| 27 |
-
Two values `k1` and `k2`
|
| 28 |
-
|
| 29 |
-
values. If `k1` and `k2` are equivalent, the container’s
|
| 30 |
-
shall return the same value for both.
|
| 31 |
|
| 32 |
[*Note 1*: Thus, when an unordered associative container is
|
| 33 |
instantiated with a non-default `Pred` parameter it usually needs a
|
| 34 |
non-default `Hash` parameter as well. — *end note*]
|
| 35 |
|
|
@@ -74,64 +74,78 @@ changes ordering between elements, and changes which buckets elements
|
|
| 74 |
appear in, but does not invalidate pointers or references to elements.
|
| 75 |
For `unordered_multiset` and `unordered_multimap`, rehashing preserves
|
| 76 |
the relative ordering of equivalent elements.
|
| 77 |
|
| 78 |
The unordered associative containers meet all the requirements of
|
| 79 |
-
Allocator-aware containers
|
| 80 |
that for `unordered_map` and `unordered_multimap`, the requirements
|
| 81 |
-
placed on `value_type` in
|
| 82 |
-
|
| 83 |
-
and `mapped_type`.
|
| 84 |
|
| 85 |
[*Note 3*: For example, `key_type` and `mapped_type` are sometimes
|
| 86 |
-
required to be
|
| 87 |
-
`pair<const key_type, mapped_type>`, is not
|
| 88 |
-
|
| 89 |
|
| 90 |
-
In
|
| 91 |
-
|
| 92 |
-
|
| 93 |
-
|
| 94 |
-
|
| 95 |
-
|
| 96 |
-
|
| 97 |
-
|
| 98 |
-
|
| 99 |
-
|
| 100 |
-
|
| 101 |
-
`
|
| 102 |
-
|
| 103 |
-
|
| 104 |
-
|
| 105 |
-
|
| 106 |
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 107 |
|
| 108 |
Two unordered containers `a` and `b` compare equal if
|
| 109 |
`a.size() == b.size()` and, for every equivalent-key group \[`Ea1`,
|
| 110 |
`Ea2`) obtained from `a.equal_range(Ea1)`, there exists an
|
| 111 |
equivalent-key group \[`Eb1`, `Eb2`) obtained from `b.equal_range(Ea1)`,
|
| 112 |
such that `is_permutation(Ea1, Ea2, Eb1, Eb2)` returns `true`. For
|
| 113 |
`unordered_set` and `unordered_map`, the complexity of `operator==`
|
| 114 |
(i.e., the number of calls to the `==` operator of the `value_type`, to
|
| 115 |
the predicate returned by `key_eq()`, and to the hasher returned by
|
| 116 |
`hash_function()`) is proportional to N in the average case and to N² in
|
| 117 |
-
the worst case, where N is a.size(). For `unordered_multiset` and
|
| 118 |
`unordered_multimap`, the complexity of `operator==` is proportional to
|
| 119 |
$\sum E_i^2$ in the average case and to N² in the worst case, where N is
|
| 120 |
`a.size()`, and Eᵢ is the size of the iᵗʰ equivalent-key group in `a`.
|
| 121 |
However, if the respective elements of each corresponding pair of
|
| 122 |
equivalent-key groups Eaᵢ and Ebᵢ are arranged in the same order (as is
|
| 123 |
commonly the case, e.g., if `a` and `b` are unmodified copies of the
|
| 124 |
same container), then the average-case complexity for
|
| 125 |
`unordered_multiset` and `unordered_multimap` becomes proportional to N
|
| 126 |
(but worst-case complexity remains 𝑂(N^2), e.g., for a pathologically
|
| 127 |
bad hash function). The behavior of a program that uses `operator==` or
|
| 128 |
-
`operator!=` on unordered containers is undefined unless the `
|
| 129 |
-
|
| 130 |
-
|
| 131 |
-
|
| 132 |
-
`Pred`.
|
| 133 |
|
| 134 |
The iterator types `iterator` and `const_iterator` of an unordered
|
| 135 |
associative container are of at least the forward iterator category. For
|
| 136 |
unordered associative containers where the key type and value type are
|
| 137 |
the same, both `iterator` and `const_iterator` are constant iterators.
|
|
@@ -154,10 +168,15 @@ pointers and references to the removed element remain valid. However,
|
|
| 154 |
accessing the element through such pointers and references while the
|
| 155 |
element is owned by a `node_type` is undefined behavior. References and
|
| 156 |
pointers to an element obtained while it is owned by a `node_type` are
|
| 157 |
invalidated if the element is successfully inserted.
|
| 158 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 159 |
A deduction guide for an unordered associative container shall not
|
| 160 |
participate in overload resolution if any of the following are true:
|
| 161 |
|
| 162 |
- It has an `InputIterator` template parameter and a type that does not
|
| 163 |
qualify as an input iterator is deduced for that parameter.
|
|
|
|
| 5 |
linear, but the average case is much faster. The library provides four
|
| 6 |
unordered associative containers: `unordered_set`, `unordered_map`,
|
| 7 |
`unordered_multiset`, and `unordered_multimap`.
|
| 8 |
|
| 9 |
Unordered associative containers conform to the requirements for
|
| 10 |
+
Containers [[container.requirements]], except that the expressions
|
| 11 |
`a == b` and `a != b` have different semantics than for the other
|
| 12 |
container types.
|
| 13 |
|
| 14 |
Each unordered associative container is parameterized by `Key`, by a
|
| 15 |
+
function object type `Hash` that meets the *Cpp17Hash* requirements
|
| 16 |
+
[[hash.requirements]] and acts as a hash function for argument values of
|
| 17 |
+
type `Key`, and by a binary predicate `Pred` that induces an equivalence
|
| 18 |
+
relation on values of type `Key`. Additionally, `unordered_map` and
|
| 19 |
+
`unordered_multimap` associate an arbitrary *mapped type* `T` with the
|
| 20 |
+
`Key`.
|
| 21 |
|
| 22 |
The container’s object of type `Hash` — denoted by `hash` — is called
|
| 23 |
the *hash function* of the container. The container’s object of type
|
| 24 |
`Pred` — denoted by `pred` — is called the *key equality predicate* of
|
| 25 |
the container.
|
| 26 |
|
| 27 |
+
Two values `k1` and `k2` are considered equivalent if the container’s
|
| 28 |
+
key equality predicate `pred(k1, k2)` is valid and returns `true` when
|
| 29 |
+
passed those values. If `k1` and `k2` are equivalent, the container’s
|
| 30 |
+
hash function shall return the same value for both.
|
| 31 |
|
| 32 |
[*Note 1*: Thus, when an unordered associative container is
|
| 33 |
instantiated with a non-default `Pred` parameter it usually needs a
|
| 34 |
non-default `Hash` parameter as well. — *end note*]
|
| 35 |
|
|
|
|
| 74 |
appear in, but does not invalidate pointers or references to elements.
|
| 75 |
For `unordered_multiset` and `unordered_multimap`, rehashing preserves
|
| 76 |
the relative ordering of equivalent elements.
|
| 77 |
|
| 78 |
The unordered associative containers meet all the requirements of
|
| 79 |
+
Allocator-aware containers [[container.requirements.general]], except
|
| 80 |
that for `unordered_map` and `unordered_multimap`, the requirements
|
| 81 |
+
placed on `value_type` in [[container.alloc.req]] apply instead to
|
| 82 |
+
`key_type` and `mapped_type`.
|
|
|
|
| 83 |
|
| 84 |
[*Note 3*: For example, `key_type` and `mapped_type` are sometimes
|
| 85 |
+
required to be *Cpp17CopyAssignable* even though the associated
|
| 86 |
+
`value_type`, `pair<const key_type, mapped_type>`, is not
|
| 87 |
+
*Cpp17CopyAssignable*. — *end note*]
|
| 88 |
|
| 89 |
+
In [[container.hash.req]]:
|
| 90 |
+
|
| 91 |
+
- `X` denotes an unordered associative container class,
|
| 92 |
+
- `a` denotes a value of type `X`,
|
| 93 |
+
- `a2` denotes a value of a type with nodes compatible with type `X` (
|
| 94 |
+
[[container.node.compat]]),
|
| 95 |
+
- `b` denotes a possibly const value of type `X`,
|
| 96 |
+
- `a_uniq` denotes a value of type `X` when `X` supports unique keys,
|
| 97 |
+
- `a_eq` denotes a value of type `X` when `X` supports equivalent keys,
|
| 98 |
+
- `a_tran` denotes a possibly const value of type `X` when the
|
| 99 |
+
*qualified-id*s `X::key_equal::is_transparent` and
|
| 100 |
+
`X::hasher::is_transparent` are both valid and denote types
|
| 101 |
+
[[temp.deduct]],
|
| 102 |
+
- `i` and `j` denote input iterators that refer to `value_type`,
|
| 103 |
+
- `[i, j)` denotes a valid range,
|
| 104 |
+
- `p` and `q2` denote valid constant iterators to `a`,
|
| 105 |
+
- `q` and `q1` denote valid dereferenceable constant iterators to `a`,
|
| 106 |
+
- `r` denotes a valid dereferenceable iterator to `a`,
|
| 107 |
+
- `[q1, q2)` denotes a valid range in `a`,
|
| 108 |
+
- `il` denotes a value of type `initializer_list<value_type>`,
|
| 109 |
+
- `t` denotes a value of type `X::value_type`,
|
| 110 |
+
- `k` denotes a value of type `key_type`,
|
| 111 |
+
- `hf` denotes a possibly const value of type `hasher`,
|
| 112 |
+
- `eq` denotes a possibly const value of type `key_equal`,
|
| 113 |
+
- `ke` is a value such that
|
| 114 |
+
- `eq(r1, ke) == eq(ke, r1)`
|
| 115 |
+
- `hf(r1) == hf(ke)` if `eq(r1, ke)` is `true`, and
|
| 116 |
+
- `(eq(r1, ke) && eq(r1, r2)) == eq(r2, ke)`
|
| 117 |
+
|
| 118 |
+
where `r1` and `r2` are keys of elements in `a_tran`,
|
| 119 |
+
- `n` denotes a value of type `size_type`,
|
| 120 |
+
- `z` denotes a value of type `float`, and
|
| 121 |
+
- `nh` denotes a non-const rvalue of type `X::node_type`.
|
| 122 |
|
| 123 |
Two unordered containers `a` and `b` compare equal if
|
| 124 |
`a.size() == b.size()` and, for every equivalent-key group \[`Ea1`,
|
| 125 |
`Ea2`) obtained from `a.equal_range(Ea1)`, there exists an
|
| 126 |
equivalent-key group \[`Eb1`, `Eb2`) obtained from `b.equal_range(Ea1)`,
|
| 127 |
such that `is_permutation(Ea1, Ea2, Eb1, Eb2)` returns `true`. For
|
| 128 |
`unordered_set` and `unordered_map`, the complexity of `operator==`
|
| 129 |
(i.e., the number of calls to the `==` operator of the `value_type`, to
|
| 130 |
the predicate returned by `key_eq()`, and to the hasher returned by
|
| 131 |
`hash_function()`) is proportional to N in the average case and to N² in
|
| 132 |
+
the worst case, where N is `a.size()`. For `unordered_multiset` and
|
| 133 |
`unordered_multimap`, the complexity of `operator==` is proportional to
|
| 134 |
$\sum E_i^2$ in the average case and to N² in the worst case, where N is
|
| 135 |
`a.size()`, and Eᵢ is the size of the iᵗʰ equivalent-key group in `a`.
|
| 136 |
However, if the respective elements of each corresponding pair of
|
| 137 |
equivalent-key groups Eaᵢ and Ebᵢ are arranged in the same order (as is
|
| 138 |
commonly the case, e.g., if `a` and `b` are unmodified copies of the
|
| 139 |
same container), then the average-case complexity for
|
| 140 |
`unordered_multiset` and `unordered_multimap` becomes proportional to N
|
| 141 |
(but worst-case complexity remains 𝑂(N^2), e.g., for a pathologically
|
| 142 |
bad hash function). The behavior of a program that uses `operator==` or
|
| 143 |
+
`operator!=` on unordered containers is undefined unless the `Pred`
|
| 144 |
+
function object has the same behavior for both containers and the
|
| 145 |
+
equality comparison function for `Key` is a refinement[^1] of the
|
| 146 |
+
partition into equivalent-key groups produced by `Pred`.
|
|
|
|
| 147 |
|
| 148 |
The iterator types `iterator` and `const_iterator` of an unordered
|
| 149 |
associative container are of at least the forward iterator category. For
|
| 150 |
unordered associative containers where the key type and value type are
|
| 151 |
the same, both `iterator` and `const_iterator` are constant iterators.
|
|
|
|
| 168 |
accessing the element through such pointers and references while the
|
| 169 |
element is owned by a `node_type` is undefined behavior. References and
|
| 170 |
pointers to an element obtained while it is owned by a `node_type` are
|
| 171 |
invalidated if the element is successfully inserted.
|
| 172 |
|
| 173 |
+
The member function templates `find`, `count`, `equal_range`, and
|
| 174 |
+
`contains` shall not participate in overload resolution unless the
|
| 175 |
+
*qualified-id*s `Pred::is_transparent` and `Hash::is_transparent` are
|
| 176 |
+
both valid and denote types [[temp.deduct]].
|
| 177 |
+
|
| 178 |
A deduction guide for an unordered associative container shall not
|
| 179 |
participate in overload resolution if any of the following are true:
|
| 180 |
|
| 181 |
- It has an `InputIterator` template parameter and a type that does not
|
| 182 |
qualify as an input iterator is deduced for that parameter.
|