Iterator (designmönster)
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från
versionen som granskades den 9 maj 2016; kontroller kräver
9 redigeringar .
Iterator är ett beteendedesignmönster . Representerar ett objekt som tillåter sekventiell åtkomst till elementen i ett aggregerat objekt utan att använda beskrivningar av vart och ett av de aggregerade objekten.
Till exempel kan element som ett träd , en länkad lista , en hashtabell och en array passeras (och modifieras) med hjälp av ett Iterator- objekt .
Iteration genom elementen görs av iteratorobjektet, inte av själva samlingen. Detta förenklar gränssnittet och implementeringen av samlingen och främjar en mer logisk separation av problem .
En funktion hos en fullt implementerad iterator är att koden som använder iteratorn kanske inte vet något om typen av itererade aggregat.
Naturligtvis (i C++) kan nästan alla aggregat upprepas med en void*-pekare, men:
- det är inte klart vad värdet för "slut på aggregerad" är, för en dubbellänkad lista är det &ListHead, för en array är det &array[storlek], för en enkellänkad lista är det NULL
- Nästa operation är starkt beroende av typen av aggregat.
Iteratorer låter dig abstrahera typen och terminatorn för ett aggregat med den polymorfa Next (ofta implementerad som operator++ i C++) och den polymorfa aggregate.end() som returnerar "end of the aggregate".
Således blir det möjligt att arbeta med intervall av iteratorer, i avsaknad av kunskap om typen av det itererade aggregatet. Till exempel:
Iterator itBegin = aggregat . börja ();
Iterator itEnd = aggregat . slut ();
func ( itBegin , itEnd );
Och vidare:
void func ( Iterator itBegin , Iterator itEnd )
{
för ( Iterator it = itBegin , it != itEnd ; ++ it )
{
}
}
Exempel
C#
Källtext i
C#
/*
exempelkod i C#
Denna strukturella kod demonstrerar Iterator-mönstret som tillhandahåller ett sätt att korsa (iteratera) över en samling av föremål utan att detaljera den underliggande strukturen för samlingen.
*/
dölj koden
// Iteratormönster -- Strukturellt exempel
använder System ;
använder System.Collections ;
namnutrymme DoFactory.GangOfFour.Iterator.Structural
{
/// <sammanfattning>
/// MainApp-startklass för Structural
/// Iterator Design Pattern.
/// </summary>
class MainApp
{
/// <summary>
/// Ingångspunkt till konsolapplikationen.
/// </summary>
static void Main ()
{
ConcreteAggregate a = new ConcreteAggregate ();
a [ 0 ] = "Artikel A" ;
a [ 1 ] = "Artikel B" ;
a [ 2 ] = "Artikel C" ;
a [ 3 ] = "Artikel D" ;
// Skapa Iterator och tillhandahåll aggregerad
ConcreteIterator i = ny ConcreteIterator ( a );
Konsol . WriteLine ( "Itererar över samling:" );
objektobjekt = i . _ först (); while (! i . IsDone ()) { Console . WriteLine ( objekt ); artikel = i . nästa (); }
// Vänta på
användarkonsolen . ReadKey ();
}
}
/// <summary>
/// Abstraktklassen 'Aggregate'
/// </summary>
abstrakt klass Aggregate
{
public abstract Iterator CreateIterator ();
public abstract int Count { get ; skyddad uppsättning ; }
offentligt abstrakt objekt detta [ int index ] { get ; set ; }
}
/// <summary>
/// Klassen 'ConcreteAggregate'
/// </summary>
klassen ConcreteAggregate : Aggregate
{
private readonly ArrayList _items = new ArrayList ();
public override Iterator CreateIterator ()
{
return new ConcreteIterator ( this );
}
// Får objektantal
public override int Count
{
get { return _items . räkna ; }
skyddad uppsättning { }
}
// Indexer
public override object this [ int index ]
{
get { return _items [ index ]; }
set { _items . infoga ( index , värde ); }
}
}
/// <summary>
/// Abstraktklassen 'Iterator'
/// </summary>
abstrakt klass Iterator
{
public abstract object First ();
offentligt abstrakt objekt Nästa ();
public abstract bool IsDone ();
offentligt abstrakt objekt CurrentItem ();
}
/// <summary>
/// Klassen 'ConcreteIterator'
/// </summary>
klassen ConcreteIterator : Iterator
{
private readonly Aggregate _aggregate ;
privat int _current ;
// Constructor
public ConcreteIterator ( Aggregerat aggregat )
{
detta . _aggregate = aggregat ;
}
// Får första iterationsobjekt
public override object First ()
{
return _aggregate [ 0 ];
}
// Hämtar nästa iterationsobjekt
public override object Next ()
{
object ret = null ;
_current ++;
if ( _current < _aggregate . Count )
{
ret = _aggregate [ _current ];
}
return ret ;
}
// Hämtar aktuellt iterationsobjekt
public override object CurrentItem ()
{
return _aggregate [ _current ];
}
// Hämtar om iterationer är fullständiga
public override bool IsDone ()
{
return _current >= _aggregate . räkna ;
}
}
}
Output
Iterating over collection :
Artikel A
Objekt B
Objekt C
Objekt D
PHP5
PHP5 källkod
/**
* Iteratormönstret tillhandahåller en mekanism för att iterera genom elementen i en samling utan att avslöja implementeringen av samlingen.
*
* Iteration genom elementen görs av iteratorobjektet, inte av själva samlingen.
* Detta förenklar gränssnittet och implementeringen av samlingen, och bidrar även till en mer logisk ansvarsfördelning.
*/
namespace iterator1 {
/**
* Att ha ett gemensamt gränssnitt är bekvämt för klienten eftersom klienten är frikopplad från implementeringen av samlingen av objekt.
*
* ConcreteAggregate innehåller en samling objekt och implementerar en metod som returnerar en iterator för denna samling.
*/
interface IAggregate
{
/**
* Varje ConcreteAggregate-smak är ansvarig för att skapa en Concrete Iterator-instans som
* kan användas för att iterera över dess samling av objekt.
*/
offentlig funktion createIterator ();
}
/**
* Iterator-gränssnittet måste implementeras av alla iteratorer.
*
* ConcreteIterator är ansvarig för att hantera den aktuella iterationspositionen.
*/
interface IIterator
{
/**
* @abstract
* @return boolean finns det ett nästa element i samlingen
*/
public function hasNext ();
/**
* @abstract
* @return mixed next array element
*/
public function next ();
/**
* Tar bort det aktuella elementet i samlingen
* @abstract
* @return void
*/
public function remove ();
}
/**
* I mitt exempel använder båda samlingarna samma iterator - en array-iterator.
*/
klass ConcreteAggregate1 implementerar IAggregate
{
/**
* @var Item[] $items
*/
public $items = array ();
public function __construct ()
{
$this -> items = array (
new Item ( 1 , 2 ),
new Item ( 1 , 2 ),
new Item ( 1 , 2 ),
);
}
public function createIterator ()
{
return new ConcreteIterator1 ( $this -> items );
}
}
class ConcreteAggregate2 implementerar IAggregate
{
/**
* @var Item[] $items
*/
public $items = array ();
public function __construct ()
{
$this -> items = array (
new Item ( 2 , 3 ),
new Item ( 2 , 3 ),
new Item ( 2 , 3 ),
);
}
public function createIterator ()
{
return new ConcreteIterator1 ( $this -> items );
}
}
class ConcreteIterator1 implementerar IIterator
{
/**
* @var Item[] $items
*/
protected $items = array ();
/**
* @var int $position lagrar den aktuella iterationspositionen i arrayen
*/
public $position = 0 ;
/**
* @param $items array av objekt att iterera över
*/
public function __construct ( $items )
{
$this -> items = $items ;
}
public function hasNext ()
{
if ( $this -> position >= count ( $this -> items ) || count ( $this -> items ) == 0 ) {
return ( false );
} annat {
return ( sant );
}
}
public function next ()
{
$menuItem = $this -> items [ $this -> position ];
$this -> position ++ ;
return ( $menuItem );
}
public function remove ()
{
if ( $this -> position <= 0 ) {
throw new \Exception ( 'Du kan inte anropa remove innan minst en nästa() har anropats' );
}
if ( $this -> items [ $this -> position - 1 ] != null ) {
for ( $i = $this -> position - 1 ; $i < count ( $this -> items ); $i + + ) {
$this -> items [ $i ] = $this -> items [ $i + 1 ];
}
$this -> items [ count ( $this -> items ) - 1 ] = null ;
}
}
}
class Client
{
/**
* @var ConcreteAggregate1 $aggregate1
*/
public $aggregate1 ;
/**
* @var ConcreteAggregate2 $aggregate2
*/
public $aggregate2 ;
offentlig funktion __construct ( $aggregate1 , $aggregate2 )
{
$this -> aggregate1 = $aggregate1 ;
$this -> aggregat2 = $aggregate2 ;
}
public function printAggregatesItems ()
{
$iterator1 = $this -> aggregate1 -> createIterator ();
echo " \ nFirst" ;
$this -> printIteratorItems ( $iterator1 );
$iterator2 = $this -> aggregate2 -> createIterator ();
echo " \n\ nAndra" ;
$this -> printIteratorItems ( $iterator2 );
}
/**
* @param $iterator IIterator
*/
privat funktion printIteratorItems ( $iterator )
{
while ( $iterator -> hasNext ()) {
$item = $iterator -> next ();
echo " \n $item->namn $item->pris $item->beskrivning " ; } } }
klass Objekt
{
public $price ;
offentligt $namn ;
offentlig $beskrivning ;
public function __construct ( $name , $price , $description = '' )
{
$this -> name = $name ;
$this -> pris = $pris ;
$this -> description = $description ;
}
}
$runner = ny klient ( ny ConcreteAggregate1 (), new ConcreteAggregate2 ());
$runner -> printAggregatesItems ();
}
PHP5 builder iterator exempel
PHP5 Builder Iterator källkod
/**
* Kompositörsmönster med extern iterator
* Iteratorn använder rekursion för att iterera genom elementträdet
*/
namespace compositeIterator {
/**
* Klienten använder AComponent-gränssnittet för att arbeta med objekt.
* AComponent-gränssnittet definierar gränssnittet för alla komponenter: både kombinationer och bladnoder.
* AComponent kan implementera standardbeteende för add() remove() getChild() och andra operationer
*/
abstrakt klass AComponent
{
public $customPropertyName ;
public $customPropertyDescription ;
/**
* @param AComponent $component
*/
public function add ( $component )
{
throw new \Exception ( "Ostödd operation" );
}
/**
* @param AComponent $component
*/
public function remove ( $component )
{
throw new \Exception ( "Ostödd operation" );
}
/**
* @param int $int
*/
offentlig funktion getChild ( $int )
{
throw new \Exception ( "Ostödd operation" );
}
/**
* @return IPhpLikeIterator
*/
abstrakt funktion createIterator ();
public function operation1 ()
{
throw new \Exception ( "Operation som inte stöds" );
}
}
/**
* Leaf ärver add() remove() getChild(-metoderna, vilket kanske inte är meningsfullt för en lövnod.
* Även om en lövnod kan betraktas som en nod med noll underordnade
*
* Leaf definierar beteendet hos elementen i en kombination. För att göra detta implementerar den operationerna som stöds av Composite-gränssnittet
*/
class Leaf utökar AComponent
{
public function __construct ( $name , $description = '' )
{
$this -> customPropertyName = $name ;
$this -> customPropertyDescription = $beskrivning ;
}
offentlig funktion createIterator ()
{
returnera ny NullIterator ();
}
public function operation1 ()
{
echo ( " \n Jag är leaf { $this -> customPropertyName } , jag vill inte göra operation 1. { $this -> customPropertyDescription } " );
}
}
class NullIterator implementerar IPhpLikeIterator
{
public function valid ()
{
return ( false );
}
public function next ()
{
return ( false );
}
public function current ()
{
return ( null );
}
public function remove ()
{
throw new \CException ( 'operation som inte stöds' );
}
}
/**
* Det sammansatta gränssnittet definierar beteendet hos komponenter som har barn och tillhandahåller lagring åt dem.
*
* The Composite implementerar också Leaf-relaterade operationer. Vissa av dem kan inte undgå att vara vettiga för kombinationer; i sådana fall görs ett undantag.
*/
class Composite utökar AComponent
{
privat $_iterator = null ;
/**
* @var \ArrayObject AComponent[] $komponenter för att lagra barn av typen AComponent
*/
public $components = null ;
offentlig funktion __construct ( $name , $description = '' )
{
$this -> customPropertyName = $name ;
$this -> customPropertyDescription = $description ;
}
/**
* @param AComponent $component
*/
public function add ( $component )
{
if ( is_null ( $this -> komponenter )) {
$this -> komponenter = new \ArrayObject ;
}
$this -> komponenter -> append ( $component );
}
public function remove ( $component )
{
foreach ( $this -> komponenter som $i => $c ) {
if ( $c === $component ) {
unset ( $this -> komponenter [ $i ]);
}
}
}
public function getChild ( $int )
{
return ( $this -> komponenter [ $int ]);
}
public function operation1 ()
{
echo " \n\n $this->customPropertyName $this->customPropertyDescription " ; echo " \n ----------------------------------------" ;
$iterator = $this -> komponenter -> getIterator ();
while ( $iterator -> giltig ()) {
$component = $iterator -> aktuell ();
$component -> operation1 ();
$iterator -> nästa ();
}
}
/**
* @return CompositeIterator
*/
public function createIterator ()
{
if ( is_null ( $this -> _iterator )) {
$this -> _iterator = new CompositeIterator ( $this -> komponenter -> getIterator ());
}
return ( $this -> _iterator );
}
}
/**
* Rekursiv sammansatt Iterator
*/
klass CompositeIterator implementerar IPhpLikeIterator
{
public $stack = array ();
/**
* @param \ArrayIterator $componentsIterator
*/
offentlig funktion __construct ( $componentsIterator )
{
//$this->stack= new \ArrayObject;
$this -> stack [] = $componentsIterator ;
}
public function remove ()
{
throw new \CException ( 'operation som inte stöds' );
}
public function valid ()
{
if ( tom ( $this -> stack )) {
return ( false );
} else {
/** @var $componentsIterator \ArrayIterator */
// få det första elementet
$componentsIterator = array_shift ( array_values ( $this -> stack ));
if ( $componentsIterator -> giltig ()) {
return ( true );
} else {
array_shift ( $this -> stack );
return ( $this -> giltig ());
}
}
}
public function next ()
{
/** @var $componentsIterator \ArrayIterator */
$componentsIterator = aktuell ( $this -> stack );
$component = $componentsIterator -> aktuell ();
if ( $component instans av Composite ) {
array_push ( $this -> stack , $component -> createIterator ());
}
$componentsIterator -> nästa ();
//retur($komponent);
}
public function current ()
{
if ( $this -> valid ()) {
/** @var $componentsIterator \ArrayIterator */
// få det första elementet
$componentsIterator = array_shift ( array_values ( $this -> stack )) ;
return ( $componentsIterator -> aktuell ());
} else {
return ( null );
}
}
}
/**
* Iterator-gränssnittet måste implementeras av alla iteratorer.
* Detta gränssnitt är en del av standardgränssnittet för php iterator.
* En viss Iterator är ansvarig för att hantera den aktuella iterationspositionen i en viss samling.
*/
interface IPhpLikeIterator
{
/**
* @abstract
* @return boolean är det aktuella elementet
*/
public function valid ();
/**
* @abstract
* @return blandad flytta markören vidare
*/
offentlig funktion nästa ();
/**
* @abstract
* @return mixed få det aktuella elementet
*/
public function current ();
/**
* ta bort det aktuella elementet i samlingen
* @abstract
* @return void
*/
public function remove ();
}
class Client
{
/**
* @varAComponent
*/
public $topItem ;
offentlig funktion __construct ( $topItem )
{
$this -> topItem = $topItem ;
}
public function printOperation1 ()
{
$this -> topItem -> operation1 ();
}
public function printOperation2 ()
{
echo " \n\n\n " ;
$iterator = $this -> topItem -> createIterator ();
while ( $iterator -> giltig ()) {
/** @var $component AComponent */
$component = $iterator -> aktuell ();
if ( strstr ( $component -> customPropertyName , 'leaf1' )) {
echo ( " \n Jag är klient, jag hittade leaf { $component -> customPropertyName } , jag lämnar det här (för min 'första-) leafs tesamling ). { $component -> customPropertyDescription } " );
}
$iterator -> nästa ();
}
}
}
class Test
{
public static function go ()
{
$a = new Composite ( "c1" );
$b = ny sammansatt ( "c2" );
$c = ny sammansatt ( "c3" );
$topItem = ny sammansatt ( "top item" );
$topItem -> lägg till ( $a );
$topItem -> lägg till ( $b );
$topItem -> lägg till ( $c );
$a -> add ( nytt blad ( "c1-blad1" ));
$a -> add ( nytt blad ( "c1-blad2" ));
$b -> add ( nytt blad ( "c2-blad1" ));
$b -> add ( nytt blad ( "c2-blad2" ));
$b -> add ( nytt blad ( "c2-blad3" ));
$c -> add ( nytt blad ( "c3-blad1" ));
$c -> add ( nytt blad ( "c3-blad2" ));
$client = ny klient ( $topItem );
$client -> printOperation1 ();
$client -> printOperation2 ();
}
}
test :: gå ();
}
Python
Källkod i
Python
från abc import ABCMeta , abstraktmetod
class Iterator ( metaclass = ABCMeta ):
"""
Abstrakt iterator
"""
_error = Ingen # klassen för felet som kastas om samlingen är utanför gränserna
def __init__ ( själv , samling , markör ):
"""
Konstruktör.
:param collection: samlingen som ska passeras av iteratorn :param cursor: markörens initiala position i samlingen (nyckel)
"""
self ._collection = collection self ._cursor = cursor
@abstractmethod
def current ( self ):
"""
Returnera det aktuella elementet som pekas på av iteratorn
"""
pass
@abstractmethod
def next ( self ):
"""
Flytta markören till nästa element i samlingen och returnera det
"""
pass
@abstractmethod
def has_next ( self ):
"""
Kontrollera om nästa element i samlingen finns
"""
pass
@abstractmethod
def remove ( self ):
"""
Ta bort det aktuella elementet i samlingen som markören
"""
pekar på
def _raise_key_exception ( self ):
"""
Höj ett ogiltigt index som finns i markören
"""
raise self . _error ( 'Samling av klass {} har inte nyckeln " {} "' . format (
self . __class__ . __name__ , self . _cursor ))
class ListIterator ( Iterator ):
"""
En iterator som itererar över en normal lista
"""
_error = IndexError
def __init__ ( själv , samling : lista ):
super ( ) . __init__ ( samling , 0 )
def aktuell ( själv ):
om själv . _cursor < len ( self . _collection ):
returnera själv . _samling [ själv . _cursor ]
själv . _raise_key_exception ()
def nästa ( själv ):
om len ( själv . _samling ) >= själv . _cursor + 1 :
själv . _cursor += 1
returnerar själv . _samling [ själv . _cursor ]
själv . _raise_key_exception ()
def has_next ( self ):
returnera len ( self . _collection ) >= self . _cursor + 1
def remove ( self ):
om 0 <= self . _cursor < len ( själv . _samling ):
själv . _samling . ta bort ( själv . _samling [ själv . _markör ])
annat :
själv . _raise_key_exception ()
class DictIterator ( Iterator ):
"""
Dictionary iterator - på grund av att ordböcker i Python är implementerade
som hashtabeller, kan genomgångsordningen ändras under olika körningar
"""
_error = KeyError
def __init__ ( själv , samling : dict ):
super ( ) . __init__ ( samling , nästa ( iter ( samling )))
själv . _keys = lista ( själv . _samling . nycklar ())
själv . _nycklar . pop ( 0 )
def aktuell ( själv ):
om själv . _markör i jaget . _kollektion :
returnera själv . _samling [ själv . _cursor ]
själv . _raise_key_exception ()
def nästa ( själv ):
if len ( self . _keys ):
själv . _cursor = själv . _nycklar . pop ( 0 )
returnera själv . _samling [ själv . _cursor ]
annat :
själv . _raise_key_exception ()
def has_next ( self ):
returnera len ( self . _keys ) > 0
def ta bort ( själv ):
om själv . _markör i jaget . _samling :
del själv . _samling [ själv . _cursor ]
try :
self . nästa ()
utom själv . _error :
raise KeyError ( 'Samling av typ {} är tom' . format ( self . __class__ . __name__ ))
else :
self . _raise_key_exception ()
klasssamling ( metaklass = ABCMeta ) : """ Abstrakt samling """
@abstractmethod
def iterator ( själv ):
godkänt
class ListCollection ( Collection ):
"""
En omslagssamling för en normal lista
"""
def __init__ ( själv , samling : lista ):
själv . _samling = samling
def iterator ( self ) :
returnera ListIterator ( self . _collection )
klass DictCollection ( Samling ):
""" Omslagssamling
för ordbok
"""
def __init__ ( själv , samling : dikt ):
själv . _samling = samling
def iterator ( själv ) :
returnera DictIterator ( self . _collection )
def test ( title = str , collection = Collection ):
print ( " \n {} \n " . format ( title ))
iterator = samling . iterator ()
print ( iterator . aktuell ())
iterator . nästa ()
print ( iterator . nästa ())
iterator . ta bort ()
print ( iterator . aktuell ())
print ( iterator . has_next ())
print ()
if __name__ == '__main__' :
print ( 'OUTPUT:' )
test ( 'List testing' , ListCollection ([ 1 , 2 , 3 , 4 , 5 ]))
test ( 'Dictionary testing' , DictCollection ({ 'a') : 1 , 'b' : 2 , 'c' : 3 , 'f' : 8 }))
'''
UTGÅNG:
Lista tester
1
3
4
Sant
Ordbokstestning
1
3
2
Falskt
'''
Rost
Rost exempel
#[derive(Debug, Clone, Copy)]
pub struct ExampleRange
{
börja :
i64 ,
ström :
i64 ,
slut :
i64 ,
}
impl Exempelintervall
{
pub fn new ( början :
i64 , slut :
i64 ) ->
Själv
{
Exempelintervall
{
börja ,
nuvarande :
börja ,
slut ,
}
}
pub fn iter ( & self ) ->
Exempelintervall
{
* själv
}
}
använd std ::
fmt ;
impl fmt ::
Display för ExampleRange
{
fn fmt ( & self , f :
& mut fmt ::
Formatterare <' _ > ) ->
fmt ::
Resultat
{
skriva! ( f , " {} " , själv . aktuell )
}
}
impl Iterator för ExampleRange
{
typeItem = i64 ; _
fn nästa ( & mut self ) ->
Alternativ < Själv ::
Objekt >
{
om jag själv . nuvarande < själv . slutet
{
( Vissa ( själv . ström ), själv . ström += 1 ). 0
}
annan
{
Ingen
}
}
fn last ( mut self ) ->
Alternativ < Self ::
Item >
{
om jag själv . nuvarande > själv . Börja
{
( self . current -= 1 , Some ( self . current )). ett
}
annan
{
Ingen
}
}
}
fn main ()
{
let it = ExampleRange ::
new ( 0 , 6 );
för föremål i den
{
println! ( "{}" , objekt );
}
}
'''
UTGÅNG :
0
ett
2
3
fyra
5
'''