index.html

《Big C++ 》Third Edition电子书和代码全集-Part1

<ul>
	<li>Indexed data structure, similar to a vector or deque</li>
	<li>2 important differences:
		<ol>
			<li>The indices (keys) can be any ordered type</li>
			<li>Ordered data structure (like the set), based on the keys</li>
		</ol>
	<li>Keys could be floats, strings, or even employees</li>
	<li>Keys may be looked up quickly</li>
	<li><tt>map</tt> demands unique keys</li>
	<li><tt>multimap</tt> permits multiple entries indexed by the same key</li>
	<li>Found in <tt>&lt;map&gt;</tt></li>
</ul>

</font>

<hr><h2><font color="#009999">23.5 Maps (cont.)</font></h2>
<font size="+1">

<ul>
	<li>Takes three template arguments:
		<blockquote>
<pre>template &lt;typename K, typename V, typename CMP = less&lt;K&gt; &gt;
class map
{
   . . .
};</pre>
		</blockquote>
		<ul>
			<li><tt>K</tt> - key type</li>
			<li><tt>V</tt> - value type</li>
			<li><tt>CMP</tt> - comparison for keys, less than by default</li>
		</ul>
	</li>
	<li><tt>operator&lt;</tt> must be defined on the key type, or provide a
		function object</li>
</ul>

</font>

<hr><h2><font color="#009999">23.5 Maps (cont.)</font></h2>
<font size="+1">

<ul>
	<li>Set that maintains a collection of <tt>pair</tt>s (chptr. 22)</li>
	<li>Insert key/value pairs</li>
	<li>Iterators return <tt>pair</tt>s:
		<blockquote>
<pre>map&lt;string, int&gt; database;
. . .
map&lt;string, int&gt;::iterator current = database.begin();
while (current != database.end())
{
   pair&lt;string, int&gt; element = *current;
   cout &lt;&lt; "key is " &lt;&lt; element.first &lt;&lt; " value is " &lt;&lt;
      element.second &lt;&lt; "\n";
   ++current;
}</pre>
		</blockquote>
	</li>
</ul>

</font>

<hr><h2><font color="#009999">23.5 Maps - Operations</font></h2>
<font size="+1">

<table border="1" width="90%" align="center">
	<tr bgcolor="#00ffff">
		<th>Operation</th>
		<th>Description</th>
	</tr>
	<tr align="center">
		<td><tt>map()</tt></td>
		<td>Construct an empty map</td>
	</tr>
	<tr align="center">
		<td><tt>map(<i>iter</i>, <i>iter</i>)</tt></td>
		<td>Initialize a new map from the given range of values</td>
	</tr>
	<tr align="center">
		<td><tt>begin()</tt></td>
		<td>Return iterator</td>
	</tr>
	<tr align="center">
		<td><tt>count(<i>key</i>)</tt></td>
		<td>Return number of entries with <i>key</i> (0 or 1)</td>
	</tr>
	<tr align="center">
		<td><tt>empty()</tt></td>
		<td>Return <tt>true</tt> if collection is empty</td>
	</tr>
	<tr align="center">
		<td><tt>end()</tt></td>
		<td>Return ending iterator</td>
	</tr>
	<tr align="center">
		<td><tt>erase(<i>iter</i>)</tt></td>
		<td>Erase value at indicated location</td>
	</tr>
	<tr align="center">
		<td><tt>erase(<i>iter</i>, <i>iter</i>)</tt></td>
		<td>Erase range of values</td>
	</tr>
</table>

</font>

<hr><h2><font color="#009999">23.5 Maps - Operations (cont.)</font></h2>
<font size="+1">

<table border="1" width="90%" align="center">
	<tr bgcolor="#00ffff">
		<th>Operation</th>
		<th>Description</th>
	</tr>
	<tr align="center">
		<td><tt>find(<i>key</i>)</tt></td>
		<td>Return iterator to value with <i>key</i></td>
	</tr>
	<tr align="center">
		<td><tt>insert(<i>elem</i>)</tt></td>
		<td>Insert <i>elem</i>, which must be a key/value <tt>pair</tt></td>
	</tr>
	<tr align="center">
		<td><tt>lower_bound(<i>key</i>)</tt></td>
		<td>Return iterator for first entry with <i>key</i> (<tt>multimap</tt>
			only)</td>
	</tr>
	<tr align="center">
		<td><tt>rbegin()</tt></td>
		<td>Return iterator in reverse order</td>
	</tr>
	<tr align="center">
		<td><tt>rend()</tt></td>
		<td>Return ending iterator in reverse order</td>
	</tr>
	<tr align="center">
		<td><tt>size()</tt></td>
		<td>Number of elements in container</td>
	</tr>
	<tr align="center">
		<td><tt>upper_bound(<i>key</i>)</tt></td>
		<td>Return iterator for past-the-end entry with <i>key</i>
			(<tt>multimap</tt> only)</td>
	</tr>
	<tr align="center">
		<td><tt>operator[<i>key</i>]</tt></td>
		<td>Return value associated with <i>key</i></td>
	</tr>
</table>

</font>

<hr><h2><font color="#009999">23.5 Maps - Example</font></h2>
<font size="+1">

<p>Consider a directory listing of telephone numbers.</p>

<ul>
	<li>Use unique names as keys</li>
	<li>Numbers as elements</li>
	<li><tt>print_all</tt> produces a (naturally) ordered listing</li>
	<li><tt>print_by_number</tt> produces a reverse white pages.  A multimap
		provides an ordering on the numbers (not unique)</li>
</ul>

</font>

<hr><h2><font color="#009999">23.5 Maps - Example (cont.)</font></h2>
<font size="+1">

<script><!-- 
	iframeWrapCode( "tele.cpp", "90%", "80%" )
//--></script>

</font>

<hr><h2><font color="#009999">23.5.1 Priority Queue</font></h2>
<font size="+1">

<ul>
	<li>Non-linear container</li>
	<li>Optimized to quickly locate the highest priority element</li>
	<li>Does not imply a sorting</li>
	<li>Elements must be comparable</li>
	<li><font color="#009999">Note</font>:  <i>queue</i> is a misnomer; FIFO is
		<u>not</u> enforced</li>
	<li>Basic operations:
		<ul>
			<li><tt>push</tt> - Insert a new element</li>
			<li><tt>top</tt> - Return element w/highest priority</li>
			<li><tt>pop</tt> - Remove element w/highest priority</li>
			<li><tt>empty</tt>, <tt>size</tt> - as usual</li>
		</ul>
	</li>
	<li>Comparison operator can be specified (less than, by default)</li>
</ul>

</font>

<hr><h2><font color="#009999">23.5.1 Priority Queue (cont.)</font></h2>
<font size="+1">

<ul>
	<li><tt>priority_queue</tt> is defined in <tt>&lt;queue&gt;</tt></li>
	<li>An adapter, wrapping an indexed structure (usually <tt>vector</tt>)</li>
	<li>Implemented using a <tt>heap</tt> (<tt>priority_queue</tt> wraps
		<tt>heap</tt>, which wraps an indexed container)</li>
</ul>

</font>

<hr><h2><font color="#009999">23.5.1 Priority Queue - Example</font></h2>
<font size="+1">

<ul>
	<li>Discrete event-driven simulation - classic application</li>
	<li>Structured around events (actions) that occur at some fixed time</li>
	<li>Often an action will spawn new events</li>
	<li>The following 2 files are the basis for an event-driven simulation</li>
	<li>Each event will be represented by an instance of <tt>Event</tt></li>
	<li>The <tt>Event</tt> records the time, the key for comparison</li>
	<li>The <u>lower</u> time has <u>higher</u> priority</li>
	<li>A pure virtual method represents the action of an event</li>
</ul>

</font>

<hr><h2><font color="#009999">23.5.1 Priority Queue (<tt>event.h</tt>)
	</font></h2>
<font size="+1">

<script><!-- 
	iframeWrapCode( "event.h", "90%", "80%" )
//--></script>

</font>

<hr><h2><font color="#009999">23.5.1 Priority Queue - Example</font></h2>
<font size="+1">

<ul>
	<li>Event loop - the heart of the simulation</li>
	<li>It pulls the next event (smallest time) from the PQ</li>
	<li>Events are removed in sequence, regardless of insertion</li>
	<li>As each event is removed it is executed, and the memory recovered</li>
	<li>The loop runs until the the queue is exhausted</li>
</ul>

</font>

<hr><h2><font color="#009999">23.5.1 Priority Queue (<tt>event.cpp</tt>)
	</font></h2>
<font size="+1">

<script><!-- 
	iframeWrapCode( "event.cpp", "80%", "60%" )
//--></script>

</font>

<hr><h2><font color="#009999">23.5.1 Priority Queue - Example</font></h2>
<font size="+1">

<ul>
	<li>Subclass <tt>Simulation</tt> and <tt>Event</tt> to emulate traffic
		at a hot dog stand</li>
	<li>Vary the number of seats, see the outcome</li>
	<li>There are two types of events:
		<ol>
			<li>Arrival event - signals the arrival of a customer.  If seated,
				(s)he stays a random amount of time, the leaves</li>
			<li>Leave event - frees the seat the customer was occupying</li>
		</ol>
	</li>
	<li>Random arrival events are generated over an hour to initialize the
		simulation</li>
</ul>

</font>

<hr><h2><font color="#009999">23.5.1 Priority Queue (<tt>hotdog.cpp</tt>)
	</font></h2>
<font size="+1">

<script><!-- 
	iframeWrapCode( "hotdog.cpp", "90%", "80%" )
//--></script>

</font>

<hr><h2><font color="#009999">23.6 Case Study: Dijkstra's Shortest Path
	Algorithm</font></h2>
<font size="+1">

<ul>
	<li>Find the shortest distance from a node on a directed graph to each
 		other node</li>
	<li>A sample of routes to cities serviced by a bus company:</li>
	
	<script><!-- // Set title on page
		image( "fig10.png" )	// country map
	//--></script>
</ul>

</font>

<hr><h2><font color="#009999">23.6 Case Study: Graph Representation</font></h2>
<font size="+1">

<ul>
	<li>Determine the minimum cost to travel from one city,
		e.g., Pierre, to each of the other cities</li>
	<li>Represent a destination, and the associated cost</li>
	<li>Could use a <tt>pair</tt></li>
	<li>Need to override comparison operator</li>
	<li>Create a new class:
</ul>

</font>

<hr><h2><font color="#009999">23.6 Case Study: Graph Representation</font></h2>
<font size="+1">

<blockquote>
<pre>class DistanceToCity
{
public:
   DistanceToCity(string n, int d);
   string name;
   int distance;
   bool operator&lt;(const DistanceToCity&amp; right) const;
};</pre>
</blockquote>

</font>

<hr><h2><font color="#009999">23.6 Case Study: Graph Representation (cont.)
	</font></h2>
<font size="+1">

<blockquote>
<pre>DistanceToCity::DistanceToCity(string n, int d)
{
   name = n;
   distance = d;
}

bool DistanceToCity::operator&lt;(const DistanceToCity&amp; right) const
{
   return right.distance &lt; distance;
}</pre>
</blockquote>

</font>

<hr><h2><font color="#009999">23.6 Case Study: Graph Representation (cont.)
	</font></h2>
<font size="+1">

<ul>
	<li>Represent graph using type of map</li>
	<li>City name is the key, a <tt>DistanceToCity</tt> is the element</li>
	<li><tt>cities</tt> is a multimap; more than one edge may leave a city
		<blockquote><tt>multimap&lt;string, DistanceToCity&gt; CityMap;</tt>
		</blockquote>
	(Adjacency list)
	</li>
	<li><tt>DistanceFinder</tt> wraps the multimap, provides 2 member functions:
		<ul>
			<li><tt>set_distance</tt> adds an edge to the graph</li>
			<li><tt>find_distance</tt> fills in a map of destinations and their
				costs, given a source node</li>
		</ul>
	</li>
</ul>

<hr><h2><font color="#009999">23.6 Case Study: Dijkstra's Algorithm</font></h2>
<font size="+1">

<ul>
	<li>A (min) PQ is used to represent the list of possible
		destinations with the relative cost of traveling to them</li>
	<li>Build a resultant map <tt>shortest</tt> of names and distances</li>
	<li>Place the source on the queue, w/distance 0</li>
	<li>Loop while the PQ is not empty:
		<ol>
			<li>Pop element</li>
			<li>If city already visited (in <tt>shortest</tt>), goto 1</li>
			<li>Place city and cost in <tt>shortest</tt></li>
			<li>For each adjacent node in <tt>cities</tt> (loop from
				<tt>lower_bound</tt> to <tt>upper_bound</tt>:
				<ul>
					<li>Add current distance to relative distance, add new entry to
						PQ</li>
				</ul>
			</li>
		</ol>
	</li>
</ul>

</font>

<hr><h2><font color="#009999">23.6 Case Study: Dijkstra's Shortest Path
	Algorithm (<tt>dijkstra.cpp</tt>)</font></h2>
<font size="+1">

<script><!-- 
	iframeWrapCode( "dijkstra.cpp", "90%", "80%" )
//--></script>

</font>

<hr><h2><font color="#009999">Chapter Summary</font></h2>
<font size="+1">
<hr color="#00ffff" size="6">

<ol>
	<li>STL - a library of classes that represent containers that occur
	frequently in computer programs in all application areas.</li>
	<li>Each class in the STL supports a relatively small set of operations.
	Basic functionality is extended through the use of generic algorithms.</li>
	<li>The 3 fundamental data structures are the vector, list, and deque.</li>
	<li>Vector and deque are indexed data structures; they support efficient
	access to each element based on an integer key.</li>
	<li>A list supports efficient insertion into or removal from the middle of a
	collection.  Lists can also be merged with other lists.</li>
</ol>

</font>

<hr><h2><font color="#009999">Chapter Summary (cont.)</font></h2>
<font size="+1">
<hr color="#00ffff" size="6">

<ol start='6'>
	<li>Stacks, queue, and priority queues are adapters built on top of the
	fundamental collections.  A stack enforces the LIFO protocol, while the
	queue uses FIFO.</li>
	<li>A set maintains elements in order.  Permits very efficient insertion,
	removal, and testing of elements.</li>
	<li>A map is a keyed container.  Entries in a map are accessed through a key,
	which can be any ordered data type.  Associated with each key is a value.
	A multimap allows more than one value to be associated with a key.</li>
	<li>A priority queue is a collection organised so as to permit fast access
	to and removal of the largest element.</li>
</ol>

</font>

</body>
</html>