pat5d.htm

Design Pattern 设计模式

</LI>

<A NAME="iter-dest"></A>
<LI><EM>Making sure iterators get deleted.</EM>
<A NAME="clean-up_proxy_for_iterators"></A>
Notice that <CODE>CreateIterator</CODE> returns a newly allocated
iterator object.  We're responsible for deleting it.  If we forget,
then we've created a storage leak.  To make life easier for clients,
we'll provide an <CODE>IteratorPtr</CODE> that acts as a proxy for an
iterator.  It takes care of cleaning up the <CODE>Iterator</CODE> object
when it goes out of scope.

<A NAME="auto1080"></A>
<P><CODE>IteratorPtr</CODE> is always allocated on the
stack.<A NAME="fn5"></A><A HREF="#footnote5"><SUP>5</SUP></A>
C++ automatically takes care of calling
its destructor, which deletes the real iterator.
<CODE>IteratorPtr</CODE> overloads both
<CODE>operator-></CODE> and
<CODE>operator*</CODE> in such a way that an <CODE>IteratorPtr</CODE> can be
treated just like a pointer to an iterator.  The members of
<CODE>IteratorPtr</CODE> are all implemented inline; thus they can incur no
overhead.</P>

<A NAME="auto1081"></A>
<PRE>
    template &lt;class Item>
    class IteratorPtr {
    public:
        IteratorPtr(Iterator&lt;Item>* i): _i(i) { }
        ~IteratorPtr() { delete _i; }
    
        Iterator&lt;Item>* operator->() { return _i; }
        Iterator&lt;Item>&amp; operator*() { return *_i; }
    private:
        // disallow copy and assignment to avoid
        // multiple deletions of _i:
    
        IteratorPtr(const IteratorPtr&amp;);
        IteratorPtr&amp; operator=(const IteratorPtr&amp;);
    private:
        Iterator&lt;Item>* _i;
    };
</PRE>

<A NAME="auto1082"></A>
<P><CODE>IteratorPtr</CODE> lets us simplify our printing code:</P>

<A NAME="auto1083"></A>
<PRE>
    AbstractList&lt;Employee*>* employees;
    // ...
    
    IteratorPtr&lt;Employee*> iterator(employees->CreateIterator());
    PrintEmployees(*iterator);
</PRE>

<A NAME="iter-internal"></A>
<LI><EM>An internal ListIterator.</EM>
As a final example, let's look at a possible implementation of an
internal or passive <CODE>ListIterator</CODE> class.  Here the iterator
controls the iteration, and it applies an operation to each element.

<A NAME="iter-param"></A>
<P>The issue in this case is how to parameterize the iterator with the
operation we want to perform on each element. C++ does not support
anonymous functions or closures that other languages provide for this
task.  There are at least two options: (1) Pass in a pointer to a
function (global or static), or (2) rely on subclassing. In the first
case, the iterator calls the operation passed to it at each point in
the iteration.  In the second case, the iterator calls an operation
that a subclass overrides to enact specific behavior.</P>

<A NAME="auto1084"></A>
<P>Neither option is perfect.  Often you want to accumulate state during
the iteration, and functions aren't well-suited to that; we would have
to use static variables to remember the state.  An
<CODE>Iterator</CODE> subclass provides us with a convenient place to
store the accumulated state, like in an instance variable.  But
creating a subclass for every different traversal is more work.</P>

<A NAME="listtrav"></A>
<P>Here's a sketch of the second option, which uses subclassing.  We call
the internal iterator a <CODE>ListTraverser</CODE>.</P>

<A NAME="auto1085"></A>
<PRE>
    template &lt;class Item>
    class ListTraverser {
    public:
        ListTraverser(List&lt;Item>* aList);
        bool Traverse();
    protected:
        virtual bool ProcessItem(const Item&amp;) = 0;
    private:
        ListIterator&lt;Item> _iterator;
    };
</PRE>

<A NAME="auto1086"></A>
<P><CODE>ListTraverser</CODE> takes a <CODE>List</CODE> instance as a parameter.
Internally it uses an external <CODE>ListIterator</CODE> to do the
traversal. <CODE>Traverse</CODE> starts the traversal and calls
<CODE>ProcessItem</CODE> for each item.  The internal iterator can choose to
terminate a traversal by returning <CODE>false</CODE> from
<CODE>ProcessItem</CODE>. <CODE>Traverse</CODE> returns whether the traversal
terminated prematurely.</P>

<A NAME="auto1087"></A>
<PRE>
    template &lt;class Item>
    ListTraverser&lt;Item>::ListTraverser (
        List&lt;Item>* aList
    ) : _iterator(aList) { }
    
    template &lt;class Item>
    bool ListTraverser&lt;Item>::Traverse () {
        bool result = false;
    
        for (
            _iterator.First();
            !_iterator.IsDone();
            _iterator.Next()
        ) {
            result = ProcessItem(_iterator.CurrentItem());
    
            if (result == false) {
                break;
            }
        }
        return result;
    }
