chap02.htm.kbk

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

file, but everything else is the same as in <B>Intset.cpp</B>. The
<B>operator&gt;&gt;</B> returns a whitespace-separated group of characters each
time it is called, until there&#8217;s no more input from the file. So it
approximately breaks an input stream up into words. Each <B>string</B> is placed
in the <B>set </B>using <B>insert(&#160;)</B>, and the <B>copy(&#160;)</B>
function is used to display the results. Because of the way <B>set</B> is
implemented (as a tree), the words are automatically sorted.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Consider how much effort it would be to
accomplish the same task in C, or even in C++ without the
STL.</FONT><A NAME="_Toc519042013"></A><BR></P></DIV>
<A NAME="Heading192"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H2 ALIGN="LEFT">
The basic concepts</H2></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The primary idea in the STL is the
<I>container</I> (also known as a <I>collection</I>), which is just what it
sounds like: a place to hold things. You need containers because objects are
constantly marching in and out of your program and there must be someplace to
put them while they&#8217;re around. You can&#8217;t make named local objects
because in a typical program you don&#8217;t know how many, or what type, or the
lifetime of the objects you&#8217;re working with. So you need a container that
will expand whenever necessary to fill your needs.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">All the containers in the STL hold
objects and expand themselves. In addition, they hold your objects in a
particular way. The difference between one container and another is the way the
objects are held and how the sequence is created. Let&#8217;s start by looking
at the simplest containers.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">A <B>vector</B> is a linear sequence that
allows rapid random access to its elements. However, it&#8217;s expensive to
insert an element in the middle of the sequence, and is also expensive when it
allocates additional storage. A <B>deque</B> is also a linear sequence, and it
allows random access that&#8217;s nearly as fast as<B> vector</B>, but
it&#8217;s significantly faster when it needs to allocate new storage, and you
can easily add new elements at either end (<B>vector </B>only allows the
addition of elements at its tail). A <B>list</B> the third type of basic linear
sequence, but it&#8217;s expensive to move around randomly and cheap to insert
an element in the middle. Thus <B>list</B>, <B>deque</B> and <B>vector</B> are
very similar in their basic functionality (they all hold linear sequences), but
different in the cost of their activities. So for your first shot at a program,
you could choose any one, and only experiment with the others if you&#8217;re
tuning for efficiency.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Many of the problems you set out to solve
will only require a simple linear sequence like a <B>vector</B>, <B>deque</B> or
<B>list</B>. All three have a member function <B>push_back(&#160;)</B> which you
use to insert a new element at the back of the sequence (<B>deque</B> and
<B>list</B> also have <B>push_front(&#160;)</B>).</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">But now how do you retrieve those
elements? With a <B>vector</B> or <B>deque</B>, it is possible to use the
indexing <B>operator[ ]</B>, but that doesn&#8217;t work with <B>list</B>. Since
it would be nicest to learn a single interface, we&#8217;ll often use the one
defined for all STL containers: the <I>iterator</I>.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">An iterator is a class that abstracts the
process of moving through a sequence. It allows you to select each element of a
sequence <I>without knowing the underlying structure of that sequence</I>. This
is a powerful feature, partly because it allows us to learn a single interface
that works with all containers, and partly because it allows containers to be
used interchangeably.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">One more observation and you&#8217;re
ready for another example. Even though the STL containers hold objects by value
(that is, they hold the whole object inside themselves) that&#8217;s probably
not the way you&#8217;ll generally use them if you&#8217;re doing
object-oriented programming. That&#8217;s because in OOP, most of the time
you&#8217;ll create objects on the heap with <B>new</B> and then <I>upcast</I>
the address to the base-class type, later manipulating it as a pointer to the
base class. The beauty of this is that you don&#8217;t worry about the specific
type of object you&#8217;re dealing with, which greatly reduces the complexity
of your code and increases the maintainability of your program. This process of
upcasting is what you try to do in OOP with polymorphism, so you&#8217;ll
usually be using containers of pointers.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Consider the classic &#8220;shape&#8221;
example where shapes have a set of common operations, and you have different
types of shapes. Here&#8217;s what it looks like using the STL <B>vector</B> to
hold pointers to various types of <B>Shape</B> created on the
heap:</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:Stlshape.cpp</font>
<font color=#009900>// Simple shapes w/ STL</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include &lt;vector&gt;
#include &lt;iostream&gt;
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;

<font color=#0000ff>class</font> Shape {
<font color=#0000ff>public</font>:
  <font color=#0000ff>virtual</font> <font color=#0000ff>void</font> draw() = 0;
  <font color=#0000ff>virtual</font> ~Shape() {};
};

<font color=#0000ff>class</font> Circle : <font color=#0000ff>public</font> Shape {
<font color=#0000ff>public</font>:
  <font color=#0000ff>void</font> draw() { cout &lt;&lt; <font color=#004488>"Circle::draw\n"</font>; }
  ~Circle() { cout &lt;&lt; <font color=#004488>"~Circle\n"</font>; }
};

<font color=#0000ff>class</font> Triangle : <font color=#0000ff>public</font> Shape {
<font color=#0000ff>public</font>:
  <font color=#0000ff>void</font> draw() { cout &lt;&lt; <font color=#004488>"Triangle::draw\n"</font>; }
  ~Triangle() { cout &lt;&lt; <font color=#004488>"~Triangle\n"</font>; }
};

<font color=#0000ff>class</font> Square : <font color=#0000ff>public</font> Shape {
<font color=#0000ff>public</font>:
  <font color=#0000ff>void</font> draw() { cout &lt;&lt; <font color=#004488>"Square::draw\n"</font>; }
  ~Square() { cout &lt;&lt; <font color=#004488>"~Square\n"</font>; }
};

<font color=#0000ff>typedef</font> std::vector&lt;Shape*&gt; Container;
<font color=#0000ff>typedef</font> Container::iterator Iter;

<font color=#0000ff>int</font> main() {
  Container shapes;
  shapes.push_back(<font color=#0000ff>new</font> Circle);
  shapes.push_back(<font color=#0000ff>new</font> Square);
  shapes.push_back(<font color=#0000ff>new</font> Triangle);
  <font color=#0000ff>for</font>(Iter i = shapes.begin();
      i != shapes.end(); i++)
    (*i)-&gt;draw();
  <font color=#009900>// ... Sometime later:</font>
  <font color=#0000ff>for</font>(Iter j = shapes.begin();
      j != shapes.end(); j++)
    <font color=#0000ff>delete</font> *j;
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The creation of <B>Shape</B>,
<B>Circle</B>, <B>Square</B> and <B>Triangle</B> should be fairly familiar.
<B>Shape</B> is a pure abstract base class (because of the <I>pure specifier</I>
<B>=0</B>) that defines the interface for all types of <B>shapes</B>. The
derived classes redefine the <B>virtual</B> function <B>draw(&#160;)</B> to
perform the appropriate operation. Now we&#8217;d like to create a bunch of
different types of <B>Shape</B> object, but where to put them? In an STL
container, of course. For convenience, this <B>typedef</B>:</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#0000ff>typedef</font> std::vector&lt;Shape*&gt; Container;</PRE></FONT></BLOCKQUOTE><DIV ALIGN="LEFT"><P><FONT FACE="Georgia">creates
an alias for a <B>vector</B> of <B>Shape*</B>, and this
<B>typedef</B>:</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#0000ff>typedef</font> Container::iterator Iter;</PRE></FONT></BLOCKQUOTE><DIV ALIGN="LEFT"><P><FONT FACE="Georgia">uses
that alias to create another one, for <B>vector&lt;Shape*&gt;::iterator</B>.
Notice that the <B>container</B> type name must be used to produce the
appropriate iterator, which is defined as a nested class. Although there are
different types of iterators (forward, bidirectional, reverse, etc., which will
be explained later) they all have the same basic interface: you can increment
them with <B>++</B>, you can dereference them to produce the object
they&#8217;re currently selecting, and you can test them to see if they&#8217;re
at the end of the sequence. That&#8217;s what you&#8217;ll want to do 90% of the
time. And that&#8217;s what is done in the above example: after creating a
container, it&#8217;s filled with different types of <B>Shape*</B>. Notice that
the upcast happens as the <B>Circle</B>, <B>Square</B> or <B>Rectangle</B>
pointer is added to the <B>shapes</B> container, which doesn&#8217;t know about
those specific types but instead holds only <B>Shape*</B>. So as soon as the
pointer is added to the container it loses its specific identity and becomes an
anonymous <B>Shape*</B>. This is exactly what we want: toss them all in and let
polymorphism sort it out.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The first <B>for</B> loop creates an
iterator and sets it to the beginning of the sequence by calling the
<B>begin(&#160;)</B> member function for the container. All containers have
<B>begin(&#160;)</B> and <B>end(&#160;)</B> member functions that produce an
iterator selecting, respectively, the beginning of the sequence and one past the
end of the sequence. To test to see if you&#8217;re done, you make sure
you&#8217;re <B>!=</B> to the iterator produced by <B>end(&#160;)</B>. Not
<B>&lt;</B> or <B>&lt;=</B>. The only test that works is <B>!=</B>. So
it&#8217;s very common to write a loop like:</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#0000ff>for</font>(Iter i = shapes.begin(); i != shapes.end(); i++)</PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">This says: &#8220;take me through every
element in the sequence.&#8221;</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">What do you do with the iterator to
produce the element it&#8217;s selecting? You dereference it using (what else)
the &#8216;<B>*</B>&#8217; (which is actually an overloaded operator). What you
get back is whatever the container is holding. This container holds
<B>Shape*</B>, so that&#8217;s what <B>*i</B> produces. If you want to send a
message to the <B>Shape</B>, you must select that message with <B>-&gt;</B>, so
you write the line:</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE>(*i)-&gt;draw();</PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">This calls the <B>draw(&#160;)</B>
function for the <B>Shape*</B> the iterator is currently selecting. The
parentheses are ugly but necessary to produce the proper order of evaluation. As
an alternative, <B>operator-&gt;</B> is defined so that you can
say:</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE>i-&gt;draw();</PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">As they are destroyed or in other cases
where the pointers are removed, the STL containers <I>do not</I> call
<B>delete</B> for the pointers they contain. If you create an object on the heap
with <B>new</B> and place its pointer in a container, the container can&#8217;t
tell if that pointer is also placed inside another container. So the STL just
doesn&#8217;t do anything about it, and puts the responsibility squarely in your
lap. The last lines in the program move through and delete every object in the
container so proper cleanup occurs.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">It&#8217;s very interesting to note that
you can change the type of container that this program uses with two lines.
Instead of including <B>&lt;vector&gt;</B>, you include <B>&lt;list&gt;</B>, and
in the first <B>typedef</B> you say:</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#0000ff>typedef</font> std::list&lt;Shape*&gt; Container;</PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">instead of using a <B>vector</B>.
Everything else goes untouched. This is possible not because of an interface
enforced by inheritance (there isn&#8217;t any inheritance in the STL, which
comes as a surprise when you first see it), but because the interface is
enforced by a convention adopted by the designers of the STL, precisely so you
could perform this kind of interchange. Now you can easily switch between
<B>vector</B> and <B>list</B> and see which one works fastest for your
needs.</FONT><A NAME="_Toc519042014"></A><BR></P></DIV>
<A NAME="Heading193"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H2 ALIGN="LEFT">
Containers of strings</H2></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">In the prior example, at the end of
<B>main(&#160;)</B>, it was necessary to move through the whole list and
<B>delete</B> all the <B>Shape</B> pointers. </FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#0000ff>for</font>(Iter j = shapes.begin();
      j != shapes.end(); j++)
    <font color=#0000ff>delete</font> *j;</PRE></FONT></BLOCKQUOTE>