var_0565.htm

C++标准库 C++标准库 C++标准库 C++标准库

<P>This algorithm illustrates three requirements for an input iterator:</P>
<UL>
<LI>An iterator can be compared for equality to another iterator.  They are equal when they point to the same position, and are otherwise not equal.</P>
<LI>An iterator can be dereferenced using the <SAMP>*</SAMP> operator, to obtain the value being denoted by the iterator.</LI>
<LI>An iterator can be incremented, so that it refers to the next element in sequence, using the operator <SAMP>++</SAMP>.</LI>
</UL>
<P>Notice that these characteristics can all be provided with new meanings in a C++ program, since the behavior of the given functions can all be modified by overloading the appropriate operators.  Because of this overloading, iterators are possible.  There are three main varieties of input iterators:</P>
<P><B>Ordinary pointers</B>.  Ordinary pointers can be used as input iterators.  In fact, since we can subscript and add to ordinary pointers, they are random access values, and thus can be used either as input or output iterators.  The end-of-range pointer describes the end of a contiguous region of memory, and the deference and increment operators have their conventional meanings.  For example, the following searches for the value 7 in an array of integers:</P>

<A HREF="sidebar1.htm#sidebar4"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Ordinary Pointers as Iterators</STRONG></A>
<PRE>int data[100];
   ...
int * where = find(data, data+100, 7);
</PRE>
<P>Note that constant pointers, pointers which do not permit the underlying array to be modified, can be created by simply placing the keyword <SAMP>const</SAMP> in a declaration.</P>
<PRE>const int * first = data;
const int * last = data + 100;
   // can't modify location returned by the following
const int * where = find(first, last, 7);
</PRE>
<A NAME="idx12"><!></A>
<P><B>Container iterators</B>.  All of the iterators constructed for the various containers provided by the standard library are at <I>least</I> as general as input iterators.  The iterator for the first element in a collection is always constructed by the member function<SAMP> begin(),</SAMP> while the iterator that denotes the "past-the-end" location is generated by the member function <SAMP>end().</SAMP>  For example, the following searches for the value 7 in a list of integers:</P>
<PRE>list&#60;int>::iterator where = find(aList.begin(), aList.end(), 7);
</PRE>
<P>Each container that supports iterators provides a type within the class declaration with the name <SAMP>iterator</SAMP>.  Using this, iterators can uniformly be declared in the fashion shown.  If the container being accessed is constant, or if the description <SAMP>const_iterator</SAMP> is used, then the iterator is a constant iterator.</P>
<P><B>Input stream iterators</B>.  The standard library provides a mechanism to operate on an input <I>stream</I> using an input iterator.  This ability is provided by the class <SAMP>istream_iterator</SAMP>, and will be described in more detail in <A HREF="str_7181.htm#2.3.1">Section 2.3.1</A>.</P>

<A NAME="2.2.2"><H3>2.2.2 Output Iterators</H3></A>
<A NAME="idx13"><!></A>
<P>An output iterator has the opposite function from an input iterator.  Output iterators can be used to assign values in a sequence, but cannot be used to access values.  For example, we can use an output iterator in a generic algorithm that copies values from one sequence into another:</P>
<PRE>template &#60;class InputIterator, class OutputIterator>
OutputIterator copy
   (InputIterator first, InputIterator last, OutputIterator result) 
{
    while (first != last) 
      *result++ = *first++;
    return result;
}
</PRE>

<A HREF="sidebar1.htm#sidebar5"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Parallel Sequences</STRONG></A>

<P>Two ranges are being manipulated here; the range of source values specified by a pair of input iterators, and the destination range.  The latter, however, is specified by only a single argument.  It is assumed that the destination is large enough to include all values, and errors will ensue if this is not the case.</P>
<P>As illustrated by this algorithm, an output iterator can modify the element to which it points, by being used as the target for an assignment.  Output iterators can use the dereference operator only in this fashion, and cannot be used to return or access the elements they denote. </P>
<P>As we noted earlier, ordinary pointers, as well as all the iterators constructed by containers in the standard library, can be used as examples of output iterators.  (Ordinary pointers are random access iterators, which are a superset of output iterators.)  So, for example, the following code fragment copies elements from an ordinary C-style array into a standard library vector:</P>
<PRE>int data[100];
vector&#60;int> newdata(100);
   ...
copy (data, data+100, newdata.begin());
</PRE>
<P>Just as the <SAMP>istream_iterator</SAMP> provided a way to  operate on an input stream using the input iterator mechanism, the standard library provides a data type, <SAMP>ostream_iterator</SAMP>, that permits values to be written to an output stream in an iterator-like fashion.  These will be described in <A HREF="str_7181.htm#2.3.2">Section 2.3.2</A>.</P>
<P>Yet another form of  output iterator is an <I>insert iterator</I>.  An insert iterator changes the output iterator operations of dereferencing/assignment and increment into insertions into a container.  This permits operations such as <SAMP>copy()</SAMP> to be used with variable length containers, such as lists and sets.  Insert iterators will be described in more detail in <A HREF="ins_0332.htm">Section 2.4</A>.</P>

<A NAME="2.2.3"><H3>2.2.3 Forward Iterators</H3></A>
<A NAME="idx14"><!></A>
<P>A forward iterator combines the features of an input iterator and an output iterator.  It permits values to both be accessed and modified.  One function that uses forward iterators is the <SAMP>replace()</SAMP> generic algorithm, which replaces occurrences of specific values with other values.  This algorithm is written as follows:</P>
<PRE>template &#60;class ForwardIterator, class T>
void 
   replace (ForwardIterator first, ForwardIterator last, 
            const T&#38; old_value, const T&#38; new_value)
{
    while (first != last) 
    {
    if (*first == old_value) 
        *first = new_value;
        ++first;
    }
}
</PRE>
<P>Ordinary pointers, as well as any of the iterators produced by containers in the standard library, can be used as forward iterators.  The following, for example, replaces instances of the value 7 with the value 11 in a vector of integers.</P>
<PRE>    replace (aVec.begin(), aVec.end(), 7, 11);</PRE>

<A NAME="2.2.4"><H3>2.2.4 Bidirectional Iterators</H3></A>
<A NAME="idx15"><!></A>
<P>A bidirectional iterator is similar to a forward iterator, except that bidirectional iterators support the decrement operator (operator <SAMP>--</SAMP>), permitting movement in either a forward or a backward direction through the elements of a container.  For example, we can use bidirectional iterators in a function that reverses the values of a container, placing the results into a new container.</P>
<PRE>template &#60;class BidirectionalIterator, class OutputIterator>
OutputIterator 
   reverse_copy (BidirectionalIterator first,
                 BidirectionalIterator last,
                 OutputIterator result) 
{
    while (first != last) 
    *result++ = *--last;
    return result;
}
</PRE>
<P>As always, the value initially denoted by the <SAMP>last</SAMP> argument is not considered to be part of the collection.</P>
<P>The <SAMP>reverse_copy()</SAMP> function could be used, for example, to reverse the values of a linked list, and place the result into a vector:</P>
<PRE>   list&#60;int> aList;
    ....
   vector&#60;int> aVec (aList.size());
   reverse_copy (aList.begin(), aList.end(), aVec.begin() );
</PRE>

<A NAME="2.2.5"><H3>2.2.5 Random Access Iterators</H3></A>
<A NAME="idx16"><!></A>
<P>Some algorithms require more functionality than the ability to access values in either a forward or backward direction.  Random access iterators permit values to be accessed by subscript, subtracted one from another (to yield the number of elements between their respective values) or modified by arithmetic operations, all in a manner similar to conventional pointers.</P>
<P>When using conventional pointers, arithmetic operations can be related to the underlying memory; that is, <SAMP>x+10</SAMP> is the memory ten elements after the beginning of <SAMP>x</SAMP>.  With iterators the logical meaning is preserved (<SAMP>x+10</SAMP> is the tenth element after <SAMP>x</SAMP>), however the physical addresses being described may be different.</P>
<P>Algorithms that use random access iterators include generic operations such as sorting and binary search.  For example, the following algorithm randomly shuffles the elements of a container.  This is similar to, although simpler than, the function <SAMP>random_shuffle()</SAMP> provided by the standard library.</P>
<PRE>template &#60;class RandomAccessIterator>
void
   mixup (RandomAccessIterator first, RandomAccessIterator last)
{
   while (first &#60; last) 
   {
      iter_swap(first, first + randomInteger(last - first));
      ++first;
   }
}
</PRE>

<A HREF="sidebar1.htm#sidebar6"><IMG SRC="images/note.gif" BORDER=0> <STRONG>randomInteger()</STRONG></A>

<A NAME="idx17"><!></A>
<P>The program will cycle as long as <SAMP>first</SAMP> is denoting a position that occurs earlier in the sequence than the one denoted by <SAMP>last</SAMP>.  Only random access iterators can be compared using relational operators; all other iterators can be compared only for equality or inequality.  On each cycle through the loop, the expression <SAMP>last - first</SAMP> yields the number of elements between the two limits.  The function <SAMP>randomInteger()</SAMP> is assumed to generate a random number between 0 and the argument.  Using the standard random number generator, this function could be written as follows:</P>
<PRE>unsigned int randomInteger (unsigned int n)
   // return random integer greater than
   // or equal to 0 and less than n
{
   return rand() % n;</PRE>
<P>}</P>
<P>This random value is added to the iterator <SAMP>first</SAMP>, resulting in an iterator to a randomly selected value in the container.  This value is then swapped with the element denoted by the iterator <SAMP>first</SAMP>.</P>

<A NAME="2.2.6"><H3>2.2.6 Reverse Iterators</H3></A>
<A NAME="idx18"><!></A>
<P>An iterator naturally imposes an order on an underlying container of values.  For a <A HREF="../stdlibcr/vec_0251.htm"><B><I>vector</I></B></A> or a <A HREF="../stdlibcr/map_8018.htm"><B><I>map</I></B></A> the order is given by increasing index values.  For a <A HREF="../stdlibcr/set_1649.htm"><B><I>set</I></B></A> it is the increasing order of the elements held in the container.  For a <A HREF="../stdlibcr/lis_3222.htm"><B><I>list</I></B></A> the order is explicitly derived from the way values are inserted.</P>
<P>A <I>reverse iterator</I> will yield values in exactly the reverse order of those given by the standard iterators.  That is, for a vector or a list, a reverse iterator will generate the last element first, and the first element last.  For a set it will generate the largest element first, and the smallest element last.  Strictly speaking, reverse iterators are not themselves a new category of iterator.  Rather, there are reverse bidirectional iterators, reverse random access iterators, and so on.</P>
<P>The <A HREF="../stdlibcr/lis_3222.htm"><B><I>list</I></B></A>, <A HREF="../stdlibcr/set_1649.htm"><B><I>set</I></B></A> and <A HREF="../stdlibcr/map_8018.htm"><B><I>map</I></B></A> data types provide a pair of member functions that produce reverse bidirectional iterators.  The functions <SAMP>rbegin()</SAMP> and <SAMP>rend()</SAMP> generate iterators that cycle through the underlying container in reverse order.  Increments to such iterators move backward, and decrements move forward through the sequence.</P>
<P>Similarly, the <A HREF="../stdlibcr/vec_0251.htm"><B><I>vector</I></B></A> and <A HREF="../stdlibcr/deq_4164.htm"><B><I>deque</I></B></A> data types provide functions (also named <SAMP>rbegin()</SAMP> and <SAMP>rend()</SAMP>) that produce reverse random access iterators.  Subscript and addition operators, as well as increments to such iterators move backward within the sequence.</P>
<HR>
<A HREF="int_2158.htm"><IMG SRC="images/prev.gif"></A> <A HREF="booktoc1.htm"><IMG SRC="images/toc.gif"></A><A HREF="tindex1.htm"><IMG SRC="images/tindex.gif"></A><A HREF="str_7181.htm"><IMG SRC="images/next.gif"></A><P>&copy;Copyright 1996, Rogue Wave Software, Inc.</P>
</BODY></HTML>