]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | .. Distributed under the Boost |
2 | .. Software License, Version 1.0. (See accompanying | |
3 | .. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
4 | ||
5 | ++++++++++++++++++++++ | |
6 | New Iterator Concepts | |
7 | ++++++++++++++++++++++ | |
8 | ||
9 | .. Version 1.25 of this ReStructuredText document is the same as | |
10 | n1550_, the paper accepted by the LWG. | |
11 | ||
12 | :Author: David Abrahams, Jeremy Siek, Thomas Witt | |
13 | :Contact: dave@boost-consulting.com, jsiek@osl.iu.edu, witt@styleadvisor.com | |
14 | :organization: `Boost Consulting`_, Indiana University `Open Systems | |
15 | Lab`_, `Zephyr Associates, Inc.`_ | |
16 | :date: $Date$ | |
17 | ||
18 | :Number: This is a revised version of n1550_\ =03-0133, which was | |
19 | accepted for Technical Report 1 by the C++ standard | |
20 | committee's library working group. This proposal is a | |
21 | revision of paper n1297_, n1477_, and n1531_. | |
22 | ||
23 | :copyright: Copyright David Abrahams, Jeremy Siek, and Thomas Witt | |
24 | 2003. | |
25 | ||
26 | .. _`Boost Consulting`: http://www.boost-consulting.com | |
27 | .. _`Open Systems Lab`: http://www.osl.iu.edu | |
28 | .. _`Zephyr Associates, Inc.`: http://www.styleadvisor.com | |
29 | ||
30 | .. _`Institute for Transport Railway Operation and Construction`: | |
31 | http://www.ive.uni-hannover.de | |
32 | ||
33 | :Abstract: We propose a new system of iterator concepts that treat | |
34 | access and positioning independently. This allows the | |
35 | concepts to more closely match the requirements | |
36 | of algorithms and provides better categorizations | |
37 | of iterators that are used in practice. | |
38 | ||
39 | .. contents:: Table of Contents | |
40 | ||
41 | .. _n1297: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1297.html | |
42 | .. _n1477: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1477.html | |
43 | .. _n1531: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1531.html | |
44 | .. _n1550: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1550.htm | |
45 | ||
46 | ============ | |
47 | Motivation | |
48 | ============ | |
49 | ||
50 | The standard iterator categories and requirements are flawed because | |
51 | they use a single hierarchy of concepts to address two orthogonal | |
52 | issues: *iterator traversal* and *value access*. As a result, many | |
53 | algorithms with requirements expressed in terms of the iterator | |
54 | categories are too strict. Also, many real-world iterators can not be | |
55 | accurately categorized. A proxy-based iterator with random-access | |
56 | traversal, for example, may only legally have a category of "input | |
57 | iterator", so generic algorithms are unable to take advantage of its | |
58 | random-access capabilities. The current iterator concept hierarchy is | |
59 | geared towards iterator traversal (hence the category names), while | |
60 | requirements that address value access sneak in at various places. The | |
61 | following table gives a summary of the current value access | |
62 | requirements in the iterator categories. | |
63 | ||
64 | +------------------------------------------------------------------------------+ | |
65 | |Value Access Requirements in Existing Iterator Categories | | |
66 | +========================+=====================================================+ | |
67 | |Output Iterator |``*i = a`` | | |
68 | +------------------------+-----------------------------------------------------+ | |
69 | |Input Iterator |``*i`` is convertible to ``T`` | | |
70 | +------------------------+-----------------------------------------------------+ | |
71 | |Forward Iterator |``*i`` is ``T&`` (or ``const T&`` once `issue 200`_ | | |
72 | | |is resolved) | | |
73 | +------------------------+-----------------------------------------------------+ | |
74 | |Random Access Iterator |``i[n]`` is convertible to ``T`` (also ``i[n] = t`` | | |
75 | | |is required for mutable iterators once `issue 299`_ | | |
76 | | |is resolved) | | |
77 | +------------------------+-----------------------------------------------------+ | |
78 | ||
79 | .. _issue 200: http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#200 | |
80 | .. _issue 299: http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#299 | |
81 | ||
82 | ||
83 | Because iterator traversal and value access are mixed together in a | |
84 | single hierarchy, many useful iterators can not be appropriately | |
85 | categorized. For example, ``vector<bool>::iterator`` is almost a | |
86 | random access iterator, but the return type is not ``bool&`` (see | |
87 | `issue 96`_ and Herb Sutter's paper J16/99-0008 = WG21 | |
88 | N1185). Therefore, the iterators of ``vector<bool>`` only meet the | |
89 | requirements of input iterator and output iterator. This is so | |
90 | nonintuitive that the C++ standard contradicts itself on this point. | |
91 | In paragraph 23.2.4/1 it says that a ``vector`` is a sequence that | |
92 | supports random access iterators. | |
93 | ||
94 | .. _issue 96: http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#96 | |
95 | ||
96 | Another difficult-to-categorize iterator is the transform iterator, an | |
97 | adaptor which applies a unary function object to the dereferenced | |
98 | value of the some underlying iterator (see `transform_iterator`_). | |
99 | For unary functions such as ``times``, the return type of | |
100 | ``operator*`` clearly needs to be the ``result_type`` of the function | |
101 | object, which is typically not a reference. Because random access | |
102 | iterators are required to return lvalues from ``operator*``, if you | |
103 | wrap ``int*`` with a transform iterator, you do not get a random | |
104 | access iterator as might be expected, but an input iterator. | |
105 | ||
106 | .. _`transform_iterator`: http://www.boost.org/libs/utility/transform_iterator.htm | |
107 | ||
108 | A third example is found in the vertex and edge iterators of the | |
109 | `Boost Graph Library`_. These iterators return vertex and edge | |
110 | descriptors, which are lightweight handles created on-the-fly. They | |
111 | must be returned by-value. As a result, their current standard | |
112 | iterator category is ``input_iterator_tag``, which means that, | |
113 | strictly speaking, you could not use these iterators with algorithms | |
114 | like ``min_element()``. As a temporary solution, the concept | |
115 | `Multi-Pass Input Iterator`_ was introduced to describe the vertex and | |
116 | edge descriptors, but as the design notes for the concept suggest, a | |
117 | better solution is needed. | |
118 | ||
119 | .. _Boost Graph Library: http://www.boost.org/libs/graph/doc/table_of_contents.html | |
120 | .. _Multi-Pass Input Iterator: http://www.boost.org/libs/utility/MultiPassInputIterator.html | |
121 | ||
122 | In short, there are many useful iterators that do not fit into the | |
123 | current standard iterator categories. As a result, the following bad | |
124 | things happen: | |
125 | ||
126 | - Iterators are often mis-categorized. | |
127 | ||
128 | - Algorithm requirements are more strict than necessary, because they | |
129 | cannot separate the need for random access or bidirectional | |
130 | traversal from the need for a true reference return type. | |
131 | ||
132 | ||
133 | ======================== | |
134 | Impact on the Standard | |
135 | ======================== | |
136 | ||
137 | This proposal for TR1 is a pure extension. Further, the new iterator | |
138 | concepts are backward-compatible with the old iterator requirements, | |
139 | and old iterators are forward-compatible with the new iterator | |
140 | concepts. That is to say, iterators that satisfy the old requirements | |
141 | also satisfy appropriate concepts in the new system, and iterators | |
142 | modeling the new concepts will automatically satisfy the appropriate | |
143 | old requirements. | |
144 | ||
145 | .. I think we need to say something about the resolution to allow | |
146 | convertibility to any of the old-style tags as a TR issue (hope it | |
147 | made it). -DWA | |
148 | ||
149 | .. Hmm, not sure I understand. Are you talking about whether a | |
150 | standards conforming input iterator is allowed to have | |
151 | a tag that is not input_iterator_tag but that | |
152 | is convertible to input_iterator_tag? -JGS | |
153 | ||
154 | Possible (but not proposed) Changes to the Working Paper | |
155 | ======================================================== | |
156 | ||
157 | The extensions in this paper suggest several changes we might make | |
158 | to the working paper for the next standard. These changes are not | |
159 | a formal part of this proposal for TR1. | |
160 | ||
161 | Changes to Algorithm Requirements | |
162 | +++++++++++++++++++++++++++++++++ | |
163 | ||
164 | The algorithms in the standard library could benefit from the new | |
165 | iterator concepts because the new concepts provide a more accurate way | |
166 | to express their type requirements. The result is algorithms that are | |
167 | usable in more situations and have fewer type requirements. | |
168 | ||
169 | For the next working paper (but not for TR1), the committee should | |
170 | consider the following changes to the type requirements of algorithms. | |
171 | These changes are phrased as textual substitutions, listing the | |
172 | algorithms to which each textual substitution applies. | |
173 | ||
174 | Forward Iterator -> Forward Traversal Iterator and Readable Iterator | |
175 | ||
176 | ``find_end, adjacent_find, search, search_n, rotate_copy, | |
177 | lower_bound, upper_bound, equal_range, binary_search, | |
178 | min_element, max_element`` | |
179 | ||
180 | Forward Iterator (1) -> Single Pass Iterator and Readable Iterator, | |
181 | Forward Iterator (2) -> Forward Traversal Iterator and Readable Iterator | |
182 | ||
183 | ``find_first_of`` | |
184 | ||
185 | Forward Iterator -> Readable Iterator and Writable Iterator | |
186 | ||
187 | ``iter_swap`` | |
188 | ||
189 | Forward Iterator -> Single Pass Iterator and Writable Iterator | |
190 | ||
191 | ``fill, generate`` | |
192 | ||
193 | Forward Iterator -> Forward Traversal Iterator and Swappable Iterator | |
194 | ||
195 | ``rotate`` | |
196 | ||
197 | Forward Iterator (1) -> Swappable Iterator and Single Pass Iterator, | |
198 | Forward Iterator (2) -> Swappable Iterator and Incrementable Iterator | |
199 | ||
200 | ``swap_ranges`` | |
201 | ||
202 | Forward Iterator -> Forward Traversal Iterator and Readable Iterator and Writable Iterator | |
203 | ``remove, remove_if, unique`` | |
204 | ||
205 | Forward Iterator -> Single Pass Iterator and Readable Iterator and Writable Iterator | |
206 | ||
207 | ``replace, replace_if`` | |
208 | ||
209 | Bidirectional Iterator -> Bidirectional Traversal Iterator and Swappable Iterator | |
210 | ``reverse`` | |
211 | ||
212 | Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable and Swappable Iterator | |
213 | ``partition`` | |
214 | ||
215 | Bidirectional Iterator (1) -> Bidirectional Traversal Iterator and Readable Iterator, | |
216 | Bidirectional Iterator (2) -> Bidirectional Traversal Iterator and Writable Iterator | |
217 | ||
218 | ``copy_backwards`` | |
219 | ||
220 | Bidirectional Iterator -> Bidirectional Traversal Iterator and Swappable Iterator and Readable Iterator | |
221 | ``next_permutation, prev_permutation`` | |
222 | ||
223 | Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator and Writable Iterator | |
224 | ``stable_partition, inplace_merge`` | |
225 | ||
226 | Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator | |
227 | ``reverse_copy`` | |
228 | ||
229 | Random Access Iterator -> Random Access Traversal Iterator and Readable and Writable Iterator | |
230 | ``random_shuffle, sort, stable_sort, partial_sort, nth_element, push_heap, pop_heap | |
231 | make_heap, sort_heap`` | |
232 | ||
233 | Input Iterator (2) -> Incrementable Iterator and Readable Iterator | |
234 | ``equal, mismatch`` | |
235 | ||
236 | Input Iterator (2) -> Incrementable Iterator and Readable Iterator | |
237 | ``transform`` | |
238 | ||
239 | Deprecations | |
240 | ++++++++++++ | |
241 | ||
242 | For the next working paper (but not for TR1), the committee should | |
243 | consider deprecating the old iterator tags, and | |
244 | std::iterator_traits, since it will be superceded by individual | |
245 | traits metafunctions. | |
246 | ||
247 | ``vector<bool>`` | |
248 | ++++++++++++++++ | |
249 | ||
250 | For the next working paper (but not for TR1), the committee should | |
251 | consider reclassifying ``vector<bool>::iterator`` as a Random | |
252 | Access Traversal Iterator and Readable Iterator and Writable | |
253 | Iterator. | |
254 | ||
255 | ======== | |
256 | Design | |
257 | ======== | |
258 | ||
259 | The iterator requirements are to be separated into two groups. One set | |
260 | of concepts handles the syntax and semantics of value access: | |
261 | ||
262 | - Readable Iterator | |
263 | - Writable Iterator | |
264 | - Swappable Iterator | |
265 | - Lvalue Iterator | |
266 | ||
267 | The access concepts describe requirements related to ``operator*`` and | |
268 | ``operator->``, including the ``value_type``, ``reference``, and | |
269 | ``pointer`` associated types. | |
270 | ||
271 | The other set of concepts handles traversal: | |
272 | ||
273 | - Incrementable Iterator | |
274 | - Single Pass Iterator | |
275 | - Forward Traversal Iterator | |
276 | - Bidirectional Traversal Iterator | |
277 | - Random Access Traversal Iterator | |
278 | ||
279 | The refinement relationships for the traversal concepts are in the | |
280 | following diagram. | |
281 | ||
282 | .. image:: traversal.png | |
283 | ||
284 | In addition to the iterator movement operators, such as | |
285 | ``operator++``, the traversal concepts also include requirements on | |
286 | position comparison such as ``operator==`` and ``operator<``. The | |
287 | reason for the fine grain slicing of the concepts into the | |
288 | Incrementable and Single Pass is to provide concepts that are exact | |
289 | matches with the original input and output iterator requirements. | |
290 | ||
291 | This proposal also includes a concept for specifying when an iterator | |
292 | is interoperable with another iterator, in the sense that ``int*`` is | |
293 | interoperable with ``int const*``. | |
294 | ||
295 | - Interoperable Iterators | |
296 | ||
297 | ||
298 | The relationship between the new iterator concepts and the old are | |
299 | given in the following diagram. | |
300 | ||
301 | .. image:: oldeqnew.png | |
302 | ||
303 | Like the old iterator requirements, we provide tags for purposes of | |
304 | dispatching based on the traversal concepts. The tags are related via | |
305 | inheritance so that a tag is convertible to another tag if the concept | |
306 | associated with the first tag is a refinement of the second tag. | |
307 | ||
308 | Our design reuses ``iterator_traits<Iter>::iterator_category`` to | |
309 | indicate an iterator's traversal capability. To specify | |
310 | capabilities not captured by any old-style iterator category, an | |
311 | iterator designer can use an ``iterator_category`` type that is | |
312 | convertible to both the the most-derived old iterator category tag | |
313 | which fits, and the appropriate new iterator traversal tag. | |
314 | ||
315 | .. dwa2003/1/2: Note that we are not *requiring* convertibility to | |
316 | a new-style traversal tag in order to meet new concepts. | |
317 | Old-style iterators still fit, after all. | |
318 | ||
319 | We do not provide tags for the purposes of dispatching based on the | |
320 | access concepts, in part because we could not find a way to | |
321 | automatically infer the right access tags for old-style iterators. | |
322 | An iterator's writability may be dependent on the assignability of | |
323 | its ``value_type`` and there's no known way to detect whether an | |
324 | arbitrary type is assignable. Fortunately, the need for | |
325 | dispatching based on access capability is not as great as the need | |
326 | for dispatching based on traversal capability. | |
327 | ||
328 | A difficult design decision concerned the ``operator[]``. The direct | |
329 | approach for specifying ``operator[]`` would have a return type of | |
330 | ``reference``; the same as ``operator*``. However, going in this | |
331 | direction would mean that an iterator satisfying the old Random Access | |
332 | Iterator requirements would not necessarily be a model of Readable or | |
333 | Writable Lvalue Iterator. Instead we have chosen a design that | |
334 | matches the preferred resolution of `issue 299`_: ``operator[]`` is | |
335 | only required to return something convertible to the ``value_type`` | |
336 | (for a Readable Iterator), and is required to support assignment | |
337 | ``i[n] = t`` (for a Writable Iterator). | |
338 | ||
339 | ||
340 | =============== | |
341 | Proposed Text | |
342 | =============== | |
343 | ||
344 | Addition to [lib.iterator.requirements] | |
345 | ======================================= | |
346 | ||
347 | Iterator Value Access Concepts [lib.iterator.value.access] | |
348 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ | |
349 | ||
350 | In the tables below, ``X`` is an iterator type, ``a`` is a constant | |
351 | object of type ``X``, ``R`` is | |
352 | ``std::iterator_traits<X>::reference``, ``T`` is | |
353 | ``std::iterator_traits<X>::value_type``, and ``v`` is a constant | |
354 | object of type ``T``. | |
355 | ||
356 | .. _Readable Iterator: | |
357 | ||
358 | Readable Iterators [lib.readable.iterators] | |
359 | ------------------------------------------- | |
360 | ||
361 | A class or built-in type ``X`` models the *Readable Iterator* concept | |
362 | for value type ``T`` if, in addition to ``X`` being Assignable and | |
363 | Copy Constructible, the following expressions are valid and respect | |
364 | the stated semantics. ``U`` is the type of any specified member of | |
365 | type ``T``. | |
366 | ||
367 | +-----------------------------------------------------------------------------------------------------------------------------+ | |
368 | |Readable Iterator Requirements (in addition to Assignable and Copy Constructible) | | |
369 | +-----------------------------------+------------------------+----------------------------------------------------------------+ | |
370 | |Expression |Return Type |Note/Precondition | | |
371 | +===================================+========================+================================================================+ | |
372 | |``iterator_traits<X>::value_type`` |``T`` |Any non-reference, | | |
373 | | | |non-cv-qualified type | | |
374 | +-----------------------------------+------------------------+----------------------------------------------------------------+ | |
375 | |``*a`` | Convertible to ``T`` |pre: ``a`` is dereferenceable. If ``a == b`` then ``*a`` | | |
376 | | | | is equivalent to ``*b``. | | |
377 | +-----------------------------------+------------------------+----------------------------------------------------------------+ | |
378 | |``a->m`` |``U&`` |pre: ``pre: (*a).m`` is well-defined. Equivalent to ``(*a).m``. | | |
379 | +-----------------------------------+------------------------+----------------------------------------------------------------+ | |
380 | ||
381 | .. We won't say anything about iterator_traits<X>::reference until the DR is resolved. -JGS | |
382 | ||
383 | .. _Writable Iterator: | |
384 | ||
385 | Writable Iterators [lib.writable.iterators] | |
386 | ------------------------------------------- | |
387 | ||
388 | A class or built-in type ``X`` models the *Writable Iterator* concept | |
389 | if, in addition to ``X`` being Copy Constructible, the following | |
390 | expressions are valid and respect the stated semantics. Writable | |
391 | Iterators have an associated *set of value types*. | |
392 | ||
393 | +---------------------------------------------------------------------+ | |
394 | |Writable Iterator Requirements (in addition to Copy Constructible) | | |
395 | +-------------------------+--------------+----------------------------+ | |
396 | |Expression |Return Type |Precondition | | |
397 | +=========================+==============+============================+ | |
398 | |``*a = o`` | | pre: The type of ``o`` | | |
399 | | | | is in the set of | | |
400 | | | | value types of ``X`` | | |
401 | +-------------------------+--------------+----------------------------+ | |
402 | ||
403 | Swappable Iterators [lib.swappable.iterators] | |
404 | --------------------------------------------- | |
405 | ||
406 | A class or built-in type ``X`` models the *Swappable Iterator* concept | |
407 | if, in addition to ``X`` being Copy Constructible, the following | |
408 | expressions are valid and respect the stated semantics. | |
409 | ||
410 | +---------------------------------------------------------------------+ | |
411 | |Swappable Iterator Requirements (in addition to Copy Constructible) | | |
412 | +-------------------------+-------------+-----------------------------+ | |
413 | |Expression |Return Type |Postcondition | | |
414 | +=========================+=============+=============================+ | |
415 | |``iter_swap(a, b)`` |``void`` |the pointed to values are | | |
416 | | | |exchanged | | |
417 | +-------------------------+-------------+-----------------------------+ | |
418 | ||
419 | [*Note:* An iterator that is a model of the `Readable Iterator`_ and | |
420 | `Writable Iterator`_ concepts is also a model of *Swappable | |
421 | Iterator*. *--end note*] | |
422 | ||
423 | ||
424 | Lvalue Iterators [lib.lvalue.iterators] | |
425 | --------------------------------------- | |
426 | ||
427 | The *Lvalue Iterator* concept adds the requirement that the return | |
428 | type of ``operator*`` type be a reference to the value type of the | |
429 | iterator. | |
430 | ||
431 | +-------------------------------------------------------------+ | |
432 | | Lvalue Iterator Requirements | | |
433 | +-------------+-----------+-----------------------------------+ | |
434 | |Expression |Return Type|Note/Assertion | | |
435 | +=============+===========+===================================+ | |
436 | |``*a`` | ``T&`` |``T`` is *cv* | | |
437 | | | |``iterator_traits<X>::value_type`` | | |
438 | | | |where *cv* is an optional | | |
439 | | | |cv-qualification. pre: ``a`` is | | |
440 | | | |dereferenceable. | | |
441 | +-------------+-----------+-----------------------------------+ | |
442 | ||
443 | If ``X`` is a `Writable Iterator`_ then ``a == b`` if and only if | |
444 | ``*a`` is the same object as ``*b``. If ``X`` is a `Readable | |
445 | Iterator`_ then ``a == b`` implies ``*a`` is the same object as | |
446 | ``*b``. | |
447 | ||
448 | ||
449 | Iterator Traversal Concepts [lib.iterator.traversal] | |
450 | ++++++++++++++++++++++++++++++++++++++++++++++++++++ | |
451 | ||
452 | In the tables below, ``X`` is an iterator type, ``a`` and ``b`` are | |
453 | constant objects of type ``X``, ``r`` and ``s`` are mutable objects of | |
454 | type ``X``, ``T`` is ``std::iterator_traits<X>::value_type``, and | |
455 | ``v`` is a constant object of type ``T``. | |
456 | ||
457 | Incrementable Iterators [lib.incrementable.iterators] | |
458 | ----------------------------------------------------- | |
459 | ||
460 | A class or built-in type ``X`` models the *Incrementable Iterator* | |
461 | concept if, in addition to ``X`` being Assignable and Copy | |
462 | Constructible, the following expressions are valid and respect the | |
463 | stated semantics. | |
464 | ||
465 | +------------------------------------------------------------------------------------+ | |
466 | |Incrementable Iterator Requirements (in addition to Assignable, Copy Constructible) | | |
467 | | | | |
468 | +--------------------------------+-------------------------------+-------------------+ | |
469 | |Expression |Return Type |Assertion | | |
470 | +================================+===============================+===================+ | |
471 | |``++r`` |``X&`` |``&r == &++r`` | | |
472 | +--------------------------------+-------------------------------+-------------------+ | |
473 | |``r++`` | | | | |
474 | +--------------------------------+-------------------------------+-------------------+ | |
475 | |``*r++`` | | | | |
476 | +--------------------------------+-------------------------------+-------------------+ | |
477 | |``iterator_traversal<X>::type`` |Convertible to | | | |
478 | | |``incrementable_traversal_tag``| | | |
479 | +--------------------------------+-------------------------------+-------------------+ | |
480 | ||
481 | ||
482 | If ``X`` is a `Writable Iterator`_ then ``X a(r++);`` is equivalent | |
483 | to ``X a(r); ++r;`` and ``*r++ = o`` is equivalent | |
484 | to ``*r = o; ++r``. | |
485 | If ``X`` is a `Readable Iterator`_ then ``T z(*r++);`` is equivalent | |
486 | to ``T z(*r); ++r;``. | |
487 | ||
488 | .. TR1: incrementable_iterator_tag changed to | |
489 | incrementable_traversal_tag for consistency. | |
490 | ||
491 | Single Pass Iterators [lib.single.pass.iterators] | |
492 | ------------------------------------------------- | |
493 | ||
494 | A class or built-in type ``X`` models the *Single Pass Iterator* | |
495 | concept if the following expressions are valid and respect the stated | |
496 | semantics. | |
497 | ||
498 | ||
499 | +----------------------------------------------------------------------------------------------------------------+ | |
500 | |Single Pass Iterator Requirements (in addition to Incrementable Iterator and Equality Comparable) | | |
501 | | | | |
502 | +----------------------------------------+-----------------------------+-------------+---------------------------+ | |
503 | |Expression |Return Type | Operational |Assertion/ | | |
504 | | | | Semantics |Pre-/Post-condition | | |
505 | +========================================+=============================+=============+===========================+ | |
506 | |``++r`` |``X&`` | |pre: ``r`` is | | |
507 | | | | |dereferenceable; post: | | |
508 | | | | |``r`` is dereferenceable or| | |
509 | | | | |``r`` is past-the-end | | |
510 | +----------------------------------------+-----------------------------+-------------+---------------------------+ | |
511 | |``a == b`` |convertible to ``bool`` | |``==`` is an equivalence | | |
512 | | | | |relation over its domain | | |
513 | +----------------------------------------+-----------------------------+-------------+---------------------------+ | |
514 | |``a != b`` |convertible to ``bool`` |``!(a == b)``| | | |
515 | +----------------------------------------+-----------------------------+-------------+---------------------------+ | |
516 | |``iterator_traits<X>::difference_type`` |A signed integral type | | | | |
517 | | |representing the distance | | | | |
518 | | |between iterators | | | | |
519 | +----------------------------------------+-----------------------------+-------------+---------------------------+ | |
520 | |``iterator_traversal<X>::type`` |Convertible to | | | | |
521 | | |``single_pass_traversal_tag``| | | | |
522 | +----------------------------------------+-----------------------------+-------------+---------------------------+ | |
523 | ||
524 | .. TR1: single_pass_iterator_tag changed to | |
525 | single_pass_traversal_tag for consistency | |
526 | ||
527 | ||
528 | Forward Traversal Iterators [lib.forward.traversal.iterators] | |
529 | ------------------------------------------------------------- | |
530 | ||
531 | A class or built-in type ``X`` models the *Forward Traversal Iterator* | |
532 | concept if, in addition to ``X`` meeting the requirements of Default | |
533 | Constructible and Single Pass Iterator, the following expressions are | |
534 | valid and respect the stated semantics. | |
535 | ||
536 | +--------------------------------------------------------------------------------------------------------+ | |
537 | |Forward Traversal Iterator Requirements (in addition to Default Constructible and Single Pass Iterator) | | |
538 | +---------------------------------------+-----------------------------------+----------------------------+ | |
539 | |Expression |Return Type |Assertion/Note | | |
540 | +=======================================+===================================+============================+ | |
541 | |``X u;`` |``X&`` |note: ``u`` may have a | | |
542 | | | |singular value. | | |
543 | +---------------------------------------+-----------------------------------+----------------------------+ | |
544 | |``++r`` |``X&`` |``r == s`` and ``r`` is | | |
545 | | | |dereferenceable implies | | |
546 | | | |``++r == ++s.`` | | |
547 | +---------------------------------------+-----------------------------------+----------------------------+ | |
548 | |``iterator_traversal<X>::type`` |Convertible to | | | |
549 | | |``forward_traversal_tag`` | | | |
550 | +---------------------------------------+-----------------------------------+----------------------------+ | |
551 | ||
552 | ||
553 | ||
554 | .. TR1: forward_traversal_iterator_tag changed to | |
555 | forward_traversal_tag for consistency | |
556 | ||
557 | ||
558 | Bidirectional Traversal Iterators [lib.bidirectional.traversal.iterators] | |
559 | ------------------------------------------------------------------------- | |
560 | ||
561 | A class or built-in type ``X`` models the *Bidirectional Traversal | |
562 | Iterator* concept if, in addition to ``X`` meeting the requirements of | |
563 | Forward Traversal Iterator, the following expressions are valid and | |
564 | respect the stated semantics. | |
565 | ||
566 | +-----------------------------------------------------------------------------------------------------+ | |
567 | |Bidirectional Traversal Iterator Requirements (in addition to Forward Traversal | | |
568 | |Iterator) | | |
569 | +--------------------------------+-------------------------------+--------------+---------------------+ | |
570 | |Expression |Return Type | Operational |Assertion/ | | |
571 | | | | Semantics |Pre-/Post-condition | | |
572 | +================================+===============================+==============+=====================+ | |
573 | |``--r`` |``X&`` | |pre: there exists | | |
574 | | | | |``s`` such that ``r | | |
575 | | | | |== ++s``. post: | | |
576 | | | | |``s`` is | | |
577 | | | | |dereferenceable. | | |
578 | | | | | | | |
579 | | | | |``++(--r) == r``. | | |
580 | | | | |``--r == --s`` | | |
581 | | | | |implies ``r == | | |
582 | | | | |s``. ``&r == &--r``. | | |
583 | +--------------------------------+-------------------------------+--------------+---------------------+ | |
584 | |``r--`` |convertible to ``const X&`` |:: | | | |
585 | | | | | | | |
586 | | | | { | | | |
587 | | | | X tmp = r; | | | |
588 | | | | --r; | | | |
589 | | | | return tmp;| | | |
590 | | | | } | | | |
591 | +--------------------------------+-------------------------------+--------------+---------------------+ | |
592 | |``iterator_traversal<X>::type`` |Convertible to | | | | |
593 | | |``bidirectional_traversal_tag``| | | | |
594 | | | | | | | |
595 | +--------------------------------+-------------------------------+--------------+---------------------+ | |
596 | ||
597 | .. TR1: bidirectional_traversal_iterator_tag changed to | |
598 | bidirectional_traversal_tag for consistency | |
599 | ||
600 | Random Access Traversal Iterators [lib.random.access.traversal.iterators] | |
601 | ------------------------------------------------------------------------- | |
602 | ||
603 | A class or built-in type ``X`` models the *Random Access Traversal | |
604 | Iterator* concept if the following expressions are valid and respect | |
605 | the stated semantics. In the table below, ``Distance`` is | |
606 | ``iterator_traits<X>::difference_type`` and ``n`` represents a | |
607 | constant object of type ``Distance``. | |
608 | ||
609 | +------------------------------------------------------------------------------------------------------------------+ | |
610 | |Random Access Traversal Iterator Requirements (in addition to Bidirectional Traversal Iterator) | | |
611 | +-------------------------------+---------------------------------+-------------------------+----------------------+ | |
612 | |Expression |Return Type |Operational Semantics |Assertion/ | | |
613 | | | | |Precondition | | |
614 | +===============================+=================================+=========================+======================+ | |
615 | |``r += n`` |``X&`` |:: | | | |
616 | | | | | | | |
617 | | | | { | | | |
618 | | | | Distance m = n; | | | |
619 | | | | if (m >= 0) | | | |
620 | | | | while (m--) | | | |
621 | | | | ++r; | | | |
622 | | | | else | | | |
623 | | | | while (m++) | | | |
624 | | | | --r; | | | |
625 | | | | return r; | | | |
626 | | | | } | | | |
627 | +-------------------------------+---------------------------------+-------------------------+----------------------+ | |
628 | |``a + n``, ``n + a`` |``X`` |``{ X tmp = a; return tmp| | | |
629 | | | |+= n; }`` | | | |
630 | | | | | | | |
631 | +-------------------------------+---------------------------------+-------------------------+----------------------+ | |
632 | |``r -= n`` |``X&`` |``return r += -n`` | | | |
633 | +-------------------------------+---------------------------------+-------------------------+----------------------+ | |
634 | |``a - n`` |``X`` |``{ X tmp = a; return tmp| | | |
635 | | | |-= n; }`` | | | |
636 | | | | | | | |
637 | +-------------------------------+---------------------------------+-------------------------+----------------------+ | |
638 | |``b - a`` |``Distance`` |``a < b ? distance(a,b) |pre: there exists a | | |
639 | | | |: -distance(b,a)`` |value ``n`` of | | |
640 | | | | |``Distance`` such that| | |
641 | | | | |``a + n == b``. ``b | | |
642 | | | | |== a + (b - a)``. | | |
643 | +-------------------------------+---------------------------------+-------------------------+----------------------+ | |
644 | |``a[n]`` |convertible to T |``*(a + n)`` |pre: a is a `Readable | | |
645 | | | | |Iterator`_ | | |
646 | +-------------------------------+---------------------------------+-------------------------+----------------------+ | |
647 | |``a[n] = v`` |convertible to T |``*(a + n) = v`` |pre: a is a `Writable | | |
648 | | | | |Iterator`_ | | |
649 | +-------------------------------+---------------------------------+-------------------------+----------------------+ | |
650 | |``a < b`` |convertible to ``bool`` |``b - a > 0`` |``<`` is a total | | |
651 | | | | |ordering relation | | |
652 | +-------------------------------+---------------------------------+-------------------------+----------------------+ | |
653 | |``a > b`` |convertible to ``bool`` |``b < a`` |``>`` is a total | | |
654 | | | | |ordering relation | | |
655 | +-------------------------------+---------------------------------+-------------------------+----------------------+ | |
656 | |``a >= b`` |convertible to ``bool`` |``!(a < b)`` | | | |
657 | +-------------------------------+---------------------------------+-------------------------+----------------------+ | |
658 | |``a <= b`` |convertible to ``bool`` |``!(a > b)`` | | | |
659 | +-------------------------------+---------------------------------+-------------------------+----------------------+ | |
660 | |``iterator_traversal<X>::type``|Convertible to | | | | |
661 | | |``random_access_traversal_tag`` | | | | |
662 | +-------------------------------+---------------------------------+-------------------------+----------------------+ | |
663 | ||
664 | .. TR1: random_access_traversal_iterator_tag changed to | |
665 | random_access_traversal_tag for consistency | |
666 | ||
667 | ||
668 | Interoperable Iterators [lib.interoperable.iterators] | |
669 | ----------------------------------------------------- | |
670 | ||
671 | A class or built-in type ``X`` that models Single Pass Iterator is | |
672 | *interoperable with* a class or built-in type ``Y`` that also models | |
673 | Single Pass Iterator if the following expressions are valid and | |
674 | respect the stated semantics. In the tables below, ``x`` is an object | |
675 | of type ``X``, ``y`` is an object of type ``Y``, ``Distance`` is | |
676 | ``iterator_traits<Y>::difference_type``, and ``n`` represents a | |
677 | constant object of type ``Distance``. | |
678 | ||
679 | +-----------+-----------------------+---------------------------------------------------+ | |
680 | |Expression |Return Type |Assertion/Precondition/Postcondition | | |
681 | +===========+=======================+===================================================+ | |
682 | |``y = x`` |``Y`` |post: ``y == x`` | | |
683 | +-----------+-----------------------+---------------------------------------------------+ | |
684 | |``Y(x)`` |``Y`` |post: ``Y(x) == x`` | | |
685 | +-----------+-----------------------+---------------------------------------------------+ | |
686 | |``x == y`` |convertible to ``bool``|``==`` is an equivalence relation over its domain. | | |
687 | +-----------+-----------------------+---------------------------------------------------+ | |
688 | |``y == x`` |convertible to ``bool``|``==`` is an equivalence relation over its domain. | | |
689 | +-----------+-----------------------+---------------------------------------------------+ | |
690 | |``x != y`` |convertible to ``bool``|``bool(a==b) != bool(a!=b)`` over its domain. | | |
691 | +-----------+-----------------------+---------------------------------------------------+ | |
692 | |``y != x`` |convertible to ``bool``|``bool(a==b) != bool(a!=b)`` over its domain. | | |
693 | +-----------+-----------------------+---------------------------------------------------+ | |
694 | ||
695 | If ``X`` and ``Y`` both model Random Access Traversal Iterator then | |
696 | the following additional requirements must be met. | |
697 | ||
698 | +-----------+-----------------------+---------------------+--------------------------------------+ | |
699 | |Expression |Return Type |Operational Semantics|Assertion/ Precondition | | |
700 | +===========+=======================+=====================+======================================+ | |
701 | |``x < y`` |convertible to ``bool``|``y - x > 0`` |``<`` is a total ordering relation | | |
702 | +-----------+-----------------------+---------------------+--------------------------------------+ | |
703 | |``y < x`` |convertible to ``bool``|``x - y > 0`` |``<`` is a total ordering relation | | |
704 | +-----------+-----------------------+---------------------+--------------------------------------+ | |
705 | |``x > y`` |convertible to ``bool``|``y < x`` |``>`` is a total ordering relation | | |
706 | +-----------+-----------------------+---------------------+--------------------------------------+ | |
707 | |``y > x`` |convertible to ``bool``|``x < y`` |``>`` is a total ordering relation | | |
708 | +-----------+-----------------------+---------------------+--------------------------------------+ | |
709 | |``x >= y`` |convertible to ``bool``|``!(x < y)`` | | | |
710 | +-----------+-----------------------+---------------------+--------------------------------------+ | |
711 | |``y >= x`` |convertible to ``bool``|``!(y < x)`` | | | |
712 | +-----------+-----------------------+---------------------+--------------------------------------+ | |
713 | |``x <= y`` |convertible to ``bool``|``!(x > y)`` | | | |
714 | +-----------+-----------------------+---------------------+--------------------------------------+ | |
715 | |``y <= x`` |convertible to ``bool``|``!(y > x)`` | | | |
716 | +-----------+-----------------------+---------------------+--------------------------------------+ | |
717 | |``y - x`` |``Distance`` |``distance(Y(x),y)`` |pre: there exists a value ``n`` of | | |
718 | | | | |``Distance`` such that ``x + n == y``.| | |
719 | | | | |``y == x + (y - x)``. | | |
720 | +-----------+-----------------------+---------------------+--------------------------------------+ | |
721 | |``x - y`` |``Distance`` |``distance(y,Y(x))`` |pre: there exists a value ``n`` of | | |
722 | | | | |``Distance`` such that ``y + n == x``.| | |
723 | | | | |``x == y + (x - y)``. | | |
724 | +-----------+-----------------------+---------------------+--------------------------------------+ | |
725 | ||
726 | ||
727 | ||
728 | Addition to [lib.iterator.synopsis] | |
729 | =================================== | |
730 | ||
731 | ||
732 | :: | |
733 | ||
734 | // lib.iterator.traits, traits and tags | |
735 | template <class Iterator> struct is_readable_iterator; | |
736 | template <class Iterator> struct iterator_traversal; | |
737 | ||
738 | struct incrementable_traversal_tag { }; | |
739 | struct single_pass_traversal_tag : incrementable_traversal_tag { }; | |
740 | struct forward_traversal_tag : single_pass_traversal_tag { }; | |
741 | struct bidirectional_traversal_tag : forward_traversal_tag { }; | |
742 | struct random_access_traversal_tag : bidirectional_traversal_tag { }; | |
743 | ||
744 | Addition to [lib.iterator.traits] | |
745 | ================================= | |
746 | ||
747 | The ``is_readable_iterator`` class | |
748 | template satisfies the UnaryTypeTrait_ requirements. | |
749 | ||
750 | Given an iterator type ``X``, ``is_readable_iterator<X>::value`` | |
751 | yields ``true`` if, for an object ``a`` of type ``X``, ``*a`` is | |
752 | convertible to ``iterator_traits<X>::value_type``, and ``false`` | |
753 | otherwise. | |
754 | ||
755 | ``iterator_traversal<X>::type`` is | |
756 | ||
757 | .. parsed-literal:: | |
758 | ||
759 | *category-to-traversal*\ (iterator_traits<X>::iterator_category) | |
760 | ||
761 | where *category-to-traversal* is defined as follows | |
762 | ||
763 | .. _`category-to-traversal`: | |
764 | ||
765 | .. parsed-literal:: | |
766 | ||
767 | *category-to-traversal*\ (C) = | |
768 | if (C is convertible to incrementable_traversal_tag) | |
769 | return C; | |
770 | else if (C is convertible to random_access_iterator_tag) | |
771 | return random_access_traversal_tag; | |
772 | else if (C is convertible to bidirectional_iterator_tag) | |
773 | return bidirectional_traversal_tag; | |
774 | else if (C is convertible to forward_iterator_tag) | |
775 | return forward_traversal_tag; | |
776 | else if (C is convertible to input_iterator_tag) | |
777 | return single_pass_traversal_tag; | |
778 | else if (C is convertible to output_iterator_tag) | |
779 | return incrementable_traversal_tag; | |
780 | else | |
781 | *the program is ill-formed* | |
782 | ||
783 | ||
784 | =========== | |
785 | Footnotes | |
786 | =========== | |
787 | ||
788 | .. _UnaryTypeTrait: n1519_ | |
789 | ||
790 | The UnaryTypeTrait concept is defined in n1519_; the LWG is | |
791 | considering adding the requirement that specializations are derived | |
792 | from their nested ``::type``. | |
793 | ||
794 | .. _n1519: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1519.htm | |
795 | ||
796 | .. | |
797 | LocalWords: Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue | |
798 | LocalWords: ReadableIterator WritableIterator SwappableIterator cv pre iter | |
799 | LocalWords: ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR | |
800 | LocalWords: ForwardTraversalIterator BidirectionalTraversalIterator lvalue | |
801 | LocalWords: RandomAccessTraversalIterator dereferenceable Incrementable tmp | |
802 | LocalWords: incrementable xxx min prev inplace png oldeqnew AccessTag struct | |
803 | LocalWords: TraversalTag typename lvalues DWA Hmm JGS mis enum |