index.html

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

<script><!--
	image( "fig4.png" )
//--></script>

</font>

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

<p>Operations unique to <tt>list</tt>:</p>

<table border="1" width="90%" align="center">
	<tr bgcolor="#00ffff">
		<th>Operation</th>
		<th>Description</th>
	</tr>
	<tr align="center">
		<td><tt>merge(<i>list</i>)</tt></td>
		<td>Merge the current (sorted) list with the (sorted) argument list</td>
	</tr>
	<tr align="center">
		<td><tt>remove(<i>value</i>)</tt></td>
		<td>Remove all instances of the given value</td>
	</tr>
	<tr align="center">
		<td><tt>remove(<i>pred</i>)</tt></td>
		<td>Remove values for which <i>pred</i> returns true</td>
	</tr>
	<tr align="center">
		<td><tt>reverse()</tt></td>
		<td>Reverse order of elements</td>
	</tr>
	<tr align="center">
		<td><tt>sort()</tt></td>
		<td>Place the values into sorted order</td>
	</tr>
	<tr align="center">
		<td><tt>sort(<i>comp</i>)</tt></td>
		<td>Place values in order using <tt>comp</tt></td>
	</tr>
	<tr align="center">
		<td><tt>splice(<i>iter</i>, <i>list</i>)</tt></td>
		<td>Splices argument list into the list at given location</td>
	</tr>
	<tr align="center">
		<td><tt>unique()</tt></td>
		<td>Remove duplicate copies of values from <u>sorted</u> list</td>
	</tr>
	<tr align="center">
		<td><tt>unique(<i>pred</i>)</tt></td>
		<td>Remove duplicate values from list sorted w/<i>pred</i></td>
	</tr>
</table>

</font>

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

<p>Simple inventory mgt. system; products have unique IDs.  Tasks:
	<br>- Process an order for a product #
	<br>- Process the shipment of a given product.</p>

</font>

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


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

</font>

<hr><h2><font color="#009999">23.2.3 Deque</font></h2>
<font size="+1">

<ul>
	<li><i>double-ended queue</i></li>
	<li>Indexed, like vector</li>
	<li>Provides O(1) insertions at front or back</li>
	<li>O(<i>n</i>) insertion at middle</li>
	<li>W/out link fields, takes up less room than a list</li>
</ul>

</font>

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

<p>Example: time-driven simulation of the line in front of a tellers'
	counter at a bank.
<ul>
	<li>Each minute there's a .9 probability that a new customer arrives
		<ul>
			<li>Add to the end of customer deque</li>
		</ul>
	</li>
	<li>Each transaction takes from 2-8 minutes (random)</li>
	<li>Calculate the avg. time a customer stands in line</li>
	<li>Each minute, examine and update the status of every teller in the
		teller deque, working off the front of the customer deque</li>
</ul>

</font>

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

<script><!-- 
	iframeWrapCode( "bank.cpp", "95%", "80%" )
//--></script>

</font>

<hr><h2><font color="#009999">Advanced Topic 23.3</font></h2>
<font size="+1">
<hr color="#00ffff" size="6">

<p><font color="#009999">Implementation of Deque</font></p>

<ul>
	<li>Not specified by the standard</li>
	<li><i>circular buffer</i> commonly used</li>
	<li>Like vector, but also store the start index</li>
	<li>Can insert/remove from the front w/out moving all of the other
		elements</li>
</ul>

</font>

<hr><h2><font color="#009999">23.3 The Stack and Queue Adapters</font></h2>
<font size="+1">

<ul>
	<li>Linear data structures that support LIFO or FIFO access (sect. 16.3)</li>
	<li>Not actually containers, but adapters (wrappers) built on containers</li>
	<li>Found in <tt>&lt;stack&gt;</tt> and <tt>&lt;queue&gt;</tt></li>
	<li>Adapter: a class that uses another container to maintain elements,
		but changes the interface</li>
	<li>Operations for the adapter are ultimately passed to the underlying
		class</li>
	<li>Slightly simplified implementation of <tt>stack</tt> (next slide)</li>
</ul>

</font>

<hr><h2><font color="#009999">23.3 (cont.) - <tt>stack</tt> implementation
	</font></h2>
<font size="+1">

<blockquote>
<pre>template &lt;class T, class C = deque&lt;T&gt; &gt;
class stack
{
public:
   int size() const;
   void push(const T&amp; x);
   T&amp; top();
   void pop();
protected:
   C values;
};</pre>
</blockquote>

</font>

<hr><h2><font color="#009999">23.3 (cont.) - <tt>stack</tt> implementation
	</font></h2>
<font size="+1">

<blockquote>
<pre>template &lt;typename T, typename C&gt;
int stack&lt;T, C&gt;::size() const
{
   return values.size();
}

template &lt;typename T, typename C&gt;
void stack&lt;T, C&gt;::push(const T&amp; x)
{
   values.push_back(x);
}</pre>
</blockquote>

</font>

<hr><h2><font color="#009999">23.3 <tt>stack</tt> implementation (cont.) 
	</font></h2>
<font size="+1">

<blockquote>
<pre>template &lt;typename T, typename C&gt;
T&amp; stack&lt;T, C&gt;::top()
{
   return values.back();
}

template &lt;typename T, typename C&gt;
void stack&lt;T, C&gt;::pop()
{
   values.pop_back();
}</pre>
</blockquote>

</font>

<hr><h2><font color="#009999">23.3 <tt>stack</tt> implementation (cont.)
	</font></h2>
<font size="+1">

<ul>
	<li><tt>values</tt> attribute is the actual container</li>
	<li><tt>stack</tt> takes two type arguments</li>
	<li>The 2nd argument is the type of the underlying container</li>
	<li>The default value depends on the first argument</li>
	<li>The default container for both <tt>stack</tt> and <tt>queue</tt> is a
		<tt>deque</tt></li>
	<li>For <tt>stack</tt> it can also be <tt>vector</tt></li>
	<li>A <tt>queue</tt> can also be built on a <tt>list</tt></li>
</ul>

</font>

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

<p><i>Reverse Polish Notation</i> (RPN, or <i>postfix</i>) calculator</p>

<ul>
	<li>Arguments written before operators
		<ul>
			<li><tt>3 + 4 * 7</tt> would be <tt>3 4 7 * +</tt></li>
		</ul>
	</li>
	<li>Calculation is easy:</li>
		<ul>
			<li>Each argument read is pushed onto a stack</li>
			<li>If a (binary) operator is read:
				<ul>
					<li>Pop top two values</li>
					<li>Perform appropriate operation</li>
					<li>Push result back onto stack</li>
				</ul>
			<li>Add 2 commands:
				<ol>
					<li><tt>p</tt> - print the top of the stack</li>
					<li><tt>q</tt> - quit the program</li>
				</ol>
		</ul>
	</li>
</ul>

</font>

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

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

</font>

<hr><h2><font color="#009999">23.4 Sets</font></h2>
<font size="+1">

<ul>
	<li>optimized for fast insertion, removal, and testing</li>
	<li>Not linear.  Often a balanced BST</li>
	<li>Finding an item takes O(log <i>n</i>) time</li>
	<li>Elements of a set are unique
		<ul>
			<li><tt>multiset</tt> removes this restriction</li>
		</ul>
	</li>
	<li>Declared in the <tt>&lt;set&gt;</tt> header file</li>
</ul>

</font>

<hr><h2><font color="#009999">23.4 Set 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>set()</tt></td>
		<td>Construct an empty set</td>
	</tr>
	<tr align="center">
		<td><tt>set(<i>iterator</i>, <i>iterator</i>)</tt></td>
		<td>Construct a set from the given range of values</td>
	</tr>
	<tr align="center">
		<td><tt>begin()</tt></td>
		<td>Return iterator for set</td>
	</tr>
	<tr align="center">
		<td><tt>count(<i>value</i>)</tt></td>
		<td>Return number of instances of <i>value</i></td>
	</tr>
	<tr align="center">
		<td><tt>empty()</tt></td>
		<td>Return <tt>true</tt> if set is empty</td>
	</tr>
	<tr align="center">
		<td><tt>end()</tt></td>
		<td>Return ending iterator for set
	</tr>
	<tr align="center">
		<td><tt>erase(<i>iterator</i>)</tt></td>
		<td>Erase position from set</td>
	</tr>
</table>
</font>

<hr><h2><font color="#009999">23.4 Set 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>erase(<i>value</i>)</tt></td>
		<td>Erase value from set</td>
	</tr>
	<tr align="center">
		<td><tt>find()</tt></td>
		<td>Return iterator for value</td>
	</tr>
	<tr align="center">
		<td><tt>insert(<i>value</i>)</tt></td>
		<td>Insert value into set</td>
	</tr>
	<tr align="center">
		<td><tt>rbegin()</tt></td>
		<td>Return iterator for values in reverse order</td>
	</tr>
	<tr align="center">
		<td><tt>rend()</tt></td>
		<td>Return ending iterator for values in reverse order</td>
	</tr>
	<tr align="center">
		<td><tt>size()</tt></td>
		<td>Return number of elements in set</td>
	</tr>
</table>

</font>

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

<ul>
	<li>Elements are maintained in sequence (sorted order)</li>
	<li>Fast lookups</li>
	<li>Need to compare elements, unlike the fundamental containers</li>
	<li>Template parameters:
		<blockquote>
<pre>template &lt;typename T, typename CMP = less&lt;T&gt; &gt;
class set
{
   . . .
};</pre>
		</blockquote>
	</li>
	<li>Second argument is the trait that compares two elements</li>
	<li>The default value is the standard <tt>less</tt> function object
		(<tt>operator&lt;</tt>)</li>
</ul>

</font>

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

<p>2 ways to form sets of a new object type.  Using the <tt>Employee</tt>
	class for our example.</p>

<ol>
	<li>Override <tt>operator&lt;</tt>, allowing the normal declaration:
		<blockquote>
<pre>
bool operator&lt; (const Employee&amp; a, const Employee&amp; b)
{
   return a.salary() &lt; b.salary();
}

set&lt;Employee&gt; workers; <font color="#0000cc">// Will be sorted by salary</font></pre>
		</blockquote>
	</li>
</ol>

</font>

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

<ol start="2">
	<li>Provide an explicit function object; name it as the second template
		argument
		<blockquote>
<pre>class SortByName
{
public:
   bool operator() (const Employee&amp; a, const Employee&amp; b) const;
};

bool SortByName::operator(const Employee&amp; a, const Employee&amp; b)
{
   return a.get_name() &lt; b.get_name();
}

set&lt;Employee, SortByName&gt; workers; <font color="#0000cc">// Now sorted by name</font></pre>
		</blockquote>
	</li>
</ol>

</font>

<hr><h2><font color="#009999">23.4 Sets - Dictionary Example</font></h2>
<font size="+1">

<p>Program to check for misspelled words.  A dictionary is read
	into a set, then checks input words against the set.</p>

<blockquote>
<pre>void spellCheck(istream&amp; dictionary, istream&amp; text)
{
   set&lt;string&gt; words;
   string word;

   // First put all words from dictionary into set.
   while (dictionary &gt;&gt; word)
      words.insert(word);

   // Then read words from text
   while (text &gt;&gt; word)
      if (words.count(word) == 0)
         cout &lt;&lt; "Misspelled word " &lt;&lt; word &lt;&lt; "\n";
}</pre>
</blockquote>

</font>

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