From Jason Turner

[associative.reqmts]

C++17 → C++20 7.6 KB 86 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpj1d6rbjg/{from.md → to.md} +42 -39
tmp/tmpj1d6rbjg/{from.md → to.md} RENAMED
@@ -3,21 +3,25 @@
3
  Associative containers provide fast retrieval of data based on keys. The
4
  library provides four basic kinds of associative containers: `set`,
5
  `multiset`, `map` and `multimap`.
6
 
7
  Each associative container is parameterized on `Key` and an ordering
8
- relation `Compare` that induces a strict weak ordering (
9
- [[alg.sorting]]) on elements of `Key`. In addition, `map` and `multimap`
10
- associate an arbitrary *mapped type* `T` with the `Key`. The object of
11
- type `Compare` is called the *comparison object* of a container.
12
 
13
  The phrase “equivalence of keys” means the equivalence relation imposed
14
- by the comparison and *not* the `operator==` on keys. That is, two keys
15
- `k1` and `k2` are considered to be equivalent if for the comparison
16
- object `comp`, `comp(k1, k2) == false && comp(k2, k1) == false`. For any
17
- two keys `k1` and `k2` in the same container, calling `comp(k1, k2)`
18
- shall always return the same value.
 
 
 
 
19
 
20
  An associative container supports *unique keys* if it may contain at
21
  most one element for each key. Otherwise, it supports *equivalent keys*.
22
  The `set` and `map` classes support unique keys; the `multiset` and
23
  `multimap` classes support equivalent keys. For `multiset` and
@@ -33,45 +37,44 @@ 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>`
@@ -108,19 +111,19 @@ 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
113
- associative container is copied, either through a copy constructor or an
114
  assignment operator, the target container shall then use the comparison
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
 
3
  Associative containers provide fast retrieval of data based on keys. The
4
  library provides four basic kinds of associative containers: `set`,
5
  `multiset`, `map` and `multimap`.
6
 
7
  Each associative container is parameterized on `Key` and an ordering
8
+ relation `Compare` that induces a strict weak ordering [[alg.sorting]]
9
+ on elements of `Key`. In addition, `map` and `multimap` associate an
10
+ arbitrary *mapped type* `T` with the `Key`. The object of type `Compare`
11
+ is called the *comparison object* of a container.
12
 
13
  The phrase “equivalence of keys” means the equivalence relation imposed
14
+ by the comparison object. That is, two keys `k1` and `k2` are considered
15
+ to be equivalent if for the comparison object `comp`,
16
+ `comp(k1, k2) == false && comp(k2, k1) == false`.
17
+
18
+ [*Note 1*: This is not necessarily the same as the result of
19
+ `k1 == k2`. — *end note*]
20
+
21
+ For any two keys `k1` and `k2` in the same container, calling
22
+ `comp(k1, k2)` shall always return the same value.
23
 
24
  An associative container supports *unique keys* if it may contain at
25
  most one element for each key. Otherwise, it supports *equivalent keys*.
26
  The `set` and `map` classes support unique keys; the `multiset` and
27
  `multimap` classes support equivalent keys. For `multiset` and
 
37
  For associative containers where the value type is the same as the key
38
  type, both `iterator` and `const_iterator` are constant iterators. It is
39
  unspecified whether or not `iterator` and `const_iterator` are the same
40
  type.
41
 
42
+ [*Note 2*: `iterator` and `const_iterator` have identical semantics in
43
  this case, and `iterator` is convertible to `const_iterator`. Users can
44
  avoid violating the one-definition rule by always using `const_iterator`
45
  in their function parameter lists. — *end note*]
46
 
47
  The associative containers meet all the requirements of Allocator-aware
48
+ containers [[container.requirements.general]], except that for `map` and
49
+ `multimap`, the requirements placed on `value_type` in
50
+ [[container.alloc.req]] apply instead to `key_type` and `mapped_type`.
 
51
 
52
+ [*Note 3*: For example, in some cases `key_type` and `mapped_type` are
53
+ required to be *Cpp17CopyAssignable* even though the associated
54
+ `value_type`, `pair<const key_type, mapped_type>`, is not
55
+ *Cpp17CopyAssignable*. — *end note*]
56
 
57
+ In [[container.assoc.req]], `X` denotes an associative container class,
58
+ `a` denotes a value of type `X`, `a2` denotes a value of a type with
59
+ nodes compatible with type `X` ([[container.node.compat]]), `b` denotes
60
+ a possibly `const` value of type `X`, `u` denotes the name of a variable
61
+ being declared, `a_uniq` denotes a value of type `X` when `X` supports
62
+ unique keys, `a_eq` denotes a value of type `X` when `X` supports
63
+ multiple keys, `a_tran` denotes a possibly `const` value of type `X`
64
+ when the *qualified-id* `X::key_compare::is_transparent` is valid and
65
+ denotes a type [[temp.deduct]], `i` and `j` meet the
66
+ *Cpp17InputIterator* requirements and refer to elements implicitly
67
+ convertible to `value_type`, \[`i`, `j`) denotes a valid range, `p`
68
+ denotes a valid constant iterator to `a`, `q` denotes a valid
69
+ dereferenceable constant iterator to `a`, `r` denotes a valid
70
+ dereferenceable iterator to `a`, `[q1, q2)` denotes a valid range of
71
+ constant iterators in `a`, `il` designates an object of type
72
  `initializer_list<value_type>`, `t` denotes a value of type
73
  `X::value_type`, `k` denotes a value of type `X::key_type` and `c`
74
  denotes a possibly `const` value of type `X::key_compare`; `kl` is a
75
+ value such that `a` is partitioned [[alg.sorting]] with respect to
76
  `c(r, kl)`, with `r` the key value of `e` and `e` in `a`; `ku` is a
77
  value such that `a` is partitioned with respect to `!c(ku, r)`; `ke` is
78
  a value such that `a` is partitioned with respect to `c(r, ke)` and
79
  `!c(ke, r)`, with `c(r, ke)` implying `!c(ke, r)`. `A` denotes the
80
  storage allocator used by `X`, if any, or `allocator<X::value_type>`
 
111
  ```
112
 
113
  When an associative container is constructed by passing a comparison
114
  object the container shall not store a pointer or reference to the
115
  passed object, even if that object is passed by reference. When an
116
+ associative container is copied, through either a copy constructor or an
117
  assignment operator, the target container shall then use the comparison
118
  object from the container being copied, as if that comparison object had
119
  been passed to the target container in its constructor.
120
 
121
+ The member function templates `find`, `count`, `contains`,
122
+ `lower_bound`, `upper_bound`, and `equal_range` shall not participate in
123
+ overload resolution unless the *qualified-id* `Compare::is_transparent`
124
+ is valid and denotes a type [[temp.deduct]].
125
 
126
  A deduction guide for an associative container shall not participate in
127
  overload resolution if any of the following are true:
128
 
129
  - It has an `InputIterator` template parameter and a type that does not