Iterator (z anglického iterator - enumerator) je rozhraní , které poskytuje přístup k prvkům kolekce ( pole nebo kontejneru ) a navigaci v nich [1] . Iterátory mohou mít v různých systémech různé společné názvy. Z hlediska systémů správy databází se iterátory nazývají kurzory . V nejjednodušším případě je iterátor v jazycích nízké úrovně ukazatel .
Použití iterátorů v generickém programování umožňuje implementovat univerzální algoritmy pro práci s kontejnery [1] .
Hlavním účelem iterátorů je umožnit uživateli přístup k jakémukoli prvku kontejneru a zároveň před uživatelem skrýt vnitřní strukturu kontejneru. To umožňuje kontejneru ukládat prvky jakýmkoli způsobem, pokud je pro uživatele přijatelné, aby s nimi zacházel jako s jednoduchou sekvencí nebo seznamem . Návrh třídy iterátoru obvykle úzce souvisí s odpovídající třídou kontejneru. Kontejner obvykle poskytuje metody pro vytváření iterátorů.
Iterátor je ve svých základních operacích podobný ukazateli : ukazuje na jeden prvek kolekce objektů (poskytuje přístup k prvku ) a obsahuje funkce pro přesun na jiný prvek v seznamu (další nebo předchozí). Kontejner, který implementuje podporu pro iterátory, musí poskytovat první prvek seznamu a také možnost zkontrolovat, zda byly iterovány všechny prvky kontejneru (pokud je iterátor konečný). V závislosti na použitém jazyce a účelu mohou iterátory podporovat další operace nebo definovat různá chování.
Někdy se počítadlo smyček nazývá „smyčkový iterátor“. Čítač smyček však poskytuje pouze iteraci prvku, nikoli přístup k prvku.
Procedurální programovací jazyky široce využívají indexování založené na počtu smyček k iteraci všech prvků sekvence (jako je pole ). Přestože indexování lze použít ve spojení s některými objektově orientovanými kontejnery, použití iterátorů má své výhody:
Schopnost modifikovat kontejner při iteraci jeho prvků se stala zásadní v moderním objektově orientovaném programování , kde vztahy mezi objekty a důsledky provádění operací nemusí být příliš zřejmé. Použití iterátoru se těchto problémů zbaví.
Některé objektově orientované jazyky, jako je Perl , Python , C# , Ruby a nejnovější verze Java a Delphi , mají speciální operátory pro iteraci prvků kontejneru bez explicitního použití iterátorů. Skutečný iterátor může skutečně existovat, ale pokud existuje, není explicitně deklarován ve zdrojovém kódu.
Iterace mezi prvky kolekce pomocí implicitního iterátoru se provádí pomocí příkazu " foreach " (nebo ekvivalentu), jako v následujícím kódu Pythonu:
pro Hodnota v seznamu : vytisknout hodnotuV jiných případech mohou být iterátory vytvořeny samotnou sbírkou objektů, jako v tomto příkladu Ruby:
seznam . každý dělá | hodnota | ukončuje hodnotu _Jazyky s povoleným seznamem mohou také používat implicitní iterátory při vytváření výsledného seznamu, jako je Python:
Mužská jména = [ Osoba . Jméno osoby v RosterList if Person . _ JeMuž ]Někdy je implicitnost pouze částečná. Například standardní knihovna šablon jazyka C++ obsahuje některé šablony funkcí, například, for_each()které provádějí takovou implicitní iteraci. Stále však vyžadují explicitní iterátor jako parametr. Po inicializaci však následná iterace probíhá implicitně bez použití jakéhokoli iterátoru. Od standardu C++11 podporuje jazyk také implicitní opakování smyček for[2] .
Jedním ze způsobů, jak implementovat iterátory, je použít koprocesy, které mohou vrátit řízení (a vypočítané výsledky) vícekrát, přičemž si pamatují jejich stav a návratový bod z předchozího volání. V některých jazycích mohou být koprocedury reprezentovány speciálním druhem funkce nazývané generátor . Generátor je funkce, která si pamatuje, kde byl předchozí návrat, a při dalším vyvolání pokračuje v práci z místa přerušení.
Většina iterátorů je přirozeně popsána pomocí generátorů, a protože si generátory mezi voláními zachovávají svůj aktuální stav, dobře se hodí pro složité iterátory, jejichž implementace vyžaduje složité datové struktury k zapamatování aktuální pozice v kolekci, jako je například procházení stromu .
Příklad generátoru, který vrací Fibonacciho čísla pomocí operátoruyield Python :
def fibonacci (): a , b = 0 , 1 while True : výnos a # return a, + zapamatujte si, kde restartovat další volání a , b = b , a + b pro číslo ve Fibonacci (): # Použijte generátor jako číslo tisku iterátoruObvyklý odkaz na proměnné , které tvoří řadu , se provádí jejich počtem. V tomto případě se adresa požadované proměnné vypočítá jako: "adresa 1. proměnné" + "velikost proměnné" x "číslo sady". Se sekvenčním přístupem k takovým proměnným můžete získat významný nárůst výkonu, pokud adresu další proměnné vypočítáte z adresy předchozí. K tomu slouží posuvník. Typ proměnných, které tvoří řadu, ke které se bude postupně přistupovat, se nazývá referenční typ posuvníku a počet proměnných v sérii, o které se posuvník po každém takovém přístupu posune, se nazývá krok posuvníku. . Krok posuvníku je dán jako celočíselná konstanta. Pokud není krok posuvníku při deklaraci pohledu zadán, považuje se krok za rovný 1.
Jazyk C++ široce využívá iterátory v STL , který podporuje několik různých typů iterátorů, včetně 'jednosměrných iterátorů', 'obousměrných iterátorů' a ' iterátorů s náhodným přístupem'. Všechny standardní šablony typu kontejneru implementují různorodou, ale konzistentní sadu typů iterátorů. Syntaxe standardních iterátorů je podobná jako u ukazatelů v běžném jazyce C , kde se operátory a *používají ->k určení prvku, na který iterátor ukazuje, a aritmetické operátory ukazatelů, jako je ++, se používají k přesunutí iterátoru na další prvek.
Iterátory se obvykle používají ve dvojicích, z nichž jeden se používá k označení aktuální iterace a druhý se používá k označení konce kolekce. Iterátory se vytvářejí pomocí příslušných tříd kontejnerů pomocí standardních metod, begin()jako je end(). Funkce begin()vrací ukazatel na první prvek a vrací ukazatel na end() imaginární neexistující prvek následující za posledním.
Když iterátor přejde za poslední prvek, podle definice se to rovná speciální koncové hodnotě iterátoru. Následující příklad ukazuje typické použití iterátoru:
std :: list < int > C ; // Namísto std::list for ( std :: list < int >:: iterator it = C . begin (), end = C . end (); it != end ; ++ lze použít jakýkoli standardní kontejner STL it ) { //pro měnitelný iterátor * it = 8 ; // prvek, na který ukazuje iterátor, lze změnit } for ( std :: list < int >:: const_iterator it = C . begin (), end = C . end (); it != end ; ++ it ) { //pokud nepotřebujete upravovat prvky std :: cout << * it << std :: endl ; }Existuje mnoho druhů iterátorů, které se liší svým chováním: jednosměrné, reverzní (reverzní) a obousměrné iterátory; vstupní a výstupní iterátory; const iterators (chrání kontejner nebo jeho prvky před modifikací). Ne každý typ kontejneru však podporuje některý z těchto typů iterátorů. Uživatelé mohou vytvářet své vlastní typy iterátorů definováním podtříd založených na standardu std::iterator.
Bezpečnost použití iterátoru je definována samostatně pro různé typy standardních kontejnerů; v některých případech iterátor umožňuje změny kontejneru během iterace.
Implicitní iterace je také částečně podporována C++ prostřednictvím standardních šablon funkcí jako std::for_each()[1] a std::accumulate()[2] . Při použití musí být inicializovány pomocí existujících iterátorů, obvykle begin a end , které definují rozsah iterace, ale pro další iteraci nesmí existovat žádná explicitní definice iterátorů. Následující příklad ukazuje použití for_each.
ContainerType < ItemType > C ; // Libovolný typ kontejneru standardní položky ItemType void ProcessItem ( const ItemType & I ) // Funkce, která zpracovává každou položku v kolekci { std :: cout << I << std :: endl ; } std :: for_each ( C.begin ( ) , C. end ( ), ProcessItem ) ; // Zobrazit smyčkuNevýhodou této metody je nemožnost deklarovat tělo cyklu uvnitř, což vyžaduje někde deklarovat ukazatel funkce nebo funktor a předat jej jako argument. To lze částečně kompenzovat použitím knihovny, jako je Boost , a použitím funkce lambda k implicitnímu vytvoření funktorů s podobnou syntaxí operátoru infix. Pouze s ohledem na to musí taková knihovna provádět určité operace stanovenými způsoby.
Počínaje standardem C++11 lze iterátory používat implicitně ve smyčce fora poskytují funkce pro iteraci všech prvků kontejneru:
#include <vektor> #include <iostream> int main ( void ) { std :: vector < int > v ; v . push_back ( 1 ); v . push_back ( 2 ); v . push_back ( 3 ); for ( auto e : v ) { std :: cout << e << std :: endl ; // Vytiskne hodnotu každého prvku } návrat 0 ; }Rozhraní, které bylo představeno ve verzi JDK 1.2 jazyka Java , poskytuje iteraci tříd kontejnerů. Každý implementuje a volitelně podporuje . Iterátory jsou vytvářeny odpovídajícími třídami kontejnerů, obvykle pomocí . java.util.IteratorIteratornext()hasNext()remove()iterator()
Metoda next()posune iterátor na další hodnotu a vrátí zadanou hodnotu iterátoru. Při prvním vytvoření iterátor ukazuje na speciální hodnotu před prvním prvkem, takže první prvek lze načíst až po prvním volání next(). Testovací metoda se používá k určení, kdy byly iterovány všechny prvky v kontejneru hasNext(). Následující příklad ukazuje jednoduché použití iterátorů:
Iterátor iter = seznam . iterátor (); //Iterator<MyType> iter = list.iterator(); v J2SE 5.0 while ( iter . hasNext ()) System . ven . println ( iter.next ( ) );U kolekce typů, která to podporuje, metoda iterátoru remove()odstraní z kontejneru poslední „navštívený“ prvek. Téměř všechny ostatní typy úprav kontejneru během iterace jsou nebezpečné.
Má také java.util.Listpodobné java.util.ListIteratorAPI, ale umožňuje iteraci vpřed a vzad, což poskytuje určení aktuálního indexu v seznamu a přesun na prvek podle jeho pozice.
S vydáním J2SE 5.0 bylo představeno rozhraní pro Iterablepodporu vylepšeného foreach pro iteraci kolekcí a polí. definuje metodu , která vrací . Pomocí vylepšené smyčky lze předchozí příklad přepsat jako forIterableiterator()Iteratorfor
for ( MyType obj : list ) System . ven . tisknout ( obj );Iterátory v .NET Framework se nazývají 'enumerátory' a jsou reprezentovány příponou IEnumerator. IEnumeratorimplementuje metodu MoveNext(), která se přesune na další prvek a indikuje, zda bylo dosaženo konce kolekce; vlastnost Currentse používá k získání hodnoty zadaného prvku; volitelná metoda Reset()vrátí enumerátor do původní polohy. Enumerátor zpočátku ukazuje na speciální hodnotu před prvním prvkem, takže MoveNext()pro zahájení iterace je nutné volání.
Enumerátory jsou obvykle předávány voláním metody na GetEnumerator()objektu, který implementuje IEnumerable. Toto rozhraní obvykle implementují třídy kontejnerů. Výraz foreach v C# však může pracovat s jakýmkoli objektem, který takovou metodu podporuje, i když neimplementuje IEnumerable. Obě rozhraní byla rozšířena v generických verzích .NET 2.0 .
Následující příklad ukazuje jednoduché použití iterátorů v C# 2.0:
// 'explicitní' verze IEnumerator < MyType > iter = list . GetEnumerator (); while ( iter . MoveNext ()) Konzole . WriteLine ( iter . Aktuální ); // 'implicitní' verze foreach ( hodnota MyType v seznamu ) Console . WriteLine ( hodnota );C# 2.0 také podporuje generátory : metodu deklarovanou jako vratnou IEnumerator(nebo IEnumerable), ale používající výraz „ “ (flexibilní návrat) yield returnk vytvoření sekvence prvků namísto vracení entity objektu, přeloží kompilátor na novou třídu, která implementuje odpovídající rozhraní.
Iterátory v Pythonu jsou nedílnou součástí jazyka a v mnoha případech se používají implicitně ve výrazu for( vyhledávací smyčka ), při manipulaci se seznamy a ve výrazech generátoru . Všechny standardní typy smyček, které jsou součástí jazyka Python, podporují iteraci, stejně jako mnoho tříd, které jsou součástí . Následující příklad ukazuje typickou implicitní iteraci se smyčkou:
pro hodnotu v pořadí : tisk ( hodnota )Slovníky Pythonu (druh asociativního pole ) lze také iterovat přímo a vracet klíče slovníku. Nebo lze metodu položek slovníku iterovat, když dokončí přidružený klíč a hodnota tohoto páru je n-tice:
pro klíč ve slovníku : hodnota = slovník [ klíč ] tisk ( klíč , hodnota ) pro klíč , hodnota ve slovníku . položky (): tisk ( klíč , hodnota )Iterátory však lze použít a specifikovat explicitně. Pro jakýkoli výčtový typ smyčky nebo třídy vytvoří vestavěná funkce iter()iterátor. Iterátor implementuje metodu next(), která vrací další prvek v kontejneru. Pokud nezbývají žádné další prvky, zobrazí se chyba StopIteration. Následující příklad ukazuje vhodnou iteraci smyčky pomocí explicitních iterátorů:
it = iter ( sekvence ) while True : try : value = it . další () kromě StopIteration : break print ( value )V následujícím příkladu pro Python 2.4 (a novější) je iterátorem samotný souborový objekt f, který k souboru přistupuje jako posloupnost řetězců:
f = otevřít ( "README" ) # otevřít soubor tisk ( f . další ()) # další hodnota iterátoru je další řádek tisku souboru ( součet ( len ( řádek ) pro řádek v f )) # součet délek všech ostatních řádků souboruJakákoli vlastní třída může podporovat standardní iteraci (explicitní nebo implicitní) při definování metody __iter__(), která vytváří iterátor. Iterátor pak potřebuje definici metody next(), která vrátí další prvek. Stojí za to pochopit rozdíl mezi iterovatelným objektem (objekt, ze kterého funkce iter()vrací iterátor) a iterátorem (objekt, který má metodu __next__).
Generátory jazyka Python implementují protokol pro tuto iteraci.
PHP 4 představilo konstrukce look-loop v Perlu a některých dalších. To vám umožní procházet pole jednoduchým způsobem. V PHP 4 funguje vyhledávací smyčka pouze s poli a při pokusu o její použití s proměnnými různých typů nebo neinicializovanými proměnnými vyvolá chybu.
V PHP5 umožňuje vyhledávací smyčka iteraci objektů přes všechny veřejné členy.
K tomu existují dvě syntaxe, přičemž druhá je malým, ale velmi užitečným rozšířením té první.
Příklad A
<?php foreach ( array_expression as $value ) echo " $value ; \n " ; ?>Příklad B
<?php foreach ( array_expression as $key => $value ) echo "( $key ) $value ; \n " ; ?>Příklad A iteruje pole předané do array_expression. Při každém průchodu smyčkou je hodnota aktuálního prvku přiřazena proměnné $valuea ukazatel vnitřního pole se přesune na další prvek (takže při další iteraci smyčky „uvidíte“ další prvek).
Příklad B demonstruje podobnou funkcionalitu uvedenou výše. Ale doplňuje to tím, že klíčová hodnota aktuálního prvku (v tomto případě array_expression) bude přiřazena proměnné $keypři každém průchodu smyčkou.
PHP umožňuje během iterace měnit obsah pole, k čemuž stačí zadat, že hodnota $value bude získána jako reference (podle PHP), tedy jako &$value.
<?php $arr = pole ( 1 , 2 , 3 , 4 , 5 ); foreach ( $arr as & $value ) $value ++ ; // zvýší každou hodnotu o jednu // nyní $arr obsahuje hodnoty: 2,3,4,5,6 ?>V PHP 5 je rozhraní Iteratorpředdefinováno a objekty lze upravit tak, aby řídily iteraci.
<?php class MyIterator implementuje Iterator { private $var = array (); public function __construct ( $array ) { if ( is_array ( $array )) { $this -> var = $array ; } } public function přetočit () { echo " přetočit zpět \n " ; reset ( $this -> var ); } public function current () { $var = current ( $this -> var ); echo "aktuální: $var\n " ; return $var ; } veřejný funkční klíč () { $var = klíč ( $this -> var ); echo "klíč: $var\n " ; return $var ; } public function next () { $var = next ( $this -> var ); echo "další: $var\n " ; return $var ; } public function valid () { $var = $this -> aktuální () !== false ; echo "správně: { $var } \n " ; return $var ; } } ?>Tyto metody jsou plně využívány v celém cyklu prohlížení foreach($obj AS $key=>$value). Metody iterátoru se provádějí v následujícím pořadí:
1.rewind() ("přechod") 2. while valid() { 2.1 current() v $value 2.3 key() v $key 2.4 další() }Předchozí příklad lze značně zjednodušit použitím rozhraní IteratorAggregate, které nutí vývojáře implementovat pouze jednu metodu getIterator().
<?php class MyIterator implementuje IteratorAggregate { private $var = array (); public function __construct ( pole $array ) { // kontrolu typu provádí interpret: __construct(pole $pole) $this -> var = $pole ; } public function getIterator () { return new ArrayIterator ( $this -> var ); } } ?>Iterátory v jazyce XL jsou zobecněním generátorů a iterátorů.
import IO = XL . ui _ ŘÍDICÍ PANEL . _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ // Všimněte si, že není potřeba samostatná deklarace I, protože 'var out' je deklarováno v iterátoru // Implicitní deklarace I jako celého čísla se vyskytuje níže pro I v 1 .. 5 cyklu IO . NapišteLn " Já = " , jáIterátory v jazyce ActionScript 3 jsou zabudovány do samotného jazyka a jsou podporovány příkazy foreach a for...in . Z jazykového hlediska jsou pole a instance dynamických tříd iterátory:
var obj : Object = { prop1 : "a" , prop2 : "b" , prop3 : "c" }; // další smyčka "proběhne" všechny klíče (názvy vlastností) objektu obj for ( var name : String in obj ) trace ( name ); // další smyčka "proběhne" všechny hodnoty vlastností obj foreach ( var val :* in obj ) trace ( val ); }Standardní knihovna Haskell definuje třídu typu Traversable [3] [4] :
třída ( Functor t , Foldable t ) => Traversable t where traverse :: Aplikativní f => ( a -> f b ) -> t a -> f ( t b )Zde t je nějaký polymorfní typ (možná kontejner nebo kolekce ), f je "zobrazený" typ (například I/O, explicitní změna stavu nebo možnost chyby). "traverse" je specializace funktoru a fold , která je vyjádřena v kontextu (záhlaví) třídy.
Například pro binární strom lze metodu „procházení“ definovat takto:
Strom dat a = Prázdný | list a | Uzel ( Strom a ) a ( Strom a ) instance Traversable Tree traverz f Prázdný = čistý Prázdný traverz f ( List x ) = List <$> f x traverz f ( Uzel l k r ) = Uzel <$> traverz f l <*> f k <*> traverz f rPříklad použití:
-- | Vytiskněte obsah každého uzlu stromu. printTree tree = procházet stromem tisku -- | Tato funkce vezme nějakou binární funkci g a strom, projde strom, aplikuje g na každý uzel (druhý argument -- je požadován ze standardního vstupu) a vrátí upravený strom. CombinedWithStdin :: ( Přečíst c ) => ( a -> c -> b ) -> Strom a -> IO ( Strom b ) CombinedWithStdin g = procházet kombinovat kde kombinovat x = g x <$> readLn {- Příklad: strom = uzel (uzel (list 3) 6 (list 9)) 10 (uzel (list 9) 0 prázdný) $ combiWithStdin (+) strom > 10 > 20 > 30 > 40 > 50 > 60 $ Uzel (Uzel (List 13) 26 (List 39)) 50 (Uzel (List 59) 60 Prázdný) -}Na základě metod třídy typu „Traversable“ můžete sestavit své vlastní funkce se specifickou strategií procházení.
Od verze 6.12 kompilátoru GHC byla zavedena rozšíření "-XDeriveFunctor" "-XDeriveFoldable" a "-XDeriveTraversable", která automaticky vytvářejí instance příslušných tříd typu. Příklad:
Strom dat a = Prázdný | list a | Uzel ( Strom a ) a ( Strom a ) odvození ( Funktor , Skládací , Traversovatelný )