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 50The standard iterator categories and requirements are flawed because 51they use a single hierarchy of concepts to address two orthogonal 52issues: *iterator traversal* and *value access*. As a result, many 53algorithms with requirements expressed in terms of the iterator 54categories are too strict. Also, many real-world iterators can not be 55accurately categorized. A proxy-based iterator with random-access 56traversal, for example, may only legally have a category of "input 57iterator", so generic algorithms are unable to take advantage of its 58random-access capabilities. The current iterator concept hierarchy is 59geared towards iterator traversal (hence the category names), while 60requirements that address value access sneak in at various places. The 61following table gives a summary of the current value access 62requirements 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 83Because iterator traversal and value access are mixed together in a 84single hierarchy, many useful iterators can not be appropriately 85categorized. For example, ``vector<bool>::iterator`` is almost a 86random access iterator, but the return type is not ``bool&`` (see 87`issue 96`_ and Herb Sutter's paper J16/99-0008 = WG21 88N1185). Therefore, the iterators of ``vector<bool>`` only meet the 89requirements of input iterator and output iterator. This is so 90nonintuitive that the C++ standard contradicts itself on this point. 91In paragraph 23.2.4/1 it says that a ``vector`` is a sequence that 92supports random access iterators. 93 94.. _issue 96: http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#96 95 96Another difficult-to-categorize iterator is the transform iterator, an 97adaptor which applies a unary function object to the dereferenced 98value of the some underlying iterator (see `transform_iterator`_). 99For unary functions such as ``times``, the return type of 100``operator*`` clearly needs to be the ``result_type`` of the function 101object, which is typically not a reference. Because random access 102iterators are required to return lvalues from ``operator*``, if you 103wrap ``int*`` with a transform iterator, you do not get a random 104access iterator as might be expected, but an input iterator. 105 106.. _`transform_iterator`: http://www.boost.org/libs/utility/transform_iterator.htm 107 108A third example is found in the vertex and edge iterators of the 109`Boost Graph Library`_. These iterators return vertex and edge 110descriptors, which are lightweight handles created on-the-fly. They 111must be returned by-value. As a result, their current standard 112iterator category is ``input_iterator_tag``, which means that, 113strictly speaking, you could not use these iterators with algorithms 114like ``min_element()``. As a temporary solution, the concept 115`Multi-Pass Input Iterator`_ was introduced to describe the vertex and 116edge descriptors, but as the design notes for the concept suggest, a 117better 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 122In short, there are many useful iterators that do not fit into the 123current standard iterator categories. As a result, the following bad 124things 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 137This proposal for TR1 is a pure extension. Further, the new iterator 138concepts are backward-compatible with the old iterator requirements, 139and old iterators are forward-compatible with the new iterator 140concepts. That is to say, iterators that satisfy the old requirements 141also satisfy appropriate concepts in the new system, and iterators 142modeling the new concepts will automatically satisfy the appropriate 143old 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 154Possible (but not proposed) Changes to the Working Paper 155======================================================== 156 157The extensions in this paper suggest several changes we might make 158to the working paper for the next standard. These changes are not 159a formal part of this proposal for TR1. 160 161Changes to Algorithm Requirements 162+++++++++++++++++++++++++++++++++ 163 164The algorithms in the standard library could benefit from the new 165iterator concepts because the new concepts provide a more accurate way 166to express their type requirements. The result is algorithms that are 167usable in more situations and have fewer type requirements. 168 169For the next working paper (but not for TR1), the committee should 170consider the following changes to the type requirements of algorithms. 171These changes are phrased as textual substitutions, listing the 172algorithms to which each textual substitution applies. 173 174Forward 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 180Forward Iterator (1) -> Single Pass Iterator and Readable Iterator, 181Forward Iterator (2) -> Forward Traversal Iterator and Readable Iterator 182 183 ``find_first_of`` 184 185Forward Iterator -> Readable Iterator and Writable Iterator 186 187 ``iter_swap`` 188 189Forward Iterator -> Single Pass Iterator and Writable Iterator 190 191 ``fill, generate`` 192 193Forward Iterator -> Forward Traversal Iterator and Swappable Iterator 194 195 ``rotate`` 196 197Forward Iterator (1) -> Swappable Iterator and Single Pass Iterator, 198Forward Iterator (2) -> Swappable Iterator and Incrementable Iterator 199 200 ``swap_ranges`` 201 202Forward Iterator -> Forward Traversal Iterator and Readable Iterator and Writable Iterator 203 ``remove, remove_if, unique`` 204 205Forward Iterator -> Single Pass Iterator and Readable Iterator and Writable Iterator 206 207 ``replace, replace_if`` 208 209Bidirectional Iterator -> Bidirectional Traversal Iterator and Swappable Iterator 210 ``reverse`` 211 212Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable and Swappable Iterator 213 ``partition`` 214 215Bidirectional Iterator (1) -> Bidirectional Traversal Iterator and Readable Iterator, 216Bidirectional Iterator (2) -> Bidirectional Traversal Iterator and Writable Iterator 217 218 ``copy_backwards`` 219 220Bidirectional Iterator -> Bidirectional Traversal Iterator and Swappable Iterator and Readable Iterator 221 ``next_permutation, prev_permutation`` 222 223Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator and Writable Iterator 224 ``stable_partition, inplace_merge`` 225 226Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator 227 ``reverse_copy`` 228 229Random 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 233Input Iterator (2) -> Incrementable Iterator and Readable Iterator 234 ``equal, mismatch`` 235 236Input Iterator (2) -> Incrementable Iterator and Readable Iterator 237 ``transform`` 238 239Deprecations 240++++++++++++ 241 242For the next working paper (but not for TR1), the committee should 243consider deprecating the old iterator tags, and 244std::iterator_traits, since it will be superceded by individual 245traits metafunctions. 246 247``vector<bool>`` 248++++++++++++++++ 249 250For the next working paper (but not for TR1), the committee should 251consider reclassifying ``vector<bool>::iterator`` as a Random 252Access Traversal Iterator and Readable Iterator and Writable 253Iterator. 254 255======== 256 Design 257======== 258 259The iterator requirements are to be separated into two groups. One set 260of concepts handles the syntax and semantics of value access: 261 262- Readable Iterator 263- Writable Iterator 264- Swappable Iterator 265- Lvalue Iterator 266 267The access concepts describe requirements related to ``operator*`` and 268``operator->``, including the ``value_type``, ``reference``, and 269``pointer`` associated types. 270 271The 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 279The refinement relationships for the traversal concepts are in the 280following diagram. 281 282.. image:: traversal.png 283 284In addition to the iterator movement operators, such as 285``operator++``, the traversal concepts also include requirements on 286position comparison such as ``operator==`` and ``operator<``. The 287reason for the fine grain slicing of the concepts into the 288Incrementable and Single Pass is to provide concepts that are exact 289matches with the original input and output iterator requirements. 290 291This proposal also includes a concept for specifying when an iterator 292is interoperable with another iterator, in the sense that ``int*`` is 293interoperable with ``int const*``. 294 295- Interoperable Iterators 296 297 298The relationship between the new iterator concepts and the old are 299given in the following diagram. 300 301.. image:: oldeqnew.png 302 303Like the old iterator requirements, we provide tags for purposes of 304dispatching based on the traversal concepts. The tags are related via 305inheritance so that a tag is convertible to another tag if the concept 306associated with the first tag is a refinement of the second tag. 307 308Our design reuses ``iterator_traits<Iter>::iterator_category`` to 309indicate an iterator's traversal capability. To specify 310capabilities not captured by any old-style iterator category, an 311iterator designer can use an ``iterator_category`` type that is 312convertible to both the the most-derived old iterator category tag 313which 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 319We do not provide tags for the purposes of dispatching based on the 320access concepts, in part because we could not find a way to 321automatically infer the right access tags for old-style iterators. 322An iterator's writability may be dependent on the assignability of 323its ``value_type`` and there's no known way to detect whether an 324arbitrary type is assignable. Fortunately, the need for 325dispatching based on access capability is not as great as the need 326for dispatching based on traversal capability. 327 328A difficult design decision concerned the ``operator[]``. The direct 329approach for specifying ``operator[]`` would have a return type of 330``reference``; the same as ``operator*``. However, going in this 331direction would mean that an iterator satisfying the old Random Access 332Iterator requirements would not necessarily be a model of Readable or 333Writable Lvalue Iterator. Instead we have chosen a design that 334matches the preferred resolution of `issue 299`_: ``operator[]`` is 335only 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 344Addition to [lib.iterator.requirements] 345======================================= 346 347Iterator Value Access Concepts [lib.iterator.value.access] 348++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 349 350In the tables below, ``X`` is an iterator type, ``a`` is a constant 351object 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 354object of type ``T``. 355 356.. _Readable Iterator: 357 358Readable Iterators [lib.readable.iterators] 359------------------------------------------- 360 361A class or built-in type ``X`` models the *Readable Iterator* concept 362for value type ``T`` if, in addition to ``X`` being Assignable and 363Copy Constructible, the following expressions are valid and respect 364the stated semantics. ``U`` is the type of any specified member of 365type ``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 385Writable Iterators [lib.writable.iterators] 386------------------------------------------- 387 388A class or built-in type ``X`` models the *Writable Iterator* concept 389if, in addition to ``X`` being Copy Constructible, the following 390expressions are valid and respect the stated semantics. Writable 391Iterators 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 403Swappable Iterators [lib.swappable.iterators] 404--------------------------------------------- 405 406A class or built-in type ``X`` models the *Swappable Iterator* concept 407if, in addition to ``X`` being Copy Constructible, the following 408expressions 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 421Iterator*. *--end note*] 422 423 424Lvalue Iterators [lib.lvalue.iterators] 425--------------------------------------- 426 427The *Lvalue Iterator* concept adds the requirement that the return 428type of ``operator*`` type be a reference to the value type of the 429iterator. 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 443If ``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 445Iterator`_ then ``a == b`` implies ``*a`` is the same object as 446``*b``. 447 448 449Iterator Traversal Concepts [lib.iterator.traversal] 450++++++++++++++++++++++++++++++++++++++++++++++++++++ 451 452In the tables below, ``X`` is an iterator type, ``a`` and ``b`` are 453constant objects of type ``X``, ``r`` and ``s`` are mutable objects of 454type ``X``, ``T`` is ``std::iterator_traits<X>::value_type``, and 455``v`` is a constant object of type ``T``. 456 457Incrementable Iterators [lib.incrementable.iterators] 458----------------------------------------------------- 459 460A class or built-in type ``X`` models the *Incrementable Iterator* 461concept if, in addition to ``X`` being Assignable and Copy 462Constructible, the following expressions are valid and respect the 463stated 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 482If ``X`` is a `Writable Iterator`_ then ``X a(r++);`` is equivalent 483to ``X a(r); ++r;`` and ``*r++ = o`` is equivalent 484to ``*r = o; ++r``. 485If ``X`` is a `Readable Iterator`_ then ``T z(*r++);`` is equivalent 486to ``T z(*r); ++r;``. 487 488.. TR1: incrementable_iterator_tag changed to 489 incrementable_traversal_tag for consistency. 490 491Single Pass Iterators [lib.single.pass.iterators] 492------------------------------------------------- 493 494A class or built-in type ``X`` models the *Single Pass Iterator* 495concept if the following expressions are valid and respect the stated 496semantics. 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 528Forward Traversal Iterators [lib.forward.traversal.iterators] 529------------------------------------------------------------- 530 531A class or built-in type ``X`` models the *Forward Traversal Iterator* 532concept if, in addition to ``X`` meeting the requirements of Default 533Constructible and Single Pass Iterator, the following expressions are 534valid 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 558Bidirectional Traversal Iterators [lib.bidirectional.traversal.iterators] 559------------------------------------------------------------------------- 560 561A class or built-in type ``X`` models the *Bidirectional Traversal 562Iterator* concept if, in addition to ``X`` meeting the requirements of 563Forward Traversal Iterator, the following expressions are valid and 564respect 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 600Random Access Traversal Iterators [lib.random.access.traversal.iterators] 601------------------------------------------------------------------------- 602 603A class or built-in type ``X`` models the *Random Access Traversal 604Iterator* concept if the following expressions are valid and respect 605the stated semantics. In the table below, ``Distance`` is 606``iterator_traits<X>::difference_type`` and ``n`` represents a 607constant 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 668Interoperable Iterators [lib.interoperable.iterators] 669----------------------------------------------------- 670 671A 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 673Single Pass Iterator if the following expressions are valid and 674respect the stated semantics. In the tables below, ``x`` is an object 675of type ``X``, ``y`` is an object of type ``Y``, ``Distance`` is 676``iterator_traits<Y>::difference_type``, and ``n`` represents a 677constant 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 695If ``X`` and ``Y`` both model Random Access Traversal Iterator then 696the 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 728Addition 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 744Addition to [lib.iterator.traits] 745================================= 746 747The ``is_readable_iterator`` class 748template satisfies the UnaryTypeTrait_ requirements. 749 750Given an iterator type ``X``, ``is_readable_iterator<X>::value`` 751yields ``true`` if, for an object ``a`` of type ``X``, ``*a`` is 752convertible to ``iterator_traits<X>::value_type``, and ``false`` 753otherwise. 754 755``iterator_traversal<X>::type`` is 756 757.. parsed-literal:: 758 759 *category-to-traversal*\ (iterator_traits<X>::iterator_category) 760 761where *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 790The UnaryTypeTrait concept is defined in n1519_; the LWG is 791considering adding the requirement that specializations are derived 792from 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 804
