📄 iterators.html
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Author" CONTENT="Zafir Anjum">
<TITLE>MFC Programmer's SourceBook : STL Programmer's Guide</TITLE>
<META name="description"
content="A freely available implementation
of the C++ Standard Template Library, including
hypertext documentation.">
<META name="keywords"
content="generic programming, STL, standard template library">
</HEAD>
<SCRIPT LANGUAGE="JavaScript"><!--
var adcategory = "cpp";
// -->
</SCRIPT>
<body background="../../fancyhome/back.gif" bgcolor="#FFFFFF" >
<SCRIPT LANGUAGE="JavaScript"><!--
var nfrm = location.href.indexOf("_nfrm_");
var validframes = (top.frames.length > 0 && top.frames['ad'] && top.frames['logo'] );
var random = Math.random();
if( !validframes && nfrm == -1 )
{
var dclkPage = "www.codeguru.com/";
if( self.adcategory )
dclkPage += adcategory;
else
dclkPage += "mfc";
document.write('<nolayer><center>');
document.write('<iframe src="http://ad.doubleclick.net/adi/' + dclkPage + ';ord='
+ random + '" width=470 height=62 marginwidth=0 marginheight=0 hspace=0 vspace=0 '
+ 'frameborder=0 scrolling=no bordercolor="#000000">');
document.write('<a href="http://ad.doubleclick.net/jump/' + dclkPage + ';ord='
+ random + '">');
document.write('<img src="http://ad.doubleclick.net/ad/' + dclkPage + ';ord='
+ random + '" height=60 width=468>' + '</a>');
document.write('</iframe>');
document.write('</center></nolayer>');
document.write('<layer src="http://ad.doubleclick.net/adl/' + dclkPage +
';ord=' + random + '"></layer>');
document.write('<ilayer visibility=hide width=468 height=83></ilayer>');
}
// top.location = "/show.cgi?" + adcategory + "=" + location.pathname;
// -->
</SCRIPT>
<noscript>
<p align="center">
<a href="http://ad.doubleclick.net/jump/www.codeguru.com/cpp;ord=Nupad9FCY34AAHfZfDU">
<img src="http://ad.doubleclick.net/ad/www.codeguru.com/cpp;ord=Nupad9FCY34AAHfZfDU"></a>
</p>
</noscript>
<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" tppabs="http://www.sgi.com/Technology/STL/OutputIterator.shtml">Output Iterator</A>, <A href="ForwardIterator.html" tppabs="http://www.sgi.com/Technology/STL/ForwardIterator.shtml">Forward Iterator</A>,
<A href="BidirectionalIterator.html">Bidirectional Iterator</A>, and <A href="RandomAccessIterator.html" tppabs="http://www.sgi.com/Technology/STL/RandomAccessIterator.shtml">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" tppabs="http://www.sgi.com/Technology/STL/InputIterator.shtml">Input Iterators</A> and
<A href="OutputIterator.html">Output Iterators</A>: they support the <A href="InputIterator.html" tppabs="http://www.sgi.com/Technology/STL/InputIterator.shtml">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" tppabs="http://www.sgi.com/Technology/STL/ForwardIterator.shtml">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" tppabs="http://www.sgi.com/Technology/STL/ForwardIterator.shtml">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" tppabs="http://www.sgi.com/Technology/STL/iterator_traits.shtml">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" tppabs="http://www.sgi.com/Technology/STL/distance_type.shtml">distance_type</A></tt>, and
<tt><A href="value_type.html">value_type</A></tt>.
<h3>See also</h3>
<HR SIZE="6"> <FONT SIZE="-2"> Copyright © 1996 Silicon Graphics, Inc.
<HR>
<TABLE BORDER=0 WIDTH="100%" >
<TR>
<TD WIDTH="33%"><FONT SIZE=-1><A HREF="index.html" >
STL</A></FONT></TD>
<TD WIDTH="33%">
<CENTER><FONT SIZE=-2>© Copyright 1997-1998 CodeGuru</FONT> </CENTER>
</TD>
<TD WIDTH="34%">
<DIV ALIGN=right><FONT SIZE=-1>Contact : <A HREF="mailto:webmaster@codeguru.com">webmaster@codeguru.com</A> </FONT></DIV>
</TD>
</TR>
</TABLE>
<SCRIPT LANGUAGE="JavaScript" ><!--
var adurl = "/cgi-bin/doubleclick.cgi?";
if( self.adcategory )
adurl += adcategory;
else
adurl += "mfc";
if( self.parent.norefreshad )
parent.norefreshad = false;
else if( validframes )
parent.frames['ad'].location = adurl;
if( !validframes && nfrm == -1)
{
var dclkPage = "www.codeguru.com/";
if( self.adcategory )
dclkPage += adcategory;
else
dclkPage += "mfc";
// var random = Math.random();
document.write('<nolayer><center>');
document.write('<iframe src="http://ad.doubleclick.net/adi/' + dclkPage + ';ord='
+ random + '" width=470 height=62 marginwidth=0 marginheight=0 hspace=0 vspace=0 '
+ 'frameborder=0 scrolling=no bordercolor="#000000">');
document.write('<a href="http://ad.doubleclick.net/jump/' + dclkPage + ';ord='
+ random + '">');
document.write('<img src="http://ad.doubleclick.net/ad/' + dclkPage + ';ord='
+ random + '" height=60 width=468>' + '</a>');
document.write('</iframe>');
document.write('</center></nolayer>');
document.write('<layer src="http://ad.doubleclick.net/adl/' + dclkPage +
';ord=' + random + '"></layer>');
document.write('<ilayer visibility=hide width=468 height=83></ilayer>');
}
// -->
</SCRIPT>
<!-- SCRIPT LANGUAGE="JavaScript" SRC="/global/fscript.js">
//
</SCRIPT -->
<noscript>
<p align="center">
<a href="http://ad.doubleclick.net/jump/www.codeguru.com/cpp;ord=Nupad9FCY34AAHfZfDU">
<img src="http://ad.doubleclick.net/ad/www.codeguru.com/cpp;ord=Nupad9FCY34AAHfZfDU"></a>
</p>
</noscript>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -