<HTML>
<HEAD>
<TITLE>Example Programs</TITLE>
<LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD>
<BODY BGCOLOR=#FFFFFF>
<A HREF="9-2.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="10.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library User's Guide</B></DIV>
<H2>9.3 Example Programs</H2>
<P>In this section, we present three example programs that illustrate the use of <B><I><A HREF="../stdlibref/map.html">map</A></I></B>s and <B><I><A HREF="../stdlibref/multimap.html">multimap</A></I></B>s. These examples deal with a telephone database, graphs, and a concordance.</P>
<A NAME="931"><H3>9.3.1 Example: A Telephone Database</H3></A>
<BLOCKQUOTE><HR><B>
NOTE -- The complete example program is in the file tutorial tele.cpp.
</B><HR></BLOCKQUOTE>
<A NAME="idx178"><!></A>
<P>A maintenance program for a simple telephone database is a good application for a <B><I><A HREF="../stdlibref/map.html">map</A></I></B>. The database is simply an indexed structure, where the name of the person or business (a <SAMP>std::string</SAMP>) is the key value, and the telephone number (a <SAMP>long</SAMP>) is the associated entry. We might write such a class as follows:</P>

<UL><PRE>
typedef std::map&lt;std::string, long, std::less&lt;std::string&gt;,
                 std::allocator&lt;std::pair&lt;const std::string,
                                long&gt; &gt; &gt; friendMap;

typedef friendMap::value_type entry_type;

class telephoneDirectory {
public:
  void addEntry (std::string name, long number) {
    database[name] = number;
  }
  void remove (std::string name) {
    database.erase (name);
  }
  void update (std::string name, long number) {
    remove (name);
    addEntry (name, number);
  }
  void displayDatabase () {
    std::for_each (database.begin (), database.end (), printEntry);
  }
  void displayPrefix (int);
  void displayByPrefix (); 
private:
  friendMap database;
};

</PRE></UL>
<P>Simple operations on our database are directly implemented using member functions of the  <B><I><A HREF="../stdlibref/map.html">map</A></I></B>. Adding an element to the database is simply an <SAMP>insert()</SAMP>, removing an element is an <SAMP>erase()</SAMP>, and updating is a combination of the two. To print all the entries in the database we can use the <SAMP>for_each()</SAMP> algorithm, and apply the following simple utility routine to each entry:</P>

<UL><PRE>
void printEntry (const entry_type &amp; entry) {
    std::cout &lt;&lt; entry.first &lt;&lt; ":" &lt;&lt; entry.second &lt;&lt; std::endl;
}
</PRE></UL>
<P>We now use a pair of slightly more complex operations to illustrate how a few of the algorithms described in <A HREF="13.html">Chapter&nbsp;13</A> can be used with <B><I><A HREF="../stdlibref/map.html">map</A></I></B>s. Suppose we want to display all the phone numbers with a certain three-digit initial prefix. We use the <SAMP>std::find_if()</SAMP> function, which is not to be confused with the <SAMP>find()</SAMP> member function of <B><I>map</I></B>, to locate the first entry. Starting from this location, subsequent calls on <SAMP>std::find_if()</SAMP> uncover each successive entry:</P>

<UL><PRE>
void telephoneDirectory::displayPrefix (int pfx) {
    
  std::cout &lt;&lt; "Listing for prefix " &lt;&lt; pfx &lt;&lt; std::endl;

  friendMap::iterator
    where = std::find_if (database.begin (), database.end (),
                          checkPrefix (pfx));
    while (where != database.end ()) {
      printEntry (*where);
      where = std::find_if (++where, database.end (),
                            checkPrefix (pfx));
    }

    std::cout &lt;&lt; "end of prefix listing" &lt;&lt; std::endl;
}

</PRE></UL>
<P>For the predicate to this operation, we require a boolean function that takes only a single argument, the <B><I><A HREF="../stdlibref/pair.html">pair</A></I></B> representing a database entry, and tells us whether or not it is in the given prefix. There is no obvious candidate function, and in any case the test prefix is not being passed as an argument to the comparison function. The solution to this problem is to employ a common C++ Standard Library technique: define the predicate function as an instance of a class, and store the test predicate as an instance variable in the class, initialized when the class is constructed. The desired function is defined as the function call operator for the class:</P>

<UL><PRE>
long prefix (const entry_type&amp; entry) {
  return entry.second / 10000;
}

