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

Files changed (1) hide show

tmp/tmpkl3wug2g/{from.md → to.md} +27 -14

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

@@ -17,19 +17,24 @@ function object type `Hash` that meets the `Hash` requirements (
 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`.
-A hash function is a function object that takes a single argument of
-type `Key` and returns a value of type `std::size_t`.
 Two values `k1` and `k2` of type `Key` are considered equivalent if the
-container’s `key_equal` function object returns `true` when passed those
-values. If `k1` and `k2` are equivalent, the 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.
 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
@@ -45,10 +50,18 @@ 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>`.
 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,
@@ -83,15 +96,14 @@ 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 `distance(Ea1, Ea2) == distance(Eb1, Eb2)` and
-`is_permutation(Ea1, Ea2, Eb1)` 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`.
@@ -113,12 +125,13 @@ 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.
 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

 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` 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
 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
 per bucket is kept below a bound. Rehashing invalidates iterators,
 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`.
 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

Diff to HTML by rtfpessoa