1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
|
<HTML>
<!--
-- Copyright (c) 1996,1997
-- Silicon Graphics Computer Systems, Inc.
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. Silicon Graphics makes no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
--
-- Copyright (c) 1994
-- Hewlett-Packard Company
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. Hewlett-Packard Company makes no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
--
-->
<Head>
<Title>Iterators</Title>
<!-- Generated by htmldoc -->
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="CorpID.gif"
ALT="Silicon Graphics, Inc." HEIGHT="43" WIDTH="151">
<!--end header-->
<BR Clear>
<H1>Iterators</H1>
<Table CellPadding=0 CellSpacing=0 width=100%>
<TR>
<TD Align=left><Img src = "iterators.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD>
<TD Align=right><Img src = "overview.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: iterators</TD>
<TD Align=right VAlign=top><b>Component type</b>: overview</TD>
</TR>
</Table>
<h3>Summary</h3>
Iterators are a generalization of pointers: they are
objects that point to other objects. As the name suggests, iterators
are often used to iterate over a range of objects: if an iterator
points to one element in a range, then it is possible to increment
it so that it points to the next element.
<P>
Iterators are central to generic programming because they are an
interface between containers and algorithms: algorithms typically
take iterators as arguments, so a container need only provide a way to
access its elements using iterators. This makes it possible to write
a generic algorithm that operates on many different kinds of
containers, even containers as different as a <A href="Vector.html">vector</A> and a
<A href="List.html">doubly linked list</A>.
<P>
The STL defines several different concepts related to iterators,
several predefined iterators, and a collection of types and functions
for manipulating iterators.
<h3>Description</h3>
Iterators are in fact not a single concept, but six concepts that
form a hierarchy: some of them define only a very restricted set of
operations, while others define additional functionality. The
five concepts that are actually used by algorithms are
<A href="InputIterator.html">Input Iterator</A>, <A href="OutputIterator.html">Output Iterator</A>, <A href="ForwardIterator.html">Forward Iterator</A>,
<A href="BidirectionalIterator.html">Bidirectional Iterator</A>, and <A href="RandomAccessIterator.html">Random Access Iterator</A>. A sixth
concept, <A href="trivial.html">Trivial Iterator</A>, is introduced only to clarify the
definitions of the other iterator concepts.
<P>
The most restricted sorts of iterators are <A href="InputIterator.html">Input Iterators</A> and
<A href="OutputIterator.html">Output Iterators</A>, both of which permit "single pass" algorithms
but do not necessarily support "multi-pass" algorithms.
<A href="InputIterator.html">Input iterators</A> only guarantee read access: it is possible to
dereference an <A href="InputIterator.html">Input Iterator</A> to obtain the value it points to,
but not it is not necessarily possible to assign a new value through
an input iterator. Similarly, <A href="OutputIterator.html">Output Iterators</A> only guarantee
write access: it is possible to assign a value through an
<A href="OutputIterator.html">Output Iterator</A>, but not necessarily possible to refer to that value.
<P>
<A href="ForwardIterator.html">Forward Iterators</A> are a refinement of <A href="InputIterator.html">Input Iterators</A> and
<A href="OutputIterator.html">Output Iterators</A>: they support the <A href="InputIterator.html">Input Iterator</A> and
<A href="OutputIterator.html">Output Iterator</A> operations and also provide additional
functionality. In particular, it is possible to use "multi-pass"
algorithms with <A href="ForwardIterator.html">Forward Iterators</A>. A <A href="ForwardIterator.html">Forward Iterator</A> may be
<i>constant</i>, in which case it is possible to access the object it
points to but not to to assign a new value through it, or <i>mutable</i>,
in which case it is possible to do both.
<P>
<A href="BidirectionalIterator.html">Bidirectional Iterators</A>, like <A href="ForwardIterator.html">Forward Iterators</A>, allow
multi-pass algorithms. As the name suggests, they are different in
that they support motion in both directions: a
<A href="BidirectionalIterator.html">Bidirectional Iterator</A> may be incremented to obtain the next
element or decremented to obtain the previous element. A
<A href="ForwardIterator.html">Forward Iterator</A>, by contrast, is only required to support forward
motion. An iterator used to traverse a singly linked list, for
example, would be a <A href="ForwardIterator.html">Forward Iterator</A>, while an iterator used to
traverse a doubly linked list would be a <A href="BidirectionalIterator.html">Bidirectional Iterator</A>.
<P>
Finally, <A href="RandomAccessIterator.html">Random Access Iterators</A> allow the operations of
pointer arithmetic: addition of arbitrary offsets, subscripting,
subtraction of one iterator from another to find a distance, and
so on.
<P>
Most algorithms are expressed not in terms of a single iterator but in
terms of a <i>range</i> of iterators <A href="#1">[1]</A>; the notation <tt>[first,
last)</tt> refers to all of the iterators from <tt>first</tt> up to, but <b>not
including</b>, <tt>last</tt>. <A href="#2">[2]</A> Note that a range may be empty, <i>i.e.</i>
<tt>first</tt> and <tt>last</tt> may be the same iterator. Note also that if there
are <tt>n</tt> iterators in a range, then the notation <tt>[first, last)</tt>
represents <tt>n+1</tt> positions. This is crucial: algorithms that
operate on <tt>n</tt> things frequently require
<tt>n+1</tt> positions. Linear search, for example (<tt><A href="find.html">find</A></tt>) must be able
to return some value to indicate that the search was unsuccessful.
<P>
Sometimes it is important to be able to infer some properties of an
iterator: the type of object that is returned when it is dereferenced,
for example. There are two different mechanisms to support
this sort of inferrence: an older mechanism called
<A href="iterator_tags.html">Iterator Tags</A>, and a newer mechanism called <tt><A href="iterator_traits.html">iterator_traits</A></tt>
<A href="#3">[3]</A>.
<h3>Concepts</h3>
<UL>
<LI>
<A href="trivial.html">Trivial Iterator</A>
<LI>
<A href="InputIterator.html">Input Iterator</A>
<LI>
<A href="OutputIterator.html">Output Iterator</A>
<LI>
<A href="ForwardIterator.html">Forward Iterator</A>
<LI>
<A href="BidirectionalIterator.html">Bidirectional Iterator</A>
<LI>
<A href="RandomAccessIterator.html">Random Access Iterator</A>
</UL>
<h3>Types</h3>
<UL>
<LI>
<tt><A href="istream_iterator.html">istream_iterator</A></tt>
<LI>
<tt><A href="ostream_iterator.html">ostream_iterator</A></tt>
</UL>
<UL>
<LI>
<tt><A href="ReverseIterator.html">reverse_iterator</A></tt>
<LI>
<tt><A href="ReverseBidirectionalIterator.html">reverse_bidirectional_iterator</A></tt>
<LI>
<tt><A href="insert_iterator.html">insert_iterator</A></tt>
<LI>
<tt><A href="front_insert_iterator.html">front_insert_iterator</A></tt>
<LI>
<tt><A href="back_insert_iterator.html">back_insert_iterator</A></tt>
</UL>
<UL>
<LI>
<tt><A href="iterator_traits.html">iterator_traits</A></tt>
</UL>
<UL>
<LI>
<tt><A href="input_iterator_tag.html">input_iterator_tag</A></tt>
<LI>
<tt><A href="output_iterator_tag.html">output_iterator_tag</A></tt>
<LI>
<tt><A href="forward_iterator_tag.html">forward_iterator_tag</A></tt>
<LI>
<tt><A href="bidirectional_iterator_tag.html">bidirectional_iterator_tag</A></tt>
<LI>
<tt><A href="random_access_iterator_tag.html">random_access_iterator_tag</A></tt>
</UL>
<UL>
<LI>
<tt><A href="input_iterator.html">input_iterator</A></tt>
<LI>
<tt><A href="output_iterator.html">output_iterator</A></tt>
<LI>
<tt><A href="forward_iterator.html">forward_iterator</A></tt>
<LI>
<tt><A href="bidirectional_iterator.html">bidirectional_iterator</A></tt>
<LI>
<tt><A href="random_access_iterator.html">random_access_iterator</A></tt>
</UL>
<h3>Functions</h3>
<UL>
<LI>
<tt><A href="distance_type.html">distance_type</A></tt>
<LI>
<tt><A href="value_type.html">value_type</A></tt>
<LI>
<tt><A href="iterator_category.html">iterator_category</A></tt>
</UL>
<UL>
<LI>
<tt><A href="distance.html">distance</A></tt>
<LI>
<tt><A href="advance.html">advance</A></tt>
</UL>
<UL>
<LI>
<tt><A href="insert_iterator.html">inserter</A></tt>
<LI>
<tt><A href="front_insert_iterator.html">front_inserter</A></tt>
<LI>
<tt><A href="back_insert_iterator.html">back_inserter</A></tt>
</UL>
<h3>Notes</h3>
<P><A name="1">[1]</A>
Ranges are not a well-defined concept for <A href="trivial.html">Trivial Iterators</A>,
because a <A href="trivial.html">Trivial Iterator</A> cannot be incremented: there is no such
thing as a next element. They are also not a well-defined concept
for <A href="OutputIterator.html">Output Iterators</A>, because it is impossible to compare two
<A href="OutputIterator.html">Output Iterators</A> for equality. Equality is crucial to the
definition of a range, because only by comparing an iterator for
equality with the last element is it possible to step through a range.
<P><A name="2">[2]</A>
Sometimes the notation <tt>[first, last)</tt> refers to the iterators
<tt>first</tt>, <tt>first+1</tt>, ..., <tt>last-1</tt> and sometimes it refers to the
objects pointed to by those iterators: <tt>*first</tt>, <tt>*(first+1)</tt>, ...,
<tt>*(last-1)</tt>. In most cases it will be obvious from context which of
these is meant; where the distinction is important, the notation will
be qualified explicitly as "range of iterators" or "range of objects".
<P><A name="3">[3]</A>
The <tt><A href="iterator_traits.html">iterator_traits</A></tt> class relies on a C++ feature known as
<i>partial specialization</i>. Many of today's compilers don't implement
the complete standard; in particular, many compilers do not support
partial specialization. If your compiler does not support partial
specialization, then you will not be able to use
<tt><A href="iterator_traits.html">iterator_traits</A></tt>, and you will instead have to continue using the
functions <tt><A href="iterator_category.html">iterator_category</A></tt>, <tt><A href="distance_type.html">distance_type</A></tt>, and
<tt><A href="value_type.html">value_type</A></tt>.
<h3>See also</h3>
<!--start footer-->
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54"
ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif"
HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright ©
1996 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML>
|
