📄 pat5d-1.htm
字号:
<HTML><HEAD> <TITLE>Iterator</TITLE>
<SCRIPT>
function setFocus() {
if ((navigator.appName != "Netscape") && (parseFloat(navigator.appVersion) == 2)) {
return;
} else {
self.focus();
}
}
</SCRIPT>
</HEAD>
<BODY BGCOLOR = #FFFFFF
TEXT = #000000
onLoad="setFocus()";
>
<A NAME="top"></A>
<A NAME="Iterator"></A>
<A NAME="intent"></A>
<H2><A HREF="#alsoknownas"><IMG SRC="down3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/down3.gif" BORDER=0 ALT="next:
Also Known As"></A> Intent</H2>
<A NAME="auto1000"></A>
<P>Provide a way to access the elements of an aggregate object
sequentially without exposing its underlying representation.</P>
<A NAME="alsoknownas"><A>
<H2><A HREF="#motivation"><IMG SRC="down3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/down3.gif" BORDER=0 ALT="next:
Motivation"></A> Also Known As</H2>
<A NAME="auto1001"></A>
<P>Cursor</P>
<A NAME="motivation"></A>
<H2><A HREF="#applicability"><IMG SRC="down3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/down3.gif" BORDER=0
ALT="next: Applicability"></A> Motivation</H2>
<A NAME="auto1002"></A>
<P>An aggregate object such as a list should give you a way to access its
elements without exposing its internal structure. Moreover, you might
want to traverse the list in different ways, depending on what you
want to accomplish. But you probably don't want to bloat the List
interface with operations for different traversals, even if you could
anticipate the ones you will need. You might also need to have more than
one traversal pending on the same list.</P>
<A NAME="auto1003"></A>
<P>The Iterator pattern lets you do all this. The key idea in this
pattern is to take the responsibility for access and traversal out of
the list object and put it into an <STRONG>iterator</STRONG> object. The
Iterator class defines an interface for accessing the list's elements.
An iterator object is responsible for keeping track of the current
element; that is, it knows which elements have been traversed already.</P>
<A NAME="list1"></A>
<A NAME="list-iter1"></A>
<P>For example, a List class would call for a ListIterator with the
following relationship between them:</P>
<A NAME="iterator-eg-simple"></A>
<P ALIGN=CENTER><IMG SRC="itera039-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/Pictures/itera039.gif"></P>
<A NAME="auto1004"></A>
<P>Before you can instantiate ListIterator, you must supply the List to
traverse. Once you have the ListIterator instance, you can access the
list's elements sequentially. The CurrentItem operation returns the
current element in the list, First initializes the current element to
the first element, Next advances the current element to the next
element, and IsDone tests whether we've advanced beyond the last
element—that is, we're finished with the traversal.</P>
<A NAME="auto1005"></A>
<P>Separating the traversal mechanism from the List object lets us define
iterators for different traversal policies without enumerating them in
the List interface. For example, FilteringListIterator might provide
access only to those elements that satisfy specific filtering
constraints.</P>
<A NAME="iter-polyiter"></A>
<P>Notice that the iterator and the list are coupled, and the client must
know that it is a <EM>list</EM> that's traversed as opposed to some other
aggregate structure. Hence the client commits to a particular
aggregate structure. It would be better if we could change the aggregate
class without changing client code. We can do this by generalizing
the iterator concept to support <STRONG>polymorphic iteration</STRONG>.</P>
<A NAME="def-skiplist"></A>
<P>As an example, let's assume that we also have a SkipList
implementation of a list. A skiplist [<A HREF="bibfs-1.htm#skiplists" tppabs="http://ultra/development/DesignPatterns/lowres/bibfs.htm#skiplists" TARGET="_mainDisplayFrame">Pug90</A>] is a
probabilistic data structure with characteristics similar to balanced
trees. We want to be able to write code that works for both List and
SkipList objects.</P>
<A NAME="auto1006"></A>
<P>We define an AbstractList class that provides a common interface
for manipulating lists. Similarly, we need an abstract Iterator
class that defines a common iteration interface. Then we can define
concrete Iterator subclasses for the different list implementations.
As a result, the iteration mechanism becomes independent of concrete
aggregate classes.</P>
<A NAME="iterator-eg-poly"></A>
<A NAME="skiplist-258c"></A>
<P ALIGN=CENTER><IMG SRC="itera040-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/Pictures/itera040.gif"></P>
<A NAME="auto1007"></A>
<P>The remaining problem is how to create the iterator. Since we want to
write code that's independent of the concrete List subclasses, we
cannot simply instantiate a specific class. Instead, we make the list
objects responsible for creating their corresponding iterator. This
requires an operation like CreateIterator through which clients
request an iterator object.</P>
<A NAME="fact-iter-create"></A>
<P>CreateIterator is an example of a factory method (see <A HREF="pat3cfs-1.htm" tppabs="http://ultra/development/DesignPatterns/lowres/pat3cfs.htm" TARGET="_mainDisplayFrame">Factory Method (107)</A>). We use it here to let a client ask
a list object for the appropriate iterator. The Factory Method
approach give rise to two class hierarchies, one for lists and another
for iterators. The CreateIterator factory method "connects" the two
hierarchies.</P>
<A NAME="applicability"></A>
<H2><A HREF="#structure"><IMG SRC="down3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/down3.gif" BORDER=0 ALT="next:
Structure"></A> Applicability</H2>
<A NAME="auto1008"></A>
<P>Use the Iterator pattern</P>
<UL>
<A NAME="auto1009"></A>
<LI>to access an aggregate object's contents without exposing its internal
representation.</P>
<A NAME="auto1010"></A>
<LI>to support multiple traversals of aggregate objects.</P>
<A NAME="auto1011"></A>
<LI>to provide a uniform interface for traversing different aggregate
structures (that is, to support polymorphic iteration).</P>
</UL>
<A NAME="structure"></A>
<H2><A HREF="#participants"><IMG SRC="down3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/down3.gif" BORDER=0 ALT="next:
Participants"></A> Structure</H2>
<A NAME="259c"></A>
<P ALIGN=CENTER><IMG SRC="iterator-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/Pictures/iterator.gif"></P>
<A NAME="participants"></A>
<H2><A HREF="#collaborations"><IMG SRC="down3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/down3.gif" BORDER=0
ALT="next: Collaborations"></A> Participants</H2>
<UL>
<A NAME="auto1012"></A>
<LI><B>Iterator</B></LI>
<A NAME="auto1013"></A>
<P></P>
<UL>
<A NAME="auto1014"></A>
<LI>defines an interface for accessing and traversing elements.
</UL>
<A NAME="auto1015"></A>
<P></P>
<A NAME="auto1016"></A>
<LI><B>ConcreteIterator</B>
<A NAME="auto1017"></A>
<P></P>
<UL>
<A NAME="auto1018"></A>
<LI>implements the Iterator interface.</LI>
<A NAME="auto1019"></A>
<P><!-- extra space --></P>
<A NAME="auto1020"></A>
<LI>keeps track of the current position in the traversal of
the aggregate.</LI>
</UL>
<A NAME="auto1021"></A>
<P></P>
<A NAME="auto1022"></A>
<LI><B>Aggregate</B>
<A NAME="auto1023"></A>
<P></P>
<UL>
<A NAME="auto1024"></A>
<LI>defines an interface for creating an Iterator object.</LI>
</UL>
<A NAME="auto1025"></A>
<P></P>
<A NAME="auto1026"></A>
<LI><B>ConcreteAggregate</B></LI>
<A NAME="auto1027"></A>
<P></P>
<UL>
<A NAME="auto1028"></A>
<LI>implements the Iterator creation interface to return an
instance of the proper ConcreteIterator.</LI>
</UL>
</UL>
<A NAME="collaborations"></A>
<H2><A HREF="#consequences"><IMG SRC="down3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/down3.gif" BORDER=0
ALT="next: Consequences"></A> Collaborations</H2>
<UL>
<A NAME="auto1029"></A>
<LI>A ConcreteIterator keeps track of the current object in the
aggregate and can compute the succeeding object in the
traversal.</LI>
</UL>
<A NAME="consequences"></A>
<H2><A HREF="#implementation"><IMG SRC="down3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/down3.gif" BORDER=0
ALT="next: Implementation"></A> Consequences</H2>
<A NAME="auto1030"></A>
<P>The Iterator pattern has three important consequences:</P>
<OL>
<A NAME="auto1031"></A>
<LI><EM>It supports variations in the traversal of an aggregate.</EM>
Complex aggregates may be traversed in many ways. For example, code
generation and semantic checking involve traversing parse trees. Code
generation may traverse the parse tree inorder or preorder.
Iterators make it easy to change the traversal algorithm: Just replace
the iterator instance with a different one. You can also define
Iterator subclasses to support new traversals.</LI>
<A NAME="auto1032"></A>
<P></P>
<A NAME="auto1033"></A>
<LI><EM>Iterators simplify the Aggregate interface.</EM>
Iterator's traversal interface obviates the need for a similar
interface in Aggregate, thereby simplifying the aggregate's interface.</LI>
<A NAME="auto1034"></A>
<P></P>
<A NAME="auto1035"></A>
<LI><EM>More than one traversal can be pending on an aggregate.</EM>
An iterator keeps track of its own traversal state. Therefore you can
have more than one traversal in progress at once.</LI>
</OL>
<A NAME="implementation"></A>
<H2><A HREF="#samplecode"><IMG SRC="down3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/down3.gif" BORDER=0 ALT="next:
Sample Code"></A> Implementation</H2>
<A NAME="auto1036"></A>
<P>Iterator has many implementation variants and alternatives. Some
important ones follow. The trade-offs often depend on the
control structures your language provides. Some languages
(CLU [<A HREF="bibfs-1.htm#CLU" tppabs="http://ultra/development/DesignPatterns/lowres/bibfs.htm#CLU" TARGET="_mainDisplayFrame">LG86</A>], for example) even support this pattern directly.</P>
<OL>
<A NAME="iter-ext-int"></A>
<A NAME="iter-passive"></A>
<LI><EM>Who controls the iteration?</EM>
A fundamental issue is deciding which party controls the iteration,
the iterator or the client that uses the iterator. When the client
controls the iteration, the iterator is called an <STRONG>external
iterator</STRONG>, and when the iterator controls it, the iterator is an
<STRONG>internal iterator</STRONG>.<A NAME="fn2"></A><A HREF="#footnote2"><SUP>2</SUP></A>
Clients that use an
external iterator must advance the traversal and request the next
element explicitly from the iterator. In contrast, the client hands
an internal iterator an operation to perform, and the iterator applies
that operation to every element in the aggregate.
<A NAME="auto1037"></A>
<P>External iterators are more flexible than internal iterators. It's
easy to compare two collections for equality with an external
iterator, for example, but it's practically impossible with internal
iterators. Internal iterators are especially weak in a language like
C++ that does not provide anonymous functions, closures, or
continuations like Smalltalk and CLOS. But on the other hand,
internal iterators are easier to use, because they define the iteration
logic for you.</P>
</LI>
<A NAME="auto1038"></A>
<P></P>
<A NAME="iter-cursor"></A>
<LI><EM>Who defines the traversal algorithm?</EM>
The iterator is not the only place where the traversal algorithm can
be defined. The aggregate might define the traversal algorithm and
use the iterator to store just the state of the iteration. We call
this kind of iterator a <STRONG>cursor</STRONG>, since it merely points to
the current position in the aggregate. A client will invoke the Next
operation on the aggregate with the cursor as an argument, and the
Next operation will change the state of the
cursor.<A NAME="fn3"></A><A HREF="#footnote3"><SUP>3</SUP></A>
<A NAME="auto1039"></A>
<P>If the iterator is responsible for the traversal algorithm, then it's
easy to use different iteration algorithms on the same aggregate, and
it can also be easier to reuse the same algorithm on different
aggregates. On the other hand, the traversal algorithm might need to
access the private variables of the aggregate. If so, putting the
traversal algorithm in the iterator violates the encapsulation of the
aggregate.</P>
</LI>
<A NAME="auto1040"></A>
<P></P>
<A NAME="auto1041"></A>
<LI><EM>How robust is the iterator?</EM>
It can be dangerous to modify an aggregate while you're traversing it.
If elements are added or deleted from the aggregate, you might end up
accessing an element twice or missing it completely. A simple
solution is to copy the aggregate and traverse the copy, but that's
too expensive to do in general.
<A NAME="iter-robust"></A>
<P>A <STRONG>robust iterator</STRONG> ensures that insertions and removals
won't interfere with traversal, and it does it without copying the
aggregate. There are many ways to implement robust iterators. Most
rely on registering the iterator with the aggregate. On insertion or
removal, the aggregate either adjusts the internal state of iterators
it has produced, or it maintains information internally to ensure
proper traversal.</P>
<A NAME="et-use-iter"></A>
<P>Kofler provides a good discussion of how robust iterators are
implemented in ET++ [<A HREF="bibfs-1.htm#kofler-iterators" tppabs="http://ultra/development/DesignPatterns/lowres/bibfs.htm#kofler-iterators" TARGET="_mainDisplayFrame">Kof93</A>]. Murray discusses the
implementation of robust iterators for the USL StandardComponents'
List class [<A HREF="bibfs-1.htm#murray_c++strategies" tppabs="http://ultra/development/DesignPatterns/lowres/bibfs.htm#murray_c++strategies" TARGET="_mainDisplayFrame">Mur93</A>].</P>
</LI>
<A NAME="auto1042"></A>
<P></P>
<A NAME="iter-interface"></A>
<LI><EM>Additional Iterator operations.</EM>
The minimal interface to Iterator consists of the operations First,
Next, IsDone, and CurrentItem.<A NAME="fn4"></A><A HREF="#footnote4"><SUP>4</SUP></A>
Some
additional operations might prove useful. For example, ordered
aggregates can have a Previous operation that positions the iterator
to the previous element. A SkipTo operation is useful for sorted or
indexed collections. SkipTo positions the iterator to an object
matching specific criteria.</LI>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -