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
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
|
<HTML>
<!--
-- Copyright (c) 1996-1999
-- 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>iterator_traits<Iterator></Title>
<!-- Generated by htmldoc -->
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="CorpID.gif"
ALT="SGI" HEIGHT="43" WIDTH="151">
<!--end header-->
<BR Clear>
<H1>iterator_traits<Iterator></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 = "type.gif" Alt="" WIDTH = "194" HEIGHT = "39" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: iterators</TD>
<TD Align=right VAlign=top><b>Component type</b>: type</TD>
</TR>
</Table>
<h3>Description</h3>
As described in the <A href="Iterators.html">Iterator Overview</A>, one of the most important
facts about iterators is that they have associated types. An iterator
type, for example, has an associated <i>value type</i>: the type of
object that the iterator points to. It also has an associated
<i>distance type</i>, or <i>difference type</i>, a signed integral type that
can be used to represent the distance between two iterators.
<P>
(Pointers, for example, are iterators; the value type of
<tt>int*</tt> is <tt>int</tt>. Its distance type is <tt>ptrdiff_t</tt>, because, if
<tt>p1</tt> and <tt>p2</tt> are pointers, the expression <tt>p1 - p2</tt> has type
<tt>ptrdiff_t</tt>.)
<P>
Generic algorithms often need to have access to these associated
types; an algorithm that takes a range of iterators, for example,
might need to declare a temporary variable whose type is the
iterators' value type. The class <tt>iterator_traits</tt> is a
mechanism that allows such declarations.
<P>
The most obvious way to allow declarations of that sort would
be to require that all iterators declare nested types; an iterator
<tt>I</tt>'s value type, for example, would be <tt>I::value_type</tt>. That
can't possibly work, though. Pointers are iterators, and
pointers aren't classes; if <tt>I</tt> is (say) <tt>int*</tt>, then it's
impossible to define <tt>I::value_type</tt> to be <tt>int</tt>.
Instead, <tt>I</tt>'s value type is written <tt>iterator_traits<I>::value_type</tt>.
<tt>iterator_traits</tt> is a template class that contains nothing but
nested <tt>typedef</tt>s; in addition to <tt>value_type</tt>, <tt>iterator_traits</tt>
defines the nested types <tt>iterator_category</tt>, <tt>difference_type</tt>,
<tt>pointer</tt>, and <tt>reference</tt>.
<P>
The library contains two definitions of <tt>iterator_traits</tt>:
a fully generic one, and a specialization that is used whenever
the template argument is a pointer type <A href="#1">[1]</A>. The fully
generic version defines <tt>iterator_traits<I>::value_type</tt> as
a synonym for <tt>I::value_type</tt>,
<tt>iterator_traits<I>::difference_type</tt> as a synonym for
<tt>I::difference_type</tt>, and so on. Since pointers don't have
nested types, <tt>iterator_traits<T*></tt> has a different definition.
<P>
The implementation of <tt>iterator_traits</tt> is actually simpler
than this discussion.
<pre>
template <class Iterator>
struct iterator_traits {
typedef typename Iterator::iterator_category iterator_category;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
};
template <class T>
struct iterator_traits<T*> {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
};
</pre>
<P>
If you are defining a new iterator type <tt>I</tt>, then you must ensure
that <tt>iterator_traits<I></tt> is defined properly. There are two ways
to do this. First, you can define your iterator so that it has
nested types <tt>I::value_type</tt>, <tt>I::difference_type</tt>, and so on.
Second, you can explicitly specialize <tt>iterator_traits</tt> for your
type. The first way is almost always more convenient, however,
especially since you can easily ensure that your iterator has
the appropriate nested types just by inheriting from one of the
base classes <tt><A href="input_iterator.html">input_iterator</A></tt>, <tt><A href="output_iterator.html">output_iterator</A></tt>,
<tt><A href="forward_iterator.html">forward_iterator</A></tt>, <tt><A href="bidirectional_iterator.html">bidirectional_iterator</A></tt>, or
<tt><A href="random_access_iterator.html">random_access_iterator</A></tt>.
<P>
Note that <tt>iterator_traits</tt> is new; it was added to the draft C++
standard relatively recently. Both the old <A href="iterator_tags.html">iterator tags</A>
mechanism and the new <tt>iterator_traits</tt> mechanism are currently
supported <A href="#1">[1]</A>, but the old iterator tag functions are no longer
part of the standard C++ library and they will eventually be
removed.
<h3>Example</h3>
This generic function returns the last element in a non-empty range.
Note that there is no way to define a function with this interface
in terms of the old <tt><A href="value_type.html">value_type</A></tt> function, because the function's
return type must be declared to be the iterator's value type.
<pre>
template <class InputIterator>
iterator_traits<InputIterator>::value_type
last_value(InputIterator first, InputIterator last) {
iterator_traits<InputIterator>::value_type result = *first;
for (++first; first != last; ++first)
result = *first;
return result;
}
</pre>
<P>
(Note: this is an example of how to use <tt>iterator_traits</tt>; it is not
an example of good code. There are better ways of finding the last
element in a range of <A href="BidirectionalIterator.html">bidirectional iterators</A>, or even
<A href="ForwardIterator.html">forward iterators</A>.)
<h3>Definition</h3>
Defined in the standard header <A href="iterator">iterator</A>, and in the
nonstandard backward-compatibility header <A href="iterator.h">iterator.h</A>.
<h3>Template parameters</h3>
<Table border>
<TR>
<TH>
Parameter
</TH>
<TH>
Description
</TH>
<TH>
Default
</TH>
</TR>
<TR>
<TD VAlign=top>
<tt>Iterator</tt>
</TD>
<TD VAlign=top>
The iterator type whose associated types are being accessed.
</TD>
<TD VAlign=top>
</TD>
</tr>
</table>
<h3>Model of</h3>
<A href="DefaultConstructible.html">Default Constructible</A>, <A href="Assignable.html">Assignable</A>
<h3>Type requirements</h3>
<UL>
<LI>
<tt>Iterator</tt> is a model of one of the iterator concepts.
(<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>, or <A href="RandomAccessIterator.html">Random Access Iterator</A>.)
</UL>
<h3>Public base classes</h3>
None.
<h3>Members</h3>
None, except for nested types.
<Table border>
<TR>
<TH>
Member
</TH>
<TH>
Description
</TH>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator_category</tt>
</TD>
<TD VAlign=top>
One of the types <tt>input_iterator_tag</tt>, <tt>output_iterator_tag</tt>,
<tt>forward_iterator_tag</tt>, <tt>bidirectional_iterator_tag</tt>, or
<tt>random_access_iterator_tag</tt>. An iterator's category is the
<i>most specific</i> iterator concept that it is a model of.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>value_type</tt>
</TD>
<TD VAlign=top>
<tt>Iterator</tt>'s value type, as defined in the <A href="trivial.html">Trivial Iterator</A>
requirements.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>difference_type</tt>
</TD>
<TD VAlign=top>
<tt>Iterator</tt>'s distance type, as defined in the <A href="InputIterator.html">Input Iterator</A>
requirements.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>pointer</tt>
</TD>
<TD VAlign=top>
<tt>Iterator</tt>'s pointer type: a pointer to its value type.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reference</tt>
</TD>
<TD VAlign=top>
<tt>Iterator</tt>'s reference type: a reference to its value type.
</TD>
</tr>
</table>
<h3>Notes</h3>
<P><A name="3">[3]</A>
The <tt>iterator_traits</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>iterator_traits</tt>, and you will have to continue using the old
iterator tag 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>. This is one reason that those functions have not
yet been removed.
<h3>See also</h3>
The <A href="Iterators.html">iterator overview</A>,
<A href="iterator_tags.html">iterator tags</A>,
<tt><A href="input_iterator_tag.html">input_iterator_tag</A>,
</tt><A href="output_iterator_tag.html">output_iterator_tag</A>,
<tt><A href="forward_iterator_tag.html">forward_iterator_tag</A>,
</tt><A href="bidirectional_iterator_tag.html">bidirectional_iterator_tag</A>,
<tt><A href="random_access_iterator_tag.html">random_access_iterator_tag</A>,
</tt><A href="input_iterator.html">input_iterator</A>,
<tt><A href="output_iterator.html">output_iterator</A>,
</tt><A href="forward_iterator.html">forward_iterator</A>,
<tt><A href="bidirectional_iterator.html">bidirectional_iterator</A>,
</tt><A href="random_access_iterator.html">random_access_iterator</A>
<!--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 ©
1999 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>
|