class checkPrefix {
public:
  checkPrefix (long p) : testPrefix (p)
    { }
  long testPrefix;
  bool operator () (const entry_type&amp; entry) {
    return prefix(entry)==testPrefix;
  }
};
</PRE></UL>
<P>Our final example displays the directory sorted by prefix. It is not possible to alter the order of the <B><I><A HREF="../stdlibref/map.html">map</A></I></B>s themselves. Instead, we create a new <B><I>map</I></B> with the element types reversed and copy the values into the new <B><I>map</I></B>, which orders the values by prefix. Once the new <B><I>map</I></B> is created, it is printed:</P>

<UL><PRE>
typedef std::map&lt;long, std::string, std::less&lt;long&gt;,
                 std::allocator&lt;std::pair&lt;const long,
                                std::string&gt; &gt; &gt; sortedMap;

typedef sortedMap::value_type sorted_entry_type;


void telephoneDirectory::displayByPrefix () {
    
    std::cout &lt;&lt; "Display by prefix" &lt;&lt; std::endl;

    sortedMap sortedData;

    for (friendMap::iterator i = database.begin ();
         i != database.end (); i++)
      sortedData.insert (sortedMap::value_type ((*i).second,
                         (*i).first));

    std::for_each (sortedData.begin (), sortedData.end (),
                   printSortedEntry);

    std::cout &lt;&lt; "end display by prefix" &lt;&lt; std::endl;
}

</PRE></UL>
<P>Here is the function used to print the sorted entries:</P>

<UL><PRE>
void printSortedEntry (const sorted_entry_type &amp; entry) {
    std::cout &lt;&lt; entry.first &lt;&lt; ":" &lt;&lt; entry.second &lt;&lt; std::endl;
}

</PRE></UL>
<A NAME="932"><H3>9.3.2 An Example: Graphs</H3></A>
<BLOCKQUOTE><HR><B>
NOTE -- The complete version of this program is in the file graph.cpp.
</B><HR></BLOCKQUOTE>
<A NAME="idx179"><!></A>
<P>A <B><I><A HREF="../stdlibref/map.html">map</A></I></B> whose elements are themselves <B><I>map</I></B>s is a natural representation for a directed graph. For example, suppose we use strings to encode the names of cities, and we wish to construct a map where the value associated with an edge is the distance between two connected cities. We could create such a graph as follows:</P>

<UL><PRE>
typedef
    std::map&lt;std::string, int, std::less&lt;std::string&gt;,
             std::allocator&lt;std::pair&lt;const std::string, int&gt; &gt; &gt;
        stringVector;

typedef
    std::map&lt;std::string, stringVector, std::less&lt;std::string&gt;,
             std::allocator&lt;std::pair&lt;const std::string,
                                      stringVector&gt; &gt; &gt;
        graph;

// define strings for city names
std::string pendleton ("Pendleton");
std::string pensacola ("Pensacola");
std::string peoria ("Peoria");
std::string phoenix ("Phoenix");
std::string pierre ("Pierre");
std::string pittsburgh ("Pittsburgh");
std::string princeton ("Princeton");
std::string pueblo ("Pueblo");

// declare the graph that holds the map
graph cityMap;      

// add edges to the graph
cityMap[pendleton][phoenix]    = 4;
cityMap[pendleton][pueblo]     = 8;
cityMap[pensacola][phoenix]    = 5;
cityMap[peoria][pittsburgh]    = 5;
cityMap[peoria][pueblo]        = 3;
cityMap[phoenix][peoria]       = 4;
cityMap[phoenix][pittsburgh]   = 10;
cityMap[phoenix][pueblo]       = 3;
cityMap[pierre][pendleton]     = 2;
cityMap[pittsburgh][pensacola] = 4;
cityMap[princeton][pittsburgh] = 2;
cityMap[pueblo][pierre]        = 3;

</PRE></UL>
<P>The type <B><I>stringVector</I></B> is a map of integers indexed by text strings. The type <I>graph</I> is, in effect, a two-dimensional sparse array, indexed by <B><I><A HREF="../stdlibref/basic-string.html">string</A></I></B><SAMP>s</SAMP> and holding <SAMP>int</SAMP> values. A sequence of assignment statements initializes the <I>graph</I>.</P>
<A NAME="idx180"><!></A>
<P>A number of classic algorithms can be used to manipulate graphs represented in this form. One example is Dijkstra's shortest-path algorithm. Dijkstra's algorithm begins from a specific city given as an initial location. A <B><I><A HREF="../stdlibref/priority-queue.html">priority_queue</A></I></B> of distance/city <B><I><A HREF="../stdlibref/pair.html">pair</A></I></B>s is then constructed, and initialized with the distance from the starting city to itself (namely, zero). The definition for the distance <B><I>pair</I></B> datatype is as follows:</P>

<UL><PRE>
struct DistancePair {
  unsigned first;
  std::string   second;
  DistancePair () : first (0) {}
  DistancePair (unsigned f, const std::string&amp; s)
    : first (f), second (s)
    {}
};

bool operator&lt; (const DistancePair&amp; lhs, const DistancePair&amp; rhs) {
  return lhs.first &lt; rhs.first;
}
</PRE></UL>
<P>In the algorithm that follows, note how the conditional test is reversed on the <B><I><A HREF="../stdlibref/priority-queue.html">priority_queue</A></I></B>, because at each step we wish to pull the smallest, and not the largest, value from the collection. On each iteration around the loop we pull a city from the queue. If we have not yet found a shorter path to the city, the current distance is recorded, and we can compute the distance from this city to each of its adjacent cities by examining the graph. This process continues until the priority_queue becomes exhausted:</P>

<UL><PRE>
void shortestDistance (graph&amp; cityMap, std::string&amp; start,
                       stringVector&amp; distances) {
    
  // Process a priority queue of distances to nodes.
  std::priority_queue&lt;DistancePair,
                      std::vector&lt;DistancePair,
                                  std::allocator&lt;DistancePair&gt; &gt;,
                      std::greater&lt;DistancePair&gt; &gt; que;
  que.push (DistancePair (0, start));
    
  while (! que.empty()) {
        
    // Pull nearest city from queue.
    int distance = que.top().first;
    std::string city = que.top().second;
    que.pop();

    // If we haven't seen it already, process it.
    if (0 == distances.count (city))
    {
      // Then add it to shortest distance map.
      distances[city] = distance;

      // And put values into queue.
      const stringVector&amp; cities = cityMap[city];
      stringVector::const_iterator start = cities.begin ();
      stringVector::const_iterator stop  = cities.end ();

      for (; start != stop; ++start) 
        que.push(DistancePair (distance + (*start).second,
                               (*start).first));
    }
  }
}

</PRE></UL>
<P>Notice that this relatively simple algorithm makes use of <B><I><A HREF="../stdlibref/vector.html">vector</A></I></B> (<A HREF="5.html">Chapter&nbsp;5</A>), <B><I><A HREF="../stdlibref/map.html">map</A></I></B> (<A HREF="9.html">Chapter&nbsp;9</A>), <B><I><A HREF="../stdlibref/basic-string.html">string</A></I></B> (<A HREF="12.html">Chapter&nbsp;12</A>), and <B><I><A HREF="../stdlibref/priority-queue.html">priority_queue</A></I></B> (<A HREF="11.html">Chapter&nbsp;11</A>).</P>
<A NAME="933"><H3>9.3.3 Example: A Concordance</H3></A>
<A NAME="idx181"><!></A>
<P>A concordance is an alphabetical listing of words in a text that shows the line numbers on which each word occurs.  </P>
<BLOCKQUOTE><HR><B>
NOTE -- The executable version of this program is in the file concord.cpp.
</B><HR></BLOCKQUOTE>
<A NAME="idx182"><!></A>
<P>We develop a concordance to illustrate the use of the <B><I><A HREF="../stdlibref/map.html">map</A></I></B> and <B><I><A HREF="../stdlibref/multimap.html">multimap</A></I></B> container classes. The data values are maintained in the concordance by a <B><I>multimap</I></B>, indexed by word (a <B><I><A HREF="../stdlibref/basic-string.html">string</A></I></B>)  and holding the line numbers (<SAMP>int</SAMP>). A <B><I>multimap</I></B> is used because the same word is expected to appear on different lines; indeed, discovering such connections is one of the primary purposes of a concordance. Another possibility would be to use a <B><I>map</I></B> and use a <B><I><A HREF="../stdlibref/set.html">set</A></I></B> of integer elements as the associated values.</P>

<UL><PRE>
class concordance {

  typedef
    std::multimap&lt;std::string,int,
                  std::less&lt;std::string&gt;,
                  std::allocator&lt;std::pair&lt;const std::string,
                                           int&gt; &gt; &gt;
    wordDictType;


public:
  void addWord (std::string, int);
  void readText (std::istream &amp;);
  void printConcordance (std::ostream &amp;);
private:
  wordDictType wordMap;
};
</PRE></UL>
<P>The creation of the concordance is divided into two steps: the program generates the concordance by reading lines from an input stream, then prints the result on the output stream. This is reflected in the two member functions <SAMP>readText()</SAMP> and <SAMP>printConcordance()</SAMP>. The first of these, <SAMP>readText()</SAMP>, is written as follows:</P>

