📄 index.html
字号:
<!-- -*-html-*-
$Source: /usr/local/cvsroot/BigC++/26/index.html,v $
$Revision: 1.4 $
Big C++, chptr 26
editor: cols=80, tabstop=2
Kurt Schmidt, kschmidt@cs.drexel.edu
NOTES
- 3 spaces are used for each indent in examples
REVISIONS:
$Log: index.html,v $
Revision 1.4 2004/04/20 22:03:04 kurt
Made slides smaller (view %150, on 1024x768 display)
Revision 1.3 2004/03/26 20:29:38 kurt
Formatting (size +3)
Revision 1.2 2004/02/21 21:43:00 kurt
Finished (for now)
Revision 1.1 2004/02/21 02:27:14 kurt
Creation
-->
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<script language="JavaScript" src="./config.js"></script>
<script language="JavaScript" src="./pageFormat.js"></script>
<script><!-- // Set title on page
title()
//--></script>
</head>
<body>
<hr><h2><font color="#009999" size="+3">Chapter 26 - An Introduction to
Design Patterns</font></h2>
<font size="+1">
<script><!--
image( "cover.png" )
//--></script>
</font>
<hr><h2><font color="#009999" size="+2">Chapter Goals</font></h2>
<hr noshade size="4" color="#009999">
<font size="+1">
<ul>
<li>To review the advantages of iterators</li>
<li>To learn about the pattern concept</li>
<li>To study several common design patterns: ITERATOR, ADAPTER, TEMPLATE
METHOD, STRATEGY, COMPOSITE</li>
<li>To learn where patterns are used in the standard C++ library</li>
<li>To put patterns to work in a complex program</li>
</ul>
</font>
<hr><h2><font color="#009999">An Introduction to Design Patterns</font></h2>
<font size="+1">
<ul>
<li>A description of a problem and its solution</li>
<li>Can be applied to many situations</li>
<li>Useful patterns have been standardized</li>
<li>This chptr covers 5 common and easily understood patterns</li>
</ul>
</font>
<hr><h2><font color="#009999">26.1 Iterators</font></h2>
<font size="+1">
<ul>
<li>To traverse an STL linked-list:
<blockquote>
<pre>list<string>::iterator pos;
for (pos = list.begin(); pos != list.end(); ++pos)
{
string item = *pos;
. . .
}</pre>
</blockquote>
</li>
</ul>
</font>
<hr><h2><font color="#009999">26.1 Iterators (cont.)</font></h2>
<font size="+1">
<ul>
<li>Compared to traditional traversal:
<blockquote>
<pre>Node* current = list.head;
while (current != NULL)
{
string item = current->data;
current = current->next;
. . .
}</pre>
</blockquote>
</li>
</ul>
</font>
<hr><h2><font color="#009999">26.1 Iterators (cont.)</font></h2>
<font size="+1">
<ul>
<li>Nodes are artifacts of a linked-lists</li>
<li>Consider circular lists, dummy head/tail nodes, etc.</li>
<li>Lists are easily corrupted</li>
<li>A list client should remain ignorant of nodes</li>
</ul>
</font>
<hr><h2><font color="#009999">26.1 Iterators (cont.)</font></h2>
<font size="+1">
<p>Consider the interface:</p>
<table cellpadding="5">
<tr>
<td width='50%' valign='top'><font size="+1">A stack has:
<ul>
<li><tt>push</tt></li>
<li><tt>pop</tt></li>
<li><tt>top</tt></li>
</ul>
</font>
</td>
<td>
<script><!--
image( "fig01.png" )
//--></script>
</td>
</tr>
</table>
</font>
<hr><h2><font color="#009999">26.1 Iterators (cont.)</font></h2>
<font size="+1">
<table cellpadding="5">
<tr>
<td width='50%' valign='top'>
<font size="+1">A array structure w/random access has:
<ul>
<li><tt>operator[]</tt></li>
<li><tt>push_back</tt></li>
<li><tt>size</tt></li>
</ul>
</font>
</td>
<td>
<script><!--
image( "fig02.png" )
//--></script>
</td>
</tr>
</table>
</font>
<hr><h2><font color="#009999">26.1 Iterators (cont.)</font></h2>
<font size="+1">
<ul>
<li>Interface for a linked list is more complicated</li>
<ul>
<li>Adding/removing in the middle desired</li>
<li>Indices inefficient</li>
</ul>
<li><i>Cursors</i> (internal iterators) are one solution:
<script><!--
image( "fig03.png" )
//--></script>
</li>
</ul>
</font>
<hr><h2><font color="#009999">26.1 Iterators (cont.)</font></h2>
<font size="+1">
<h3>Interface for list w/cursor</h3>
<blockquote>
<pre>T get() const <font color="#0000cc">// Get element at cursor</font>
void set(const T& t) <font color="#0000cc">// Set element at cursor to t</font>
T remove() <font color="#0000cc">// Remove element at cursor</font>
void insert(const T& t) <font color="#0000cc">// Insert t before cursor</font>
void reset() <font color="#0000cc">// Reset cursor to head</font>
void next() <font color="#0000cc">// Advance cursor</font>
bool is_done() <font color="#0000cc">// Check if cursor can be advanced</font></pre>
</blockquote>
</font>
<hr><h2><font color="#009999">26.1 Iterators (cont.)</font></h2>
<font size="+1">
<h3>Cursors</h3>
<ul>
<li>Member of the list</li>
<li>Hides node details</li>
<li><tt>reset</tt> moves cursor to beginning</li>
<li><tt>next</tt> advances cursor</li>
<li><tt>get</tt>, <tt>set</tt>, <tt>insert</tt>, and <tt>remove</tt>
are relative to cursor</li>
</ul>
</font>
<hr><h2><font color="#009999">26.1 Iterators (cont.)</font></h2>
<font size="+1">
<h3>Cursors (cont.)</h3>
<ul>
<li>To traverse the list:
<blockquote>
<pre>for (list.reset(); !list.is_done(); list.next())
{
T item = list.get();
. . .
}</pre>
</blockquote>
</li>
</ul>
</font>
<hr><h2><font color="#009999">26.1 Iterators (cont.)</font></h2>
<font size="+1">
<h3>Drawbacks of cursors</h3>
<ul>
<li>Only one</li>
<li>Can't implement algorithms to compare elements</li>
<li>Printing list moves cursor (is not <b>const</b>)</li>
</ul>
</font>
<hr><h2><font color="#009999">26.1 Iterators (cont.)</font></h2>
<font size="+1">
<ul>
<li>The iterator is a superior concept</li>
<li>Can have any number of iterators on a container</li>
<li>Consider uses outside of lists:
<ul>
<li><tt>istream</tt> - sequence of bytes</li>
<li>Visit rows of a database</li>
</ul>
</li>
<li>Examples of a common <i>pattern</i></li>
</ul>
</font>
<hr><h2><font color="#009999">26.2 The Pattern Concept</font></h2>
<font size="+1">
<ul>
<li>Christopher Alexander formulated > 250 patterns for architectural
design</li>
<li>Every pattern has:
<ul>
<li>A short <i>name</i></li>
<li>A brief description of the <i>context</i></li>
<li>A lengthy description of the <i>problem</i></li>
<li>A prescription for a <i>solution</i></li>
</ul>
</li>
</ul>
</font>
<hr><h2><font color="#009999">26.2 The Pattern Concept</font></h2>
<font size="+1">
<ul>
<li>Patterns distill a design rule into a simple format</li>
<li>Provides cookbook for solutions</li>
<li>We apply the same principles to software design</li>
<li>We start with the ITERATOR pattern:</li>
</ul>
</font>
<hr><h2><font color="#009999">Pattern ITERATOR</font></h2>
<font size="+1">
<hr color="#00ffff" size="6">
<h3><font color="#009999">Context</font></h3>
<ol>
<li>An object (<i>aggregate</i>) contains other objects (<i>elements</i>)</li>
<li><i>Clients</i> need access</li>
<li>Aggregate should not expose its internals</li>
<li>Multiple clients may need simultaneous access</li>
</ol>
</font>
<hr><h2><font color="#009999">Pattern ITERATOR (cont.)</font></h2>
<font size="+1">
<hr color="#00ffff" size="6">
<h3><font color="#009999">Solution</font></h3>
<ol>
<li>Define an iterator class
<ul>
<li>External</li>
<li>Fetches one element at a time</li>
</ul>
</li>
<li>Each iterator object needs to keep track of the position of the next
element to fetch</li>
</ol>
</font>
<hr><h2><font color="#009999">Pattern ITERATOR (cont.)</font></h2>
<font size="+1">
<hr color="#00ffff" size="6">
<h3><font color="#009999">Solution</font></h3>
<script><!--
image( "un03.png" )
//--></script>
</font>
<hr><h2><font color="#009999">26.2 The Pattern Concept (cont.)</font></h2>
<font size="+1">
<ul>
<li>Names are simply examples</li>
<li>Consider the linked list iterators:
<br><br>
<table border='1' cellpadding='4'>
<tr bgcolor="#00ffff">
<th width='50%'>Name in Design Pattern</th>
<th width="50%">Actual Name (List Iterators)</th>
</tr>
<tr>
<td align='center'><tt>Aggregate</tt></td>
<td align='center'><tt>list<T></tt></td>
</tr>
<tr>
<td align='center'><tt>Iterator</tt></td>
<td align='center'><tt>list<T>::iterator</tt></td>
</tr>
<tr>
<td align='center'><tt>create_iterator()</tt></td>
<td align='center'><tt>begin(), end()</tt></td>
</tr>
<tr>
<td align='center'><tt>next()</tt></td>
<td align='center'><tt>++</tt> operator</td>
</tr>
<tr>
<td align='center'><tt>is_done</tt></td>
<td align='center'>Test against <tt>end()</tt></td>
</tr>
<tr>
<td align='center'><tt>current_item()</tt></td>
<td align='center'><tt>*</tt> operator</td>
</tr>
</table>
</li>
</ul>
</font>
<hr><h2><font color="#009999">26.2 The Pattern Concept (cont.)</font></h2>
<font size="+1">
<p>Input streams as example of iterator pattern:</p>
<ul>
<table border='1' cellpadding='4'>
<tr bgcolor="#00ffff">
<th width='50%'>Name in Design Pattern</th>
<th width="50%">Actual Name (Input Streams)</th>
</tr>
<tr>
<td align='center'><tt>Aggregate</tt></td>
<td align='center'>Source of Bytes</td>
</tr>
<tr>
<td align='center'><tt>Iterator</tt></td>
<td align='center'><tt>istream</tt></td>
</tr>
<tr>
<td align='center'><tt>create_iterator()</tt></td>
<td align='center'><tt>open()</tt></td>
</tr>
<tr>
<td align='center'><tt>next()</tt></td>
<td align='center'><tt>get()</tt></td>
</tr>
<tr>
<td align='center'><tt>is_done()</tt></td>
<td align='center'><tt>! fail()</tt></td>
</tr>
<tr>
<td align='center'><tt>current_item()</tt></td>
<td align='center'>Return value of <tt>get()</tt></td>
</tr>
</table>
</ul>
</font>
<hr><h2><font color="#009999">26.2 The Pattern Concept (cont.)</font></h2>
<font size="+1">
<ul>
<li>More abstract than an algorithm</li>
<li>Algorithm implements a computation</li>
<li>Pattern gives advice on solving a problem</li>
<li>See <u>Design Patterns</u>, Gamma, Helm, Johnson, & Vlissides</li>
</ul>
</font>
<hr><h2><font color="#009999">Advanced Topic 26.1</font></h2>
<font size="+1">
<hr color="#00ffff" size="6">
<p><font color="#009999">Generic Programming with Inheritance and Templates
</font></p>
<ul>
<li><u>Design Patterns</u> further recommends using an abstract base class
for the iterator and the aggregate</li>
<li>Generic code can then be written:
<blockquote>
<pre>void print_all(AbstractAggregate* items)
{
AbstractIterator* iter = items->create_iterator();
while (!iter->is_done())
{
cout << iter->current_item() << "\n";
iter->next();
}
}</pre>
</blockquote>
</li>
</ul>
</font>
<hr><h2><font color="#009999">Advanced Topic 26.1 (cont.)</font></h2>
<font size="+1">
<hr color="#00ffff" size="6">
<ul>
<li>Very common in Java and Smalltalk, e.g.</li>
<li>C++ uses templates, not inheritance</li>
<li>Avoids cost of virtual functions</li>
<li>Similar functionality:
<blockquote>
<pre>template<typename T>
void print_all(const T& items)
{
T::iterator iter = items.begin();
while (iter != items.end())
{
cout << *iter << "\n";
iter++;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -