pat5d.htm

Design Pattern 设计模式

<A NAME="auto1043"></A>
<P></P>

<A NAME="iter-use-poly"></A>
<LI><EM>Using polymorphic iterators in C++.</EM>
Polymorphic iterators have their cost. They require the iterator
object to be allocated dynamically by a factory method.  Hence they
should be used only when there's a need for polymorphism.  Otherwise
use concrete iterators, which can be allocated on the stack.

<A NAME="auto1044"></A>
<P>Polymorphic iterators have another drawback: the client is responsible
for deleting them.  This is error-prone, because it's easy to forget
to free a heap-allocated iterator object when you're finished with it.
That's especially likely when there are multiple exit points in an
operation.  And if an exception is triggered, the iterator object will
never be freed.</P>

<A NAME="proxy-w-iter"></A>
<P>The <A HREF="pat4gfs.htm" TARGET="_mainDisplayFrame">Proxy (207)</A> pattern provides a remedy.  We can use a
stack-allocated proxy as a stand-in for the real iterator. The proxy
deletes the iterator in its destructor.  Thus when the proxy goes out
of scope, the real iterator will get deallocated along with it.  The
proxy ensures proper cleanup, even in the face of exceptions.  This
is an application of the well-known C++ technique "resource
allocation is initialization" [<A HREF="bibfs.htm#c++_arm" TARGET="_mainDisplayFrame">ES90</A>].  The Sample Code gives
an example.</P>

</LI>

<A NAME="auto1045"></A>
<P></P>

<A NAME="friend-iter"></A>
<LI><EM>Iterators may have privileged access.</EM>
An iterator can be viewed as an extension of the aggregate that
created it.  The iterator and the aggregate are tightly coupled.  We
can express this close relationship in C++ by making the iterator a
<CODE>friend</CODE> of its aggregate.  Then you don't need to
define aggregate operations whose sole purpose is to let iterators
implement traversal efficiently.

<A NAME="auto1046"></A>
<P>However, such privileged access can make defining new traversals
difficult, since it'll require changing the aggregate interface to add
another friend.  To avoid this problem, the Iterator class can include
<CODE>protected</CODE> operations for accessing important but publicly
unavailable members of the aggregate.  Iterator subclasses (and <EM>only</EM> Iterator subclasses) may use these protected operations to gain
privileged access to the aggregate.</P>

</LI>

<A NAME="auto1047"></A>
<P></P>

<A NAME="iter-recur"></A>
<LI><EM>Iterators for composites.</EM>
External iterators can be difficult to implement over recursive
aggregate structures like those in the <A HREF="pat4cfs.htm" TARGET="_mainDisplayFrame">Composite (163)</A>
pattern, because a position in the structure may span many levels of
nested aggregates.  Therefore an external iterator has to store a path
through the Composite to keep track of the current object.  Sometimes
it's easier just to use an internal iterator.  It can record the
current position simply by calling itself recursively, thereby storing
the path implicitly in the call stack.

<A NAME="auto1048"></A>
<P>If the nodes in a Composite have an interface for moving from a node
to its siblings, parents, and children, then a cursor-based iterator
may offer a better alternative. The cursor only needs to keep track of
the current node; it can rely on the node interface to traverse the
Composite.</P>

<A NAME="trav-in-pre-post"></A>
<P>Composites often need to be traversed in more than one way.  Preorder,
postorder, inorder, and breadth-first traversals are common.  You can
support each kind of traversal with a different class of iterator.</P>

</LI>

<A NAME="auto1049"></A>
<P></P>

<A NAME="NullIterator"></A>
<LI><EM>Null iterators.</EM>
A <STRONG>NullIterator</STRONG> is a degenerate iterator that's helpful for
handling boundary conditions. By definition, a NullIterator is <EM>always</EM> done with traversal; that is, its IsDone operation always
evaluates to true.

<A NAME="auto1050"></A>
<P>NullIterator can make traversing tree-structured aggregates (like
Composites) easier.  At each point in the traversal, we ask the
current element for an iterator for its children.  Aggregate elements
return a concrete iterator as usual.  But leaf elements return an
instance of NullIterator.  That lets us implement traversal over the
entire structure in a uniform way.</P>

</LI>

</OL>

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

<A NAME="auto1051"></A>
<P>We'll look at the implementation of a simple List class, which is part
of our foundation library
(<A HREF="chapCfs.htm" TARGET="_mainDisplayFrame">Appendix&nbsp;C</A>).
We'll
show two Iterator implementations, one for traversing the List in
front-to-back order, and another for traversing back-to-front (the
foundation library supports only the first one).  Then we show how to
use these iterators and how to avoid committing to a particular
implementation.  After that, we change the design to make sure
iterators get deleted properly.  The last example illustrates an
internal iterator and compares it to its external counterpart.</P>

<OL>

<A NAME="iter-interface2"></A>
<A NAME="list-interface"></A>
<LI><EM>List and Iterator interfaces.</EM>
First let's look at the part of the List interface that's relevant to
implementing iterators. Refer to
(<A HREF="chapCfs.htm" TARGET="_mainDisplayFrame">Appendix&nbsp;C</A>).
for the full interface.

<A NAME="auto1052"></A>
<PRE>
    template &lt;class Item>
    class List {
    public:
        List(long size = DEFAULT_LIST_CAPACITY);
    
        long Count() const;
        Item&amp; Get(long index) const;
        // ...
    };
</PRE>

<A NAME="auto1053"></A>
<P>The <CODE>List</CODE> class provides a reasonably efficient way to
support iteration through its public interface.  It's sufficient to
implement both traversals. So there's no need to give iterators
privileged access to the underlying data structure; that is, the
iterator classes are not friends of <CODE>List</CODE>.  To enable
transparent use of the different traversals we define an abstract
<CODE>Iterator</CODE> class, which defines the iterator interface.</P>

<A NAME="class_Iterator_declaration"></A>
<PRE>
    template &lt;class Item>
    class Iterator {
    public:
        virtual void First() = 0;
        virtual void Next() = 0;
        virtual bool IsDone() const = 0;
        virtual Item CurrentItem() const = 0;
    protected:
        Iterator();
    };
</PRE>

</LI>
<A NAME="auto1054"></A>
<P></P>
<A NAME="auto1055"></A>
<LI><EM>Iterator subclass implementations.</EM>
<CODE>ListIterator</CODE> is a subclass of <CODE>Iterator</CODE>.

<A NAME="auto1056"></A>
<PRE>
    template &lt;class Item>
    class ListIterator : public Iterator&lt;Item> {
    public:
        ListIterator(const List&lt;Item>* aList);
        virtual void First();
        virtual void Next();
        virtual bool IsDone() const;
        virtual Item CurrentItem() const;
    
    private:
        const List&lt;Item>* _list;
        long _current;
    };
</PRE>

<A NAME="list-iter2"></A>
<P>The implementation of <CODE>ListIterator</CODE> is straightforward.  It
stores the <CODE>List</CODE> along with an index <CODE>_current</CODE> into
the list:</P>

<A NAME="auto1057"></A>
<PRE>
    template &lt;class Item>
    ListIterator&lt;Item>::ListIterator (
        const List&lt;Item>* aList
    ) : _list(aList), _current(0) {
    }
</PRE>

<A NAME="auto1058"></A>
<P><CODE>First</CODE> positions the iterator to the first element:</P>

<A NAME="auto1059"></A>
<PRE>
    template &lt;class Item>
    void ListIterator&lt;Item>::First () {
        _current = 0;
    }
</PRE>

<A NAME="auto1060"></A>
<P><CODE>Next</CODE> advances the current element:</P>

<A NAME="auto1061"></A>
<PRE>
    template &lt;class Item>
    void ListIterator&lt;Item>::Next () {
        _current++;
    }
</PRE>

<A NAME="auto1062"></A>
<P><CODE>IsDone</CODE> checks whether the index refers to an element within
the List:</P>

<A NAME="auto1063"></A>
<PRE>
    template &lt;class Item>
    bool ListIterator&lt;Item>::IsDone () const {
        return _current >= _list->Count();
    }
</PRE>

<A NAME="auto1064"></A>
<P>Finally, <CODE>CurrentItem</CODE> returns the item at the current index.
If the iteration has already terminated, then we throw an
<CODE>IteratorOutOfBounds</CODE> exception:</P>

<A NAME="auto1065"></A>
<PRE>
    template &lt;class Item>
    Item ListIterator&lt;Item>::CurrentItem () const {
        if (IsDone()) {
            throw IteratorOutOfBounds;
        }
        return _list->Get(_current);
    }
</PRE>

<A NAME="auto1066"></A>
<P>The implementation of ReverseListIterator is identical, except its
<CODE>First</CODE> operation positions <CODE>_current</CODE>
to the end of the list, and <CODE>Next</CODE> decrements
<CODE>_current</CODE> toward the first item.</P>

</LI>

<A NAME="auto1067"></A>
<P></P>

<A NAME="auto1068"></A>
<LI><EM>Using the iterators.</EM>
Let's assume we have a <CODE>List</CODE> of <CODE>Employee</CODE> objects,
and we would like to print all the contained employees.  The
<CODE>Employee</CODE> class supports this with a <CODE>Print</CODE>
operation.  To print the list, we define a <CODE>PrintEmployees</CODE>
operation that takes an iterator as an argument. It uses the iterator
to traverse and print the list.

<A NAME="auto1069"></A>
<PRE>
    void PrintEmployees (Iterator&lt;Employee*>&amp; i) {
        for (i.First(); !i.IsDone(); i.Next()) {
            i.CurrentItem()->Print();
        }
    }
</PRE>

<A NAME="auto1070"></A>
<P>Since we have iterators for both back-to-front and front-to-back
traversals, we can reuse this operation to print the employees in both
orders.</P>

<A NAME="auto1071"></A>
<PRE>
    List&lt;Employee*>* employees;
    // ...
    ListIterator&lt;Employee*> forward(employees);
    ReverseListIterator&lt;Employee*> backward(employees);
    
    PrintEmployees(forward);
    PrintEmployees(backward);
</PRE>

</LI>

<A NAME="skiplist-265"></A>
<LI><EM>Avoiding commitment to a specific list implementation.</EM>
Let's consider how a skiplist variation of <CODE>List</CODE> would affect
our iteration code.  A <CODE>SkipList</CODE> subclass of
<CODE>List</CODE> must provide a <CODE>SkipListIterator</CODE> that
implements the <CODE>Iterator</CODE> interface.  Internally, the
<CODE>SkipListIterator</CODE> has to keep more than just an index to
do the iteration efficiently.  But since
<CODE>SkipListIterator</CODE> conforms to the
<CODE>Iterator</CODE> interface, the <CODE>PrintEmployees</CODE> operation
can also be used when the employees are stored in a <CODE>SkipList</CODE>
object.

<A NAME="auto1072"></A>
<PRE>
    SkipList&lt;Employee*>* employees;
    // ...
    
    SkipListIterator&lt;Employee*> iterator(employees);
    PrintEmployees(iterator);
</PRE>

<A NAME="auto1073"></A>
<P>Although this approach works, it would be better if we didn't have to commit
to a specific <CODE>List</CODE> implementation, namely
<CODE>SkipList</CODE>.  We can introduce an <CODE>AbstractList</CODE>
class to standardize the list interface for different list
implementations.  <CODE>List</CODE> and <CODE>SkipList</CODE> become
subclasses of <CODE>AbstractList</CODE>.

<A NAME="iter-poly-enable"></A>
<P>To enable polymorphic iteration, <CODE>AbstractList</CODE> defines a
factory method <CODE>CreateIterator</CODE>, which subclasses override to
return their corresponding iterator:</P>

<A NAME="auto1074"></A>
<PRE>
    template &lt;class Item>
    class AbstractList {
    public:
        virtual Iterator&lt;Item>* CreateIterator() const = 0;
        // ...
    };
</PRE>

<A NAME="auto1075"></A>
<P>An alternative would be to define a general mixin class
<CODE>Traversable</CODE> that defines the interface for creating an
iterator.  Aggregate classes can mix in
<CODE>Traversable</CODE> to support polymorphic iteration.

<A NAME="auto1076"></A>
<P><CODE>List</CODE> overrides <CODE>CreateIterator</CODE> to return a
<CODE>ListIterator</CODE> object:</P>

<A NAME="auto1077"></A>
<PRE>
    template &lt;class Item>
    Iterator&lt;Item>* List&lt;Item>::CreateIterator () const {
        return new ListIterator&lt;Item>(this);
    }
</PRE>

<A NAME="auto1078"></A>
<P>Now we're in a position to write the code for printing
the employees independent of a concrete representation.</P>

<A NAME="auto1079"></A>
<PRE>
    // we know only that we have an AbstractList
    AbstractList&lt;Employee*>* employees;
    // ...
    
    Iterator&lt;Employee*>* iterator = employees->CreateIterator();
    PrintEmployees(*iterator);
    delete iterator;
</PRE>