</PRE>

<A NAME="auto1088"></A>
<P>Let's use a <CODE>ListTraverser</CODE> to print the first 10
employees from our employee list. To do it we have to subclass
<CODE>ListTraverser</CODE> and override <CODE>ProcessItem</CODE>. We
count the number of printed employees in a <CODE>_count</CODE> instance
variable.</P>

<A NAME="auto1089"></A>
<PRE>
    class PrintNEmployees : public ListTraverser&lt;Employee*> {
    public:
        PrintNEmployees(List&lt;Employee*>* aList, int n) :
            ListTraverser&lt;Employee*>(aList),
            _total(n), _count(0) { }
    
    protected:
        bool ProcessItem(Employee* const&amp;);
    private:
        int _total;
        int _count;
    };
    
    bool PrintNEmployees::ProcessItem (Employee* const&amp; e) {
        _count++;
        e->Print();
        return _count &lt; _total;
    }
</PRE>

<A NAME="auto1090"></A>
<P>Here's how <CODE>PrintNEmployees</CODE> prints the first 10 employees
on the list:</P>

<A NAME="auto1091"></A>
<PRE>
    List&lt;Employee*>* employees;
    // ...
    
    PrintNEmployees pa(employees, 10);
    pa.Traverse();
</PRE>

<A NAME="iter-external"></A>
<P>Note how the client doesn't specify the iteration loop. The entire
iteration logic can be reused. This is the primary benefit of an
internal iterator.  It's a bit more work than an external iterator,
though, because we have to define a new class.  Contrast this with
using an external iterator:</P>

<A NAME="auto1092"></A>
<PRE>
    ListIterator&lt;Employee*> i(employees);
    int count = 0;
    
    for (i.First(); !i.IsDone(); i.Next()) {
        count++;
        i.CurrentItem()->Print();
    
        if (count >= 10) {
            break;
        }
    }
</PRE>

<A NAME="auto1093"></A>
<P>Internal iterators can encapsulate different kinds of iteration. For
example, <CODE>FilteringListTraverser</CODE> encapsulates an
iteration that processes only items that satisfy a test:</P>
<A NAME="auto1094"></A>
<PRE>
    template &lt;class Item>
    class FilteringListTraverser {
    public:
        FilteringListTraverser(List&lt;Item>* aList);
        bool Traverse();
    protected:
        virtual bool ProcessItem(const Item&amp;) = 0;
        virtual bool TestItem(const Item&amp;) = 0;
    private:
        ListIterator&lt;Item> _iterator;
    };
</PRE>

<A NAME="auto1095"></A>
<P>This interface is the same as <CODE>ListTraverser</CODE>'s except for an
added <CODE>TestItem</CODE> member function that defines the test.
Subclasses override <CODE>TestItem</CODE> to specify the test.</P>

<A NAME="auto1096"></A>
<P><CODE>Traverse</CODE> decides to continue the traversal based on the
outcome of the test:</P>

<A NAME="auto1097"></A>
<PRE>
    template &lt;class Item>
    void FilteringListTraverser&lt;Item>::Traverse () {
        bool result = false;
    
        for (
            _iterator.First();
            !_iterator.IsDone();
            _iterator.Next()
        ) {
            if (TestItem(_iterator.CurrentItem())) {
                result = ProcessItem(_iterator.CurrentItem());
    
                if (result == false) {
                    break;
                }
            }
        }
        return result;
    }
</PRE>

<A NAME="auto1098"></A>
<P>A variant of this class could define <CODE>Traverse</CODE> to return if
at least one item satisfies the test.<A NAME="fn6"></A><A HREF="#footnote6"><SUP>6</SUP></A></P>

</LI>

</OL>

<A NAME="knownuses"><A>
<H2><A HREF="#relatedpatterns"><IMG SRC="gifsb/down3.gif" BORDER=0 
ALT="next: Related Patterns"></A> Known Uses</H2> 

<A NAME="auto1099"></A>
<P>Iterators are common in object-oriented systems.  Most collection
class libraries offer iterators in one form or another.</P>

<A NAME="auto1100"></A>
<P>Here's an example from the Booch components [<A HREF="bibfs.htm#booch_ood" TARGET="_mainDisplayFrame">Boo94</A>], a
popular collection class library.  It provides both a fixed size
(bounded) and dynamically growing (unbounded) implementation of a
queue. The queue interface is defined by an abstract Queue class. To
support polymorphic iteration over the different queue
implementations, the queue iterator is implemented in the terms of the
abstract Queue class interface.  This variation has the advantage that
you don't need a factory method to ask the queue implementations for
their appropriate iterator.  However, it requires the interface of the
abstract Queue class to be powerful enough to implement the iterator
efficiently.</P>

