chap07.htm

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

<B>set</B> created to work with <B>int</B>s by providing <B>int</B> as the
template argument to <B>set</B>:</FONT><BR></P></DIV>

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

<font color=#0000ff>int</font> main() {
  set&lt;<font color=#0000ff>int</font>&gt; intset;
    <font color=#0000ff>for</font>(<font color=#0000ff>int</font> i = 0; i &lt; 25; i++)
      <font color=#0000ff>for</font>(<font color=#0000ff>int</font> j = 0; j &lt; 10; j++)
        <font color=#009900>// Try to insert multiple copies:</font>
        intset.insert(j);
  <font color=#009900>// Print to output:</font>
  copy(intset.begin(), intset.end(),
    ostream_iterator&lt;<font color=#0000ff>int</font>&gt;(cout, <font color=#004488>"\n"</font>));
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>insert(&#160;)</B> member does all
the work: it tries putting the new element in and rejects it if it&#8217;s
already there. Very often the activities involved in using a set are simply
insertion and a test to see whether it contains the element. You can also form a
union, intersection, or difference of sets, and test to see if one set is a
subset of another.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">In this example, the values 0 - 9 are
inserted into the set 25 times, and the results are printed out to show that
only one of each of the values is actually retained in the set.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>copy(&#160;)</B> function is
actually the instantiation of an STL template function, of which there are many.
These template functions are generally referred to as &#8220;the STL
Algorithms&#8221; and will be the subject of the following chapter. However,
several of the algorithms are so useful that they will be introduced in this
chapter. Here, <B>copy(&#160;) </B>shows the use of iterators. The <B>set</B>
member functions <B>begin(&#160;)</B> and <B>end(&#160;)</B> produce iterators
as their return values. These are used by <B>copy(&#160;)</B> as beginning and
ending points for its operation, which is simply to move between the boundaries
established by the iterators and copy the elements to the third argument, which
is also an iterator, but in this case, a special type created for iostreams.
This places <B>int</B> objects on <B>cout</B> and separates them with a
newline.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Because of its genericity,
<B>copy(&#160;)</B> is certainly not restricted to printing on a stream. It can
be used in virtually any situation: it needs only three iterators to talk to.
All of the algorithms follow the form of <B>copy(&#160;)</B> and simply
manipulate iterators (the use of iterators is the &#8220;extra level of
indirection&#8221;).</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Now consider taking the form of
<B>Intset.cpp</B> and reshaping it to display a list of the words used in a
document. The solution becomes remarkably simple.</FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:WordSet.cpp</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <font color=#004488>"..</font><font color=#004488>/require.h"</font>
#include &lt;string&gt;
#include &lt;fstream&gt;
#include &lt;iostream&gt;
#include &lt;set&gt;
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;

<font color=#0000ff>void</font> wordSet(<font color=#0000ff>char</font>* fileName) {
  ifstream source(fileName);
  assure(source, fileName);
  string word;
  set&lt;string&gt; words;
  <font color=#0000ff>while</font>(source &gt;&gt; word)
    words.insert(word);
  copy(words.begin(), words.end(),
    ostream_iterator&lt;string&gt;(cout, <font color=#004488>"\n"</font>));
  cout &lt;&lt; <font color=#004488>"Number of unique words:"</font> 
    &lt;&lt; words.size() &lt;&lt; endl;
}  

<font color=#0000ff>int</font> main(<font color=#0000ff>int</font> argc, <font color=#0000ff>char</font>* argv[]) {
  <font color=#0000ff>if</font>(argc &gt; 1)
    wordSet(argv[1]);
  <font color=#0000ff>else</font>
    wordSet(<font color=#004488>"WordSet.cpp"</font>);
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The only substantive difference here is
that <B>string</B> is used instead of <B>int</B>. The words are pulled from a
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>