Az Iterator (az angol iterator - enumerator szóból) egy olyan felület , amely hozzáférést biztosít egy gyűjtemény elemeihez ( tömb vagy tároló ), és azokon belüli navigációt [1] . Az iterátoroknak különböző közös neveik lehetnek a különböző rendszereken. Az adatbázis-kezelő rendszerek tekintetében az iterátorokat kurzoroknak nevezzük . A legegyszerűbb esetben az alacsony szintű nyelvek iterátora egy mutató .
Az iterátorok használata az általános programozásban lehetővé teszi univerzális algoritmusok megvalósítását a konténerekkel való munkához [1] .
Az iterátorok fő célja, hogy a felhasználó hozzáférjen a tároló bármely eleméhez, miközben elrejti a tároló belső szerkezetét a felhasználó elől. Ez lehetővé teszi a tároló számára, hogy bármilyen módon tároljon elemeket, ameddig elfogadható a felhasználó számára, hogy azt egyszerű sorozatként vagy listaként kezelje . Az iterátor osztály kialakítása általában szorosan kapcsolódik a megfelelő konténerosztályhoz. Általában a tároló módszereket biztosít az iterátorok létrehozására.
Az iterátor alapvető műveleteiben hasonló a mutatóhoz : objektumok gyűjteményének egyetlen elemére mutat ( hozzáférést biztosít az elemhez ), és funkciókat tartalmaz a lista egy másik elemére (következő vagy előző) történő átlépéshez. Az iterátorok támogatását megvalósító tárolónak biztosítania kell a lista első elemét, valamint annak ellenőrzését, hogy a tároló összes eleme megtörtént-e iteráció (ha az iterátor véges). A használt nyelvtől és céltól függően az iterátorok további műveleteket támogathatnak, vagy eltérő viselkedéseket határozhatnak meg.
Néha a hurokszámlálót "hurokiterátornak" nevezik. A hurokszámláló azonban csak elemiterációt biztosít, elemelérést nem.
Az eljárási programozási nyelvek széles körben alkalmazzák a hurokszámláláson alapuló indexelést a sorozat (például egy tömb ) összes elemének iterálására. Bár az indexelés egyes objektum-orientált tárolókkal együtt használható, az iterátorok használatának vannak előnyei:
A tárolók elemeinek iterálása közbeni módosításának képessége elengedhetetlenné vált a modern objektum-orientált programozásban , ahol az objektumok közötti kapcsolatok és a műveletek végrehajtásának következményei nem túl nyilvánvalóak. Az iterátor használata megszabadul az ilyen jellegű problémáktól.
Egyes objektumorientált nyelvek, mint például a Perl , Python , C# , Ruby , valamint a Java és Delphi legújabb verziói speciális operátorokkal rendelkeznek a tárolóelemek iterációjához anélkül, hogy kifejezetten iterátorokat használnának. Valós iterátor valóban létezik, de ha létezik, akkor nincs kifejezetten deklarálva a forráskódban.
A gyűjtemény elemein keresztüli iteráció implicit iterátor segítségével a " foreach " utasítással (vagy azzal egyenértékű) történik, ahogy a következő Python-kódban:
Érték a listában esetén : Nyomtasson értéketMás esetekben az iterátorokat maga az objektumok gyűjteménye is létrehozhatja, mint ebben a Ruby példában:
lista . mindegyik do | érték | értékvéget tesz _A lista- kompatibilis nyelvek implicit iterátorokat is használhatnak az eredményül kapott lista létrehozásakor, például a Python:
MaleNames = [ Személy . A személy neve a névjegyzékben , ha személy . férfi ]Néha az implicitség csak részleges. Például a C++ nyelv szabványos sablonkönyvtára tartalmaz néhány függvénysablont, amelyek például ilyen implicit iterációt hajtanak végre. Azonban továbbra is szükség van egy explicit iterátorra paraméterként. De az inicializálás után a következő iteráció implicit módon, iterátor használata nélkül történik. A C++11 szabvány óta a nyelv az implicit hurokiterációt is támogatja [2] . for_each()for
Az iterátorok megvalósításának egyik módja a társeljárások használata , amelyek többször is visszaadhatják a vezérlést (és a számított eredményeket), emlékezve az előző hívás állapotára és visszatérési pontjára. Egyes nyelvekben a társeljárásokat egy speciális, generátornak nevezett függvény ábrázolhatja . A generátor egy olyan függvény, amely megjegyzi, hol volt az előző visszatérés, és a következő meghívásakor a megszakított helyről folytatja a munkát.
A legtöbb iterátort természetesen generátorokkal írják le, és mivel a generátorok megtartják jelenlegi állapotukat a meghívások között, jól illeszkednek az összetett iterátorokhoz, amelyek megvalósításához összetett adatstruktúrákra van szükség ahhoz, hogy emlékezzen a gyűjtemény aktuális pozíciójára, például a fa bejárására .
Példa egy olyan generátorra, amely Fibonacci számokatyield ad vissza Python operátor használatával :
def fibonacci (): a , b = 0 , 1 while True : eredmény a # return a, + ne feledje, hol kell újraindítani a következő hívást a , b = b , a + b Fibonacci - beli számokhoz (): # Használja a generátort iterátor nyomtatási számkéntA sorozatot alkotó változókra való szokásos hivatkozás a számuk alapján történik. Ebben az esetben a szükséges változó címét a következőképpen számítjuk ki: "1. változó címe" + "változó mérete" x "készlet száma". Az ilyen változókhoz való szekvenciális hozzáféréssel jelentős teljesítménynövekedés érhető el, ha a következő változó címét az előző címén keresztül számítja ki. Erre való a csúszka. A sorozatot alkotó változók típusát, amelyekhez szekvenciálisan hozzáférünk, a csúszka referenciatípusának nevezzük, és a sorozatban lévő változók számát, amennyivel a csúszka minden ilyen hozzáférés után elmozdul, csúszkalépésnek. . A csúszka lépése egész konstansként van megadva. Ha a csúszka lépése nincs megadva a nézet deklarálásakor, akkor a lépés 1-gyel egyenlőnek minősül.
A C++ nyelv széles körben használja az iterátorokat az STL -ben, amely többféle iterátort támogat, beleértve az „egyirányú iterátorokat”, a „kétirányú iterátorokat” és a „véletlen hozzáférésű iterátorokat”. Az összes szabványos tárolótípus-sablon változatos, de konzisztens iterátortípus-készletet valósít meg. A szabványos iterátorok szintaxisa hasonló a hagyományos C nyelvi mutatókhoz , ahol a és operátorok segítségével határozza meg azt az elemet, amelyre az iterátor mutat, és a mutató aritmetikai operátorai, mint például a , az iterátor következő elemre való mozgatására szolgálnak. *->++
Az iterátorokat általában párban használják, amelyek közül az egyik az aktuális iterációt jelzi, a másik pedig a gyűjtemény végét. Az iterátorok a megfelelő konténerosztályok használatával jönnek létre, szabványos metódusokkal, begin()például end(). A függvény begin()visszaad egy mutatót az első elemre, és egy mutatót ad vissza egy end() képzeletbeli nem létező elemre, amely az utolsó után következik.
Amikor egy iterátor túllép az utolsó elemen, ez definíció szerint megegyezik az iterátor speciális végértékével. A következő példa egy iterátor tipikus használatát mutatja be:
std :: lista < int > C ; // Az std::list helyett bármely szabványos STL konténer használható ( std :: list < int > :: iterator it = C . begin (), end = C . end (); it != end ; ++ it ) { //változó iterátorhoz * it = 8 ; // az iterátor által mutatott elem megváltoztatható } for ( std :: list < int >:: const_iterator it = C . begin (), end = C . end (); it != end ; ++ it ) { //ha nem kell módosítani az elemeket std :: cout << * it << std :: endl ; }Sokféle iterátor létezik, amelyek viselkedésükben különböznek: egyirányú, fordított (fordított) és kétirányú iterátorok; bemeneti és kimeneti iterátorok; const iterátorok (megvédik a tárolót vagy elemeit a módosítástól). Azonban nem minden tárolótípus támogatja ezen iterátortípusok egyikét sem. A felhasználók saját iterátortípusokat hozhatnak létre a szabvány alapján alosztályok meghatározásával std::iterator.
Az iterátor használatának biztonsága külön van meghatározva a különböző típusú szabványos tárolókra; bizonyos esetekben az iterátor lehetővé teszi a konténer módosítását az iteráció során.
Az implicit iterációt a C++ is részben támogatja olyan szabványos függvénysablonokon keresztül, mint az std::for_each()[1] és std::accumulate()[2] . Használatukkor ezeket a meglévő iterátorokkal kell inicializálni, jellemzően a kezdettel és a végekkel, meghatározva az iteráció hatókörét, de a további iterációhoz nem lehet kifejezetten meghatározni az iterátorokat. A következő példa a használatát mutatja be for_each.
ContainerType < ItemType > C ; // Bármely szabványos elemtároló típus ItemType void ProcessItem ( const ItemType & I ) // A gyűjtemény minden elemét feldolgozó függvény { std :: cout << I << std :: endl ; } std :: for_each ( C.begin ( ) , C.end ( ) , ProcessItem ) ; // View LoopEnnek a módszernek az a hátránya, hogy képtelen deklarálni a ciklus törzsét belülről, ezért valahol deklarálni kell egy függvénymutatót vagy funktort , és argumentumként át kell adni. Ez részben ellensúlyozható egy olyan könyvtár használatával, mint a Boost , és egy lambda függvény használatával implicit módon hasonló infix operátor szintaxisú funktorok létrehozásához. Csak ezt szem előtt tartva egy ilyen könyvtárnak meghatározott módon kell végrehajtania bizonyos műveleteket.
A C++11 szabványtól kezdődően az iterátorok implicit módon is használhatók egy ciklusban for, biztosítva a tároló összes eleme feletti iterációt:
#include <vektor> #include <iostream> int main ( érvénytelen ) { 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 ; // Minden elem értékének kinyomtatása } return 0 ; }A Java nyelv JDK 1.2-es kiadásában bevezetett felület java.util.Iterator biztosítja a konténerosztályok iterációját. Mindegyik Iteratormegvalósítja next()és hasNext()opcionálisan támogatja a remove(). Az iterátorokat a megfelelő konténerosztályok hozzák létre, általában a iterator().
A metódus next()a következő értékre viszi az iterátort, és visszaadja a megadott értéket az iterátornak. Kezdetben létrehozásakor egy iterátor egy speciális értékre mutat az első elem előtt, így az első elem csak az első hívás után kérhető le next(). A vizsgálati módszer annak meghatározására szolgál , hogy a tartályban lévő összes elemet mikor végezték el hasNext(). A következő példa az iterátorok egyszerű használatát mutatja be:
Iterátor iter = lista . iterátor (); //Iterátor<Sajáttípus> iter = list.iterator(); J2SE 5.0-ban while ( iter . hasNext ()) System . ki . println ( iter.next ( ) );Az ezt támogató típusok gyűjteményénél az iterátor metódus remove()eltávolítja az utoljára „látogatott” elemet a tárolóból. Szinte minden más típusú tárolómódosítás az iteráció során nem biztonságos.
Hasonló API-val is java.util.Listrendelkezik java.util.ListIterator, de lehetővé teszi az előre és visszafelé történő iterációt, lehetővé téve az aktuális index meghatározását a listában, és a pozíciója alapján egy elemhez való mozgást.
A J2SE 5.0 kiadásával egy interfész került bevezetésre Iterable, amely támogatja a továbbfejlesztett foreach -t a gyűjtemények és tömbök iterációjához. definiál egy metódust , amely visszaadja a . Egy továbbfejlesztett ciklus használatával az előző példa átírható a következőre: forIterableiterator()Iteratorfor
for ( MyType obj : list ) System . ki . nyomtat ( obj );A .NET-keretrendszer iterátorait „felsorolóknak” nevezik, és a IEnumerator. IEnumeratorolyan metódust valósít meg MoveNext(), amely a következő elemre lép, és jelzi, hogy elérték-e a gyűjtés végét; a tulajdonság Currenta megadott elem értékének lekérésére szolgál; az opcionális metódus Reset()visszaállítja a számlálót az eredeti helyére. A felsoroló kezdetben egy speciális értékre mutat az első elem előtt, ezért a hívás MoveNext()szükséges az iteráció elindításához.
A felsorolókat általában úgy adják át, hogy meghívnak egy metódust egy GetEnumerator()objektumon, amely megvalósítja a IEnumerable. A tárolóosztályok általában ezt a felületet valósítják meg. A C# foreach kifejezés azonban bármilyen objektumon működhet, amely támogatja az ilyen metódust, még akkor is, ha nem valósítja meg a . Mindkét interfész kibővült a .NET 2.0 általános verzióiban . IEnumerable
A következő példa az iterátorok egyszerű használatát mutatja be a C# 2.0-ban:
// Az IEnumerator < MyType > iter = lista 'explicit' verziója . GetEnumerator (); while ( iter . MoveNext ()) Konzol . WriteLine ( iter . Current ); // a foreach 'implicit' verziója ( MyType érték a listában ) Konzol . WriteLine ( érték );A C# 2.0 támogatja a generátorokatIEnumerator is: a visszaadhatónak (vagy ) deklarált metódust, IEnumerableamely a " " (flexible return) kifejezést yield returnhasználja, hogy elemsorozatot hozzon létre ahelyett, hogy objektum entitást adna vissza, a fordító új osztályba alakítja, amely megvalósítja a megfelelő felület.
A Python iterátorai a nyelv szerves részét képezik, és sok esetben implicit módon használatosak egy kifejezésben for( lookup loop ), a listakezelésben és a generátor kifejezésekben . A Python nyelv részét képező összes szabványos huroktípus támogatja az iterációt, csakúgy, mint sok olyan osztály, amely a . A következő példa egy tipikus implicit iterációt mutat be ciklussal:
az értékhez sorrendben : print ( érték ) _A Python szótárak (egyfajta asszociatív tömb ) közvetlenül is iterálhatók, szótári kulcsokat adva vissza. Vagy a szótár tételek metódusa ismételhető, amikor befejezi a társított kulcsot, és ennek a párnak az értéke egy sor:
kulcs a szótárban : érték = szótár [ kulcs ] nyomtatás ( kulcs , érték ) _ kulcs esetén érték a szótárban . _ tételek (): nyomtatás ( kulcs , érték )Az iterátorok azonban kifejezetten használhatók és megadhatók. Bármilyen felsorolt típusú ciklushoz vagy osztályhoz a beépített függvény iter()létrehoz egy iterátort. Az iterátor olyan metódust valósít meg next(), amely a tároló következő elemét adja vissza. Ha már nincs több elem, hibaüzenet jelenik meg StopIteration. A következő példa bemutatja a megfelelő hurokiterációt explicit iterátorok használatával:
it = iter ( szekvencia ) míg True : try : value = it . következő ( ) kivéve a StopIteration : tört nyomtatás ( érték )A következő példában a Python 2.4 (és újabb) esetében az iterátor maga a fájlobjektum f, amely karakterláncok sorozataként éri el a fájlt:
f = open ( "README" ) # fájl megnyitása print ( f . next ()) # az iterátor következő értéke a fájl következő sora print ( sum ( len ( line ) for line in f )) # a a fájl összes többi sorának hosszának összegeBármely egyéni osztály támogathatja a szabványos iterációt (explicit vagy implicit), amikor __iter__()egy iterátort létrehozó metódust definiál. Az iterátornak ezután olyan metódusdefinícióra van szüksége, next()amely visszaadja a következő elemet. Érdemes megérteni a különbséget az iterálható objektum (olyan objektum, amelyből a függvény iter()egy iterátort ad vissza) és az iterátor (olyan objektum, amelynek metódusa van __next__) között.
A Python nyelvgenerátorok valósítják meg ennek az iterációnak a protokollját.
A PHP 4 bevezette a look-loop konstrukciókat a Perlben és néhány másban. Ez lehetővé teszi a tömbök egyszerű böngészését. A PHP 4-ben a keresési ciklus csak tömbökkel működik, és hibát ad, ha különböző típusú változókkal vagy inicializálatlan változókkal próbálja használni.
A PHP5-ben a keresési ciklus lehetővé teszi az objektumok iterációját az összes nyilvános tagon keresztül.
Két szintaxis létezik erre, a második az első kicsi, de nagyon hasznos kiterjesztése.
A példa
<?php foreach ( array_expression mint $érték ) echo " $value ; \n " ; ?>B példa
<?php foreach ( tömb_kifejezés mint $kulcs => $érték ) echo "( $kulcs ) $érték ; \n " ; ?>Példa A iterál a következőnek átadott tömbön array_expression. A cikluson keresztül minden alkalommal az aktuális elem értéke hozzá van rendelve a változóhoz $value, és a belső tömbmutató a következő elemre lép (tehát a ciklus következő iterációjában a következő elemet fogja látni).
A B példa a fent bemutatott hasonló funkciókat mutatja be. De kiegészíti azzal a ténnyel, hogy az aktuális elem kulcsértéke (ebben az esetben array_expression) hozzá lesz rendelve a változóhoz $keya ciklus minden egyes lépésében.
A PHP lehetővé teszi az iteráció során egy tömb tartalmának megváltoztatását, amihez elég megadni, hogy a $value értéke referenciaként (PHP-ban kifejezve), azaz &$értékként kerüljön felhasználásra.
<?php $arr = tömb ( 1 , 2 , 3 , 4 , 5 ); foreach ( $arr as & $value ) $value ++ ; // minden érték növelése eggyel // most az $arr a következő értékeket tartalmazza: 2,3,4,5,6 ?>A PHP 5-ben az interfész Iteratorelőre meghatározott, és az objektumok módosíthatók az iteráció szabályozására.
<?php class MyIterator implements Iterator { private $var = array (); public function __construct ( $tömb ) { if ( is_tömb ( $tömb )) { $this -> var = $tömb ; } } public function rewind () { echo " rewind \n " ; reset ( $this -> var ); } public function current () { $var = aktuális ( $this -> var ); echo "current: $var\n " ; return $var ; } public function key () { $var = key ( $this -> var ); echo "kulcs: $var\n " ; return $var ; } public function next () { $var = next ( $this -> var ); echo "next: $var\n " ; return $var ; } public function valid () { $var = $this -> current () !== false ; echo "helyes: { $var } \n " ; return $var ; } } ?>Ezeket a módszereket a teljes böngészési ciklus teljes mértékben kihasználja foreach($obj AS $key=>$value). Az iterátor metódusok végrehajtása a következő sorrendben történik:
1.rewind() ("átmenet") 2. amíg érvényes() { 2.1 current() $ értékben 2.3 key() a $kulcsban 2.4 következő() }Az előző példa nagyban leegyszerűsíthető az IteratorAggregate felület használatával, amely arra kényszeríti a fejlesztőt, hogy csak egy getIterator() metódust implementáljon.
<?php class A MyIterator implementálja az IteratorAggregate -t { private $var = array (); public function __construct ( tömb $tömb ) { // a típusellenőrzést az interpreter végzi el: __construct(array $tömb) $this -> var = $tömb ; } public function getIterator () { return new ArrayIterator ( $this -> var ); } } ?>Az iterátorok az XL nyelvben generátorok és iterátorok általánosításai.
import IO = XL . ui . KONZOL iterator IntegerIterator ( var out Számláló : egész szám ; Alacsony , Magas : egész szám ) Írta a számlálót alacsonyban _ _ _ _ _ _ _ _ _ _ _ _ _ // Megjegyzendő, hogy nincs szükség az I külön deklarációjára, mivel a 'var out' egy iterátorban van deklarálva // Az I implicit deklarációja egész számként történik az alábbiakban I in 1 .. 5 ciklus IO esetén . WriteLn " I = " , IAz ActionScript 3 iterátorai magába a nyelvbe vannak beépítve, és a foreach és a for...in utasítások támogatják őket . Nyelvi szempontból a dinamikus osztályok tömbjei és példányai iterátorok:
var obj : Object = { prop1 : "a" , prop2 : "b" , prop3 : "c" }; // a következő ciklus az obj objektum összes kulcsán (tulajdonságnevén) "fut" for ( var name : String in obj ) trace ( name ); // a következő ciklus az obj összes tulajdonságértékén keresztül fog futni foreach ( var val :* in obj ) trace ( val ); }A Haskell szabványkönyvtár definiálja a Traversable típusú osztályt [3] [4] :
osztály ( Funktor t , Összehajtható t ) => Átjárható t ahol traverse :: Applikatív f => ( a -> f b ) -> t a -> f ( t b )Itt a t valamilyen polimorf típus (talán egy tároló vagy egy gyűjtemény ), az f egy "showy" típus (például I/O, explicit állapotváltozás vagy hibalehetőség). A "traverse" a functor és a fold szakterülete , amely az osztály kontextusában (fejlécében) fejeződik ki.
Például egy bináris fa esetében a "bejárás" metódus a következőképpen definiálható:
adatfa a = Üres | _ levél a | Csomópont ( a fa ) a ( fa a ) példány Bejárható Fa bejárás f Üres = tiszta Üres bejárás f ( Levél x ) = Levél <$> f x bejárás f ( Csomópont l k r ) = Csomópont <$> traverse f l <*> f k <* > traverse f rHasználati példa:
-- | Nyomtassa ki az egyes facsomópontok tartalmát. printTree tree = traver print tree -- | Ez a függvény felvesz néhány g bináris függvényt és egy fát, bejárja a fát, minden csomópontra g-t alkalmazva (a második argumentum -- a szabványos bemenetből kérhető), és visszaadja a módosított fát. CombinWithStdin :: ( Olvassa el a c ) => ( a -> c -> b ) -> Tree a -> IO ( Tree b ) combinWithStdin g = átmenő kombinál , ahol kombinál x = g x <$> readLn {- Példa: fa = Csomópont (Csomópont (3. levél) 6 (9. levél)) 10 (Csomópont (9. levél) 0 Üres) $ combinWithStdin (+) fa > 10 > 20 > 30 > 40 > 50 > 60 $ Csomópont (Csomópont (13. levél) 26 (39. levél)) 50 (Csomópont (59. levél) 60 Üres) -}A „Traversable” típusú osztály metódusai alapján saját függvényeket építhetünk fel meghatározott bejárási stratégiával.
A GHC fordító 6.12-es verziója óta bevezették a "-XDeriveFunctor" "-XDeriveFoldable" és "-XDeriveTraversable" kiterjesztéseket, amelyek automatikusan létrehozzák a megfelelő típusosztályok példányait. Példa:
adatfa a = Üres | _ levél a | Csomópont ( a fa ) a ( fa a ) származtatása ( függvény , összecsukható , átjárható )