<A NAME="smalltalk-use-iter"></A>
<P>Iterators don't have to be defined as explicitly in Smalltalk.  The
standard collection classes (Bag, Set, Dictionary, OrderedCollection,
String, etc.) define an internal iterator method <CODE>do:</CODE>, which
takes a block (i.e., closure) as an argument.  Each element in the
collection is bound to the local variable in the block; then the block
is executed.  Smalltalk also includes a set of Stream classes that
support an iterator-like interface.  ReadStream is essentially an
Iterator, and it can act as an external iterator for all the
sequential collections.  There are no standard external iterators for
nonsequential collections such as Set and Dictionary.</P>

<A NAME="unidraw-use-iter"></A>
<P>Polymorphic iterators and the cleanup Proxy described earlier are
provided by the ET++ container classes [<A HREF="bibfs.htm#et++" TARGET="_mainDisplayFrame">WGM88</A>].  The Unidraw
graphical editing framework classes use cursor-based
iterators [<A HREF="bibfs.htm#unidraw_framework" TARGET="_mainDisplayFrame">VL90</A>].</P>

<A NAME="auto1101"></A>
<P>ObjectWindows 2.0 [<A HREF="bibfs.htm#objectwindows" TARGET="_mainDisplayFrame">Bor94</A>] provides a class hierarchy of
iterators for containers.  You can iterate over different container
types in the same way.  The ObjectWindow iteration syntax relies on
overloading the postincrement operator <CODE>++</CODE> to advance the
iteration.</P>

<A NAME="relatedpatterns"></A>
<H2><A HREF="#last"><IMG SRC="gifsb/down3.gif" BORDER=0 ALT="next: 
navigation"></A> Related Patterns</H2> 

<A NAME="auto1102"></A>
<P><A HREF="pat4cfs.htm" TARGET="_mainDisplayFrame">Composite (163)</A>:
Iterators are often applied to recursive structures such as
Composites.</P>

<A NAME="auto1103"></A>
<P><A HREF="pat3cfs.htm" TARGET="_mainDisplayFrame">Factory Method (107)</A>:
Polymorphic iterators rely on factory methods to instantiate the
appropriate Iterator subclass.</P>

<A NAME="auto1104"></A>
<P><A HREF="pat5ffs.htm" TARGET="_mainDisplayFrame">Memento (283)</A> is
often used in conjunction with the Iterator pattern.  An iterator
can use a memento to capture the state of an iteration.  The iterator
stores the memento internally.</P>

<A NAME="last"></A>
<P><A HREF="#intent"><IMG SRC="gifsb/up3.gif" BORDER=0></A><BR>
<A HREF="pat5efs.htm" TARGET="_mainDisplayFrame"><IMG SRC="gifsb/rightar3.gif"
        ALIGN=TOP BORDER=0></A> <A HREF="pat5efs.htm"
        TARGET="_mainDisplayFrame">Mediator</A><BR>
<A HREF="pat5cfs.htm" TARGET="_mainDisplayFrame"><IMG SRC="gifsb/leftarr3.gif"
        ALIGN=TOP BORDER=0></A> <A HREF="pat5cfs.htm"
        TARGET="_mainDisplayFrame">Interpreter</A>
</P>

<HR>

<A NAME="footnote2"></A>
<P><SUP>2</SUP>Booch refers to external and internal iterators as
<STRONG>active</STRONG> and <STRONG>passive</STRONG> iterators,
respectively [<A HREF="bibfs.htm#booch_ood" TARGET="_mainDisplayFrame">Boo94</A>].  The
terms "active" and "passive" describe the role of the client, not
the level of activity in the iterator.
</P>

<A NAME="footnote3"></A>
<P><SUP>3</SUP>Cursors are a simple example of the <A HREF="pat5ffs.htm"
TARGET="_mainDisplayFrame">Memento (283)</A> pattern and share many of its
implementation issues.
</P>

<A NAME="footnote4"></A>
<P><SUP>4</SUP>We can make this interface
even <EM>smaller</EM> by merging Next, IsDone, and CurrentItem into a
single operation that advances to the next object and returns it.  If
the traversal is finished, then this operation returns a special
value (0, for instance) that marks the end of the iteration.
</P>

<A NAME="footnote5"></A>
<P><SUP>5</SUP>You can ensure this at compile-time just by declaring
private <CODE>new</CODE> and <CODE>delete</CODE> operators.  An accompanying
implementation isn't needed.
</P>

<A NAME="footnote6"></A>
<P><SUP>6</SUP>The <CODE>Traverse</CODE> operation in these examples
is a <A HREF="pat5jfs.htm" TARGET="_mainDisplayFrame">Template Method (325)</A>
with primitive operations <CODE>TestItem</CODE> and
<CODE>ProcessItem</CODE>.
</P>

</BODY>

</HTML>