tmp/tmpu4_gn4yh/{from.md → to.md}
RENAMED
|
@@ -31,65 +31,82 @@ For `set` and `multiset` the value type is the same as the key type. For
|
|
| 31 |
|
| 32 |
of an associative container is of the bidirectional iterator category.
|
| 33 |
For associative containers where the value type is the same as the key
|
| 34 |
type, both `iterator` and `const_iterator` are constant iterators. It is
|
| 35 |
unspecified whether or not `iterator` and `const_iterator` are the same
|
| 36 |
-
type.
|
| 37 |
-
|
| 38 |
-
|
| 39 |
-
|
|
|
|
|
|
|
| 40 |
|
| 41 |
The associative containers meet all the requirements of Allocator-aware
|
| 42 |
containers ([[container.requirements.general]]), except that for `map`
|
| 43 |
and `multimap`, the requirements placed on `value_type` in Table
|
| 44 |
[[tab:containers.container.requirements]] apply instead to `key_type`
|
| 45 |
-
and `mapped_type`.
|
| 46 |
-
|
| 47 |
-
|
| 48 |
-
`CopyAssignable`
|
|
|
|
|
|
|
| 49 |
|
| 50 |
In Table [[tab:containers.associative.requirements]], `X` denotes an
|
| 51 |
-
associative container class, `a` denotes a value of `X`, `
|
| 52 |
-
denotes a value of
|
| 53 |
-
|
| 54 |
-
|
| 55 |
-
|
| 56 |
-
|
| 57 |
-
|
| 58 |
-
|
| 59 |
-
|
| 60 |
-
|
| 61 |
-
|
| 62 |
-
|
| 63 |
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 64 |
`c(r, kl)`, with `r` the key value of `e` and `e` in `a`; `ku` is a
|
| 65 |
value such that `a` is partitioned with respect to `!c(ku, r)`; `ke` is
|
| 66 |
a value such that `a` is partitioned with respect to `c(r, ke)` and
|
| 67 |
`!c(ke, r)`, with `c(r, ke)` implying `!c(ke, r)`. `A` denotes the
|
| 68 |
-
storage allocator used by `X`, if any, or
|
| 69 |
-
|
| 70 |
-
|
| 71 |
|
| 72 |
The `insert` and `emplace` members shall not affect the validity of
|
| 73 |
iterators and references to the container, and the `erase` members shall
|
| 74 |
invalidate only iterators and references to the erased elements.
|
| 75 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 76 |
The fundamental property of iterators of associative containers is that
|
| 77 |
they iterate through the containers in the non-descending order of keys
|
| 78 |
where non-descending is defined by the comparison that was used to
|
| 79 |
construct them. For any two dereferenceable iterators `i` and `j` such
|
| 80 |
-
that distance from `i` to `j` is positive,
|
|
|
|
| 81 |
|
| 82 |
``` cpp
|
| 83 |
value_comp(*j, *i) == false
|
| 84 |
```
|
| 85 |
|
| 86 |
For associative containers with unique keys the stronger condition
|
| 87 |
-
holds
|
| 88 |
|
| 89 |
``` cpp
|
| 90 |
-
value_comp(*i, *j) != false
|
| 91 |
```
|
| 92 |
|
| 93 |
When an associative container is constructed by passing a comparison
|
| 94 |
object the container shall not store a pointer or reference to the
|
| 95 |
passed object, even if that object is passed by reference. When an
|
|
@@ -98,13 +115,23 @@ assignment operator, the target container shall then use the comparison
|
|
| 98 |
object from the container being copied, as if that comparison object had
|
| 99 |
been passed to the target container in its constructor.
|
| 100 |
|
| 101 |
The member function templates `find`, `count`, `lower_bound`,
|
| 102 |
`upper_bound`, and `equal_range` shall not participate in overload
|
| 103 |
-
resolution unless the qualified-id `Compare::is_transparent` is valid
|
| 104 |
and denotes a type ([[temp.deduct]]).
|
| 105 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 106 |
#### Exception safety guarantees <a id="associative.reqmts.except">[[associative.reqmts.except]]</a>
|
| 107 |
|
| 108 |
For associative containers, no `clear()` function throws an exception.
|
| 109 |
`erase(k)` does not throw an exception unless that exception is thrown
|
| 110 |
by the container’s `Compare` object (if any).
|
|
|
|
| 31 |
|
| 32 |
of an associative container is of the bidirectional iterator category.
|
| 33 |
For associative containers where the value type is the same as the key
|
| 34 |
type, both `iterator` and `const_iterator` are constant iterators. It is
|
| 35 |
unspecified whether or not `iterator` and `const_iterator` are the same
|
| 36 |
+
type.
|
| 37 |
+
|
| 38 |
+
[*Note 1*: `iterator` and `const_iterator` have identical semantics in
|
| 39 |
+
this case, and `iterator` is convertible to `const_iterator`. Users can
|
| 40 |
+
avoid violating the one-definition rule by always using `const_iterator`
|
| 41 |
+
in their function parameter lists. — *end note*]
|
| 42 |
|
| 43 |
The associative containers meet all the requirements of Allocator-aware
|
| 44 |
containers ([[container.requirements.general]]), except that for `map`
|
| 45 |
and `multimap`, the requirements placed on `value_type` in Table
|
| 46 |
[[tab:containers.container.requirements]] apply instead to `key_type`
|
| 47 |
+
and `mapped_type`.
|
| 48 |
+
|
| 49 |
+
[*Note 2*: For example, in some cases `key_type` and `mapped_type` are
|
| 50 |
+
required to be `CopyAssignable` even though the associated `value_type`,
|
| 51 |
+
`pair<const key_type, mapped_type>`, is not
|
| 52 |
+
`CopyAssignable`. — *end note*]
|
| 53 |
|
| 54 |
In Table [[tab:containers.associative.requirements]], `X` denotes an
|
| 55 |
+
associative container class, `a` denotes a value of type `X`, `a2`
|
| 56 |
+
denotes a value of a type with nodes compatible with type `X` (Table
|
| 57 |
+
[[tab:containers.node.compat]]), `b` denotes a possibly `const` value of
|
| 58 |
+
type `X`, `u` denotes the name of a variable being declared, `a_uniq`
|
| 59 |
+
denotes a value of type `X` when `X` supports unique keys, `a_eq`
|
| 60 |
+
denotes a value of type `X` when `X` supports multiple keys, `a_tran`
|
| 61 |
+
denotes a possibly `const` value of type `X` when the *qualified-id*
|
| 62 |
+
`X::key_compare::is_transparent` is valid and denotes a type (
|
| 63 |
+
[[temp.deduct]]), `i` and `j` satisfy input iterator requirements and
|
| 64 |
+
refer to elements implicitly convertible to `value_type`, \[`i`, `j`)
|
| 65 |
+
denotes a valid range, `p` denotes a valid constant iterator to `a`, `q`
|
| 66 |
+
denotes a valid dereferenceable constant iterator to `a`, `r` denotes a
|
| 67 |
+
valid dereferenceable iterator to `a`, `[q1, q2)` denotes a valid range
|
| 68 |
+
of constant iterators in `a`, `il` designates an object of type
|
| 69 |
+
`initializer_list<value_type>`, `t` denotes a value of type
|
| 70 |
+
`X::value_type`, `k` denotes a value of type `X::key_type` and `c`
|
| 71 |
+
denotes a possibly `const` value of type `X::key_compare`; `kl` is a
|
| 72 |
+
value such that `a` is partitioned ([[alg.sorting]]) with respect to
|
| 73 |
`c(r, kl)`, with `r` the key value of `e` and `e` in `a`; `ku` is a
|
| 74 |
value such that `a` is partitioned with respect to `!c(ku, r)`; `ke` is
|
| 75 |
a value such that `a` is partitioned with respect to `c(r, ke)` and
|
| 76 |
`!c(ke, r)`, with `c(r, ke)` implying `!c(ke, r)`. `A` denotes the
|
| 77 |
+
storage allocator used by `X`, if any, or `allocator<X::value_type>`
|
| 78 |
+
otherwise, `m` denotes an allocator of a type convertible to `A`, and
|
| 79 |
+
`nh` denotes a non-const rvalue of type `X::node_type`.
|
| 80 |
|
| 81 |
The `insert` and `emplace` members shall not affect the validity of
|
| 82 |
iterators and references to the container, and the `erase` members shall
|
| 83 |
invalidate only iterators and references to the erased elements.
|
| 84 |
|
| 85 |
+
The `extract` members invalidate only iterators to the removed element;
|
| 86 |
+
pointers and references to the removed element remain valid. However,
|
| 87 |
+
accessing the element through such pointers and references while the
|
| 88 |
+
element is owned by a `node_type` is undefined behavior. References and
|
| 89 |
+
pointers to an element obtained while it is owned by a `node_type` are
|
| 90 |
+
invalidated if the element is successfully inserted.
|
| 91 |
+
|
| 92 |
The fundamental property of iterators of associative containers is that
|
| 93 |
they iterate through the containers in the non-descending order of keys
|
| 94 |
where non-descending is defined by the comparison that was used to
|
| 95 |
construct them. For any two dereferenceable iterators `i` and `j` such
|
| 96 |
+
that distance from `i` to `j` is positive, the following condition
|
| 97 |
+
holds:
|
| 98 |
|
| 99 |
``` cpp
|
| 100 |
value_comp(*j, *i) == false
|
| 101 |
```
|
| 102 |
|
| 103 |
For associative containers with unique keys the stronger condition
|
| 104 |
+
holds:
|
| 105 |
|
| 106 |
``` cpp
|
| 107 |
+
value_comp(*i, *j) != false
|
| 108 |
```
|
| 109 |
|
| 110 |
When an associative container is constructed by passing a comparison
|
| 111 |
object the container shall not store a pointer or reference to the
|
| 112 |
passed object, even if that object is passed by reference. When an
|
|
|
|
| 115 |
object from the container being copied, as if that comparison object had
|
| 116 |
been passed to the target container in its constructor.
|
| 117 |
|
| 118 |
The member function templates `find`, `count`, `lower_bound`,
|
| 119 |
`upper_bound`, and `equal_range` shall not participate in overload
|
| 120 |
+
resolution unless the *qualified-id* `Compare::is_transparent` is valid
|
| 121 |
and denotes a type ([[temp.deduct]]).
|
| 122 |
|
| 123 |
+
A deduction guide for an associative container shall not participate in
|
| 124 |
+
overload resolution if any of the following are true:
|
| 125 |
+
|
| 126 |
+
- It has an `InputIterator` template parameter and a type that does not
|
| 127 |
+
qualify as an input iterator is deduced for that parameter.
|
| 128 |
+
- It has an `Allocator` template parameter and a type that does not
|
| 129 |
+
qualify as an allocator is deduced for that parameter.
|
| 130 |
+
- It has a `Compare` template parameter and a type that qualifies as an
|
| 131 |
+
allocator is deduced for that parameter.
|
| 132 |
+
|
| 133 |
#### Exception safety guarantees <a id="associative.reqmts.except">[[associative.reqmts.except]]</a>
|
| 134 |
|
| 135 |
For associative containers, no `clear()` function throws an exception.
|
| 136 |
`erase(k)` does not throw an exception unless that exception is thrown
|
| 137 |
by the container’s `Compare` object (if any).
|