📄 iterators.html
字号:
<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>Iterators</Title><!-- Generated by htmldoc --></HEAD><BODY TEXT="#000000" LINK="#006600" ALINK="#003300" VLINK="#7C7F87" BGCOLOR="#FFFFFF"><A HREF="/"><IMG SRC="/images/common/sgilogo_small.gif" ALT="SGI Logo" WIDTH="80" HEIGHT="72" BORDER="0"></A><P><!--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 areobjects that point to other objects. As the name suggests, iteratorsare often used to iterate over a range of objects: if an iteratorpoints to one element in a range, then it is possible to incrementit so that it points to the next element.<P>Iterators are central to generic programming because they are aninterface between containers and algorithms: algorithms typicallytake iterators as arguments, so a container need only provide a way toaccess its elements using iterators. This makes it possible to writea generic algorithm that operates on many different kinds ofcontainers, 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 functionsfor manipulating iterators.<h3>Description</h3>Iterators are in fact not a single concept, but six concepts thatform a hierarchy: some of them define only a very restricted set ofoperations, 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 sixthconcept, <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" algorithmsbut do not necessarily support "multi-pass" algorithms. <A href="InputIterator.html">Input iterators</A> only guarantee read access: it is possible todereference 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 throughan input iterator. Similarly, <A href="OutputIterator.html">Output Iterators</A> only guaranteewrite 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 additionalfunctionality. 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 itpoints 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>, allowmulti-pass algorithms. As the name suggests, they are different inthat they support motion in both directions: a <A href="BidirectionalIterator.html">Bidirectional Iterator</A> may be incremented to obtain the nextelement or decremented to obtain the previous element. A <A href="ForwardIterator.html">Forward Iterator</A>, by contrast, is only required to support forwardmotion. An iterator used to traverse a singly linked list, forexample, would be a <A href="ForwardIterator.html">Forward Iterator</A>, while an iterator used totraverse 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 ofpointer arithmetic: addition of arbitrary offsets, subscripting,subtraction of one iterator from another to find a distance, andso on.<P>Most algorithms are expressed not in terms of a single iterator but interms 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>notincluding</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 thereare <tt>n</tt> iterators in a range, then the notation <tt>[first, last)</tt>represents <tt>n+1</tt> positions. This is crucial: algorithms thatoperate 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 ableto return some value to indicate that the search was unsuccessful.<P>Sometimes it is important to be able to infer some properties of aniterator: the type of object that is returned when it is dereferenced,for example. There are two different mechanisms to supportthis 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 conceptfor <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 thedefinition of a range, because only by comparing an iterator forequality 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 theobjects 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 ofthese is meant; where the distinction is important, the notation willbe 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 implementthe complete standard; in particular, many compilers do not supportpartial specialization. If your compiler does not support partialspecialization, 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 thefunctions <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 --><!-- Footer Begins --><STYLE TYPE="text/css"><!--TD.footer, TD.footer A{ font-family: Arial, helvetica, sans-serif; font-size: 8pt;}A.home {font-family: Arial, helvetica, sans-serif;}--></STYLE><P><A CLASS="home" HREF="index.html">STL Home</A><P><TABLE WIDTH="600" CELLPADDING="0" CELLPADDING="0" BORDER="0"> <TR> <TD ALIGN="RIGHT" CLASS="footer"><A HREF="/company_info/terms.html" TARGET="_top">terms of use</A> | <A HREF="/company_info/privacy.html" TARGET="_top">privacy policy</A></TD> <TD ALIGN="CENTER" CLASS="footer"> | </TD> <TD ALIGN="LEFT" CLASS="footer"><A HREF="/cgi-bin/feedback/" TARGET="_top">contact us</A></TD> </TR><TR> <TD ALIGN="RIGHT" CLASS="footer">Copyright © 1993-2003 Silicon Graphics, Inc. All rights reserved.</TD> <TD ALIGN="CENTER" CLASS="footer"> | </TD> <TD ALIGN="LEFT" CLASS="footer"><A HREF="/company_info/trademarks/" TARGET="_top">Trademark Information</A></TD> </TR></TABLE><!-- Footer Ends --><!-- end footer --><P></BODY></HTML> ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -