1 <?xml version=
"1.0" encoding=
"utf-8" ?>
2 <!DOCTYPE html PUBLIC
"-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
3 <html xmlns=
"http://www.w3.org/1999/xhtml" xml:
lang=
"en" lang=
"en">
5 <meta http-equiv=
"Content-Type" content=
"text/html; charset=utf-8" />
6 <meta name=
"generator" content=
"Docutils 0.7: http://docutils.sourceforge.net/" />
7 <title>The MPL Reference Manual: Forward Iterator
</title>
8 <link rel=
"stylesheet" href=
"../style.css" type=
"text/css" />
10 <body class=
"docframe refmanual">
11 <table class=
"header"><tr class=
"header"><td class=
"header-group navigation-bar"><span class=
"navigation-group"><a href=
"./iterators-concepts.html" class=
"navigation-link">Prev
</a> <a href=
"./bidirectional-iterator.html" class=
"navigation-link">Next
</a></span><span class=
"navigation-group-separator"> |
</span><span class=
"navigation-group">Back
<a href=
"./bidirectional-iterator.html" class=
"navigation-link">Along
</a></span><span class=
"navigation-group-separator"> |
</span><span class=
"navigation-group"><a href=
"./iterators-concepts.html" class=
"navigation-link">Up
</a> <a href=
"../refmanual.html" class=
"navigation-link">Home
</a></span><span class=
"navigation-group-separator"> |
</span><span class=
"navigation-group"><a href=
"./refmanual_toc.html" class=
"navigation-link">Full TOC
</a></span></td>
12 <td class=
"header-group page-location"><a href=
"../refmanual.html" class=
"navigation-link">Front Page
</a> /
<a href=
"./iterators.html" class=
"navigation-link">Iterators
</a> /
<a href=
"./iterators-concepts.html" class=
"navigation-link">Concepts
</a> /
<a href=
"./forward-iterator.html" class=
"navigation-link">Forward Iterator
</a></td>
13 </tr></table><div class=
"header-separator"></div>
14 <div class=
"section" id=
"forward-iterator">
15 <h1><a class=
"toc-backref" href=
"./iterators-concepts.html#id1450">Forward Iterator
</a></h1>
16 <div class=
"section" id=
"id384">
17 <h3><a class=
"subsection-title" href=
"#description" name=
"description">Description
</a></h3>
18 <p>A
<a class=
"reference internal" href=
"./forward-iterator.html">Forward Iterator
</a> <tt class=
"literal"><span class=
"pre">i
</span></tt> is a type that represents a positional reference
19 to an element of a
<a class=
"reference internal" href=
"./forward-sequence.html">Forward Sequence
</a>. It allows to access the element through
20 a dereference operation, and provides a way to obtain an iterator to
21 the next element in a sequence.
</p>
22 <!-- A [Forward Iterator] guarantees a linear traversal over
25 <div class=
"section" id=
"id385">
26 <h3><a class=
"subsection-title" href=
"#definitions" name=
"definitions">Definitions
</a></h3>
28 <li>An iterator can be
<cite>dereferenceable
</cite>, meaning that
<tt class=
"literal"><span class=
"pre"><a href=
"./deref.html" class=
"identifier">deref
</a><i
>::type
</span></tt>
29 is a well-defined expression.
</li>
30 <li>An iterator is
<cite>past-the-end
</cite> if it points beyond the last element of a
31 sequence; past-the-end iterators are non-dereferenceable.
</li>
32 <li>An iterator
<tt class=
"literal"><span class=
"pre">i
</span></tt> is
<cite>incrementable
</cite> if there is a
"next
" iterator, that
33 is, if
<tt class=
"literal"><span class=
"pre"><a href=
"./next.html" class=
"identifier">next
</a><i
>::type
</span></tt> expression is well-defined; past-the-end iterators are
34 not incrementable.
</li>
35 <li>Two iterators into the same sequence are
<cite>equivalent
</cite> if they have the same
37 <li>An iterator
<tt class=
"literal"><span class=
"pre">j
</span></tt> is
<cite>reachable
</cite> from an iterator
<tt class=
"literal"><span class=
"pre">i
</span></tt> if , after recursive
38 application of
<tt class=
"literal"><span class=
"pre"><a href=
"./next.html" class=
"identifier">next
</a></span></tt> metafunction to
<tt class=
"literal"><span class=
"pre">i
</span></tt> a finite number of times,
<tt class=
"literal"><span class=
"pre">i
</span></tt>
39 is equivalent to
<tt class=
"literal"><span class=
"pre">j
</span></tt>.
</li>
40 <li>The notation [
<tt class=
"literal"><span class=
"pre">i
</span></tt>,
<tt class=
"literal"><span class=
"pre">j
</span></tt>) refers to a
<cite>range
</cite> of iterators beginning with
41 <tt class=
"literal"><span class=
"pre">i
</span></tt> and up to but not including
<tt class=
"literal"><span class=
"pre">j
</span></tt>.
</li>
42 <li>The range [
<tt class=
"literal"><span class=
"pre">i
</span></tt>,
<tt class=
"literal"><span class=
"pre">j
</span></tt>) is a
<cite>valid range
</cite> if
<tt class=
"literal"><span class=
"pre">j
</span></tt> is reachable from
<tt class=
"literal"><span class=
"pre">i
</span></tt>.
</li>
45 <div class=
"section" id=
"id386">
46 <h3><a class=
"subsection-title" href=
"#expression-requirements" name=
"expression-requirements">Expression requirements
</a></h3>
47 <table border=
"1" class=
"docutils table">
53 <thead valign=
"bottom">
54 <tr><th class=
"head">Expression
</th>
55 <th class=
"head">Type
</th>
56 <th class=
"head">Complexity
</th>
60 <tr><td><tt class=
"literal"><span class=
"pre"><a href=
"./deref.html" class=
"identifier">deref
</a><i
>::type
</span></tt></td>
62 <td>Amortized constant time
</td>
64 <tr><td><tt class=
"literal"><span class=
"pre"><a href=
"./next.html" class=
"identifier">next
</a><i
>::type
</span></tt></td>
65 <td><a class=
"reference internal" href=
"./forward-iterator.html">Forward Iterator
</a></td>
66 <td>Amortized constant time
</td>
68 <tr><td><tt class=
"literal"><span class=
"pre">i::category
</span></tt></td>
69 <td><a class=
"reference internal" href=
"./integral-constant.html">Integral Constant
</a>, convertible
70 to
<tt class=
"literal"><span class=
"pre">forward_iterator_tag
</span></tt></td>
71 <td>Constant time
</td>
76 <div class=
"section" id=
"id387">
77 <h3><a class=
"subsection-title" href=
"#expression-semantics" name=
"expression-semantics">Expression semantics
</a></h3>
78 <pre class=
"literal-block">
79 typedef
<a href=
"./deref.html" class=
"identifier">deref
</a><i
>::type j;
81 <table class=
"docutils field-list" frame=
"void" rules=
"none">
82 <col class=
"field-name" />
83 <col class=
"field-body" />
85 <tr class=
"field"><th class=
"field-name">Precondition:
</th><td class=
"field-body"><tt class=
"literal"><span class=
"pre">i
</span></tt> is dereferenceable
</td>
87 <tr class=
"field"><th class=
"field-name">Semantics:
</th><td class=
"field-body"><tt class=
"literal"><span class=
"pre">j
</span></tt> is identical to the type of the pointed element
</td>
91 <!-- .......................................................................... -->
92 <pre class=
"literal-block">
93 typedef
<a href=
"./next.html" class=
"identifier">next
</a><i
>::type j;
95 <table class=
"docutils field-list" frame=
"void" rules=
"none">
96 <col class=
"field-name" />
97 <col class=
"field-body" />
99 <tr class=
"field"><th class=
"field-name">Precondition:
</th><td class=
"field-body"><tt class=
"literal"><span class=
"pre">i
</span></tt> is incrementable
</td>
101 <tr class=
"field"><th class=
"field-name">Semantics:
</th><td class=
"field-body"><tt class=
"literal"><span class=
"pre">j
</span></tt> is the next iterator in a sequence
</td>
103 <tr class=
"field"><th class=
"field-name">Postcondition:
</th><td class=
"field-body"><tt class=
"literal"><span class=
"pre">j
</span></tt> is dereferenceable or past-the-end
</td>
107 <!-- .......................................................................... -->
108 <pre class=
"literal-block">
109 typedef i::category c;
111 <table class=
"docutils field-list" frame=
"void" rules=
"none">
112 <col class=
"field-name" />
113 <col class=
"field-body" />
115 <tr class=
"field"><th class=
"field-name">Semantics:
</th><td class=
"field-body"><tt class=
"literal"><span class=
"pre">c
</span></tt> is identical to the iterator's category tag
</td>
120 <div class=
"section" id=
"id388">
121 <h3><a class=
"subsection-title" href=
"#invariants" name=
"invariants">Invariants
</a></h3>
122 <p>For any forward iterators
<tt class=
"literal"><span class=
"pre">i
</span></tt> and
<tt class=
"literal"><span class=
"pre">j
</span></tt> the following invariants always hold:
</p>
124 <li><tt class=
"literal"><span class=
"pre">i
</span></tt> and
<tt class=
"literal"><span class=
"pre">j
</span></tt> are equivalent if and only if they are pointing to the same
126 <li>If
<tt class=
"literal"><span class=
"pre">i
</span></tt> is dereferenceable, and
<tt class=
"literal"><span class=
"pre">j
</span></tt> is equivalent to
<tt class=
"literal"><span class=
"pre">i
</span></tt>, then
<tt class=
"literal"><span class=
"pre">j
</span></tt> is
127 dereferenceable as well.
</li>
128 <li>If
<tt class=
"literal"><span class=
"pre">i
</span></tt> and
<tt class=
"literal"><span class=
"pre">j
</span></tt> are equivalent and dereferenceable, then
<tt class=
"literal"><span class=
"pre"><a href=
"./deref.html" class=
"identifier">deref
</a><i
>::type
</span></tt>
129 and
<tt class=
"literal"><span class=
"pre"><a href=
"./deref.html" class=
"identifier">deref
</a><j
>::type
</span></tt> are identical.
</li>
130 <li>If
<tt class=
"literal"><span class=
"pre">i
</span></tt> is incrementable, and
<tt class=
"literal"><span class=
"pre">j
</span></tt> is equivalent to
<tt class=
"literal"><span class=
"pre">i
</span></tt>, then
<tt class=
"literal"><span class=
"pre">j
</span></tt> is
131 incrementable as well.
</li>
132 <li>If
<tt class=
"literal"><span class=
"pre">i
</span></tt> and
<tt class=
"literal"><span class=
"pre">j
</span></tt> are equivalent and incrementable, then
<tt class=
"literal"><span class=
"pre"><a href=
"./next.html" class=
"identifier">next
</a><i
>::type
</span></tt>
133 and
<tt class=
"literal"><span class=
"pre"><a href=
"./next.html" class=
"identifier">next
</a><j
>::type
</span></tt> are equivalent.
</li>
136 <div class=
"section" id=
"id389">
137 <h3><a class=
"subsection-title" href=
"#see-also" name=
"see-also">See also
</a></h3>
138 <p><a class=
"reference internal" href=
"./iterators.html">Iterators
</a>,
<a class=
"reference internal" href=
"./bidirectional-iterator.html">Bidirectional Iterator
</a>,
<a class=
"reference internal" href=
"./forward-sequence.html">Forward Sequence
</a>,
<a class=
"reference internal" href=
"./deref.html">deref
</a>,
<a class=
"reference internal" href=
"./next.html">next
</a></p>
139 <!-- Iterators/Concepts//Bidirectional Iterator |20 -->
143 <div class=
"footer-separator"></div>
144 <table class=
"footer"><tr class=
"footer"><td class=
"header-group navigation-bar"><span class=
"navigation-group"><a href=
"./iterators-concepts.html" class=
"navigation-link">Prev
</a> <a href=
"./bidirectional-iterator.html" class=
"navigation-link">Next
</a></span><span class=
"navigation-group-separator"> |
</span><span class=
"navigation-group">Back
<a href=
"./bidirectional-iterator.html" class=
"navigation-link">Along
</a></span><span class=
"navigation-group-separator"> |
</span><span class=
"navigation-group"><a href=
"./iterators-concepts.html" class=
"navigation-link">Up
</a> <a href=
"../refmanual.html" class=
"navigation-link">Home
</a></span><span class=
"navigation-group-separator"> |
</span><span class=
"navigation-group"><a href=
"./refmanual_toc.html" class=
"navigation-link">Full TOC
</a></span></td>
145 <td><div class=
"copyright-footer"><div class=
"copyright">Copyright ©
2001-
2009 Aleksey Gurtovoy and David Abrahams
</div>
146 Distributed under the Boost Software License, Version
1.0. (See accompanying
147 file LICENSE_1_0.txt or copy at
<a class=
"reference external" href=
"http://www.boost.org/LICENSE_1_0.txt" target=
"_top">http://www.boost.org/LICENSE_1_0.txt
</a>)
</div></td></tr></table></body>