Iterador

De la Viquipèdia, l'enciclopèdia lliure.
Saltar a la navegació Saltar a la cerca

En informàtica , un iterador és un objecte que permet visitar tots els elements continguts en un altre objecte, normalment un contenidor, sense haver de preocupar-se pels detalls d’una implementació específica. De vegades, un iterador s’anomena cursor , sobretot en el context de fonaments de dades .

Descripció

Es pot considerar un iterador com un tipus de punter especialitzat que proporciona un punt d' accés seqüencial als elements d'un objecte que conté un nombre finit d'objectes més senzills, anomenats agregats.

L'iterador ofereix dues operacions bàsiques:

  • Accés a l'element de l'agregat actualment orientat;
  • Actualitzeu el punter perquè apunti al següent element de la seqüència.

Aquestes operacions senzilles permeten accedir als elements d'un agregat de manera uniforme i independent de l'estructura interna de l'agregat, que pot ser molt més complexa que les seqüències lineals implementades per matrius i llistes . Exemples d’agregats complexos són la matriu associativa , l’ arbre i la taula de hash .

A més d’accedir i actualitzar-se, un iterador ha de proporcionar almenys dues operacions:

  • Inicialització o restauració de l’estat inicial, en què l’element que apunta l’iterador és el primer de la seqüència;
  • Comproveu si l’iterador ha esgotat tots els elements de l’agregat, és a dir, si s’ha actualitzat més enllà de l’últim element de la seqüència.

Segons el llenguatge i les necessitats, els iteradors poden proporcionar operacions addicionals o mostrar comportaments diferents. Els iteradors bidireccionals ofereixen un exemple d'iteradors especialitzats, que us permeten visitar tots els elements d'un agregat començant per l'últim element i avançant cap al primer. Un altre exemple l’ofereixen els iteradors de filtratge , que permeten visitar només el subconjunt dels elements d’un agregat que compleix les condicions preestablertes dins de l’ iterador .

Normalment, una classe iteradora es dissenya en estreta coordinació amb la classe contenidora corresponent. Normalment, el contenidor proporciona mètodes per crear-hi iteradors.

Motius i beneficis

L’objectiu principal d’un iterador és permetre que el codi que l’utilitza visiti cada element d’un contenidor sense dependre de l’estructura interna i dels detalls d’ implementació del contenidor.

Això us permet reutilitzar, amb mínimes variacions, el codi que accedeix a les dades. És a dir, és possible modificar o substituir un contenidor per un d’estructura diferent sense comprometre la correcció del codi que visita els seus elements.

Comparació amb l'ús d'índexs

En els llenguatges de procediment és freqüent utilitzar índexs enters per recórrer els elements d'una matriu. Tot i que els índexs enters també es poden utilitzar amb alguns contenidors orientats a objectes, l'ús d'iteradors té els següents avantatges:

  • Els cicles de recompte no són adequats per a totes les estructures de dades; en particular, per a estructures de dades on l’accés directe és lent o absent, com ara llistes i arbres.
  • Els iteradors poden proporcionar una manera coherent d'iterar sobre les estructures de dades de cada categoria i, per tant, fer que el codi sigui més llegible, reutilitzable i menys sensible als canvis en l'estructura de dades.
  • Un iterador pot imposar restriccions d’accés addicionals, com ara assegurar-vos que no ometeu els articles ni visiteu el mateix element diverses vegades.
  • Un iterador pot permetre la modificació de l'objecte contenidor sense invalidar l'iterador. Per exemple, després que un iterador hagi avançat més enllà del primer element, és possible inserir elements addicionals al començament del contenidor amb resultats previsibles. Amb l’ús d’índexs, això és problemàtic, ja que els índexs han de canviar.

Els iteradors implícits

Alguns llenguatges orientats a objectes, com Perl i Python, ofereixen una forma intrínseca d’iterar sobre els elements d’un objecte contenidor sense introduir un objecte iterador explícit. Això sovint es manifesta en algun tipus d'operador "per a cada", com en els exemples següents:

 # Perl, iteració implícita
   foreach $ val ( @list ) {
       imprimeix "$ val \ n" ;
   }
# Python, iteració implícita
   per al valor de la llista :
       valor d' impressió

El llenguatge C ++ també té una plantilla de funció std :: for_each () que permet una iteració implícita similar, però encara requereix objectes iteradors explícits com a entrada inicial.

Els generadors

Un generador és una categoria especial d'iterador en què l'objecte contenidor no es realitza completament. Això permet elaborar un element a la vegada de col·leccions abstractes o fins i tot infinites. Els generadors són habituals en llenguatges de programació funcionals o en llenguatges que prenen prestats alguns conceptes funcionals. Els generadors solen implementar-se en termes de continuacions.

Iteradors en diversos llenguatges de programació

C ++

El llenguatge C ++ fa un ús extens dels iteradors a la seva biblioteca de plantilles estàndard. Totes les plantilles de tipus de contenidor estàndard proporcionen un conjunt ric i coherent de tipus d'iteradors. La sintaxi dels iteradors estàndard està dissenyada per assemblar-se a la de l'aritmètica del punter C ordinari, en què s'utilitzen els operadors * i -> per fer referència a l'element que apunta l'iterador, i els operadors aritmètics del punter com ++ s'utilitzen per avançar l'iterador a el següent element.

Els iteradors solen utilitzar-se per parelles, on s’utilitza un per a la iteració real i el segon serveix per marcar el final de la col·lecció. Els iteradors es creen a partir de la classe de contenidors corresponent mitjançant mètodes estàndard com ara begin() i end() . L'iterador representat per begin() apunta al primer element, mentre que l'iterador representat per end() és un valor especial que no fa referència a cap element.

Quan un iterador s'avança més enllà de l'últim element, per definició és igual al valor especial retornat per end() . L'exemple següent mostra un ús típic d'un iterador.

 ContainerType C ; // Qualsevol tipus de contenidor estàndard, com ara std :: list <algun tipus>
ContainerType :: iterador A = C. begin ();
ContainerType :: iterador Z = C. end ();
mentre que ( A ! = Z ) {
   ContainerType :: value_type value = * A ;
   std :: cout « valor « std :: endl ;
    ++ A ;
}

Hi ha moltes varietats d'iteradors, cadascun amb un comportament lleugerament diferent, incloent: iteradors cap endavant, cap enrere i bidireccionals; iteradors d'accés directe; iteradors d'entrada i sortida; i els iteradors "const" (que protegeixen el contenidor o els seus elements de qualsevol modificació). Tot i això, no tots els tipus de contenidors admeten tots els tipus d’iteradors. Els usuaris poden crear els seus propis tipus d'iteradors derivant subclasses de la plantilla de classe estàndard std :: iterator.

La seguretat dels iteradors es defineix per separat per als diferents tipus de contenidors estàndard; en alguns casos, l'iterador és molt permissiu en permetre canvis al contenidor durant la iteració.

Java

Introduït a la versió 1.2, el suport per als iteradors s’aconsegueix mitjançant la classe paramètrica ListIterator del paquet Java.util. De fet, cada classe que implementa la interfície Iterable té un conjunt de mètodes de suport: un mètode listIterator () que crea l’iterador, un mètode next () que l’avança i un mètode hasNext () que verifica l’existència del node next i opcionalment un mètode remove ().

 // creeu una llista enllaçada que es visitarà gràcies a l'iterador
   LinkedList < String > list = new LinkedList < String > ();
   // suposem que la llista s’omple mentrestant
   ListIterator < String > it = list . listIterator ();
   // creeu l'iterador
   while ( it . hasNext ()) {
       // ja que el mètode next () retorna un objecte és possible realitzar un càsting
       String temp = ( String ) it . next ();
       Sistema . fora . println ( temp );
   }

Per als tipus de col·leccions que el suporten, es pot utilitzar el mètode remove () de l'iterador per eliminar l'últim element visitat del contenidor. La majoria dels altres tipus de canvis de contenidors no són segurs mentre itereu.

Python

Els iteradors de Python són una part fonamental del llenguatge i, en molts casos, passen desapercebuts ja que s’utilitzen implícitament a través de la declaració "for". Tots els tipus de seqüència integrats a Python admeten la iteració, igual que moltes classes que formen part de la biblioteca estàndard. L'exemple següent mostra una iteració implícita típica sobre una seqüència:

 per obtenir un valor en seqüència :
       valor d' impressió

No obstant això, els iteradors es poden utilitzar i definir explícitament. Per a cada tipus o classe de seqüència iterable, la funció incorporada iter () s'utilitza per crear un objecte iterador. Aquest objecte iterador proporciona un mètode next () que representa el següent element del contenidor. Quan no quedin més elements, es generarà una excepció StopIteration. L'exemple següent mostra una iteració equivalent sobre una seqüència mitjançant iteradors explícits:

 it = iter ( seqüència )
   provar :
       mentre que és cert :
           imprimeix -lo . next ()
   excepte StopIteration :
       passar

Qualsevol classe definida per l'usuari pot admetre la iteració estàndard (tant implícita com explícita) definint un __iter__() que crea un objecte iterador (que haurà de definir el mètode next() ).

Python també admet els generadors, que són una categoria especial d'iteradors sobre una col·lecció no realitzada. Un generador és una funció "congelada". Un cop emès cada valor (amb la sentència "rendiment"), l'estat de la funció es congela. Quan es torna a invocar la funció, es reprèn l'execució on la sentència "rendiment" l'ha deixat, amb totes les variables de la funció en l'estat en què es trobaven. Aquí teniu un exemple d’un generador que representa cada número de la seqüència de Fibonacci:

 def fibo_gen ():
       x = 0
       y = 1
       mentre que és cert :
           rendiment x
           x , y = y , x + y

Articles relacionats

Altres projectes

Enllaços externs

Informàtica Portal de TI : accediu a les entrades de Viquipèdia relacionades amb TI