From Jason Turner

[iterator.traits]

C++17 → C++20 9.2 KB 202 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/tmp912q89_a/{from.md → to.md} +147 -52
tmp/tmp912q89_a/{from.md → to.md} RENAMED
@@ -1,96 +1,191 @@
1
- ### Iterator traits <a id="iterator.traits">[[iterator.traits]]</a>
2
 
3
- To implement algorithms only in terms of iterators, it is often
4
- necessary to determine the value and difference types that correspond to
5
- a particular iterator type. Accordingly, it is required that if
6
- `Iterator` is the type of an iterator, the types
7
 
8
  ``` cpp
9
- iterator_traits<Iterator>::difference_type
10
- iterator_traits<Iterator>::value_type
11
- iterator_traits<Iterator>::iterator_category
12
  ```
13
 
14
- be defined as the iterator’s difference type, value type and iterator
15
- category, respectively. In addition, the types
16
 
17
  ``` cpp
18
- iterator_traits<Iterator>::reference
19
- iterator_traits<Iterator>::pointer
20
  ```
21
 
22
- shall be defined as the iterator’s reference and pointer types, that is,
23
- for an iterator object `a`, the same type as the type of `*a` and `a->`,
24
- respectively. In the case of an output iterator, the types
 
 
 
25
 
26
  ``` cpp
27
- iterator_traits<Iterator>::difference_type
28
- iterator_traits<Iterator>::value_type
29
- iterator_traits<Iterator>::reference
30
- iterator_traits<Iterator>::pointer
31
  ```
32
 
33
  may be defined as `void`.
34
 
35
- If `Iterator` has valid ([[temp.deduct]]) member types
36
- `difference_type`, `value_type`, `pointer`, `reference`, and
37
- `iterator_category`, `iterator_traits<Iterator>` shall have the
38
- following as publicly accessible members:
39
 
40
  ``` cpp
41
- using difference_type = typename Iterator::difference_type;
42
- using value_type = typename Iterator::value_type;
43
- using pointer = typename Iterator::pointer;
44
- using reference = typename Iterator::reference;
45
- using iterator_category = typename Iterator::iterator_category;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
46
  ```
47
 
48
- Otherwise, `iterator_traits<Iterator>` shall have no members by any of
49
- the above names.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
50
 
51
- It is specialized for pointers as
52
 
53
  ``` cpp
54
  namespace std {
55
- template<class T> struct iterator_traits<T*> {
 
 
 
 
 
56
  using difference_type = ptrdiff_t;
57
- using value_type = T;
58
  using pointer = T*;
59
  using reference = T&;
60
- using iterator_category = random_access_iterator_tag;
61
- };
62
- }
63
- ```
64
-
65
- and for pointers to const as
66
-
67
- ``` cpp
68
- namespace std {
69
- template<class T> struct iterator_traits<const T*> {
70
- using difference_type = ptrdiff_t;
71
- using value_type = T;
72
- using pointer = const T*;
73
- using reference = const T&;
74
- using iterator_category = random_access_iterator_tag;
75
  };
76
  }
77
  ```
78
 
79
  [*Example 1*:
80
 
81
  To implement a generic `reverse` function, a C++ program can do the
82
  following:
83
 
84
  ``` cpp
85
- template <class BidirectionalIterator>
86
- void reverse(BidirectionalIterator first, BidirectionalIterator last) {
87
- typename iterator_traits<BidirectionalIterator>::difference_type n =
88
  distance(first, last);
89
  --n;
90
  while(n > 0) {
91
- typename iterator_traits<BidirectionalIterator>::value_type
92
  tmp = *first;
93
  *first++ = *--last;
94
  *last = tmp;
95
  n -= 2;
96
  }
 
1
+ #### Iterator traits <a id="iterator.traits">[[iterator.traits]]</a>
2
 
3
+ To implement algorithms only in terms of iterators, it is sometimes
4
+ necessary to determine the iterator category that corresponds to a
5
+ particular iterator type. Accordingly, it is required that if `I` is the
6
+ type of an iterator, the type
7
 
8
  ``` cpp
9
+ iterator_traits<I>::iterator_category
 
 
10
  ```
11
 
12
+ be defined as the iterator’s iterator category. In addition, the types
 
13
 
14
  ``` cpp
15
+ iterator_traits<I>::pointer
16
+ iterator_traits<I>::reference
17
  ```
18
 
19
+ shall be defined as the iterator’s pointer and reference types; that is,
20
+ for an iterator object `a` of class type, the same type as
21
+ `decltype(a.operator->())` and `decltype(*a)`, respectively. The type
22
+ `iterator_traits<I>::pointer` shall be `void` for an iterator of class
23
+ type `I` that does not support `operator->`. Additionally, in the case
24
+ of an output iterator, the types
25
 
26
  ``` cpp
27
+ iterator_traits<I>::value_type
28
+ iterator_traits<I>::difference_type
29
+ iterator_traits<I>::reference
 
30
  ```
31
 
32
  may be defined as `void`.
33
 
34
+ The definitions in this subclause make use of the following
35
+ exposition-only concepts:
 
 
36
 
37
  ``` cpp
38
+ template<class I>
39
+ concept cpp17-iterator =
40
+ copyable<I> && requires(I i) {
41
+ { *i } -> can-reference;
42
+ { ++i } -> same_as<I&>;
43
+ { *i++ } -> can-reference;
44
+ };
45
+
46
+ template<class I>
47
+ concept cpp17-input-iterator =
48
+ cpp17-iterator<I> && equality_comparable<I> && requires(I i) {
49
+ typename incrementable_traits<I>::difference_type;
50
+ typename indirectly_readable_traits<I>::value_type;
51
+ typename common_reference_t<iter_reference_t<I>&&,
52
+ typename indirectly_readable_traits<I>::value_type&>;
53
+ typename common_reference_t<decltype(*i++)&&,
54
+ typename indirectly_readable_traits<I>::value_type&>;
55
+ requires signed_integral<typename incrementable_traits<I>::difference_type>;
56
+ };
57
+
58
+ template<class I>
59
+ concept cpp17-forward-iterator =
60
+ cpp17-input-iterator<I> && constructible_from<I> &&
61
+ is_lvalue_reference_v<iter_reference_t<I>> &&
62
+ same_as<remove_cvref_t<iter_reference_t<I>>,
63
+ typename indirectly_readable_traits<I>::value_type> &&
64
+ requires(I i) {
65
+ { i++ } -> convertible_to<const I&>;
66
+ { *i++ } -> same_as<iter_reference_t<I>>;
67
+ };
68
+
69
+ template<class I>
70
+ concept cpp17-bidirectional-iterator =
71
+ cpp17-forward-iterator<I> && requires(I i) {
72
+ { --i } -> same_as<I&>;
73
+ { i-- } -> convertible_to<const I&>;
74
+ { *i-- } -> same_as<iter_reference_t<I>>;
75
+ };
76
+
77
+ template<class I>
78
+ concept cpp17-random-access-iterator =
79
+ cpp17-bidirectional-iterator<I> && totally_ordered<I> &&
80
+ requires(I i, typename incrementable_traits<I>::difference_type n) {
81
+ { i += n } -> same_as<I&>;
82
+ { i -= n } -> same_as<I&>;
83
+ { i + n } -> same_as<I>;
84
+ { n + i } -> same_as<I>;
85
+ { i - n } -> same_as<I>;
86
+ { i - i } -> same_as<decltype(n)>;
87
+ { i[n] } -> convertible_to<iter_reference_t<I>>;
88
+ };
89
+ ```
90
+
91
+ The members of a specialization `iterator_traits<I>` generated from the
92
+ `iterator_traits` primary template are computed as follows:
93
+
94
+ - If `I` has valid [[temp.deduct]] member types `difference_type`,
95
+ `value_type`, `reference`, and `iterator_category`, then
96
+ `iterator_traits<I>` has the following publicly accessible members:
97
+ ``` cpp
98
+ using iterator_category = typename I::iterator_category;
99
+ using value_type = typename I::value_type;
100
+ using difference_type = typename I::difference_type;
101
+ using pointer = see below;
102
+ using reference = typename I::reference;
103
  ```
104
 
105
+ If the *qualified-id* `I::pointer` is valid and denotes a type, then
106
+ `iterator_traits<I>::pointer` names that type; otherwise, it names
107
+ `void`.
108
+ - Otherwise, if `I` satisfies the exposition-only concept
109
+ `cpp17-input-iterator`, `iterator_traits<I>` has the following
110
+ publicly accessible members:
111
+ ``` cpp
112
+ using iterator_category = see below;
113
+ using value_type = typename indirectly_readable_traits<I>::value_type;
114
+ using difference_type = typename incrementable_traits<I>::difference_type;
115
+ using pointer = see below;
116
+ using reference = see below;
117
+ ```
118
+
119
+ - If the *qualified-id* `I::pointer` is valid and denotes a type,
120
+ `pointer` names that type. Otherwise, if
121
+ `decltype({}declval<I&>().operator->())` is well-formed, then
122
+ `pointer` names that type. Otherwise, `pointer` names `void`.
123
+ - If the *qualified-id* `I::reference` is valid and denotes a type,
124
+ `reference` names that type. Otherwise, `reference` names
125
+ `iter_reference_t<I>`.
126
+ - If the *qualified-id* `I::iterator_category` is valid and denotes a
127
+ type, `iterator_category` names that type. Otherwise,
128
+ `iterator_category` names:
129
+ - `random_access_iterator_tag` if `I` satisfies
130
+ `cpp17-random-access-iterator`, or otherwise
131
+ - `bidirectional_iterator_tag` if `I` satisfies
132
+ `cpp17-bidirectional-iterator`, or otherwise
133
+ - `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`,
134
+ or otherwise
135
+ - `input_iterator_tag`.
136
+ - Otherwise, if `I` satisfies the exposition-only concept
137
+ `cpp17-iterator`, then `iterator_traits<I>` has the following publicly
138
+ accessible members:
139
+ ``` cpp
140
+ using iterator_category = output_iterator_tag;
141
+ using value_type = void;
142
+ using difference_type = see below;
143
+ using pointer = void;
144
+ using reference = void;
145
+ ```
146
+
147
+ If the *qualified-id* `incrementable_traits<I>::difference_type` is
148
+ valid and denotes a type, then `difference_type` names that type;
149
+ otherwise, it names `void`.
150
+ - Otherwise, `iterator_traits<I>` has no members by any of the above
151
+ names.
152
+
153
+ Explicit or partial specializations of `iterator_traits` may have a
154
+ member type `iterator_concept` that is used to indicate conformance to
155
+ the iterator concepts [[iterator.concepts]].
156
 
157
+ `iterator_traits` is specialized for pointers as
158
 
159
  ``` cpp
160
  namespace std {
161
+ template<class T>
162
+ requires is_object_v<T>
163
+ struct iterator_traits<T*> {
164
+ using iterator_concept = contiguous_iterator_tag;
165
+ using iterator_category = random_access_iterator_tag;
166
+ using value_type = remove_cv_t<T>;
167
  using difference_type = ptrdiff_t;
 
168
  using pointer = T*;
169
  using reference = T&;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
170
  };
171
  }
172
  ```
173
 
174
  [*Example 1*:
175
 
176
  To implement a generic `reverse` function, a C++ program can do the
177
  following:
178
 
179
  ``` cpp
180
+ template<class BI>
181
+ void reverse(BI first, BI last) {
182
+ typename iterator_traits<BI>::difference_type n =
183
  distance(first, last);
184
  --n;
185
  while(n > 0) {
186
+ typename iterator_traits<BI>::value_type
187
  tmp = *first;
188
  *first++ = *--last;
189
  *last = tmp;
190
  n -= 2;
191
  }