Iterator (från engelska iterator - enumerator) är ett gränssnitt som ger tillgång till elementen i en samling ( array eller container ) och navigering genom dem [1] . Iteratorer kan ha olika vanliga namn på olika system. När det gäller databashanteringssystem kallas iteratorer för markörer . I det enklaste fallet är en iterator på lågnivåspråk en pekare .
Användningen av iteratorer i generisk programmering låter dig implementera universella algoritmer för att arbeta med behållare [1] .
Huvudsyftet med iteratorer är att tillåta användaren att komma åt vilket element som helst i behållaren samtidigt som den döljer behållarens interna struktur för användaren. Detta gör att behållaren kan lagra element på vilket sätt som helst så länge det är acceptabelt för användaren att behandla det som en enkel sekvens eller lista . Utformningen av en iteratorklass är vanligtvis nära relaterad till motsvarande behållarklass. Vanligtvis tillhandahåller en behållare metoder för att skapa iteratorer.
En iterator liknar en pekare i sina grundläggande operationer: den pekar på ett enda element i en samling objekt (ger åtkomst till elementet ), och den innehåller funktioner för att flytta till ett annat element i listan (nästa eller föregående). En behållare som implementerar stöd för iteratorer måste tillhandahålla det första elementet i listan, samt möjligheten att kontrollera om alla element i behållaren har itererats (om iteratorn är finit). Beroende på språket och syftet som används kan iteratorer stödja ytterligare operationer eller definiera olika beteenden.
Ibland kallas en loopräknare för en "loopiterator". Men loopräknaren tillhandahåller bara elementiteration, inte elementåtkomst.
Procedurprogrammeringsspråk använder i stor utsträckning loop count - baserad indexering för att iterera över alla element i en sekvens (som en array ). Även om indexering kan användas tillsammans med vissa objektorienterade behållare, finns det fördelar med att använda iteratorer:
Möjligheten att modifiera en behållare samtidigt som den itererar dess element har blivit väsentlig i modern objektorienterad programmering , där relationerna mellan objekt och konsekvenserna av att utföra operationer kanske inte är alltför uppenbara. Att använda en iterator blir av med den här typen av problem.
Vissa objektorienterade språk, som Perl , Python , C# , Ruby och nyare versioner av Java och Delphi , har speciella operatorer för att iterera containerelement utan att använda iteratorer uttryckligen. En riktig iterator kan faktiskt existera, men om den existerar, deklareras den inte uttryckligen i källkoden.
Iteration genom elementen i en samling med en implicit iterator görs med " foreach "-satsen (eller motsvarande), som i följande Python-kod:
för värde i listan : skriv ut värdeI andra fall kan iteratorer skapas av själva samlingen av objekt, som i detta Ruby-exempel:
lista . varje gör | värde | sätter värdet slutListaktiverade språk kan också använda implicita iteratorer när du skapar den resulterande listan, som Python:
MaleNames = [ Person . Namn på person i listan om person . IsMale ]Ibland är implicititeten bara partiell. Till exempel innehåller standardmallbiblioteket för C ++-språket några funktionsmallar, till exempel, for_each()som utför en sådan implicit iteration. Men de kräver fortfarande en explicit iterator som parameter. Men efter initialisering sker efterföljande iteration implicit utan att använda någon iterator. Sedan C++11- standarden stöder språket även implicit loop-iteration for[2] .
Ett sätt att implementera iteratorer är att använda samprocedurer , som kan returnera kontroll (och beräknade resultat) flera gånger, komma ihåg deras tillstånd och returpunkt från föregående anrop. På vissa språk kan samprocedurer representeras av en speciell typ av funktion som kallas en generator . En generator är en funktion som kommer ihåg var den tidigare returen var, och nästa gång den anropas återupptar den arbetet från den avbrutna platsen.
De flesta iteratorer beskrivs naturligt i termer av generatorer, och eftersom generatorer behåller sitt nuvarande tillstånd mellan anrop, är de väl lämpade för komplexa iteratorer vars implementering kräver komplexa datastrukturer för att komma ihåg den aktuella positionen i samlingen, såsom trädgenomgång .
Ett exempel på en generator som returnerar Fibonacci-tal med en yieldPython - operator :
def fibonacci (): a , b = 0 , 1 medan True : ge a # returnera a, + kom ihåg var du ska starta om nästa anrop a , b = b , a + b för nummer i fibonacci (): # Använd generatorn som ett iteratorutskriftsnummerDen vanliga hänvisningen till de variabler som utgör serien utförs av deras antal. I detta fall beräknas adressen för den önskade variabeln som: "adress för den första variabeln" + "storlek på variabeln" x "uppsättningsnummer". Med sekventiell tillgång till sådana variabler kan du få en betydande prestandavinst om du beräknar adressen till nästa variabel genom adressen till den föregående. Detta är vad reglaget är till för. Typen av variabler som utgör serien, som kommer att nås sekventiellt, kallas skjutreglagets referenstyp, och antalet variabler i serien, med vilka skjutreglaget kommer att flyttas efter varje sådan åtkomst, kallas skjutreglagets steg . Reglersteget ges som en heltalskonstant. Om skjutreglagets steg inte anges när vyn deklareras, anses steget vara lika med 1.
C++-språket använder i stor utsträckning iteratorer i STL , som stöder flera olika typer av iteratorer, inklusive 'enkelriktade iteratorer', 'dubbelriktade iteratorer' och 'slumpåtkomstiteratorer'. Alla standardmallarna för behållartyp implementerar en varierad men konsekvent uppsättning iteratortyper. Syntaxen för standarditeratorer är gjord på samma sätt som vanliga C- språkpekare , där operatorerna och används för att specificera elementet som iteratorn pekar på, och aritmetiska pekoperatorer som , används för att flytta iteratorn till nästa element. *->++
Iteratorer används vanligtvis i par, varav en används för att indikera den aktuella iterationen och den andra används för att markera slutet på samlingen. Iteratorer skapas med lämpliga containerklasser, med standardmetoder begin()som end(). Funktionen begin()returnerar en pekare till det första elementet och returnerar en pekare till ett end() imaginärt icke-existerande element efter det sista.
När en iterator går förbi det sista elementet är detta per definition lika med iteratorns speciella slutvärde. Följande exempel visar en typisk användning av en iterator:
std :: lista < int > C ; // Vilken standard STL-behållare som helst kan användas istället för std::list för ( std :: list < int >:: iterator it = C . begin (), end = C . end (); it != end ; ++ it ) { //för föränderlig iterator * it = 8 ; // elementet som iteratorn pekar på kan ändras } for ( std :: list < int >:: const_iterator it = C . begin (), end = C . end (); it != end ; ++ it ) { //om du inte behöver ändra element std :: cout << * it << std :: endl ; }Det finns många varianter av iteratorer som skiljer sig åt i sitt beteende: enkelriktade, omvända (omvända) och dubbelriktade iteratorer; ingångs- och utdataiteratorer; konst iteratorer (skyddar behållaren eller dess element från att modifieras). Men inte alla behållartyper stöder någon av dessa iteratortyper. Användare kan skapa sina egna iteratortyper genom att definiera underklasser baserat på standarden std::iterator.
Säkerheten med att använda en iterator definieras separat för de olika typerna av standardbehållare; i vissa fall tillåter en iterator behållarändringar under iteration.
Implicit iteration stöds också delvis av C++ genom standardfunktionsmallar som std::for_each()[1] och std::accumulate()[2] . När de används måste de initieras med befintliga iteratorer, vanligtvis start och slut , som definierar omfattningen av iterationen, men det får inte finnas någon explicit definition av iteratorer för ytterligare iteration. Följande exempel visar användningen av for_each.
ContainerType < ItemType > C ; // Alla standardobjektbehållarestyper ItemType void ProcessItem ( const ItemType & I ) // En funktion som bearbetar varje objekt i samlingen { std :: cout << I << std :: endl ; } std :: for_each ( C.begin ( ) , C.end ( ), ProcessItem ) ; // View LoopNackdelen med denna metod är oförmågan att deklarera slingans kropp inuti, vilket kräver någonstans att deklarera en funktionspekare eller funktor och skicka den som ett argument. Detta kan delvis kompenseras genom att använda ett bibliotek som Boost och använda en lambda-funktion för att implicit skapa funktorer med en liknande infixoperatorsyntax. Endast med detta i åtanke måste ett sådant bibliotek utföra vissa operationer på specificerade sätt.
Från och med C++11 -standarden kan iteratorer användas implicit i en loop for, vilket ger funktionen att iterera över alla element i en behållare:
#inkludera <vektor> #include <iostream> int main ( void ) { std :: vektor < int > v ; v . push_back ( 1 ); v . push_back ( 2 ); v . push_back ( 3 ); for ( auto e : v ) { std :: cout << e << std :: endl ; // Skriv ut värdet för varje element } returnera 0 ; }Introducerat i JDK 1.2-versionen av Java -språket, ger gränssnittet java.util.Iterator iteration av containerklasser. Varje Iteratorimplementerar next()och hasNext()stöder valfritt en remove(). Iteratorer skapas av motsvarande containerklasser, vanligtvis av iterator().
Metoden next()flyttar iteratorn till nästa värde och returnerar det angivna värdet till iteratorn. När den ursprungligen skapas pekar en iterator på ett speciellt värde före det första elementet, så det första elementet kan bara hämtas efter det första anropet till next(). Testmetoden används för att avgöra när alla element i behållaren har itererats hasNext(). Följande exempel visar den enkla användningen av iteratorer:
Iterator iter = lista . iterator (); //Iterator<MyType> iter = list.iterator(); i J2SE 5.0 while ( iter . hasNext ()) System . ut . println ( iter.next ( ) );För en samling typer som stöder detta tar iteratormetoden remove()bort det senast "besökta" elementet från behållaren. Nästan alla andra typer av containermodifiering under iteration är osäkra.
Den java.util.Listhar också java.util.ListIteratorett liknande API, men tillåter iteration framåt och bakåt, vilket ger en bestämning av det aktuella indexet i listan och flyttar till ett element genom dess position.
Med lanseringen av J2SE 5.0 introducerades ett gränssnitt för Iterableatt stödja förbättrad foreach för iterering över samlingar och arrayer. definierar en metod som returnerar . Med hjälp av en förbättrad loop kan föregående exempel skrivas om som forIterableiterator()Iteratorfor
för ( MyType obj : list ) System . ut . print ( obj );Iteratorer i .NET Framework kallas "uppräknare" och representeras av IEnumerator. IEnumeratorimplementerar en metod MoveNext()som flyttar till nästa element och indikerar om slutet av samlingen har nåtts; egenskapen Currentanvänds för att få värdet på det angivna elementet; den valfria metoden Reset()återställer räknaren till sin ursprungliga position. Enumeratorn pekar initialt på ett speciellt värde före det första elementet, så anropet MoveNext()är nödvändigt för att starta iterationen.
Uppräknare skickas vanligtvis genom att anropa en metod på ett GetEnumerator()objekt som implementerar IEnumerable. Behållarklasser implementerar vanligtvis detta gränssnitt. C# foreach - uttrycket kan dock fungera på vilket objekt som helst som stöder en sådan metod, även om det inte implementerar . Båda gränssnitten har utökats i generiska versioner av .NET 2.0 . IEnumerable
Följande exempel visar en enkel användning av iteratorer i C# 2.0:
// 'explicit' version av IEnumerator < MyType > iter = lista . GetEnumerator (); while ( iter . MoveNext ()) Konsol . WriteLine ( iter . Current ); // 'implicit' version av foreach ( MyType- värde i listan ) Console . WriteLine ( värde );C# 2.0 stöder också generatorer : en metod som deklareras som returbar IEnumerator(eller IEnumerable) men som använder uttrycket " " (flexibel retur) yield returnför att producera en sekvens av element istället för att returnera en objektenhet kommer att omvandlas till en ny klass av kompilatorn som implementerar motsvarande gränssnitt.
Iteratorer i Python är en integrerad del av språket och används i många fall implicit i ett uttryck for( lookup loop ), i listmanipulation och i generatoruttryck . Alla standardlooptyper som ingår i Python-språket stöder iteration, liksom många av klasserna som ingår i . Följande exempel visar typisk implicit iteration med en loop:
för värde i följd : print ( värde )Python-ordböcker (ett slags associativ array ) kan också itereras direkt och returnera ordboksnycklar. Eller så kan ordbokens objektmetod upprepas när den slutför den associerade nyckeln, och värdet på det paret är en tupel:
för nyckel i ordbok : värde = ordbok [ nyckel ] skriv ut ( nyckel , värde ) för nyckel , värde i ordbok . objekt (): print ( nyckel , värde )Men iteratorer kan användas och specificeras explicit. För alla uppräknade typer av loop eller klass skapar den inbyggda funktionen iter()en iterator. En iterator implementerar en metod next()som returnerar nästa element i behållaren. När det inte finns fler element kvar, uppstår ett fel StopIteration. Följande exempel visar lämplig loop-iteration med explicita iteratorer:
it = iter ( sekvens ) medan True : try : value = it . nästa () utom StopIteration : break print ( värde )I följande exempel, för Python 2.4 (och senare), är iteratorn själva filobjektet f, som kommer åt filen som en sekvens av strängar:
f = öppen ( "README" ) # öppna en fil utskrift ( f . nästa ()) # nästa värde i iteratorn är nästa rad i filen utskrift ( summa ( len ( rad ) för rad i f )) # den summan av längden på alla andra rader i filenAlla anpassade klasser kan stödja standard iteration (explicit eller implicit) när man definierar en metod __iter__()som skapar en iterator. Iteratorn behöver då en metoddefinition next()som returnerar nästa element. Det är värt att förstå skillnaden mellan ett itererbart objekt (ett objekt från vilket en funktion iter()returnerar en iterator) och en iterator (ett objekt som har en metod __next__).
Python-språkgeneratorerna implementerar protokollet för denna iteration.
PHP 4 introducerade look-loop-konstruktionerna i Perl och några andra. Detta gör att du kan bläddra i arrayer på ett enkelt sätt. I PHP 4 fungerar uppslagsslingan endast med arrayer och ger ett felmeddelande när man försöker använda den med variabler av olika typer eller oinitierade variabler.
I PHP5 tillåter uppslagsslingan objekt att itereras genom alla offentliga medlemmar.
Det finns två syntaxer för detta, den andra är en liten men mycket användbar förlängning av den första.
Exempel A
<?php foreach ( array_expression som $value ) echo " $value ; \n " ; ?>Exempel B
<?php foreach ( array_expression som $key => $value ) echo "( $key ) $value ; \n " ; ?>Exempel A itererar över arrayen som skickas till array_expression. Varje gång genom slingan tilldelas värdet för det aktuella elementet variabeln $valueoch den interna arraypekaren flyttas till nästa element (så vid nästa iteration av slingan kommer du att "se" nästa element).
Exempel B visar liknande funktionalitet som visas ovan. Men kompletterar det med det faktum att nyckelvärdet för det aktuella elementet (i detta fall array_expression) kommer att tilldelas variabeln $keyvid varje pass av slingan.
PHP låter dig ändra innehållet i en array under iteration, för vilken det räcker att specificera att värdet på $value kommer att erhållas som en referens (i PHP-termer), det vill säga som &$value.
<?php $arr = array ( 1 , 2 , 3 , 4 , 5 ); foreach ( $arr som & $value ) $value ++ ; // öka varje värde med ett // nu innehåller $arr värdena: 2,3,4,5,6 ?>I PHP 5 är gränssnittet Iteratorfördefinierat och objekt kan modifieras för att styra iteration.
<?php class MyIterator implementerar Iterator { private $var = array (); offentlig funktion __construct ( $array ) { if ( is_array ( $array )) { $this -> var = $array ; } } offentlig funktion spola tillbaka () { echo " spola tillbaka \n " ; återställ ( $this -> var ); } public function current () { $var = aktuell ( $this -> var ); echo "current: $var\n " ; returnera $var ; } offentlig funktionstangent () { $var = nyckel ( $this - > var ); echo "nyckel: $var\n " ; returnera $var ; } public function next () { $var = nästa ( $this -> var ); echo "nästa: $var\n " ; returnera $var ; } offentlig funktion giltig () { $var = $this -> aktuell () !== false ; echo "korrekt: { $var } \n " ; returnera $var ; } } ?>Dessa metoder används fullt ut under hela webbläsarcykeln foreach($obj AS $key=>$value). Iteratormetoder exekveras i följande ordning:
1.rewind() ("övergång") 2. medan giltig() { 2.1 aktuell() i $värde 2.3 nyckel() i $nyckel 2.4 nästa() }Det föregående exemplet kan förenklas avsevärt genom att använda IteratorAggregate-gränssnittet, som tvingar utvecklaren att implementera bara en getIterator()-metod.
<?php class MyIterator implementerar IteratorAggregate { private $var = array (); public function __construct ( array $array ) { // typkontroll utförs av tolken: __construct(array $array) $this -> var = $array ; } offentlig funktion getIterator () { returnera ny ArrayIterator ( $this -> var ); } } ?>Iteratorer i XL -språket är en generalisering av generatorer och iteratorer.
import IO = XL . ui . TRÖSTA iterator IntegerIterator ( var ut Räknare : heltal ; Låg , Hög : heltal ) skriven Räknare i Låg .. Hög är Räknare := Låg medan Räknare <= Hög loop avkastning Räknare += 1 // Observera att det inte finns något behov av en separat deklaration av I, eftersom 'var out' deklareras i en iterator // Den implicita deklarationen av I som ett heltal förekommer nedan för I in 1 .. 5 loop IO . Skriv Ln " I = " , IIteratorer i ActionScript 3 är inbyggda i själva språket och stöds av foreach och for...in -satserna . Ur språksynpunkt är arrayer och instanser av dynamiska klasser iteratorer:
var obj : Objekt = { prop1 : "a" , prop2 : "b" , prop3 : "c" }; // nästa loop kommer att "köra" genom alla nycklar (egenskapsnamn) för obj-objektet för ( var name : String in obj ) trace ( name ); // nästa loop kommer att "köra" genom alla egenskapsvärdena för obj foreach ( var val :* in obj ) trace ( val ); }Haskells standardbibliotek definierar typklassen Traversable [3] [4] :
klass ( Functor t , Foldable t ) => Traverserbar t där travers :: Applikativ f => ( a -> f b ) -> t a -> f ( t b )Här är t någon polymorf typ (kanske en behållare eller en samling ), f är en "uppseendeväckande" typ (till exempel I/O, explicit tillståndsändring eller möjligheten till ett fel). "traverse" är en specialisering av functor och fold , som uttrycks i klassens sammanhang (header).
Till exempel, för ett binärt träd , kan "traverse"-metoden definieras enligt följande:
dataträd a = tomt | _ blad a | Nod ( Träd a ) a ( Träd a ) instans Traverserbar Trädtravers f Tom = ren Tom travers f ( Blad x ) = Blad <$> f x travers f ( Nod l k r ) = Nod <$> travers f l <*> f k < * > travers f rAnvändningsexempel:
-- | Skriv ut innehållet i varje trädnod. printTree tree = traversera utskriftsträd _ -- | Denna funktion tar en binär funktion g och ett träd, korsar trädet, applicerar g på varje nod (det andra argumentet -- begärs från standardinmatning), och returnerar det modifierade trädet. combineWithStdin :: ( Läs c ) => ( a -> c -> b ) -> Träd a -> IO ( Träd b ) combineWithStdin g = traversera kombinera där kombinera x = g x <$> readLn {- Exempel: träd = Nod (Nod (Löv 3) 6 (Löv 9)) 10 (Nod (Löv 9) 0 Tom) $ combineWithStdin (+) träd > 10 > 20 > 30 > 40 > 50 > 60 $ Nod (Nod (Löv 13) 26 (Löv 39)) 50 (Nod (Löv 59) 60 Tom) -}Baserat på metoderna i typklassen "Traversable" kan du bygga dina egna funktioner med en specifik traverseringsstrategi.
Sedan version 6.12 av GHC- kompilatorn har tilläggen "-XDeriveFunctor", "-XDeriveFoldable" och "-XDeriveTraversable" introducerats för att automatiskt skapa instanser av lämpliga typklasser. Exempel:
dataträd a = tomt | _ blad a | Nod ( Träd a ) en ( Träd a ) härledande ( Funktion , Foldable , Traversable )