1.. Iterators/Concepts//Forward Iterator |10 2 3Forward Iterator 4================ 5 6Description 7----------- 8 9A |Forward Iterator| ``i`` is a type that represents a positional reference 10to an element of a |Forward Sequence|. It allows to access the element through 11a dereference operation, and provides a way to obtain an iterator to 12the next element in a sequence. 13 14.. A [Forward Iterator] guarantees a linear traversal over 15 the sequence. 16 17 18Definitions 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 44Expression 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 59Expression 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 100Invariants 101---------- 102 103For 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 121See 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) 130