📄 randomaccessiterator.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=NupaitFCY34AAHeRCf4">
<img src="http://ad.doubleclick.net/ad/www.codeguru.com/cpp;ord=NupaitFCY34AAHeRCf4"></a>
</p>
</noscript>
<BR Clear>
<H1>Random Access 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 = "concept.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>: concept</TD>
</TR>
</Table>
<h3>Description</h3>
A Random Access Iterator is an iterator that provides both
increment and decrement (just like a <A href="BidirectionalIterator.html">Bidirectional Iterator</A>),
and that also provides constant-time methods for moving forward
and backward in arbitrary-sized steps. Random Access Iterators
provide essentially all of the operations of ordinary
C pointer arithmetic.
<h3>Refinement of</h3>
<A href="BidirectionalIterator.html">Bidirectional Iterator</A>, <A href="LessThanComparable.html" tppabs="http://www.sgi.com/Technology/STL/LessThanComparable.shtml">LessThan Comparable</A>
<h3>Associated types</h3>
The same as for <A href="BidirectionalIterator.html">Bidirectional Iterator</A>
<h3>Notation</h3>
<Table>
<TR>
<TD VAlign=top>
<tt>X</tt>
</TD>
<TD VAlign=top>
A type that is a model of Random Access Iterator
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>T</tt>
</TD>
<TD VAlign=top>
The value type of <tt>X</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>Distance</tt>
</TD>
<TD VAlign=top>
The distance type of <tt>X</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>i</tt>, <tt>j</tt>
</TD>
<TD VAlign=top>
Object of type <tt>X</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>t</tt>
</TD>
<TD VAlign=top>
Object of type <tt>T</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>n</tt>
</TD>
<TD VAlign=top>
Object of type <tt>Distance</tt>
</TD>
</tr>
</table>
<h3>Definitions</h3>
<h3>Valid expressions</h3>
In addition to the expressions defined in <A href="BidirectionalIterator.html">Bidirectional Iterator</A>,
the following expressions must be valid.
<Table border>
<TR>
<TH>
Name
</TH>
<TH>
Expression
</TH>
<TH>
Type requirements
</TH>
<TH>
Return type
</TH>
</TR>
<TR>
<TD VAlign=top>
Iterator addition
</TD>
<TD VAlign=top>
<tt>i += n</tt>
</TD>
<TD VAlign=top>
</TD>
<TD VAlign=top>
<tt>X&</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Iterator addition
</TD>
<TD VAlign=top>
<tt>i + n</tt> or <tt>n + i</tt>
</TD>
<TD VAlign=top>
</TD>
<TD VAlign=top>
<tt>X</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Iterator subtraction
</TD>
<TD VAlign=top>
<tt>i -= n</tt>
</TD>
<TD VAlign=top>
</TD>
<TD VAlign=top>
<tt>X&</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Iterator subtraction
</TD>
<TD VAlign=top>
<tt>i - n</tt>
</TD>
<TD VAlign=top>
</TD>
<TD VAlign=top>
<tt>X</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Difference
</TD>
<TD VAlign=top>
<tt>i - j</tt>
</TD>
<TD VAlign=top>
</TD>
<TD VAlign=top>
<tt>Distance</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Element operator
</TD>
<TD VAlign=top>
<tt>i[n]</tt>
</TD>
<TD VAlign=top>
</TD>
<TD VAlign=top>
Convertible to <tt>T</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
Element assignment
</TD>
<TD VAlign=top>
<tt>i[n] = t</tt>
</TD>
<TD VAlign=top>
<tt>X</tt> is mutable
</TD>
<TD VAlign=top>
Convertible to <tt>T</tt>
</TD>
</tr>
</table>
<h3>Expression semantics</h3>
Semantics of an expression is defined only where it differs from,
or is not defined in, <A href="BidirectionalIterator.html">Bidirectional Iterator</A> or
<A href="LessThanComparable.html">LessThan Comparable</A>.
<Table border>
<TR>
<TH>
Name
</TH>
<TH>
Expression
</TH>
<TH>
Precondition
</TH>
<TH>
Semantics
</TH>
<TH>
Postcondition
</TH>
</TR>
<TR>
<TD VAlign=top>
Forward motion
</TD>
<TD VAlign=top>
<tt>i += n</tt>
</TD>
<TD VAlign=top>
Including <tt>i</tt> itself, there must be <tt>n</tt> dereferenceable or
past-the-end iterators following or preceding <tt>i</tt>, depending
on whether <tt>n</tt> is positive or negative.
</TD>
<TD VAlign=top>
If <tt>n > 0</tt>, equivalent to executing <tt>++i</tt> <tt>n</tt> times. If <tt>n < 0</tt>,
equivalent to executing <tt>--i</tt> <tt>n</tt> times. If <tt>n == 0</tt>, this is
a null operation. <A href="#1">[1]</A>
</TD>
<TD VAlign=top>
<tt>i</tt> is dereferenceable or past-the-end.
</TD>
</TR>
<TR>
<TD VAlign=top>
Iterator addition
</TD>
<TD VAlign=top>
<tt>i + n</tt> or <tt>n + i</tt>
</TD>
<TD VAlign=top>
Same as for <tt>i += n</tt>
</TD>
<TD VAlign=top>
Equivalent to <tt>{ X tmp = i; return tmp += n; }</tt>. The two forms
<tt>i + n</tt> and <tt>n + i</tt> are identical.
</TD>
<TD VAlign=top>
Result is dereferenceable or past-the-end
</TD>
</TR>
<TR>
<TD VAlign=top>
Iterator subtraction
</TD>
<TD VAlign=top>
<tt>i -= n</tt>
</TD>
<TD VAlign=top>
Including <tt>i</tt> itself, there must be <tt>n</tt> dereferenceable or
past-the-end iterators preceding or following <tt>i</tt>, depending
on whether <tt>n</tt> is positive or negative.
</TD>
<TD VAlign=top>
Equivalent to <tt>i += (-n)</tt>.
</TD>
<TD VAlign=top>
<tt>i</tt> is dereferenceable or past-the-end.
</TD>
</TR>
<TR>
<TD VAlign=top>
Iterator subtraction
</TD>
<TD VAlign=top>
<tt>i - n</tt>
</TD>
<TD VAlign=top>
Same as for <tt>i -= n</tt>
</TD>
<TD VAlign=top>
Equivalent to <tt>{ X tmp = i; return tmp -= n; }</tt>.
</TD>
<TD VAlign=top>
Result is dereferenceable or past-the-end
</TD>
</TR>
<TR>
<TD VAlign=top>
Difference
</TD>
<TD VAlign=top>
<tt>i - j</tt>
</TD>
<TD VAlign=top>
Either <tt>i</tt> is reachable from <tt>j</tt> or <tt>j</tt> is reachable from <tt>i</tt>, or both.
</TD>
<TD VAlign=top>
Returns a number <tt>n</tt> such that <tt>i == j + n</tt>
</TD>
<TD VAlign=top>
</TD>
</TR>
<TR>
<TD VAlign=top>
Element operator
</TD>
<TD VAlign=top>
<tt>i[n]</tt>
</TD>
<TD VAlign=top>
<tt>i + n</tt> exists and is dereferenceable.
</TD>
<TD VAlign=top>
Equivalent to <tt>*(i + n)</tt> <A href="#2">[2]</A>
</TD>
<TD VAlign=top>
</TD>
</TR>
<TR>
<TD VAlign=top>
Element assignment
</TD>
<TD VAlign=top>
<tt>i[n] = t</tt>
</TD>
<TD VAlign=top>
<tt>i + n</tt> exists and is dereferenceable.
</TD>
<TD VAlign=top>
Equivalent to <tt>*(i + n) = t</tt> <A href="#2">[2]</A>
</TD>
<TD VAlign=top>
<tt>i[n]</tt> is a copy of <tt>t</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Less
</TD>
<TD VAlign=top>
<tt>i < j</tt>
</TD>
<TD VAlign=top>
Either <tt>i</tt> is reachable from <tt>j</tt> or <tt>j</tt> is reachable from <tt>i</tt>, or both. <A href="#3">[3]</A>
</TD>
<TD VAlign=top>
As described in <A href="LessThanComparable.html">LessThan Comparable</A> <A href="#4">[4]</A>
</TD>
<TD VAlign=top>
</TD>
</tr>
</table>
<h3>Complexity guarantees</h3>
All operations on Random Access Iterators are amortized constant
time. <A href="#5">[5]</A>
<h3>Invariants</h3>
<Table border>
<TR>
<TD VAlign=top>
Symmetry of addition and subtraction
</TD>
<TD VAlign=top>
If <tt>i + n</tt> is well-defined, then <tt>i += n; i -= n;</tt> and <tt>(i + n) - n</tt>
are null operations. Similarly, if <tt>i - n</tt> is well-defined,
then <tt>i -= n; i += n;</tt> and <tt>(i - n) + n</tt> are null operations.
</TD>
</TR>
<TR>
<TD VAlign=top>
Relation between distance and addition
</TD>
<TD VAlign=top>
If <tt>i - j</tt> is well-defined, then <tt>i == j + (i - j)</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Reachability and distance
</TD>
<TD VAlign=top>
If <tt>i</tt> is reachable from <tt>j</tt>, then <tt>i - j >= 0</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
Ordering
</TD>
<TD VAlign=top>
<tt>operator <</tt> is a strict weak ordering, as defined in
<A href="LessThanComparable.html">LessThan Comparable</A>.
</TD>
</tr>
</table>
<h3>Models</h3>
<UL>
<LI>
<tt>T*</tt>
<LI>
<tt><A href="Vector.html">vector</A><T>::iterator</tt>
<LI>
<tt><A href="Vector.html">vector</A><T>::const_iterator</tt>
<LI>
<tt><A href="Deque.html">deque</A><T>::iterator</tt>
<LI>
<tt><A href="Deque.html">deque</A><T>::const_iterator</tt>
</UL>
<h3>Notes</h3>
<P><A name="1">[1]</A>
"Equivalent to" merely means that <tt>i += n</tt> yields the same iterator
as if <tt>i</tt> had been incremented (decremented) <tt>n</tt> times. It does
not mean that this is how <tt>operator+=</tt> should be implemented; in fact,
this is not a permissible implementation. It is guaranteed that <tt>i += n</tt>
is amortized constant time, regardless of the magnitude of <tt>n</tt>. <A href="#5">[5]</A>
<P><A name="2">[2]</A>
One minor syntactic oddity: in C, if <tt>p</tt> is a pointer and
<tt>n</tt> is an int, then <tt>p[n]</tt> and <tt>n[p]</tt> are equivalent. This equivalence
is not guaranteed, however, for Random Access Iterators: only
<tt>i[n]</tt> need be supported. This isn't a terribly important restriction,
though, since the equivalence of <tt>p[n]</tt> and <tt>n[p]</tt> has essentially
no application except for obfuscated C contests.
<P><A name="3">[3]</A>
The precondition defined in <A href="LessThanComparable.html">LessThan Comparable</A> is that <tt>i</tt>
and <tt>j</tt> be in the domain of <tt>operator <</tt>. Essentially, then, this
is a definition of that domain: it is the set of pairs of iterators such
that one iterator is reachable from the other.
<P><A name="4">[4]</A>
All of the other comparison operators have the same domain and
are defined in terms of <tt>operator <</tt>, so they have exactly the same
semantics as described in <A href="LessThanComparable.html">LessThan Comparable</A>.
<P><A name="5">[5]</A>
This complexity guarantee is in fact the only reason why
Random Access Iterator exists as a distinct concept. Every
operation in iterator arithmetic can be defined for
<A href="BidirectionalIterator.html">Bidirectional Iterators</A>; in fact, that is exactly what the
algorithms <tt><A href="advance.html">advance</A></tt> and <tt><A href="distance.html" tppabs="http://www.sgi.com/Technology/STL/distance.shtml">distance</A></tt> do. The distinction is
simply that the <A href="BidirectionalIterator.html">Bidirectional Iterator</A> implementations are
linear time, while Random Access Iterators are required to support
random access to elements in amortized constant time. This has
major implications for the sorts of algorithms that can sensibly
be written using the two types of iterators.
<h3>See also</h3>
<A href="LessThanComparable.html">LessThan Comparable</A>, <A href="trivial.html" tppabs="http://www.sgi.com/Technology/STL/trivial.shtml">Trivial Iterator</A>,
<A href="BidirectionalIterator.html">Bidirectional Iterator</A>, <A href="Iterators.html" tppabs="http://www.sgi.com/Technology/STL/Iterators.shtml">Iterator overview</A>
<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=NupaitFCY34AAHeRCf4">
<img src="http://ad.doubleclick.net/ad/www.codeguru.com/cpp;ord=NupaitFCY34AAHeRCf4"></a>
</p>
</noscript>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -