3.5. Iterátor

Obsah

3.5.1. Provedení akce nad všemi prvky kolekce
3.5.2. Úlohy k řešení

Iterátor představuje další abstraktní datový typ, jehož účelem je obecná reprezentace pozice v nějaké kolekci. Umožňuje zobecnit algoritmus procházení všemi prvky kolekce tak, aby nebyl závislý na konkrétní implementaci kolekce. Například pokud pro reprezentaci kolekce použijeme indexovaného pole, může iterátor uchovávat kromě odkazu na samotnou kolekci také index aktuálního prvku. V případě reprezentace kolekce vázaným seznamem prvků může místo indexu iterátor uchovávat zase ukazatel nebo referenci na aktuální prvek seznamu.

Kolekce dovedou poskytnout iterátor nastavený na začátek a umožňující průchod kolekcí směrem vpřed, např. v případě kolekcí v Javě je to operace

Iterator iterator();
která je součástí rozhraní Collection a vrací objekt implementující rozhraní iterátoru.

Mohou ale nabízet i iterátor nastavený na konec a umožňující pohyb směrem zpět, případně obecný pohyb v obou směrech. Iterátor může být také výsledkem operace vyhledání prvku v kolekci, kdy po úspěšném vyhledání umožní např. vyhledaný prvek z kolekce odstranit.

Jednosměrný iterátor může poskytovat následující rozhraní:

interface Iterator { 
	boolean hasNext(); 
	Object next(); 
}

Operace hasNext() testuje, zda se na pozici iterátoru nachází další prvek. Operace next() přesune iterátor na následující prvek a vrátí referenci na tento prvek. Ovšem pozor, pokud se v kolekci další prvek nenachází a zavoláme operaci next(), pak bude generována výjimka.

V případě obousměrného iterátoru, jenž umožňuje i přesun od konce kolekce k jejímu začátku, mohou být navíc k dispozici obdobné operace hasPrevious() a previous().

Ukažme si nyní na opakovaném zadání příkladu typický postup pro průchod všemi prvky kolekce pomocí iterátoru.

Příklad 3.7.
Vytvořte statickou funkci, která projde pomocí iterátoru zadanou kolekcí prvků a vypíše je na standardní výstup.

Tato funkce nyní díky použití iterátoru není závislá na tom, o jaký typ kolekce se jedná. Můžeme ji tedy zapsat obecně pro libovolný objekt implementující rozhraní Collection.

static void print(Collection coll) { 
   Iterator it = coll.iterator(); 
   System.out.print("[ "); 
   while( it.hasNext() ) { 
      Object obj = it.next(); 
      System.out.print(obj + " "); 
   } 
   System.out.println("]"); 
}

Iterátor se obvykle implementuje současně s kolekcí, pro kterou je určen, neboť může ke své činnosti využívat i těch vnitřních proměnných kolekce, které jsou jinak uživateli nedostupné. K tomu nabízí Java velmi užitečnou konstrukci, kterou jsou vnitřní třídy. Jedná se o třídy deklarované jako prvky jiných tříd, k jejichž instancím se navážou při vytvoření a k jejichž atributům a metodám mají přímý přístup.

Příklad 3.8.
Implementujte jednosměrný iterátor k výše uvedené třídě ArrayList.

Tento iterátor musí mít k dispozici kromě odkazu na kolekci také index aktuálního prvku, na který je nastaven. Do třídy ArrayList tedy doplníme chybějící metodu iterator() a vnitřní třídu ArrayListIterator, jejíž instanci metoda iterator() vrátí:

  public Iterator iterator() 
  { 
  	return new ArrayListIterator(); 
  } 
 
  protected class ArrayListIterator implements Iterator { 
  	 
    public Object next() 
    { 
      assert _current < _size : "Neni dalsi prvek"; 
      return _data[_current++]; 
    } 
 
    public boolean hasNext()  
    { 
      return _current < _size; 
    } 
 
    int _current = 0; // aktuální pozice 
  }   

Je zřejmé, že pokud by během práce s takto definovaným iterátorem nastala v kolekci nějaká změna a změnilo se například pořadí prvků, ovlivní to i hodnoty, které bude iterátor vracet. O takovém iterátoru se říká, že je nestabilní. Naproti tomu stabilní iterátor je na změnách kolekce nezávislý, což můžeme například zajistit tím, že kolekci při vytvoření iterátoru okopírujeme a pracujeme dále jen s kopiemi. Na tuto vlastnost je třeba si dát dobrý pozor, neboť pro některé algoritmy může být stabilita iterátoru podstatná.