123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803 |
- .. Distributed under the Boost
- .. Software License, Version 1.0. (See accompanying
- .. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- ++++++++++++++++++++++
- New Iterator Concepts
- ++++++++++++++++++++++
- .. Version 1.25 of this ReStructuredText document is the same as
- n1550_, the paper accepted by the LWG.
- :Author: David Abrahams, Jeremy Siek, Thomas Witt
- :Contact: dave@boost-consulting.com, jsiek@osl.iu.edu, witt@styleadvisor.com
- :organization: `Boost Consulting`_, Indiana University `Open Systems
- Lab`_, `Zephyr Associates, Inc.`_
- :date: $Date$
- :Number: This is a revised version of n1550_\ =03-0133, which was
- accepted for Technical Report 1 by the C++ standard
- committee's library working group. This proposal is a
- revision of paper n1297_, n1477_, and n1531_.
- :copyright: Copyright David Abrahams, Jeremy Siek, and Thomas Witt
- 2003.
- .. _`Boost Consulting`: http://www.boost-consulting.com
- .. _`Open Systems Lab`: http://www.osl.iu.edu
- .. _`Zephyr Associates, Inc.`: http://www.styleadvisor.com
- .. _`Institute for Transport Railway Operation and Construction`:
- http://www.ive.uni-hannover.de
- :Abstract: We propose a new system of iterator concepts that treat
- access and positioning independently. This allows the
- concepts to more closely match the requirements
- of algorithms and provides better categorizations
- of iterators that are used in practice.
-
- .. contents:: Table of Contents
- .. _n1297: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1297.html
- .. _n1477: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1477.html
- .. _n1531: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1531.html
- .. _n1550: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1550.htm
- ============
- Motivation
- ============
- The standard iterator categories and requirements are flawed because
- they use a single hierarchy of concepts to address two orthogonal
- issues: *iterator traversal* and *value access*. As a result, many
- algorithms with requirements expressed in terms of the iterator
- categories are too strict. Also, many real-world iterators can not be
- accurately categorized. A proxy-based iterator with random-access
- traversal, for example, may only legally have a category of "input
- iterator", so generic algorithms are unable to take advantage of its
- random-access capabilities. The current iterator concept hierarchy is
- geared towards iterator traversal (hence the category names), while
- requirements that address value access sneak in at various places. The
- following table gives a summary of the current value access
- requirements in the iterator categories.
- +------------------------------------------------------------------------------+
- |Value Access Requirements in Existing Iterator Categories |
- +========================+=====================================================+
- |Output Iterator |``*i = a`` |
- +------------------------+-----------------------------------------------------+
- |Input Iterator |``*i`` is convertible to ``T`` |
- +------------------------+-----------------------------------------------------+
- |Forward Iterator |``*i`` is ``T&`` (or ``const T&`` once `issue 200`_ |
- | |is resolved) |
- +------------------------+-----------------------------------------------------+
- |Random Access Iterator |``i[n]`` is convertible to ``T`` (also ``i[n] = t`` |
- | |is required for mutable iterators once `issue 299`_ |
- | |is resolved) |
- +------------------------+-----------------------------------------------------+
- .. _issue 200: http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#200
- .. _issue 299: http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#299
- Because iterator traversal and value access are mixed together in a
- single hierarchy, many useful iterators can not be appropriately
- categorized. For example, ``vector<bool>::iterator`` is almost a
- random access iterator, but the return type is not ``bool&`` (see
- `issue 96`_ and Herb Sutter's paper J16/99-0008 = WG21
- N1185). Therefore, the iterators of ``vector<bool>`` only meet the
- requirements of input iterator and output iterator. This is so
- nonintuitive that the C++ standard contradicts itself on this point.
- In paragraph 23.2.4/1 it says that a ``vector`` is a sequence that
- supports random access iterators.
- .. _issue 96: http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#96
- Another difficult-to-categorize iterator is the transform iterator, an
- adaptor which applies a unary function object to the dereferenced
- value of the some underlying iterator (see `transform_iterator`_).
- For unary functions such as ``times``, the return type of
- ``operator*`` clearly needs to be the ``result_type`` of the function
- object, which is typically not a reference. Because random access
- iterators are required to return lvalues from ``operator*``, if you
- wrap ``int*`` with a transform iterator, you do not get a random
- access iterator as might be expected, but an input iterator.
- .. _`transform_iterator`: http://www.boost.org/libs/utility/transform_iterator.htm
- A third example is found in the vertex and edge iterators of the
- `Boost Graph Library`_. These iterators return vertex and edge
- descriptors, which are lightweight handles created on-the-fly. They
- must be returned by-value. As a result, their current standard
- iterator category is ``input_iterator_tag``, which means that,
- strictly speaking, you could not use these iterators with algorithms
- like ``min_element()``. As a temporary solution, the concept
- `Multi-Pass Input Iterator`_ was introduced to describe the vertex and
- edge descriptors, but as the design notes for the concept suggest, a
- better solution is needed.
- .. _Boost Graph Library: http://www.boost.org/libs/graph/doc/table_of_contents.html
- .. _Multi-Pass Input Iterator: http://www.boost.org/libs/utility/MultiPassInputIterator.html
- In short, there are many useful iterators that do not fit into the
- current standard iterator categories. As a result, the following bad
- things happen:
- - Iterators are often mis-categorized.
- - Algorithm requirements are more strict than necessary, because they
- cannot separate the need for random access or bidirectional
- traversal from the need for a true reference return type.
- ========================
- Impact on the Standard
- ========================
- This proposal for TR1 is a pure extension. Further, the new iterator
- concepts are backward-compatible with the old iterator requirements,
- and old iterators are forward-compatible with the new iterator
- concepts. That is to say, iterators that satisfy the old requirements
- also satisfy appropriate concepts in the new system, and iterators
- modeling the new concepts will automatically satisfy the appropriate
- old requirements.
- .. I think we need to say something about the resolution to allow
- convertibility to any of the old-style tags as a TR issue (hope it
- made it). -DWA
- .. Hmm, not sure I understand. Are you talking about whether a
- standards conforming input iterator is allowed to have
- a tag that is not input_iterator_tag but that
- is convertible to input_iterator_tag? -JGS
- Possible (but not proposed) Changes to the Working Paper
- ========================================================
- The extensions in this paper suggest several changes we might make
- to the working paper for the next standard. These changes are not
- a formal part of this proposal for TR1.
- Changes to Algorithm Requirements
- +++++++++++++++++++++++++++++++++
- The algorithms in the standard library could benefit from the new
- iterator concepts because the new concepts provide a more accurate way
- to express their type requirements. The result is algorithms that are
- usable in more situations and have fewer type requirements.
- For the next working paper (but not for TR1), the committee should
- consider the following changes to the type requirements of algorithms.
- These changes are phrased as textual substitutions, listing the
- algorithms to which each textual substitution applies.
- Forward Iterator -> Forward Traversal Iterator and Readable Iterator
- ``find_end, adjacent_find, search, search_n, rotate_copy,
- lower_bound, upper_bound, equal_range, binary_search,
- min_element, max_element``
- Forward Iterator (1) -> Single Pass Iterator and Readable Iterator,
- Forward Iterator (2) -> Forward Traversal Iterator and Readable Iterator
- ``find_first_of``
- Forward Iterator -> Readable Iterator and Writable Iterator
- ``iter_swap``
- Forward Iterator -> Single Pass Iterator and Writable Iterator
- ``fill, generate``
- Forward Iterator -> Forward Traversal Iterator and Swappable Iterator
- ``rotate``
- Forward Iterator (1) -> Swappable Iterator and Single Pass Iterator,
- Forward Iterator (2) -> Swappable Iterator and Incrementable Iterator
- ``swap_ranges``
- Forward Iterator -> Forward Traversal Iterator and Readable Iterator and Writable Iterator
- ``remove, remove_if, unique``
- Forward Iterator -> Single Pass Iterator and Readable Iterator and Writable Iterator
- ``replace, replace_if``
- Bidirectional Iterator -> Bidirectional Traversal Iterator and Swappable Iterator
- ``reverse``
- Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable and Swappable Iterator
- ``partition``
- Bidirectional Iterator (1) -> Bidirectional Traversal Iterator and Readable Iterator,
- Bidirectional Iterator (2) -> Bidirectional Traversal Iterator and Writable Iterator
- ``copy_backwards``
- Bidirectional Iterator -> Bidirectional Traversal Iterator and Swappable Iterator and Readable Iterator
- ``next_permutation, prev_permutation``
- Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator and Writable Iterator
- ``stable_partition, inplace_merge``
- Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator
- ``reverse_copy``
- Random Access Iterator -> Random Access Traversal Iterator and Readable and Writable Iterator
- ``random_shuffle, sort, stable_sort, partial_sort, nth_element, push_heap, pop_heap
- make_heap, sort_heap``
- Input Iterator (2) -> Incrementable Iterator and Readable Iterator
- ``equal, mismatch``
- Input Iterator (2) -> Incrementable Iterator and Readable Iterator
- ``transform``
- Deprecations
- ++++++++++++
- For the next working paper (but not for TR1), the committee should
- consider deprecating the old iterator tags, and
- std::iterator_traits, since it will be superceded by individual
- traits metafunctions.
- ``vector<bool>``
- ++++++++++++++++
- For the next working paper (but not for TR1), the committee should
- consider reclassifying ``vector<bool>::iterator`` as a Random
- Access Traversal Iterator and Readable Iterator and Writable
- Iterator.
- ========
- Design
- ========
- The iterator requirements are to be separated into two groups. One set
- of concepts handles the syntax and semantics of value access:
- - Readable Iterator
- - Writable Iterator
- - Swappable Iterator
- - Lvalue Iterator
- The access concepts describe requirements related to ``operator*`` and
- ``operator->``, including the ``value_type``, ``reference``, and
- ``pointer`` associated types.
- The other set of concepts handles traversal:
- - Incrementable Iterator
- - Single Pass Iterator
- - Forward Traversal Iterator
- - Bidirectional Traversal Iterator
- - Random Access Traversal Iterator
- The refinement relationships for the traversal concepts are in the
- following diagram.
- .. image:: traversal.png
- In addition to the iterator movement operators, such as
- ``operator++``, the traversal concepts also include requirements on
- position comparison such as ``operator==`` and ``operator<``. The
- reason for the fine grain slicing of the concepts into the
- Incrementable and Single Pass is to provide concepts that are exact
- matches with the original input and output iterator requirements.
- This proposal also includes a concept for specifying when an iterator
- is interoperable with another iterator, in the sense that ``int*`` is
- interoperable with ``int const*``.
- - Interoperable Iterators
- The relationship between the new iterator concepts and the old are
- given in the following diagram.
- .. image:: oldeqnew.png
- Like the old iterator requirements, we provide tags for purposes of
- dispatching based on the traversal concepts. The tags are related via
- inheritance so that a tag is convertible to another tag if the concept
- associated with the first tag is a refinement of the second tag.
- Our design reuses ``iterator_traits<Iter>::iterator_category`` to
- indicate an iterator's traversal capability. To specify
- capabilities not captured by any old-style iterator category, an
- iterator designer can use an ``iterator_category`` type that is
- convertible to both the the most-derived old iterator category tag
- which fits, and the appropriate new iterator traversal tag.
- .. dwa2003/1/2: Note that we are not *requiring* convertibility to
- a new-style traversal tag in order to meet new concepts.
- Old-style iterators still fit, after all.
- We do not provide tags for the purposes of dispatching based on the
- access concepts, in part because we could not find a way to
- automatically infer the right access tags for old-style iterators.
- An iterator's writability may be dependent on the assignability of
- its ``value_type`` and there's no known way to detect whether an
- arbitrary type is assignable. Fortunately, the need for
- dispatching based on access capability is not as great as the need
- for dispatching based on traversal capability.
- A difficult design decision concerned the ``operator[]``. The direct
- approach for specifying ``operator[]`` would have a return type of
- ``reference``; the same as ``operator*``. However, going in this
- direction would mean that an iterator satisfying the old Random Access
- Iterator requirements would not necessarily be a model of Readable or
- Writable Lvalue Iterator. Instead we have chosen a design that
- matches the preferred resolution of `issue 299`_: ``operator[]`` is
- only required to return something convertible to the ``value_type``
- (for a Readable Iterator), and is required to support assignment
- ``i[n] = t`` (for a Writable Iterator).
- ===============
- Proposed Text
- ===============
- Addition to [lib.iterator.requirements]
- =======================================
- Iterator Value Access Concepts [lib.iterator.value.access]
- ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
- In the tables below, ``X`` is an iterator type, ``a`` is a constant
- object of type ``X``, ``R`` is
- ``std::iterator_traits<X>::reference``, ``T`` is
- ``std::iterator_traits<X>::value_type``, and ``v`` is a constant
- object of type ``T``.
- .. _Readable Iterator:
- Readable Iterators [lib.readable.iterators]
- -------------------------------------------
- A class or built-in type ``X`` models the *Readable Iterator* concept
- for value type ``T`` if, in addition to ``X`` being Assignable and
- Copy Constructible, the following expressions are valid and respect
- the stated semantics. ``U`` is the type of any specified member of
- type ``T``.
- +-----------------------------------------------------------------------------------------------------------------------------+
- |Readable Iterator Requirements (in addition to Assignable and Copy Constructible) |
- +-----------------------------------+------------------------+----------------------------------------------------------------+
- |Expression |Return Type |Note/Precondition |
- +===================================+========================+================================================================+
- |``iterator_traits<X>::value_type`` |``T`` |Any non-reference, |
- | | |non-cv-qualified type |
- +-----------------------------------+------------------------+----------------------------------------------------------------+
- |``*a`` | Convertible to ``T`` |pre: ``a`` is dereferenceable. If ``a == b`` then ``*a`` |
- | | | is equivalent to ``*b``. |
- +-----------------------------------+------------------------+----------------------------------------------------------------+
- |``a->m`` |``U&`` |pre: ``pre: (*a).m`` is well-defined. Equivalent to ``(*a).m``. |
- +-----------------------------------+------------------------+----------------------------------------------------------------+
- .. We won't say anything about iterator_traits<X>::reference until the DR is resolved. -JGS
- .. _Writable Iterator:
- Writable Iterators [lib.writable.iterators]
- -------------------------------------------
- A class or built-in type ``X`` models the *Writable Iterator* concept
- if, in addition to ``X`` being Copy Constructible, the following
- expressions are valid and respect the stated semantics. Writable
- Iterators have an associated *set of value types*.
- +---------------------------------------------------------------------+
- |Writable Iterator Requirements (in addition to Copy Constructible) |
- +-------------------------+--------------+----------------------------+
- |Expression |Return Type |Precondition |
- +=========================+==============+============================+
- |``*a = o`` | | pre: The type of ``o`` |
- | | | is in the set of |
- | | | value types of ``X`` |
- +-------------------------+--------------+----------------------------+
- Swappable Iterators [lib.swappable.iterators]
- ---------------------------------------------
- A class or built-in type ``X`` models the *Swappable Iterator* concept
- if, in addition to ``X`` being Copy Constructible, the following
- expressions are valid and respect the stated semantics.
- +---------------------------------------------------------------------+
- |Swappable Iterator Requirements (in addition to Copy Constructible) |
- +-------------------------+-------------+-----------------------------+
- |Expression |Return Type |Postcondition |
- +=========================+=============+=============================+
- |``iter_swap(a, b)`` |``void`` |the pointed to values are |
- | | |exchanged |
- +-------------------------+-------------+-----------------------------+
- [*Note:* An iterator that is a model of the `Readable Iterator`_ and
- `Writable Iterator`_ concepts is also a model of *Swappable
- Iterator*. *--end note*]
- Lvalue Iterators [lib.lvalue.iterators]
- ---------------------------------------
- The *Lvalue Iterator* concept adds the requirement that the return
- type of ``operator*`` type be a reference to the value type of the
- iterator.
- +-------------------------------------------------------------+
- | Lvalue Iterator Requirements |
- +-------------+-----------+-----------------------------------+
- |Expression |Return Type|Note/Assertion |
- +=============+===========+===================================+
- |``*a`` | ``T&`` |``T`` is *cv* |
- | | |``iterator_traits<X>::value_type`` |
- | | |where *cv* is an optional |
- | | |cv-qualification. pre: ``a`` is |
- | | |dereferenceable. |
- +-------------+-----------+-----------------------------------+
- If ``X`` is a `Writable Iterator`_ then ``a == b`` if and only if
- ``*a`` is the same object as ``*b``. If ``X`` is a `Readable
- Iterator`_ then ``a == b`` implies ``*a`` is the same object as
- ``*b``.
- Iterator Traversal Concepts [lib.iterator.traversal]
- ++++++++++++++++++++++++++++++++++++++++++++++++++++
- In the tables below, ``X`` is an iterator type, ``a`` and ``b`` are
- constant objects of type ``X``, ``r`` and ``s`` are mutable objects of
- type ``X``, ``T`` is ``std::iterator_traits<X>::value_type``, and
- ``v`` is a constant object of type ``T``.
- Incrementable Iterators [lib.incrementable.iterators]
- -----------------------------------------------------
- A class or built-in type ``X`` models the *Incrementable Iterator*
- concept if, in addition to ``X`` being Assignable and Copy
- Constructible, the following expressions are valid and respect the
- stated semantics.
- +------------------------------------------------------------------------------------+
- |Incrementable Iterator Requirements (in addition to Assignable, Copy Constructible) |
- | |
- +--------------------------------+-------------------------------+-------------------+
- |Expression |Return Type |Assertion |
- +================================+===============================+===================+
- |``++r`` |``X&`` |``&r == &++r`` |
- +--------------------------------+-------------------------------+-------------------+
- |``r++`` | | |
- +--------------------------------+-------------------------------+-------------------+
- |``*r++`` | | |
- +--------------------------------+-------------------------------+-------------------+
- |``iterator_traversal<X>::type`` |Convertible to | |
- | |``incrementable_traversal_tag``| |
- +--------------------------------+-------------------------------+-------------------+
- If ``X`` is a `Writable Iterator`_ then ``X a(r++);`` is equivalent
- to ``X a(r); ++r;`` and ``*r++ = o`` is equivalent
- to ``*r = o; ++r``.
- If ``X`` is a `Readable Iterator`_ then ``T z(*r++);`` is equivalent
- to ``T z(*r); ++r;``.
- .. TR1: incrementable_iterator_tag changed to
- incrementable_traversal_tag for consistency.
- Single Pass Iterators [lib.single.pass.iterators]
- -------------------------------------------------
- A class or built-in type ``X`` models the *Single Pass Iterator*
- concept if the following expressions are valid and respect the stated
- semantics.
- +----------------------------------------------------------------------------------------------------------------+
- |Single Pass Iterator Requirements (in addition to Incrementable Iterator and Equality Comparable) |
- | |
- +----------------------------------------+-----------------------------+-------------+---------------------------+
- |Expression |Return Type | Operational |Assertion/ |
- | | | Semantics |Pre-/Post-condition |
- +========================================+=============================+=============+===========================+
- |``++r`` |``X&`` | |pre: ``r`` is |
- | | | |dereferenceable; post: |
- | | | |``r`` is dereferenceable or|
- | | | |``r`` is past-the-end |
- +----------------------------------------+-----------------------------+-------------+---------------------------+
- |``a == b`` |convertible to ``bool`` | |``==`` is an equivalence |
- | | | |relation over its domain |
- +----------------------------------------+-----------------------------+-------------+---------------------------+
- |``a != b`` |convertible to ``bool`` |``!(a == b)``| |
- +----------------------------------------+-----------------------------+-------------+---------------------------+
- |``iterator_traits<X>::difference_type`` |A signed integral type | | |
- | |representing the distance | | |
- | |between iterators | | |
- +----------------------------------------+-----------------------------+-------------+---------------------------+
- |``iterator_traversal<X>::type`` |Convertible to | | |
- | |``single_pass_traversal_tag``| | |
- +----------------------------------------+-----------------------------+-------------+---------------------------+
- .. TR1: single_pass_iterator_tag changed to
- single_pass_traversal_tag for consistency
- Forward Traversal Iterators [lib.forward.traversal.iterators]
- -------------------------------------------------------------
- A class or built-in type ``X`` models the *Forward Traversal Iterator*
- concept if, in addition to ``X`` meeting the requirements of Default
- Constructible and Single Pass Iterator, the following expressions are
- valid and respect the stated semantics.
- +--------------------------------------------------------------------------------------------------------+
- |Forward Traversal Iterator Requirements (in addition to Default Constructible and Single Pass Iterator) |
- +---------------------------------------+-----------------------------------+----------------------------+
- |Expression |Return Type |Assertion/Note |
- +=======================================+===================================+============================+
- |``X u;`` |``X&`` |note: ``u`` may have a |
- | | |singular value. |
- +---------------------------------------+-----------------------------------+----------------------------+
- |``++r`` |``X&`` |``r == s`` and ``r`` is |
- | | |dereferenceable implies |
- | | |``++r == ++s.`` |
- +---------------------------------------+-----------------------------------+----------------------------+
- |``iterator_traversal<X>::type`` |Convertible to | |
- | |``forward_traversal_tag`` | |
- +---------------------------------------+-----------------------------------+----------------------------+
- .. TR1: forward_traversal_iterator_tag changed to
- forward_traversal_tag for consistency
- Bidirectional Traversal Iterators [lib.bidirectional.traversal.iterators]
- -------------------------------------------------------------------------
- A class or built-in type ``X`` models the *Bidirectional Traversal
- Iterator* concept if, in addition to ``X`` meeting the requirements of
- Forward Traversal Iterator, the following expressions are valid and
- respect the stated semantics.
- +-----------------------------------------------------------------------------------------------------+
- |Bidirectional Traversal Iterator Requirements (in addition to Forward Traversal |
- |Iterator) |
- +--------------------------------+-------------------------------+--------------+---------------------+
- |Expression |Return Type | Operational |Assertion/ |
- | | | Semantics |Pre-/Post-condition |
- +================================+===============================+==============+=====================+
- |``--r`` |``X&`` | |pre: there exists |
- | | | |``s`` such that ``r |
- | | | |== ++s``. post: |
- | | | |``s`` is |
- | | | |dereferenceable. |
- | | | | |
- | | | |``++(--r) == r``. |
- | | | |``--r == --s`` |
- | | | |implies ``r == |
- | | | |s``. ``&r == &--r``. |
- +--------------------------------+-------------------------------+--------------+---------------------+
- |``r--`` |convertible to ``const X&`` |:: | |
- | | | | |
- | | | { | |
- | | | X tmp = r; | |
- | | | --r; | |
- | | | return tmp;| |
- | | | } | |
- +--------------------------------+-------------------------------+--------------+---------------------+
- |``iterator_traversal<X>::type`` |Convertible to | | |
- | |``bidirectional_traversal_tag``| | |
- | | | | |
- +--------------------------------+-------------------------------+--------------+---------------------+
- .. TR1: bidirectional_traversal_iterator_tag changed to
- bidirectional_traversal_tag for consistency
- Random Access Traversal Iterators [lib.random.access.traversal.iterators]
- -------------------------------------------------------------------------
- A class or built-in type ``X`` models the *Random Access Traversal
- Iterator* concept if the following expressions are valid and respect
- the stated semantics. In the table below, ``Distance`` is
- ``iterator_traits<X>::difference_type`` and ``n`` represents a
- constant object of type ``Distance``.
- +------------------------------------------------------------------------------------------------------------------+
- |Random Access Traversal Iterator Requirements (in addition to Bidirectional Traversal Iterator) |
- +-------------------------------+---------------------------------+-------------------------+----------------------+
- |Expression |Return Type |Operational Semantics |Assertion/ |
- | | | |Precondition |
- +===============================+=================================+=========================+======================+
- |``r += n`` |``X&`` |:: | |
- | | | | |
- | | | { | |
- | | | Distance m = n; | |
- | | | if (m >= 0) | |
- | | | while (m--) | |
- | | | ++r; | |
- | | | else | |
- | | | while (m++) | |
- | | | --r; | |
- | | | return r; | |
- | | | } | |
- +-------------------------------+---------------------------------+-------------------------+----------------------+
- |``a + n``, ``n + a`` |``X`` |``{ X tmp = a; return tmp| |
- | | |+= n; }`` | |
- | | | | |
- +-------------------------------+---------------------------------+-------------------------+----------------------+
- |``r -= n`` |``X&`` |``return r += -n`` | |
- +-------------------------------+---------------------------------+-------------------------+----------------------+
- |``a - n`` |``X`` |``{ X tmp = a; return tmp| |
- | | |-= n; }`` | |
- | | | | |
- +-------------------------------+---------------------------------+-------------------------+----------------------+
- |``b - a`` |``Distance`` |``a < b ? distance(a,b) |pre: there exists a |
- | | |: -distance(b,a)`` |value ``n`` of |
- | | | |``Distance`` such that|
- | | | |``a + n == b``. ``b |
- | | | |== a + (b - a)``. |
- +-------------------------------+---------------------------------+-------------------------+----------------------+
- |``a[n]`` |convertible to T |``*(a + n)`` |pre: a is a `Readable |
- | | | |Iterator`_ |
- +-------------------------------+---------------------------------+-------------------------+----------------------+
- |``a[n] = v`` |convertible to T |``*(a + n) = v`` |pre: a is a `Writable |
- | | | |Iterator`_ |
- +-------------------------------+---------------------------------+-------------------------+----------------------+
- |``a < b`` |convertible to ``bool`` |``b - a > 0`` |``<`` is a total |
- | | | |ordering relation |
- +-------------------------------+---------------------------------+-------------------------+----------------------+
- |``a > b`` |convertible to ``bool`` |``b < a`` |``>`` is a total |
- | | | |ordering relation |
- +-------------------------------+---------------------------------+-------------------------+----------------------+
- |``a >= b`` |convertible to ``bool`` |``!(a < b)`` | |
- +-------------------------------+---------------------------------+-------------------------+----------------------+
- |``a <= b`` |convertible to ``bool`` |``!(a > b)`` | |
- +-------------------------------+---------------------------------+-------------------------+----------------------+
- |``iterator_traversal<X>::type``|Convertible to | | |
- | |``random_access_traversal_tag`` | | |
- +-------------------------------+---------------------------------+-------------------------+----------------------+
- .. TR1: random_access_traversal_iterator_tag changed to
- random_access_traversal_tag for consistency
- Interoperable Iterators [lib.interoperable.iterators]
- -----------------------------------------------------
- A class or built-in type ``X`` that models Single Pass Iterator is
- *interoperable with* a class or built-in type ``Y`` that also models
- Single Pass Iterator if the following expressions are valid and
- respect the stated semantics. In the tables below, ``x`` is an object
- of type ``X``, ``y`` is an object of type ``Y``, ``Distance`` is
- ``iterator_traits<Y>::difference_type``, and ``n`` represents a
- constant object of type ``Distance``.
- +-----------+-----------------------+---------------------------------------------------+
- |Expression |Return Type |Assertion/Precondition/Postcondition |
- +===========+=======================+===================================================+
- |``y = x`` |``Y`` |post: ``y == x`` |
- +-----------+-----------------------+---------------------------------------------------+
- |``Y(x)`` |``Y`` |post: ``Y(x) == x`` |
- +-----------+-----------------------+---------------------------------------------------+
- |``x == y`` |convertible to ``bool``|``==`` is an equivalence relation over its domain. |
- +-----------+-----------------------+---------------------------------------------------+
- |``y == x`` |convertible to ``bool``|``==`` is an equivalence relation over its domain. |
- +-----------+-----------------------+---------------------------------------------------+
- |``x != y`` |convertible to ``bool``|``bool(a==b) != bool(a!=b)`` over its domain. |
- +-----------+-----------------------+---------------------------------------------------+
- |``y != x`` |convertible to ``bool``|``bool(a==b) != bool(a!=b)`` over its domain. |
- +-----------+-----------------------+---------------------------------------------------+
- If ``X`` and ``Y`` both model Random Access Traversal Iterator then
- the following additional requirements must be met.
- +-----------+-----------------------+---------------------+--------------------------------------+
- |Expression |Return Type |Operational Semantics|Assertion/ Precondition |
- +===========+=======================+=====================+======================================+
- |``x < y`` |convertible to ``bool``|``y - x > 0`` |``<`` is a total ordering relation |
- +-----------+-----------------------+---------------------+--------------------------------------+
- |``y < x`` |convertible to ``bool``|``x - y > 0`` |``<`` is a total ordering relation |
- +-----------+-----------------------+---------------------+--------------------------------------+
- |``x > y`` |convertible to ``bool``|``y < x`` |``>`` is a total ordering relation |
- +-----------+-----------------------+---------------------+--------------------------------------+
- |``y > x`` |convertible to ``bool``|``x < y`` |``>`` is a total ordering relation |
- +-----------+-----------------------+---------------------+--------------------------------------+
- |``x >= y`` |convertible to ``bool``|``!(x < y)`` | |
- +-----------+-----------------------+---------------------+--------------------------------------+
- |``y >= x`` |convertible to ``bool``|``!(y < x)`` | |
- +-----------+-----------------------+---------------------+--------------------------------------+
- |``x <= y`` |convertible to ``bool``|``!(x > y)`` | |
- +-----------+-----------------------+---------------------+--------------------------------------+
- |``y <= x`` |convertible to ``bool``|``!(y > x)`` | |
- +-----------+-----------------------+---------------------+--------------------------------------+
- |``y - x`` |``Distance`` |``distance(Y(x),y)`` |pre: there exists a value ``n`` of |
- | | | |``Distance`` such that ``x + n == y``.|
- | | | |``y == x + (y - x)``. |
- +-----------+-----------------------+---------------------+--------------------------------------+
- |``x - y`` |``Distance`` |``distance(y,Y(x))`` |pre: there exists a value ``n`` of |
- | | | |``Distance`` such that ``y + n == x``.|
- | | | |``x == y + (x - y)``. |
- +-----------+-----------------------+---------------------+--------------------------------------+
- Addition to [lib.iterator.synopsis]
- ===================================
- ::
- // lib.iterator.traits, traits and tags
- template <class Iterator> struct is_readable_iterator;
- template <class Iterator> struct iterator_traversal;
- struct incrementable_traversal_tag { };
- struct single_pass_traversal_tag : incrementable_traversal_tag { };
- struct forward_traversal_tag : single_pass_traversal_tag { };
- struct bidirectional_traversal_tag : forward_traversal_tag { };
- struct random_access_traversal_tag : bidirectional_traversal_tag { };
- Addition to [lib.iterator.traits]
- =================================
- The ``is_readable_iterator`` class
- template satisfies the UnaryTypeTrait_ requirements.
- Given an iterator type ``X``, ``is_readable_iterator<X>::value``
- yields ``true`` if, for an object ``a`` of type ``X``, ``*a`` is
- convertible to ``iterator_traits<X>::value_type``, and ``false``
- otherwise.
- ``iterator_traversal<X>::type`` is
- .. parsed-literal::
- *category-to-traversal*\ (iterator_traits<X>::iterator_category)
- where *category-to-traversal* is defined as follows
- .. _`category-to-traversal`:
- .. parsed-literal::
- *category-to-traversal*\ (C) =
- if (C is convertible to incrementable_traversal_tag)
- return C;
- else if (C is convertible to random_access_iterator_tag)
- return random_access_traversal_tag;
- else if (C is convertible to bidirectional_iterator_tag)
- return bidirectional_traversal_tag;
- else if (C is convertible to forward_iterator_tag)
- return forward_traversal_tag;
- else if (C is convertible to input_iterator_tag)
- return single_pass_traversal_tag;
- else if (C is convertible to output_iterator_tag)
- return incrementable_traversal_tag;
- else
- *the program is ill-formed*
- ===========
- Footnotes
- ===========
- .. _UnaryTypeTrait: n1519_
- The UnaryTypeTrait concept is defined in n1519_; the LWG is
- considering adding the requirement that specializations are derived
- from their nested ``::type``.
- .. _n1519: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1519.htm
- ..
- LocalWords: Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue
- LocalWords: ReadableIterator WritableIterator SwappableIterator cv pre iter
- LocalWords: ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR
- LocalWords: ForwardTraversalIterator BidirectionalTraversalIterator lvalue
- LocalWords: RandomAccessTraversalIterator dereferenceable Incrementable tmp
- LocalWords: incrementable xxx min prev inplace png oldeqnew AccessTag struct
- LocalWords: TraversalTag typename lvalues DWA Hmm JGS mis enum
|