📄 pat5d.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 = #000000onLoad="setFocus()";><A NAME="top"></A><A NAME="Iterator"></A><A NAME="intent"></A><H2><A HREF="#alsoknownas"><IMG SRC="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 objectsequentially without exposing its underlying representation.</P><A NAME="alsoknownas"><A><H2><A HREF="#motivation"><IMG SRC="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="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 itselements without exposing its internal structure. Moreover, you mightwant to traverse the list in different ways, depending on what youwant to accomplish. But you probably don't want to bloat the Listinterface with operations for different traversals, even if you couldanticipate the ones you will need. You might also need to have more thanone traversal pending on the same list.</P><A NAME="auto1003"></A><P>The Iterator pattern lets you do all this. The key idea in thispattern is to take the responsibility for access and traversal out ofthe list object and put it into an <STRONG>iterator</STRONG> object. TheIterator class defines an interface for accessing the list's elements.An iterator object is responsible for keeping track of the currentelement; 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 thefollowing relationship between them:</P><A NAME="iterator-eg-simple"></A><P ALIGN=CENTER><IMG SRC="Pictures/itera039.gif"></P><A NAME="auto1004"></A><P>Before you can instantiate ListIterator, you must supply the List totraverse. Once you have the ListIterator instance, you can access thelist's elements sequentially. The CurrentItem operation returns thecurrent element in the list, First initializes the current element tothe first element, Next advances the current element to the nextelement, and IsDone tests whether we've advanced beyond the lastelement—that is, we're finished with the traversal.</P><A NAME="auto1005"></A><P>Separating the traversal mechanism from the List object lets us defineiterators for different traversal policies without enumerating them inthe List interface. For example, FilteringListIterator might provideaccess only to those elements that satisfy specific filteringconstraints.</P><A NAME="iter-polyiter"></A><P>Notice that the iterator and the list are coupled, and the client mustknow that it is a <EM>list</EM> that's traversed as opposed to some otheraggregate structure. Hence the client commits to a particularaggregate structure. It would be better if we could change the aggregateclass without changing client code. We can do this by generalizingthe 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 SkipListimplementation of a list. A skiplist [<A HREF="bibfs.htm#skiplists" TARGET="_mainDisplayFrame">Pug90</A>] is aprobabilistic data structure with characteristics similar to balancedtrees. We want to be able to write code that works for both List andSkipList objects.</P><A NAME="auto1006"></A><P>We define an AbstractList class that provides a common interfacefor manipulating lists. Similarly, we need an abstract Iteratorclass that defines a common iteration interface. Then we can defineconcrete Iterator subclasses for the different list implementations.As a result, the iteration mechanism becomes independent of concreteaggregate classes.</P><A NAME="iterator-eg-poly"></A><A NAME="skiplist-258c"></A><P ALIGN=CENTER><IMG SRC="Pictures/itera040.gif"></P><A NAME="auto1007"></A><P>The remaining problem is how to create the iterator. Since we want towrite code that's independent of the concrete List subclasses, wecannot simply instantiate a specific class. Instead, we make the listobjects responsible for creating their corresponding iterator. Thisrequires an operation like CreateIterator through which clientsrequest an iterator object.</P><A NAME="fact-iter-create"></A><P>CreateIterator is an example of a factory method (see <A HREF="pat3cfs.htm" TARGET="_mainDisplayFrame">Factory Method (107)</A>). We use it here to let a client aska list object for the appropriate iterator. The Factory Methodapproach give rise to two class hierarchies, one for lists and anotherfor iterators. The CreateIterator factory method "connects" the twohierarchies.</P><A NAME="applicability"></A><H2><A HREF="#structure"><IMG SRC="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 internalrepresentation.</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 aggregatestructures (that is, to support polymorphic iteration).</P></UL><A NAME="structure"></A><H2><A HREF="#participants"><IMG SRC="gifsb/down3.gif" BORDER=0 ALT="next: Participants"></A> Structure</H2> <A NAME="259c"></A><P ALIGN=CENTER><IMG SRC="Pictures/iterator.gif"></P><A NAME="participants"></A><H2><A HREF="#collaborations"><IMG SRC="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="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 theaggregate and can compute the succeeding object in thetraversal.</LI></UL><A NAME="consequences"></A><H2><A HREF="#implementation"><IMG SRC="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, codegeneration and semantic checking involve traversing parse trees. Codegeneration may traverse the parse tree inorder or preorder.Iterators make it easy to change the traversal algorithm: Just replacethe iterator instance with a different one. You can also defineIterator 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 similarinterface 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 canhave more than one traversal in progress at once.</LI></OL><A NAME="implementation"></A><H2><A HREF="#samplecode"><IMG SRC="gifsb/down3.gif" BORDER=0 ALT="next: Sample Code"></A> Implementation</H2> <A NAME="auto1036"></A><P>Iterator has many implementation variants and alternatives. Someimportant ones follow. The trade-offs often depend on thecontrol structures your language provides. Some languages (CLU [<A HREF="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 clientcontrols the iteration, the iterator is called an <STRONG>externaliterator</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 anexternal iterator must advance the traversal and request the nextelement explicitly from the iterator. In contrast, the client handsan internal iterator an operation to perform, and the iterator appliesthat operation to every element in the aggregate.<A NAME="auto1037"></A><P>External iterators are more flexible than internal iterators. It'seasy to compare two collections for equality with an externaliterator, for example, but it's practically impossible with internaliterators. Internal iterators are especially weak in a language likeC++ that does not provide anonymous functions, closures, orcontinuations like Smalltalk and CLOS. But on the other hand,internal iterators are easier to use, because they define the iterationlogic 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 canbe defined. The aggregate might define the traversal algorithm anduse the iterator to store just the state of the iteration. We callthis kind of iterator a <STRONG>cursor</STRONG>, since it merely points tothe current position in the aggregate. A client will invoke the Nextoperation on the aggregate with the cursor as an argument, and theNext operation will change the state of thecursor.<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'seasy to use different iteration algorithms on the same aggregate, andit can also be easier to reuse the same algorithm on differentaggregates. On the other hand, the traversal algorithm might need toaccess the private variables of the aggregate. If so, putting thetraversal algorithm in the iterator violates the encapsulation of theaggregate.</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 upaccessing an element twice or missing it completely. A simplesolution is to copy the aggregate and traverse the copy, but that'stoo expensive to do in general.<A NAME="iter-robust"></A><P>A <STRONG>robust iterator</STRONG> ensures that insertions and removalswon't interfere with traversal, and it does it without copying theaggregate. There are many ways to implement robust iterators. Mostrely on registering the iterator with the aggregate. On insertion orremoval, the aggregate either adjusts the internal state of iteratorsit has produced, or it maintains information internally to ensureproper traversal.</P><A NAME="et-use-iter"></A><P>Kofler provides a good discussion of how robust iterators areimplemented in ET++ [<A HREF="bibfs.htm#kofler-iterators" TARGET="_mainDisplayFrame">Kof93</A>]. Murray discusses theimplementation of robust iterators for the USL StandardComponents'List class [<A HREF="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>Someadditional operations might prove useful. For example, orderedaggregates can have a Previous operation that positions the iteratorto the previous element. A SkipTo operation is useful for sorted orindexed collections. SkipTo positions the iterator to an objectmatching specific criteria.</LI>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -