]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | |
2 | [section:concepts Iterator Concepts] | |
3 | ||
4 | [section:concepts_access Access] | |
5 | ||
6 | [h2 Readable Iterator Concept] | |
7 | ||
8 | A class or built-in type `X` models the *Readable Iterator* concept | |
9 | for value type `T` if, in addition to `X` being Assignable and | |
10 | Copy Constructible, the following expressions are valid and respect | |
11 | the stated semantics. `U` is the type of any specified member of | |
12 | type `T`. | |
13 | ||
14 | [table Readable Iterator Requirements (in addition to Assignable and Copy Constructible) | |
15 | [ | |
16 | [Expression] | |
17 | [Return Type] | |
18 | [Note/Precondition] | |
19 | ] | |
20 | [ | |
21 | [`iterator_traits<X>::value_type`] | |
22 | [`T`] | |
23 | [Any non-reference, non cv-qualified type] | |
24 | ] | |
25 | [ | |
26 | [`*a`] | |
27 | [ Convertible to `T`] | |
28 | [pre: `a` is dereferenceable. If `a == b` then `*a` is equivalent to `*b`.] | |
29 | ] | |
30 | [ | |
31 | [`a->m`] | |
32 | [`U&`] | |
33 | [pre: `(*a).m` is well-defined. Equivalent to `(*a).m`.] | |
34 | ] | |
35 | ] | |
36 | ||
37 | [h2 Writable Iterator Concept ] | |
38 | ||
39 | ||
40 | A class or built-in type `X` models the *Writable Iterator* concept | |
41 | if, in addition to `X` being Copy Constructible, the following | |
42 | expressions are valid and respect the stated semantics. Writable | |
43 | Iterators have an associated *set of value types*. | |
44 | ||
45 | [table Writable Iterator Requirements (in addition to Copy Constructible) | |
46 | [ | |
47 | [Expression] | |
48 | [Return Type] | |
49 | [Precondition] | |
50 | ] | |
51 | [ | |
52 | [`*a = o` ] | |
53 | [] | |
54 | [pre: The type of `o` is in the set of value types of `X`] | |
55 | ] | |
56 | ] | |
57 | ||
58 | [h2 Swappable Iterator Concept] | |
59 | ||
60 | A class or built-in type `X` models the *Swappable Iterator* concept | |
61 | if, in addition to `X` being Copy Constructible, the following | |
62 | expressions are valid and respect the stated semantics. | |
63 | ||
64 | [table Swappable Iterator Requirements (in addition to Copy Constructible) | |
65 | [ | |
66 | [Expression] | |
67 | [Return Type] | |
68 | [Postcondition] | |
69 | ] | |
70 | [ | |
71 | [`iter_swap(a, b)`] | |
72 | [`void`] | |
73 | [the pointed to values are exchanged] | |
74 | ] | |
75 | ] | |
76 | ||
77 | [blurb *Note:* An iterator that is a model of the *Readable* and *Writable Iterator* concepts | |
78 | is also a model of *Swappable Iterator*. *--end note*] | |
79 | ||
80 | [h2 Lvalue Iterator Concept] | |
81 | ||
82 | The *Lvalue Iterator* concept adds the requirement that the return | |
83 | type of `operator*` type be a reference to the value type of the | |
84 | iterator. | |
85 | ||
86 | [table Lvalue Iterator Requirements | |
87 | [ | |
88 | [Expression] | |
89 | [Return Type] | |
90 | [Note/Assertion] | |
91 | ] | |
92 | [ | |
93 | [`*a` ] | |
94 | [`T&` ] | |
95 | [ | |
96 | `T` is *cv* `iterator_traits<X>::value_type` where *cv* is an optional cv-qualification. | |
97 | pre: `a` is dereferenceable. If `a == b` then `*a` is equivalent to `*b`. | |
98 | ] | |
99 | ] | |
100 | ] | |
101 | ||
102 | [endsect] | |
103 | ||
104 | [section:concepts_traversal Traversal] | |
105 | ||
106 | [h2 Incrementable Iterator Concept] | |
107 | ||
108 | ||
109 | A class or built-in type `X` models the *Incrementable Iterator* | |
110 | concept if, in addition to `X` being Assignable and Copy | |
111 | Constructible, the following expressions are valid and respect the | |
112 | stated semantics. | |
113 | ||
114 | ||
115 | [table Incrementable Iterator Requirements (in addition to Assignable, Copy Constructible) | |
116 | [ | |
117 | [Expression ] | |
118 | [Return Type] | |
119 | [Assertion/Semantics ] | |
120 | ] | |
121 | [ | |
122 | [`++r` ] | |
123 | [`X&` ] | |
124 | [`&r == &++r`] | |
125 | ] | |
126 | [ | |
127 | [`r++` ] | |
128 | [`X` ] | |
129 | [`` | |
130 | { | |
131 | X tmp = r; | |
132 | ++r; | |
133 | return tmp; | |
134 | } | |
135 | ``] | |
136 | ] | |
137 | [ | |
138 | [`iterator_traversal<X>::type`] | |
139 | [Convertible to `incrementable_traversal_tag`] | |
140 | [] | |
141 | ] | |
142 | ] | |
143 | ||
144 | [h2 Single Pass Iterator Concept] | |
145 | ||
146 | A class or built-in type `X` models the *Single Pass Iterator* | |
147 | concept if the following expressions are valid and respect the stated | |
148 | semantics. | |
149 | ||
150 | [table Single Pass Iterator Requirements (in addition to Incrementable Iterator and Equality Comparable) | |
151 | [ | |
152 | [Expression] | |
153 | [Return Type] | |
154 | [Assertion/Semantics / Pre-/Post-condition] | |
155 | ] | |
156 | [ | |
157 | [`++r`] | |
158 | [`X&`] | |
159 | [pre:[br]`r` is dereferenceable;[br]post:[br]`r` is dereferenceable or[br]`r` is past-the-end] | |
160 | ] | |
161 | [ | |
162 | [`a == b`] | |
163 | [convertible to `bool`] | |
164 | [`==` is an equivalence relation over its domain] | |
165 | ] | |
166 | [ | |
167 | [`a != b`] | |
168 | [convertible to `bool`] | |
169 | [`!(a == b)`] | |
170 | ] | |
171 | [ | |
172 | [`iterator_traversal<X>::type`] | |
173 | [Convertible to`single_pass_traversal_tag`] | |
174 | [] | |
175 | ] | |
176 | ] | |
177 | ||
178 | ||
179 | [h2 Forward Traversal Concept] | |
180 | ||
181 | A class or built-in type `X` models the *Forward Traversal* | |
182 | concept if, in addition to `X` meeting the requirements of Default | |
183 | Constructible and Single Pass Iterator, the following expressions are | |
184 | valid and respect the stated semantics. | |
185 | ||
186 | [table Forward Traversal Iterator Requirements (in addition to Default Constructible and Single Pass Iterator) | |
187 | [ | |
188 | [Expression] | |
189 | [Return Type] | |
190 | [Assertion/Note] | |
191 | ] | |
192 | [ | |
193 | [`X u;`] | |
194 | [`X&`] | |
195 | [note: `u` may have a singular value.] | |
196 | ] | |
197 | [ | |
198 | [`++r`] | |
199 | [`X&`] | |
200 | [`r == s` and `r` is dereferenceable implies `++r == ++s.`] | |
201 | ] | |
202 | [ | |
203 | [`iterator_traits<X>::difference_type`] | |
204 | [A signed integral type representing the distance between iterators] | |
205 | [] | |
206 | ] | |
207 | [ | |
208 | [`iterator_traversal<X>::type`] | |
209 | [Convertible to `forward_traversal_tag`] | |
210 | [] | |
211 | ] | |
212 | ] | |
213 | ||
214 | [h2 Bidirectional Traversal Concept] | |
215 | ||
216 | A class or built-in type `X` models the *Bidirectional Traversal* | |
217 | concept if, in addition to `X` meeting the requirements of Forward | |
218 | Traversal Iterator, the following expressions are valid and respect | |
219 | the stated semantics. | |
220 | ||
221 | [table Bidirectional Traversal Iterator Requirements (in addition to Forward Traversal Iterator) | |
222 | [ | |
223 | [Expression] | |
224 | [Return Type] | |
225 | [Assertion/Semantics/Pre-/Post-condition] | |
226 | ] | |
227 | [ | |
228 | [`--r`] | |
229 | [`X&`] | |
230 | [pre: there exists `s` such that `r == ++s`.[br] post: `s` is dereferenceable. `--(++r) == r`. `--r == --s` implies `r == s`. `&r == &--r`.] | |
231 | ] | |
232 | [ | |
233 | [`r--`] | |
234 | [convertible to `const X&`] | |
235 | [`` | |
236 | { | |
237 | X tmp = r; | |
238 | --r; | |
239 | return tmp; | |
240 | } | |
241 | ``] | |
242 | ] | |
243 | [ | |
244 | [`iterator_traversal<X>::type`] | |
245 | [Convertible to `bidirectional_traversal_tag`] | |
246 | [] | |
247 | ] | |
248 | ] | |
249 | ||
250 | [h2 Random Access Traversal Concept] | |
251 | ||
252 | A class or built-in type `X` models the *Random Access Traversal* | |
253 | concept if the following expressions are valid and respect the stated | |
254 | semantics. In the table below, `Distance` is | |
255 | `iterator_traits<X>::difference_type` and `n` represents a | |
256 | constant object of type `Distance`. | |
257 | ||
258 | [table Random Access Traversal Iterator Requirements (in addition to Bidirectional Traversal) | |
259 | [ | |
260 | [Expression] | |
261 | [Return Type] | |
262 | [Operational Semantics] | |
263 | [Assertion/Precondition] | |
264 | ] | |
265 | [ | |
266 | [`r += n`] | |
267 | [ `X&`] | |
268 | [`` | |
269 | { | |
270 | Distance m = n; | |
271 | if (m >= 0) | |
272 | while (m--) | |
273 | ++r; | |
274 | else | |
275 | while (m++) | |
276 | --r; | |
277 | return r; | |
278 | } | |
279 | ``] | |
280 | [ ] | |
281 | ] | |
282 | [ | |
283 | [`a + n`, `n + a`] | |
284 | [`X`] | |
285 | [`` | |
286 | { | |
287 | X tmp = a; | |
288 | return tmp+= n; | |
289 | } | |
290 | ``] | |
291 | [] | |
292 | ] | |
293 | [ | |
294 | [`r -= n`] | |
295 | [`X&`] | |
296 | [`return r += -n`] | |
297 | [] | |
298 | ] | |
299 | [ | |
300 | [`a - n`] | |
301 | [`X`] | |
302 | [`` | |
303 | { | |
304 | X tmp = a; | |
305 | return tmp-= n; | |
306 | } | |
307 | ``] | |
308 | [] | |
309 | ] | |
310 | [ | |
311 | [`b - a`] | |
312 | [`Distance`] | |
313 | [`a < b ? distance(a,b) : -distance(b,a)`] | |
314 | [pre: there exists a value `n` of `Distance` such that `a + n == b`. `b == a + (b - a)`.] | |
315 | ] | |
316 | [ | |
317 | [`a\[n\]`] | |
318 | [convertible to T] | |
319 | [`*(a + n)`] | |
320 | [pre: a is a *Readable Iterator*] | |
321 | ] | |
322 | [ | |
323 | [`a\[n\] = v`] | |
324 | [convertible to T] | |
325 | [`*(a + n) = v`] | |
326 | [pre: a is a *Writable iterator*] | |
327 | ] | |
328 | [ | |
329 | [`a < b`] | |
330 | [convertible to `bool`] | |
331 | [`b - a > 0`] | |
332 | [`<` is a total ordering relation] | |
333 | ] | |
334 | [ | |
335 | [`a > b`] | |
336 | [convertible to `bool`] | |
337 | [`b < a`] | |
338 | [`>` is a total ordering relation] | |
339 | ] | |
340 | [ | |
341 | [`a >= b`] | |
342 | [convertible to `bool`] | |
343 | [`!(a < b)`] | |
344 | [] | |
345 | ] | |
346 | [ | |
347 | [`a <= b`] | |
348 | [convertible to `bool`] | |
349 | [`!(a > b)`] | |
350 | [] | |
351 | ] | |
352 | [ | |
353 | [`iterator_traversal<X>::type`] | |
354 | [convertible to `random_access_traversal_tag`] | |
355 | [] | |
356 | [] | |
357 | ] | |
358 | ] | |
359 | ||
360 | [endsect] | |
361 | ||
362 | [endsect] |