[unord.req] - C++14 → C++17

Files changed (1) hide show

tmp/tmp063svu91/{from.md → to.md} +67 -36

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

@@ -25,42 +25,47 @@ the *hash function* of the container. The container’s object of type
 the container.
 Two values `k1` and `k2` of type `Key` are considered equivalent if the
 container’s key equality predicate returns `true` when passed those
 values. If `k1` and `k2` are equivalent, the container’s hash function
-shall return the same value for both. Thus, when an unordered
-associative container is instantiated with a non-default `Pred`
-parameter it usually needs a non-default `Hash` parameter as well. 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 group*s 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
-`std::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. `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.
 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
@@ -73,37 +78,43 @@ 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 Table
 [[tab:containers.container.requirements]] apply instead to `key_type`
-and `mapped_type`. For example, `key_type` and `mapped_type` are
-sometimes required to be `CopyAssignable` even though the associated
-`value_type`, `pair<const key_type, mapped_type>`, is not
-`CopyAssignable`.
-In table  [[tab:HashRequirements]]: `X` is an unordered associative
-container class, `a` is an object of type `X`, `b` is a possibly const
-object of type `X`, `a_uniq` is an object of type `X` when `X` supports
-unique keys, `a_eq` is an object of type `X` when `X` supports
-equivalent keys, `i` and `j` are input iterators that refer to
-`value_type`, `[i, j)` is a valid range, `p` and `q2` are valid const
-iterators to `a`, `q` and `q1` are valid dereferenceable const iterators
-to `a`, `[q1, q2)` is a valid range in `a`, `il` designates an object of
-type `initializer_list<value_type>`, `t` is a value of type
-`X::value_type`, `k` is a value of type `key_type`, `hf` is a possibly
-const value of type `hasher`, `eq` is a possibly const value of type
-`key_equal`, `n` is a value of type `size_type`, and `z` is a value of
-type `float`.
 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_equal()`, 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`.
@@ -114,31 +125,51 @@ 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 `Hash` and
 `Pred` function objects respectively have the same behavior for both
-containers and the equality comparison operator 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 const 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.
 #### Exception safety guarantees <a id="unord.req.except">[[unord.req.except]]</a>
 For unordered associative containers, no `clear()` function throws an
 exception. `erase(k)` does not throw an exception unless that exception
 is thrown by the container’s `Hash` or `Pred` object (if any).
@@ -148,11 +179,11 @@ operation other than the container’s hash function from within an
 `insert` or `emplace` function inserting a single element, the insertion
 has no effect.
 For unordered associative containers, no `swap` function throws an
 exception unless that exception is thrown by the swap of the container’s
-Hash or Pred object (if any).
 For unordered associative containers, if an exception is thrown from
 within a `rehash()` function other than by the container’s hash function
 or comparison function, the `rehash()` function has no effect.

 the container.
 Two values `k1` and `k2` of type `Key` are considered equivalent if the
 container’s key equality predicate 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
 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 Table
 [[tab:containers.container.requirements]] apply instead to `key_type`
+and `mapped_type`.
+[*Note 3*: For example, `key_type` and `mapped_type` are sometimes
+required to be `CopyAssignable` even though the associated `value_type`,
+`pair<const key_type, mapped_type>`, is not
+`CopyAssignable`. — *end note*]
+In Table  [[tab:HashRequirements]]: `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` (Table
+[[tab:containers.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, `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`, `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)`,
 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`.
 `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 `Hash` and
 `Pred` function objects respectively have 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.
+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.
 #### Exception safety guarantees <a id="unord.req.except">[[unord.req.except]]</a>
 For unordered associative containers, no `clear()` function throws an
 exception. `erase(k)` does not throw an exception unless that exception
 is thrown by the container’s `Hash` or `Pred` object (if any).
 `insert` or `emplace` function inserting a single element, the insertion
 has no effect.
 For unordered associative containers, no `swap` function throws an
 exception unless that exception is thrown by the swap of the container’s
+`Hash` or `Pred` object (if any).
 For unordered associative containers, if an exception is thrown from
 within a `rehash()` function other than by the container’s hash function
 or comparison function, the `rehash()` function has no effect.

Diff to HTML by rtfpessoa