Iterator
Această intrare sau secțiune despre programare nu citează sursele necesare sau cei prezenți sunt insuficienți . |
În informatică , un iterator este un obiect care vă permite să vizitați toate elementele conținute într-un alt obiect, de obicei un container, fără să vă faceți griji cu privire la detaliile unei implementări specifice. Un iterator este uneori numit cursor , mai ales în contextul bazelor de date .
Descriere
Un iterator poate fi considerat un tip de pointer specializat care oferă un punct de acces secvențial la elementele unui obiect care conține un număr finit de obiecte mai simple, numit agregat.
Iteratorul oferă două operații de bază:
- Acces la elementul agregatului vizat în prezent;
- Actualizați indicatorul astfel încât să indice următorul element din secvență.
Aceste operații simple permit accesul la elementele unui agregat într-un mod uniform și independent de structura internă a agregatului, care poate fi mult mai complexă decât secvențele liniare implementate de tablouri și liste . Exemple de agregate complexe sunt matricea asociativă , arborele și tabelul hash .
Pe lângă accesarea și actualizarea, un iterator trebuie să furnizeze cel puțin două operații:
- Inițializarea sau restaurarea stării inițiale, în care elementul indicat de iterator este primul din secvență;
- Verificați dacă iteratorul a epuizat toate elementele agregatului, adică dacă a fost actualizat dincolo de ultimul element al secvenței.
În funcție de limbă și nevoi, iteratorii pot oferi operațiuni suplimentare sau pot prezenta comportamente diferite. Un exemplu de iteratori specializați este oferit de iteratorii bidirecționali , care vă permit să vizitați toate elementele unui agregat începând de la ultimul element și mergând spre primul. Un alt exemplu este oferit de filtrarea iteratorilor , care vă permit să vizitați doar subsetul elementelor unui agregat care îndeplinește condițiile prestabilite din cadrul iteratorului .
O clasă iterator este de obicei proiectată în strânsă coordonare cu clasa corespunzătoare care conține. De obicei, containerul oferă metode de creare a iteratorilor pe acesta.
Motive și beneficii
Scopul principal al unui iterator este de a permite codului care îl folosește să viziteze fiecare element al unui container fără a depinde de structura internă și detaliile de implementare ale containerului în sine.
Acest lucru vă permite să reutilizați, cu variații minime, codul care accesează datele. Adică, este posibil să modificați sau să înlocuiți un container cu unul dintr-o structură diferită, fără a compromite corectitudinea codului care îi vizitează elementele.
Comparație cu utilizarea indicilor
În limbajele de procedură este obișnuit să se utilizeze indici întregi pentru a itera prin elementele unui tablou. Deși indicii întregi pot fi folosiți și cu unele containere orientate obiect, utilizarea iteratorilor are următoarele avantaje:
- Ciclurile de numărare nu sunt potrivite pentru toate structurile de date; în special pentru structurile de date în care accesul direct este lent sau absent, cum ar fi listele și arborii.
- Iteratorii pot oferi un mod consecvent de iterație asupra structurilor de date din fiecare categorie și, astfel, pot face codul mai lizibil, reutilizabil și mai puțin sensibil la modificările structurii de date.
- Un iterator poate impune restricții suplimentare de acces, cum ar fi asigurarea că nu omiteți articole sau nu vizitați același articol de mai multe ori.
- Un iterator poate permite modificarea obiectului container fără a invalida iteratorul. De exemplu, după ce un iterator a avansat dincolo de primul element, poate fi posibil să se introducă elemente suplimentare la începutul containerului cu rezultate previzibile. Cu utilizarea indexurilor, acest lucru este problematic, deoarece indicii trebuie să se schimbe.
Iteratorii implicați
Unele limbaje orientate obiect, cum ar fi Perl și Python, oferă un mod intrinsec de iterație asupra elementelor unui obiect container fără a introduce un obiect iterator explicit. Acest lucru se manifestă adesea într-un fel de operator „pentru fiecare”, ca în următoarele exemple:
# Perl, iterație implicită
foreach $ val ( @list ) {
tipăriți "$ val \ n" ;
}
# Python, iterație implicită
pentru valoare în listă :
Valoare tipărită
Limbajul C ++ are și un șablon de funcție std :: for_each () care permite o iterație implicită similară, dar necesită totuși obiecte iteratoare explicite ca intrare inițială.
Generatoarele
Un generator este o categorie specială de iterator în care obiectul care conține nu este pe deplin realizat. Acest lucru permite elaborarea unui element la un moment dat de colecții abstracte sau chiar infinite. Generatoarele sunt comune în limbaje de programare funcționale sau în limbaje care împrumută unele concepte funcționale. Generatorii sunt adesea implementați în termeni de continuări.
Iteratori în diferite limbaje de programare
C ++
Limbajul C ++ folosește pe scară largă iteratorii în biblioteca de șabloane standard. Toate șabloanele standard de tip container oferă un set bogat și consistent de tipuri de iteratoare. Sintaxa iteratorilor standard este concepută să semene cu cea a aritmeticii obișnuite a indicatorului C, în care operatorii * și -> sunt utilizați pentru a face referire la elementul către care indică iteratorul, iar operatorii aritmetici ai indicatorului ca ++ sunt folosiți pentru a avansa iteratorul la următorul element.
Iteratorii sunt de obicei folosiți în perechi, unde unul este utilizat pentru iterația reală, iar al doilea servește pentru a marca sfârșitul colecției. Iteratorii sunt creați din clasa de containere corespunzătoare utilizând metode standard precum begin() și end() . Iteratorul redat de begin() indică primul element, în timp ce iteratorul redat de end() este o valoare specială care nu se referă la niciun element.
Când un iterator este avansat după ultimul element, acesta este, prin definiție, egal cu valoarea specială returnată de end() . Următorul exemplu arată o utilizare tipică a unui iterator.
ContainerType C ; // Orice tip de container standard, cum ar fi std :: list <un tip>
ContainerType :: iterator A = C. begin ();
ContainerType :: iterator Z = C. end ();
în timp ce ( A ! = Z ) {
ContainerType :: value_type value = * A ;
std :: cout « valoare « std :: endl ;
++ A ;
}
Există multe varietăți de iteratori, fiecare cu un comportament ușor diferit, inclusiv: iteratori înainte, înapoi și bidirecționali; iteratori cu acces direct; iteratoare de intrare și ieșire; și iteratorii „const” (care protejează containerul sau elementele sale de modificări). Cu toate acestea, nu toate tipurile de containere acceptă fiecare tip de iterator. Este posibil ca utilizatorii să își creeze propriile tipuri de iteratoare derivând subclasele din șablonul standard de clasă std :: iterator.
Siguranța iteratorilor este definită separat pentru diferitele tipuri de containere standard; în unele cazuri, iteratorul este foarte permisiv în a permite modificări ale containerului în timpul iterației.
Java
Introdus în versiunea 1.2, suportul pentru iteratori este realizat prin clasa parametrică ListIterator a pachetului Java.util. Fiecare clasă care implementează interfața Iterable are de fapt un set de metode de suport: o metodă listIterator () care creează iteratorul, o metodă next () care o avansează și o metodă hasNext () care verifică existența nodului next și opțional o metodă remove ().
// creați o listă legată care va fi vizitată grație iteratorului
LinkedList < String > list = new LinkedList < String > ();
// să presupunem că lista se completează între timp
ListIterator < String > it = list . listIterator ();
// creați iteratorul
while ( it . hasNext ()) {
// deoarece metoda next () returnează un obiect, este posibil să se efectueze un casting
String temp = ( String ) it . next ();
Sistem . afară . println ( temp );
}
Pentru tipurile de colecții care îl susțin, metoda remove () a iteratorului poate fi utilizată pentru a elimina ultimul element vizitat din container. Majoritatea celorlalte tipuri de modificări ale containerelor sunt nesigure în timp ce iterați.
Piton
Iteratorii Python sunt o parte fundamentală a limbajului și, în multe cazuri, trec neobservați, deoarece sunt utilizați implicit prin declarația „pentru”. Toate tipurile de secvențe încorporate în Python acceptă iterația, la fel ca multe clase care fac parte din biblioteca standard. Următorul exemplu prezintă o iterație implicită tipică asupra unei secvențe:
pentru valoare în ordine :
valoarea de imprimare
Cu toate acestea, iteratorii pot fi utilizați și definiți în mod explicit. Pentru fiecare tip sau clasă de secvență iterabilă, funcția încorporată iter () este utilizată pentru a crea un obiect iterator. Acest obiect iterator oferă o metodă next () care redă următorul element al containerului. Când nu mai sunt elemente rămase, va fi ridicată o excepție StopIteration. Următorul exemplu arată o iterație echivalentă asupra unei secvențe folosind iteratori expliciți:
it = iter ( secvență )
incearca :
în timp ce este adevărat :
tipărește- l . next ()
cu excepția StopIteration :
trece
Orice clasă definită de utilizator poate suporta iterația standard (atât implicită, cât și explicită) prin definirea unei __iter__() care creează un obiect iterator (care va trebui să definească metoda next() ).
Python acceptă, de asemenea, generatoare, care sunt o categorie specială de iteratori pentru o colecție nerealizată. Un generator este o funcție „înghețată”. După ce fiecare valoare a fost emisă (cu declarația „randament”), starea funcției este înghețată. Când funcția este invocată din nou, execuția se reia de unde a lăsat-o instrucțiunea „randament”, cu toate variabilele funcției în starea în care se aflau. Iată un exemplu de generator care redă fiecare număr din secvența Fibonacci:
def fibo_gen ():
x = 0
y = 1
în timp ce este adevărat :
randament x
x , y = y , x + y
Elemente conexe
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere despre modelul Iterator
linkuri externe
- Boost C ++ Iterator Library , la boost.org .
