]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |