ceph/src/boost/libs/mpl/doc/src/refmanual/ForwardIterator.rst

   1 .. Iterators/Concepts//Forward Iterator |10
   2
   3 Forward Iterator
   4 ================
   5
   6 Description
   7 -----------
   8
   9 A |Forward Iterator| ``i`` is a type that represents a positional reference
  10 to an element of a |Forward Sequence|. It allows to access the element through
  11 a dereference operation, and provides a way to obtain an iterator to
  12 the next element in a sequence.
  13
  14 .. A [Forward Iterator] guarantees a linear traversal over
  15    the sequence.
  16
  17
  18 Definitions
  19 -----------
  20
  21 * An iterator can be `dereferenceable`, meaning that ``deref<i>::type``
  22   is a well-defined expression.
  23
  24 * An iterator is `past-the-end` if it points beyond the last element of a
  25   sequence; past-the-end iterators are non-dereferenceable.
  26
  27 * An iterator ``i`` is `incrementable` if there is a "next" iterator, that
  28   is, if ``next<i>::type`` expression is well-defined; past-the-end iterators are
  29   not incrementable.
  30
  31 * Two iterators into the same sequence are `equivalent` if they have the same
  32   type.
  33
  34 * An iterator ``j`` is `reachable` from an iterator ``i`` if , after recursive
  35   application of ``next`` metafunction to ``i`` a finite number of times, ``i``
  36   is equivalent to ``j``.
  37
  38 * The notation [``i``,\ ``j``) refers to a `range` of iterators beginning with
  39   ``i`` and up to but not including ``j``.
  40
  41 * The range [``i``,\ ``j``) is a `valid range` if ``j`` is reachable from ``i``.
  42
  43
  44 Expression requirements
  45 -----------------------
  46
  47 +-----------------------+-------------------------------------------+---------------------------+
  48 | Expression            | Type                                      | Complexity                |
  49 +=======================+===========================================+===========================+
  50 | ``deref<i>::type``    | Any type                                  | Amortized constant time   |
  51 +-----------------------+-------------------------------------------+---------------------------+
  52 | ``next<i>::type``     | |Forward Iterator|                        | Amortized constant time   |
  53 +-----------------------+-------------------------------------------+---------------------------+
  54 | ``i::category``       | |Integral Constant|, convertible          | Constant time             |
  55 |                       | to ``forward_iterator_tag``               |                           |
  56 +-----------------------+-------------------------------------------+---------------------------+
  57
  58
  59 Expression semantics
  60 --------------------
  61
  62
  63 .. parsed-literal::
  64
  65     typedef deref<i>::type j;
  66
  67 :Precondition:
  68     ``i`` is dereferenceable
  69
  70 :Semantics:
  71     ``j`` is identical to the type of the pointed element
  72
  73
  74 .. ..........................................................................
  75
  76 .. parsed-literal::
  77
  78     typedef next<i>::type j;
  79
  80 :Precondition:
  81     ``i`` is incrementable
  82
  83 :Semantics:
  84     ``j`` is the next iterator in a sequence
  85
  86 :Postcondition:
  87     ``j`` is dereferenceable or past-the-end
  88
  89
  90 .. ..........................................................................
  91
  92 .. parsed-literal::
  93
  94     typedef i::category c;
  95
  96 :Semantics:
  97     ``c`` is identical to the iterator's category tag
  98
  99
 100 Invariants
 101 ----------
 102
 103 For any forward iterators ``i`` and ``j`` the following invariants always hold:
 104
 105 * ``i`` and ``j`` are equivalent if and only if they are pointing to the same
 106   element.
 107
 108 * If ``i`` is dereferenceable, and ``j`` is equivalent to ``i``, then ``j`` is
 109   dereferenceable as well.
 110
 111 * If ``i`` and ``j`` are equivalent and dereferenceable, then ``deref<i>::type``
 112   and ``deref<j>::type`` are identical.
 113
 114 * If ``i`` is incrementable, and ``j`` is equivalent to ``i``, then ``j`` is
 115   incrementable as well.
 116
 117 * If ``i`` and ``j`` are equivalent and incrementable, then ``next<i>::type``
 118   and ``next<j>::type`` are equivalent.
 119
 120
 121 See also
 122 --------
 123
 124 |Iterators|, |Bidirectional Iterator|, |Forward Sequence|, |deref|, |next|
 125
 126
 127 .. copyright:: Copyright ©  2001-2009 Aleksey Gurtovoy and David Abrahams
 128    Distributed under the Boost Software License, Version 1.0. (See accompanying
 129    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)