chap07.htm

This is the second part of that lab manual to teach you how to make real-time programme and how to d

iterators with associative containers is a bit different, however, and will be
delayed until those containers are more fully
introduced.</FONT><A NAME="_Toc519042018"></A><BR></P></DIV>
<A NAME="Heading197"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H3 ALIGN="LEFT">
Iterator categories</H3></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The iterators are classified into
different &#8220;categories&#8221; which describe what they are capable of
doing. The order in which they are generally described moves from the categories
with the most restricted behavior to those with the most powerful
behavior.</FONT><BR></P></DIV>
<A NAME="Heading198"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H4 ALIGN="LEFT">
Input: read-only, one pass</H4></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The only predefined implementations of
input iterators are <B>istream_iterator</B> and <B>istreambuf_iterator</B>, to
read from an <B>istream</B>. As you can imagine, an input iterator can only be
dereferenced once for each element that&#8217;s selected, just as you can only
read a particular portion of an input stream once. They can only move forward.
There is a special constructor to define the past-the-end value. In summary, you
can dereference it for reading (once only for each value), and move it
forward.</FONT><BR></P></DIV>
<A NAME="Heading199"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H4 ALIGN="LEFT">
Output: write-only, one pass</H4></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">This is the complement of an input
iterator, but for writing rather than reading. The only predefined
implementations of output iterators are <B>ostream_iterator</B> and
<B>ostreambuf_iterator</B>, to write to an <B>ostream</B>, and the
less-commonly-used <B>raw_storage_iterator</B>. Again, these can only be
dereferenced once for each written value, and they can only move forward. There
is no concept of a terminal past-the-end value for an output iterator.
Summarizing, you can dereference it for writing (once only for each value) and
move it forward.</FONT><BR></P></DIV>
<A NAME="Heading200"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H4 ALIGN="LEFT">
Forward: multiple read/write</H4></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The forward iterator contains all the
functionality of both the input iterator and the output iterator, plus you can
dereference an iterator location multiple times, so you can read and write to a
value multiple times. As the name implies, you can only move forward. There are
no predefined iterators that are only forward iterators.</FONT><BR></P></DIV>
<A NAME="Heading201"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H4 ALIGN="LEFT">
Bidirectional: operator--</H4></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The bidirectional iterator has all the
functionality of the forward iterator, and in addition it can be moved backwards
one location at a time using <B>operator--</B>.</FONT><BR></P></DIV>
<A NAME="Heading202"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H4 ALIGN="LEFT">
Random-access: like a pointer</H4></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Finally, the random-access iterator has
all the functionality of the bidirectional iterator plus all the functionality
of a pointer (a pointer <I>is</I> a random-access iterator). Basically, anything
you can do with a pointer you can do with a random-access iterator, including
indexing with <B>operator[ ]</B>, adding integral values to a pointer to move it
forward or backward by a number of locations, and comparing one iterator to
another with <B>&lt;</B>, <B>&gt;=</B>,<B> </B>etc.</FONT><BR></P></DIV>
<A NAME="Heading203"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H4 ALIGN="LEFT">
Is this really important?</H4></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Why do you care about this
categorization? When you&#8217;re just using containers in a straightforward way
(for example, just hand-coding all the operations you want to perform on the
objects in the container) it usually doesn&#8217;t impact you too much. Things
either work or they don&#8217;t. The iterator categories become important
when:</FONT><BR></P></DIV>
<OL>
<LI><FONT FACE="Verdana">	</FONT><FONT FACE="Georgia">You use some of the
fancier built-in iterator types that will be demonstrated shortly. Or you
graduate to creating your own iterators (this will also be demonstrated, later
in this
chapter).</FONT><LI><FONT FACE="Verdana">	</FONT><FONT FACE="Georgia">You use
the STL algorithms (the subject of the next chapter). Each of the algorithms
have requirements that they place on the iterators that they work with.
Knowledge of the iterator categories is even more important when you create your
own reusable algorithm templates, because the iterator category that your
algorithm requires determines how flexible the algorithm will be. If you only
require the most primitive iterator category (input or output) then your
algorithm will work with <I>everything</I> (<B>copy(&#160;)</B> is an example of
this).</FONT><A NAME="_Toc519042019"></A></OL><A NAME="Heading204"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H3 ALIGN="LEFT">
Predefined iterators</H3></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The STL has a predefined set of iterator
classes that can be quite handy. For example, you&#8217;ve already seen
<B>reverse_iterator</B> (produced by calling <B>rbegin(&#160;)</B> and
<B>rend(&#160;)</B> for all the basic containers).</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <I>insertion iterators</I> are
necessary because some of the STL algorithms &#8211; <B>copy(&#160;)</B> for
example &#8211; use the assignment <B>operator=</B> in order to place objects in
the destination container. This is a problem when you&#8217;re using the
algorithm to <I>fill</I> the container rather than to overwrite items that are
already in the destination container. That is, when the space isn&#8217;t
already there. What the insert iterators do is change the implementation of the
<B>operator=</B> so that instead of doing an assignment, it calls a
&#8220;push&#8221; or &#8220;insert&#8221; function for that container, thus
causing it to allocate new space. The constructors for both
<B>back_insert_iterator</B> and <B>front_insert_iterator</B> take a basic
sequence container object (<B>vector</B>,<B> deque</B> or <B>list</B>) as their
argument and produce an iterator that calls <B>push_back(&#160;)</B> or
<B>push_front(&#160;)</B>, respectively, to perform assignment. The shorthand
functions <B>back_inserter(&#160;)</B> and <B>front_inserter(&#160;)</B> produce
the same objects with a little less typing. Since all the basic sequence
containers support <B>push_back(&#160;)</B>, you will probably find yourself
using <B>back_inserter(&#160;)</B> with some regularity.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>insert_iterator</B> allows you to
insert elements in the middle of the sequence, again replacing the meaning of
<B>operator=</B>, but this time with <B>insert(&#160;)</B> instead of one of the
&#8220;push&#8221; functions. The <B>insert(&#160;)</B> member function requires
an iterator indicating the place to insert before, so the <B>insert_iterator</B>
requires this iterator in addition to the container object. The shorthand
function <B>inserter(&#160;)</B> produces the same object.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The following example shows the use of
the different types of inserters:</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:Inserters.cpp</font>
<font color=#009900>// Different types of iterator inserters</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;deque&gt;
#include &lt;list&gt;
#include &lt;iterator&gt;
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;

<font color=#0000ff>int</font> a[] = { 1, 3, 5, 7, 11, 13, 17, 19, 23 };

<font color=#0000ff>template</font>&lt;<font color=#0000ff>class</font> Cont&gt;
<font color=#0000ff>void</font> frontInsertion(Cont&amp; ci) {
  copy(a, a + <font color=#0000ff>sizeof</font>(a)/<font color=#0000ff>sizeof</font>(<font color=#0000ff>int</font>), 
    front_inserter(ci));
  copy(ci.begin(), ci.end(),
    ostream_iterator&lt;<font color=#0000ff>int</font>&gt;(cout, <font color=#004488>" "</font>));
  cout &lt;&lt; endl;
}

<font color=#0000ff>template</font>&lt;<font color=#0000ff>class</font> Cont&gt;
<font color=#0000ff>void</font> backInsertion(Cont&amp; ci) {
  copy(a, a + <font color=#0000ff>sizeof</font>(a)/<font color=#0000ff>sizeof</font>(<font color=#0000ff>int</font>), 
    back_inserter(ci));
  copy(ci.begin(), ci.end(),
    ostream_iterator&lt;<font color=#0000ff>int</font>&gt;(cout, <font color=#004488>" "</font>));
  cout &lt;&lt; endl;
}

<font color=#0000ff>template</font>&lt;<font color=#0000ff>class</font> Cont&gt;
<font color=#0000ff>void</font> midInsertion(Cont&amp; ci) {
  <font color=#0000ff>typename</font> Cont::iterator it = ci.begin();
  it++; it++; it++;
  copy(a, a + <font color=#0000ff>sizeof</font>(a)/(<font color=#0000ff>sizeof</font>(<font color=#0000ff>int</font>) * 2),
    inserter(ci, it));
  copy(ci.begin(), ci.end(),
    ostream_iterator&lt;<font color=#0000ff>int</font>&gt;(cout, <font color=#004488>" "</font>));
  cout &lt;&lt; endl;
}

<font color=#0000ff>int</font> main() {
  deque&lt;<font color=#0000ff>int</font>&gt; di;
  list&lt;<font color=#0000ff>int</font>&gt;  li;
  vector&lt;<font color=#0000ff>int</font>&gt; vi;
  <font color=#009900>// Can't use a front_inserter() with vector</font>
  frontInsertion(di);
  frontInsertion(li);
  di.clear();
  li.clear();
  backInsertion(vi);
  backInsertion(di);
  backInsertion(li);
  midInsertion(vi);
  midInsertion(di);
  midInsertion(li);
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Since <B>vector</B> does not support
<B>push_front(&#160;)</B>, it cannot produce a <B>front_insertion_iterator</B>.
However, you can see that <B>vector</B> does support the other two types of
insertion (even though, as you shall see later, <B>insert(&#160;)</B> is not a
very efficient operation for <B>vector</B>).</FONT><BR></P></DIV>
<A NAME="Heading205"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H4 ALIGN="LEFT">
IO stream iterators</H4></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">You&#8217;ve already seen some use of the
<B>ostream_iterator</B> (an output iterator) in conjunction with
<B>copy(&#160;)</B> to place the contents of a container on an output stream.
There is a corresponding <B>istream_iterator</B> (an input iterator) which
allows you to &#8220;iterate&#8221; a set of objects of a specified type from an
input stream. An important difference between <B>ostream_iterator</B> and
<B>istream_iterator</B> comes from the fact that an output stream doesn&#8217;t
have any concept of an &#8220;end,&#8221; since you can always just keep writing
more elements. However, an input stream eventually terminates (for example, when
you reach the end of a file) so there needs to be a way to represent that. An
<B>istream_iterator</B> has two constructors, one that takes an <B>istream</B>
and produces the iterator you actually read from, and the other which is the
default constructor and produces an object which is the past-the-end sentinel.
In the following program this object is named <B>end</B>:</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:StreamIt.cpp</font>
<font color=#009900>// Iterators for istreams and ostreams</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
<font color=#009900>//{-msc}</font>
#include <font color=#004488>"..</font><font color=#004488>/require.h"</font>
#include &lt;iostream&gt;
#include &lt;fstream&gt;
#include &lt;vector&gt;
#include &lt;string&gt;
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;

<font color=#0000ff>int</font> main() {
  ifstream in(<font color=#004488>"StreamIt.cpp"</font>);
  assure(in, <font color=#004488>"StreamIt.cpp"</font>);
  istream_iterator&lt;string&gt; init(in), end;
  ostream_iterator&lt;string&gt; out(cout, <font color=#004488>"\n"</font>);
  vector&lt;string&gt; vs;
  copy(init, end, back_inserter(vs));
  copy(vs.begin(), vs.end(), out);
  *out++ = vs[0];
  *out++ = <font color=#004488>"That's all, folks!"</font>;
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">When <B>in</B> runs out of input (in this
case when the end of the file is reached) then <B>init</B> becomes equivalent to
<B>end</B> and the <B>copy(&#160;)</B> terminates.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Because <B>out</B> is an
<B>ostream_iterator&lt;string&gt;</B>, you can simply assign any <B>string</B>
ob