<UL><PRE>
void concordance::readText (std::istream &amp; in) {

  std::string line;

  for (int i = 1; std::getline (in, line); i++)
  {
    allLower (line);
    std::list&lt;std::string, std::allocator&lt;std::string&gt; &gt; words;
    split (line, " , .;:", words);
    std::list&lt;std::string,
              std::allocator&lt;std::string&gt; &gt;::iterator wptr;
    for (wptr = words.begin (); wptr != words.end (); ++wptr)
      addWord (*wptr, i);
  }
}
</PRE></UL>
<P>Lines are read from the input stream one by one. The text of the line is first converted into lower case, then the line is split into words using the function <SAMP>split()</SAMP> described in <A HREF="12-3.html">Section&nbsp;12.3</A>. Each word is then entered into the concordance. The method used to enter a value into the concordance is as follows:</P>

<UL><PRE>
void concordance::addWord (std::string word, int line) {

  // First get range of entries with same key.
  wordDictType::iterator low = wordMap.lower_bound (word);
  wordDictType::iterator high = wordMap.upper_bound (word);

  // Loop over entires, see if any match current line.
  for ( ; low != high; ++low)
    if ( (*low).second == line)
      return;

  // Didn't occur, add now.
  wordMap.insert (wordDictType::value_type (word, line));
}

</PRE></UL>
<P>The major portion of <SAMP>addWord()</SAMP> is concerned with ensuring that values are not duplicated in the word <B><I><A HREF="../stdlibref/map.html">map</A></I></B> if the same word occurs twice on the same line. To assure this, the range of values matching the key is examined, each value is tested, and if any match the line number then no insertion is performed. It is only if the loop terminates without discovering the line number that the new word/line number pair is inserted.</P>
<P>The final step is to print the concordance. This is performed in the following fashion:</P>

<UL><PRE>
void concordance::printConcordance (std::ostream &amp; out) {
  std::string            lastword ("");
  wordDictType::iterator pairPtr;
  wordDictType::iterator stop = wordMap.end ();

  for (pairPtr = wordMap.begin (); pairPtr != stop; ++pairPtr)
    // If word is same as previous, just print line number.
    if (lastword == (*pairPtr).first)
      out &lt;&lt; " " &lt;&lt; (*pairPtr).second;
    else
    {
      // First entry of word.
      lastword = (*pairPtr).first;
      std::cout &lt;&lt; std::endl &lt;&lt; lastword &lt;&lt; ": "
                &lt;&lt; (*pairPtr).second;
    }
  std::cout &lt;&lt; std::endl;
}
</PRE></UL>
<P>An iterator loop is used to cycle over the elements being maintained by the word list. Each new word generates a new line of output; thereafter, line numbers appear separated by spaces. For example, if the input was the text:</P>

<UL><PRE>
It was the best of times, 
it was the worst of times.
</PRE></UL>
<P>The output, from best to worst, would be:</P>
<TABLE BORDER="0" CELLPADDING="3" CELLSPACING="3">
<tr><td valign=top><P CLASS="TABLE"><SAMP>best:</SAMP></P>
</td><td valign=top><P CLASS="TABLE"><SAMP> 1 </SAMP></P>
</td></tr>
<tr><td valign=top><P CLASS="TABLE"><SAMP>it:</SAMP></P>
</td><td valign=top><P CLASS="TABLE"><SAMP> 1 2 </SAMP></P>
</td></tr>
<tr><td valign=top><P CLASS="TABLE"><SAMP>of:</SAMP></P>
</td><td valign=top><P CLASS="TABLE"><SAMP> 1 2 </SAMP></P>
</td></tr>
<tr><td valign=top><P CLASS="TABLE"><SAMP>the:</SAMP></P>
</td><td valign=top><P CLASS="TABLE"><SAMP> 1 2 </SAMP></P>
</td></tr>
<tr><td valign=top><P CLASS="TABLE"><SAMP>times:</SAMP></P>
</td><td valign=top><P CLASS="TABLE"><SAMP> 1 2 </SAMP></P>
</td></tr>
<tr><td valign=top><P CLASS="TABLE"><SAMP>was:</SAMP></P>
</td><td valign=top><P CLASS="TABLE"><SAMP> 1 2 </SAMP></P>
</td></tr>
<tr><td valign=top><P CLASS="TABLE"><SAMP>worst:</SAMP></P>
</td><td valign=top><P CLASS="TABLE"><SAMP> 2</SAMP> </P>
</td></tr>
</TABLE>

<BR>
<HR>
<A HREF="9-2.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="10.html"><IMG SRC="images/bnext.gif" WIDTH=20 HEIGHT=21 ALT="Next file" BORDER=O></A>

<!-- Google Analytics tracking code -->
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
    _uacct = "UA-1775151-1";
    urchinTracker();
</script>
<!-- end of Google Analytics tracking code -->

</BODY>
</HTML>