chap02.htm.kbk

来自「c++设计思想」· KBK 代码 · 共 1,047 行 · 第 1/5 页

different types of containers without knowing the underlying structure of those
containers.<I> </I>Every container produces iterators. You must always be able
to say:</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE>ContainerType::iterator
ContainerType::const_iterator</PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">to produce the types of the iterators
produced by that container. Every container has a <B>begin(&#160;)</B> method
that produces an iterator indicating the beginning of the elements in the
container, and an <B>end(&#160;)</B> method that produces an iterator which is
the as the <I>past-the-end value</I> of the container. If the container is
<B>const</B>&#184; <B>begin(&#160;)</B> and <B>end(&#160;)</B> produce
<B>const</B> iterators.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Every iterator can be moved forward to
the next element using the <B>operator++</B> (an iterator may be able to do more
than this, as you shall see, but it must at least support forward movement with
<B>operator++</B>).</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The basic iterator is only guaranteed to
be able to perform <B>==</B> and <B>!=</B> comparisons. Thus, to move an
iterator <B>it</B> forward without running it off the end you say something
like:</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#0000ff>while</font>(it != pastEnd) {
  <font color=#009900>// Do something</font>
  it++;
}</PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Where <B>pastEnd</B> is the past-the-end
value produced by the container&#8217;s <B>end(&#160;)</B> member
function.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">An iterator can be used to produce the
element that it is currently selecting within a container by dereferencing the
iterator. This can take two forms. If <B>it </B>is an iterator and <B>f(&#160;)
</B>is a member function of the objects held in the container that the iterator
is pointing within, then you can say either:</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE>(*it).f();</PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">or </FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE>it-&gt;f();</PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Knowing this, you can create a template
that works with any container. Here, the <B>apply(&#160;)</B> function template
calls a member function for every object in the container, using a pointer to
member that is passed as an argument:</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:Apply.cpp</font>
<font color=#009900>// Using basic iterators</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
<font color=#009900>//{-g++3}</font>
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;iterator&gt;
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;

<font color=#0000ff>template</font>&lt;<font color=#0000ff>class</font> Cont, <font color=#0000ff>class</font> PtrMemFun&gt;
<font color=#0000ff>void</font> apply(Cont&amp; c, PtrMemFun f) {
  <font color=#0000ff>typename</font> Cont::iterator it = c.begin();
  <font color=#0000ff>while</font>(it != c.end()) {
    (it-&gt;*f)(); <font color=#009900>// Compact form</font>
    ((*it).*f)(); <font color=#009900>// Alternate form</font>
    it++;
  }
}

<font color=#0000ff>class</font> Z {
  <font color=#0000ff>int</font> i;
<font color=#0000ff>public</font>:
  Z(<font color=#0000ff>int</font> ii) : i(ii) {}
  <font color=#0000ff>void</font> g() { i++; }
  <font color=#0000ff>friend</font> ostream&amp; 
  <font color=#0000ff>operator</font>&lt;&lt;(ostream&amp; os, <font color=#0000ff>const</font> Z&amp; z) {
    <font color=#0000ff>return</font> os &lt;&lt; z.i;
  }
};

<font color=#0000ff>int</font> main() {
  ostream_iterator&lt;Z&gt; out(cout, <font color=#004488>" "</font>);
  vector&lt;Z&gt; vz;
  <font color=#0000ff>for</font>(<font color=#0000ff>int</font> i = 0; i &lt; 10; i++)
    vz.push_back(Z(i));
  copy(vz.begin(), vz.end(), out);
  cout &lt;&lt; endl;
  apply(vz, &amp;Z::g);
  copy(vz.begin(), vz.end(), out);
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Because <B>operator-&gt;</B> is defined
for STL iterators, it can be used for pointer-to-member dereferencing (in the
following chapter you&#8217;ll learn a more elegant way to handle the problem of
applying a member function or ordinary function to every object in a
container).</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Much of the time, this is all you need to
know about iterators &#8211; that they are produced by <B>begin(&#160;)</B> and
<B>end(&#160;)</B>, and that you can use them to move through a container and
select elements. Many of the problems that you solve, and the STL algorithms
(covered in the next chapter) will allow you to just flail away with the basics
of iterators. However, things can at times become more subtle, and in those
cases you need to know more about iterators. The rest of this section gives you
the details.</FONT><A NAME="_Toc519042017"></A><BR></P></DIV>
<A NAME="Heading196"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H3 ALIGN="LEFT">
Iterators in reversible containers</H3></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">All containers must produce the basic
<B>iterator</B>. A container may also be <I>reversible</I>, which means that it
can produce iterators that move backwards from the end, as well as the iterators
that move forward from the beginning.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">A reversible container has the methods
<B>rbegin(&#160;)</B> (to produce a <B>reverse_iterator</B> selecting the end)
and <B>rend(&#160;)</B> (to produce a <B>reverse_iterator</B> indicating
&#8220;one past the beginning&#8221;). If the container is <B>const</B> then
<B>rbegin(&#160;)</B> and <B>rend(&#160;)</B> will produce
<B>const_reverse_iterator</B>s.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">All the basic sequence containers
<B>vector</B>, <B>deque</B> and <B>list</B> are reversible containers. The
following example uses <B>vector</B>, but will work with <B>deque</B> and
<B>list</B> as well:</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:Reversible.cpp</font>
<font color=#009900>// Using reversible containers</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <font color=#004488>"..</font><font color=#004488>/require.h"</font>
#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;fstream&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>"Reversible.cpp"</font>);
  assure(in, <font color=#004488>"Reversible.cpp"</font>);
  string line;
  vector&lt;string&gt; lines;
  <font color=#0000ff>while</font>(getline(in, line))
    lines.push_back(line);
  vector&lt;string&gt;::reverse_iterator r;
  <font color=#0000ff>for</font>(r = lines.rbegin(); r != lines.rend(); r++)
    cout &lt;&lt; *r &lt;&lt; endl;
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">You move backward through the container
using the same syntax as moving forward through a container with an ordinary
iterator.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The associative containers <B>set</B>,
<B>multiset</B>, <B>map</B> and <B>multimap</B> are also reversible. Using
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