Iterator (din engleză iterator - enumerator) este o interfață care oferă acces la elementele unei colecții ( array sau container ) și navigarea prin acestea [1] . Iteratorii pot avea nume comune diferite pe sisteme diferite. În ceea ce privește sistemele de gestionare a bazelor de date, iteratorii sunt numiți cursori . În cel mai simplu caz, un iterator în limbaje de nivel scăzut este un pointer .
Utilizarea iteratoarelor în programarea generică vă permite să implementați algoritmi universali pentru lucrul cu containere [1] .
Scopul principal al iteratoarelor este de a permite utilizatorului să acceseze orice element al containerului în timp ce ascunde structura internă a containerului de utilizator. Acest lucru permite containerului să stocheze elemente în orice mod atâta timp cât este acceptabil ca utilizatorul să-l trateze ca o simplă secvență sau listă . Proiectarea unei clase iteratoare este de obicei strâns legată de clasa containerului corespunzătoare. De obicei, un container oferă metode pentru crearea iteratoarelor.
Un iterator este similar cu un pointer în operațiunile sale de bază: indică către un singur element dintr-o colecție de obiecte (oferă acces la elementul ) și conține funcții pentru deplasarea la un alt element din listă (următorul sau anterior). Un container care implementează suport pentru iteratoare trebuie să ofere primul element al listei, precum și capacitatea de a verifica dacă toate elementele containerului au fost iterate (dacă iteratorul este finit). În funcție de limbajul și scopul utilizat, iteratorii pot accepta operații suplimentare sau pot defini comportamente diferite.
Uneori , un contor de bucle este numit „iterator de buclă”. Cu toate acestea, contorul buclei oferă doar iterația elementului, nu accesul la element.
Limbajele de programare procedurale folosesc pe scară largă indexarea bazată pe numărarea buclelor pentru a repeta peste toate elementele unei secvențe (cum ar fi o matrice ). Deși indexarea poate fi utilizată împreună cu unele containere orientate pe obiecte, există avantaje în utilizarea iteratoarelor:
Capacitatea de a modifica un container în timp ce se repetă elementele sale a devenit esențială în programarea modernă orientată pe obiecte , unde relațiile dintre obiecte și consecințele efectuării operațiilor pot să nu fie prea evidente. Utilizarea unui iterator scapă de astfel de probleme.
Unele limbaje orientate pe obiecte, cum ar fi Perl , Python , C# , Ruby și versiunile recente de Java și Delphi , au operatori speciali pentru iterarea elementelor containerului fără a utiliza iteratoarele în mod explicit. Un iterator real poate exista de fapt, dar dacă există, nu este declarat în mod explicit în codul sursă.
Iterarea prin elementele unei colecții folosind un iterator implicit se face folosind instrucțiunea „ foreach ” (sau echivalent), ca în următorul cod Python:
pentru Value in List : print ValueÎn alte cazuri, iteratoarele pot fi create de colecția de obiecte în sine, ca în acest exemplu Ruby:
lista . fiecare face | valoare | pune capăt valoriiLimbile activate pentru listă pot folosi, de asemenea, iteratoare implicite atunci când creează lista rezultată, cum ar fi Python:
MaleNames = [ Persoană . Nume pentru Person în RosterList dacă Person . IsMale ]Uneori, implicititatea este doar parțială. De exemplu, biblioteca standard de șabloane a limbajului C++ conține unele șabloane de funcție, de exemplu, for_each()care efectuează o astfel de iterație implicită. Cu toate acestea, ele necesită încă un iterator explicit ca parametru. Dar după inițializare, iterația ulterioară are loc implicit fără a utiliza niciun iterator. Deoarece standardul C++11 , limbajul acceptă și iterația implicită a buclei for[2] .
O modalitate de a implementa iteratoarele este utilizarea coprocedurilor , care pot returna controlul (și rezultatele calculate) de mai multe ori, amintindu-și starea și punctul de întoarcere de la apelul anterior. În unele limbi, co-procedurile pot fi reprezentate printr-un tip special de funcție numită generator . Un generator este o funcție care își amintește unde a fost returnarea anterioară, iar data viitoare când este apelată, reia lucrul din locul întrerupt.
Majoritatea iteratorilor sunt descriși în mod natural în termeni de generatori și, deoarece generatorii își păstrează starea curentă între invocări, ei sunt potriviti pentru iteratorii complecși a căror implementare necesită structuri complexe de date pentru a-și aminti poziția curentă în colecție, cum ar fi traversarea arborilor .
Un exemplu de generator care returnează numere Fibonacci folosind un operatoryield Python :
def fibonacci (): a , b = 0 , 1 în timp ce Adevărat : randament a # return a, + amintiți-vă de unde să reporniți apelul următor a , b = b , a + b pentru numărul în Fibonacci (): # Utilizați generatorul ca număr de tipărire iteratorReferirea obișnuită la variabilele care alcătuiesc seria se realizează prin numărul acestora. În acest caz, adresa variabilei cerute se calculează ca: „adresa primei variabile” + „dimensiunea variabilei” x „număr set”. Cu acces secvențial la astfel de variabile, puteți obține un câștig semnificativ de performanță dacă calculați adresa următoarei variabile prin adresa celei anterioare. Pentru asta este glisorul. Tipul de variabile care alcătuiesc seria, care vor fi accesate secvenţial, se numeşte tipul de referinţă al glisorului, iar numărul de variabile din serie, prin care glisorul se va deplasa după fiecare astfel de acces, se numeşte pas de glisor. . Pasul de glisare este dat ca o constantă întreagă. Dacă pasul glisorului nu este specificat la declararea vederii, atunci pasul este considerat egal cu 1.
Limbajul C++ folosește pe scară largă iteratoarele în STL , care acceptă mai multe tipuri diferite de iteratoare, inclusiv „iteratoare unidirecționale”, „iteratoare bidirecționale” și „iteratoare cu acces aleatoriu”. Toate șabloanele standard de tip container implementează un set variat, dar consistent de tipuri de iteratoare. Sintaxa iteratoarelor standard este similară cu indicatorii obișnuiți în limbajul C , unde operatorii și *sunt ->utilizați pentru a specifica elementul către care iteratorul se adresează și operatorii aritmetici pointer, cum ar fi ++, sunt utilizați pentru a muta iteratorul la următorul element.
Iteratoarele sunt de obicei folosite în perechi, dintre care unul este folosit pentru a indica iterația curentă, iar celălalt este folosit pentru a marca sfârșitul colecției. Iteratoarele sunt create folosind clasele de containere adecvate, folosind metode standard, cum ar begin()fi end(). Funcția begin()returnează un pointer către primul element și returnează un pointer către un end() element imaginar inexistent după ultimul.
Când un iterator trece de ultimul element, prin definiție, acesta este egal cu valoarea finală specială a iteratorului. Următorul exemplu demonstrează o utilizare tipică a unui iterator:
std :: list < int > C ; // Orice container STL standard poate fi folosit în locul std::list pentru ( std :: list < int >:: iterator it = C . begin (), end = C . end (); it != end ; ++ it ) { //pentru iteratorul mutabil * it = 8 ; // elementul indicat de iterator poate fi schimbat } for ( std :: list < int >:: const_iterator it = C . begin (), end = C . end (); it != end ; ++ it ) { //dacă nu trebuie să modificați elementele std :: cout << * it << std :: endl ; }Există multe varietăți de iteratoare care diferă în comportamentul lor: iteratoare unidirecționale, inverse (reverse) și bidirecționale; iteratoare de intrare și ieșire; const iteratoare (protejarea containerului sau a elementelor acestuia de a fi modificate). Cu toate acestea, nu orice tip de container acceptă oricare dintre aceste tipuri de iteratoare. Utilizatorii își pot crea propriile tipuri de iteratoare definind subclase pe baza standardului std::iterator.
Siguranța utilizării unui iterator este definită separat pentru diferitele tipuri de containere standard; în unele cazuri, un iterator permite modificări ale containerului în timpul iterației.
Iterația implicită este, de asemenea, parțial acceptată de C++ prin șabloane de funcții standard precum std::for_each()[1] și std::accumulate()[2] . Când sunt utilizate, acestea trebuie inițializate cu iteratorii existenți, de obicei începe și se termină, definind domeniul de aplicare al iterației, dar nu trebuie să existe o definiție explicită a iteratorilor pentru o iterație ulterioară. Următorul exemplu demonstrează utilizarea for_each.
ContainerType < ItemType > C ; // Orice tip de container standard de articol ItemType void ProcessItem ( const ItemType & I ) // O funcție care procesează fiecare articol din colecție { std :: cout << I << std :: endl ; } std :: for_each ( C.begin ( ) , C.end ( ), ProcessItem ) ; // Vizualizare buclăDezavantajul acestei metode este incapacitatea de a declara corpul buclei în interior, necesitând undeva declararea unui pointer de funcție sau functor și trecerea acestuia ca argument. Acest lucru poate fi parțial compensat prin utilizarea unei biblioteci precum Boost și folosind o funcție lambda pentru a crea implicit functori cu o sintaxă similară a operatorului infix. Doar având în vedere acest lucru, o astfel de bibliotecă trebuie să efectueze anumite operații în moduri specificate.
Începând cu standardul C++11 , iteratoarele pot fi utilizate implicit într-o buclă for, oferind funcționalitatea de a itera peste toate elementele unui container:
#include <vector> #include <iostream> int main ( void ) { std :: vector < int > v ; v . push_back ( 1 ); v . push_back ( 2 ); v . push_back ( 3 ); pentru ( auto e : v ) { std :: cout << e << std :: endl ; // Imprimă valoarea fiecărui element } returnează 0 ; }Introdusă în versiunea JDK 1.2 a limbajului Java , interfața java.util.Iterator oferă o iterație a claselor de containere. Fiecare Iteratorimplementează next()și hasNext()opțional acceptă un remove(). Iteratoarele sunt create de clasele de containere corespunzătoare, de obicei de către iterator().
Metoda next()avansează iteratorul la următoarea valoare și returnează valoarea specificată iteratorului. Când a fost creat inițial, un iterator indică o valoare specială înaintea primului element, astfel încât primul element poate fi preluat numai după primul apel la next(). Metoda de testare este utilizată pentru a determina când au fost repetate toate elementele din container hasNext(). Următorul exemplu demonstrează utilizarea simplă a iteratorilor:
Iterator iter = listă . iterator (); //Iterator<MyType> iter = list.iterator(); în J2SE 5.0 while ( iter . hasNext ()) System . afară . println ( iter.next ( ) );Pentru o colecție de tipuri care acceptă acest lucru, metoda iteratorului remove()elimină ultimul element „vizitat” din container. Aproape toate celelalte tipuri de modificare a containerului în timpul iterației sunt nesigure.
De asemenea, java.util.Listare java.util.ListIteratorun API similar, dar permite iterația înainte și înapoi, oferind o determinare a indexului curent din listă și deplasarea la un element după poziția sa.
Odată cu lansarea lui J2SE 5.0, a fost introdusă o interfață pentru a sprijini foreachIterable îmbunătățit pentru iterare peste colecții și matrice. definește o metodă care returnează . Folosind o buclă îmbunătățită , exemplul anterior poate fi rescris ca forIterableiterator()Iteratorfor
pentru ( MyType obj : list ) Sistem . afară . print ( obj );Iteratorii din .NET Framework sunt numiți „enumeratori” și sunt reprezentați de IEnumerator. IEnumeratorimplementează o metodă MoveNext()care trece la următorul element și indică dacă s-a ajuns la sfârșitul colecției; proprietatea Currenteste folosită pentru a obține valoarea elementului specificat; metoda opțională Reset()readuce enumeratorul în poziția inițială. Enumeratorul indică inițial o valoare specială înaintea primului element, deci apelul MoveNext()este necesar pentru a începe iterația.
Enumeratorii sunt de obicei trecuți prin apelarea unei metode pe un GetEnumerator()obiect care implementează IEnumerable. Clasele de containere implementează de obicei această interfață. Cu toate acestea, expresia C# foreach poate opera pe orice obiect care acceptă o astfel de metodă, chiar dacă nu implementează . Ambele interfețe au fost extinse în versiuni generice ale .NET 2.0 . IEnumerable
Următorul exemplu arată o utilizare simplă a iteratoarelor în C# 2.0:
// Versiunea „explicită” a IEnumerator < MyType > iter = list . GetEnumerator (); while ( iter . MoveNext ()) Consolă . WriteLine ( iter . Current ); // Versiunea „implicită” a foreach ( valoarea MyType în listă ) Consolă . WriteLine ( valoare );C# 2.0 acceptă, de asemenea, generatoare : o metodă declarată returnabilă IEnumerator(sau IEnumerable) dar care utilizează expresia „ ” (return flexibil) yield returnpentru a produce o secvență de elemente în loc să returneze o entitate obiect va fi transformată într-o nouă clasă de către compilatorul care implementează corespunzătoare. interfata.
Iteratorii din Python sunt parte integrantă a limbajului și, în multe cazuri, sunt utilizați implicit într-o expresie for( buclă de căutare ), în manipularea listelor și în expresii generatoare . Toate tipurile de bucle standard care fac parte din limbajul Python acceptă iterația, la fel ca multe dintre clasele care fac parte din . Următorul exemplu demonstrează o iterație implicită tipică cu o buclă:
pentru valoare în secvență : imprimare ( valoare )Dicționarele Python (un fel de matrice asociativă ) pot fi, de asemenea, repetate direct, returnând cheile de dicționar. Sau metoda itemilor din dicționar poate fi repetată atunci când completează cheia asociată, iar valoarea acelei perechi este un tuplu:
pentru cheie în dicționar : valoare = dicționar [ cheie ] print ( cheie , valoare ) pentru cheie , valoare în dicționar . articole (): imprimare ( cheie , valoare )Cu toate acestea, iteratorii pot fi utilizați și specificati în mod explicit. Pentru orice tip enumerat de buclă sau clasă, funcția încorporată iter()creează un iterator. Un iterator implementează o metodă next()care returnează următorul element din container. Când nu mai sunt elemente rămase, apare o eroare StopIteration. Următorul exemplu demonstrează iterația corespunzătoare a buclei folosind iteratoare explicite:
it = iter ( secvență ) în timp ce True : try : value = it . următorul () cu excepția StopIteration : break print ( valoare )În exemplul următor, pentru Python 2.4 (și mai târziu), iteratorul este obiectul fișier însuși f, accesând fișierul ca o secvență de șiruri de caractere:
f = deschide ( „README” ) # deschide un fișier print ( f . next ()) # următoarea valoare a iteratorului este următoarea linie a fișierului tipărit ( sum ( len ( line ) for line in f )) # the suma lungimilor tuturor celorlalte linii ale fișieruluiOrice clasă personalizată poate suporta iterație standard (explicită sau implicită) atunci când definește o metodă __iter__()care creează un iterator. Iteratorul are nevoie apoi de o definiție de metodă next()care returnează următorul element. Merită să înțelegeți diferența dintre un obiect iterabil (un obiect din care o funcție iter()returnează un iterator) și un iterator (un obiect care are o metodă __next__).
Generatoarele de limbaj Python implementează protocolul pentru această iterație.
PHP 4 a introdus constructele look-loop în Perl și altele . Acest lucru vă permite să răsfoiți matrice într-un mod simplu. În PHP 4, bucla de căutare funcționează numai cu matrice și aruncă o eroare atunci când încercați să o utilizați cu variabile de diferite tipuri sau variabile neinițializate.
În PHP5, bucla de căutare permite ca obiectele să fie iterate prin toți membrii publici.
Există două sintaxe pentru aceasta, a doua fiind o extensie mică, dar foarte utilă a primei.
Exemplul A
<?php foreach ( expresie_matrice ca $valoare ) echo " $valoare ; \n " ; ?>Exemplul B
<?php foreach ( expresie_matrice as $cheie => $valoare ) echo "( $cheie ) $valoare ; \n " ; ?>Exemplul A iterează peste tabloul transmis către array_expression. De fiecare dată când trece prin buclă, valoarea elementului curent este atribuită variabilei $value, iar pointerul matricei intern se mută la următorul element (deci la următoarea iterație a buclei, veți „vedea” următorul element).
Exemplul B demonstrează funcționalitatea similară prezentată mai sus. Dar o completează cu faptul că valoarea cheie a elementului curent (în acest caz, array_expression) va fi atribuită variabilei $keyla fiecare trecere a buclei.
PHP vă permite să modificați conținutul unui tablou în timpul iterației, pentru care este suficient să specificați că valoarea lui $value va fi obținută ca referință (în termeni PHP), adică ca &$value.
<?php $arr = matrice ( 1 , 2 , 3 , 4 , 5 ); foreach ( $arr ca & $valoare ) $valoare ++ ; // incrementează fiecare valoare cu una // acum $arr conține valorile: 2,3,4,5,6 ?>În PHP 5, interfața Iteratoreste predefinită și obiectele pot fi modificate pentru a controla iterația.
<?php class MyIterator implementează Iterator { private $var = array (); function public __construct ( $array ) { if ( is_array ( $array )) { $this -> var = $array ; } } public function rewind () { echo " rewind \n " ; resetare ( $this -> var ); } public function current () { $var = curent ( $this -> var ); echo "curent: $var\n " ; return $var ; } tasta functionala publica () { $var = tasta ( $this -> var ); echo "cheie: $var\n " ; return $var ; } public function next () { $var = urmatorul ( $this -> var ); echo "next: $var\n " ; return $var ; } function public valid () { $var = $this -> current () !== false ; echo "corect: { $var } \n " ; return $var ; } } ?>Aceste metode sunt utilizate pe deplin în întregul ciclu de navigare foreach($obj AS $key=>$value). Metodele iteratoare sunt executate în următoarea ordine:
1.wind() ("tranziție") 2. cât timp este valabil() { 2.1 curent() în $valoare 2.3 key() în $key 2.4 următorul() }Exemplul anterior poate fi simplificat foarte mult prin utilizarea interfeței IteratorAggregate, care obligă dezvoltatorul să implementeze o singură metodă getIterator().
<?php clasa MyIterator implementează IteratorAggregate { private $var = array (); function public __construct ( array $array ) { // verificarea tipului se face de catre interpret: __construct(array $array) $this -> var = $array ; } public function getIterator () { return new ArrayIterator ( $this -> var ); } } ?>Iteratorii în limbajul XL sunt o generalizare a generatorilor și iteratorilor.
import IO = XL . ui . CONSOLĂ iterator IntegerIterator ( var out Counter : integer ; Low , High : integer ) scris Counter in Low .. High este Counter := Low while Counter <= High loop yield Counter += 1 // Rețineți că nu este nevoie de o declarație separată a lui I, deoarece 'var out' este declarat într-un iterator // Declarația implicită a lui I ca număr întreg apare mai jos pentru I în bucla 1 .. 5 IO . ScrieLn " I = " , IIteratoarele din ActionScript 3 sunt încorporate în limbajul în sine și sunt acceptate de instrucțiunile foreach și for...in . Din punct de vedere al limbajului, matricele și instanțele claselor dinamice sunt iteratoare:
var obj : Obiect = { prop1 : "a" , prop2 : "b" , prop3 : "c" }; // următoarea buclă va „rula” prin toate cheile (numele proprietăților) obiectului obj pentru ( var name : String in obj ) trace ( name ); // bucla următoare va „rula” prin toate valorile proprietăților obj foreach ( var val :* în obj ) trace ( val ); }Biblioteca standard Haskell definește clasa de tip Traversable [3] [4] :
class ( Functor t , Foldable t ) => Traversabil t unde traversează :: Aplicativ f => ( a -> f b ) -> t a -> f ( t b )Aici t este un tip polimorf (poate un container sau o colecție ), f este un tip „văzut” (de exemplu, I/O, schimbare explicită a stării sau posibilitatea unei erori). „traverse” este o specializare a functor și fold , care este exprimată în contextul (antetul) clasei.
De exemplu, pentru un arbore binar , metoda „traverse” ar putea fi definită după cum urmează:
Arborele de date a = Gol | frunză a | Nodul ( Arborele a ) a ( Arborele a ) exemplu Traversable Tree traverse f Gol = pur Empty traverse f ( Leaf x ) = Leaf <$> f x traverse f ( Node l k r ) = Node <$> traverse f l <*> f k <*> traverse f rExemplu de utilizare:
-- | Tipăriți conținutul fiecărui nod arbore. printTree tree = arbore de tipărire transversală -- | Această funcție ia o funcție binară g și un arbore, străbate arborele, aplicând g fiecărui nod (al doilea argument -- este solicitat de la intrarea standard) și returnează arborele modificat. combineWithStdin :: ( Read c ) => ( a -> c -> b ) -> Tree a -> IO ( Tree b ) combineWithStdin g = traverse combine unde combine x = g x <$> readLn {- Exemplu: arbore = Nod (Nod (Frunză 3) 6 (Frunză 9)) 10 (Nod (Frunză 9) 0 Gol) $ combineWithStdin (+) arbore > 10 > 20 > 30 > 40 > 50 > 60 $ Nod (Nod (Frunză 13) 26 (Frunză 39)) 50 (Nod (Frunză 59) 60 Gol) -}Pe baza metodelor clasei de tip „Traversable”, vă puteți construi propriile funcții cu o strategie de traversare specifică.
Începând cu versiunea 6.12 a compilatorului GHC , extensiile „-XDeriveFunctor” „-XDeriveFoldable” și „-XDeriveTraversable” au fost introduse pentru a crea automat instanțe ale claselor de tip adecvate. Exemplu:
Arborele de date a = Gol | frunză a | Derivarea nodului ( Arborele a ) a ( Arborele a ) ( Functor , Pliabil , Traversabil )