Naar inhoud springen

Iterator

Uit Wikipedia, de vrije encyclopedie

Een iterator is een gestandaardiseerde manier om de elementen van een datacontainer te doorlopen. Iterator staat bekend als een ontwerppatroon in de categorie gedrag (behaviour).

Dit bespaart de gebruiker van een container het schrijven van foutgevoelige code.

De elementen van een array doorlopen is niet moeilijk, een eenvoudige for-loop lost het op zoals bij dit voorbeeld in C++.

 // declaraties en definities
 #define ARRAYLENGTE 100
 MijnKlasse array[ARRAYLENGTE];

 // elders in de code
 for (int teller= 0; teller<ARRAYLENGTE; teller++)
 {
    doe_iets_met(array[teller]);
 }

Om in plaats van een array een andere datastructuur te gebruiken, bijvoorbeeld een tree of een hashtable, wordt deze eenvoudige loop ineens veel ingewikkelder. Dit kost de programmeur werk, en wat nog belangrijker is, het is foutgevoelig.

Ook moet de programmeur zich verdiepen in de precieze werking van de container in kwestie. Bovendien is het lastig in een later stadium te kiezen voor een andere container omdat dan alle code herschreven moet worden die de elementen doorloopt.

Hier een zo beknopt mogelijk voorbeeld voor het doorlopen van een binary tree.

 // declaraties en definities
 MijnTree tree;
 
 void doorloopTree(MijnTree *subtree)
 {
     if (subtree==NULL) return;
 
     doorloopTree(subtree->leftBranch);
     doe_iets_met(*subtree->object);
     doorloopTree(subtree->rightBranch);
 }
 
 // elders in de code
 doorloopTree(&tree);

Voor andere soorten containers geldt weer een andere doorlooplogica. Als van een iterator gebruik wordt gemaakt, wordt de gebruiker van de container hiervan afgeschermd. Onderstaand voorbeeld gebruikt een iterator waarvan de doorlooplogica in de container zelf opgeslagen ligt. De iterator wordt in dit geval ook wel een cursor genoemd.

 // declaraties en definities
 MijnContainer container;
 
 // elders in de code
 for (MijnCursor cursor= container.getCursor(); 
      !container.isDone(cursor); 
      container.next(cursor))
 {
     doe_iets_met(*container.getObject(cursor));
 }

Het leuke aan bovenstaand voorbeeld is dat de programmeur helemaal niet hoeft te weten hoe de container in elkaar zit, een array, hash-table, een tree, een linked list, het is allemaal eender. Wijzigingen in de container deren niet, want de interface blijft dezelfde. De gebruikte Engelstalige methodenamen in bovenstaand voorbeeld (getCursor, isDone, next, getObject) zijn tamelijk gangbaar.

Een cursor is een variant van een iterator die minder vaak toegepast wordt. Meestal wordt de doorlooplogica in de iterator zelf gezet. Voordeel hiervan is dat een andere manier van doorlopen (bijvoorbeeld van achter naar voren) gebruikt kan worden zonder de container aan te hoeven passen.

Dit geeft meer flexibiliteit. De code ziet er bijna hetzelfde uit als het in het vorige voorbeeld, alleen zijn hier de methodes member van de iteratorklasse, en de factory-methode 'getCursor()' ontbreekt.

 // declaraties en definities
 MijnContainer container();
 
 // elders in de code
 for (MijnIterator iterator(container); !iterator.isDone(); iterator.next())
 {
     doe_iets_met(*iterator.getObject());
 }

Iterators worden gebruikt bij tal van containerbibliotheken in veel verschillende programmeertalen. In veel programmeertalen zijn iterators zelfs dermate grondig geïntegreerd dat er een 'for'- of 'foreach'-constructie bestaat die automatisch iterators gebruikt. Dit is onder andere het geval in C++, C#, Java en Visual Basic.

Implementatie-overwegingen

[bewerken | brontekst bewerken]
  • Voor het implementeren van een tweede soort iteratie (bijvoorbeeld van achter naar voren) kan een bestaande iterator gebruikt worden die dan in twee modes kan werken. Beter is het echter om in dat geval een tweede iterator te maken.
  • Een iterator die de doorloopcode bevat kan het beste afgeleid worden van een iteratorklasse of interface die friend is van de containerklasse. Dan hoeven er in de container geen public methodes voor de toegang gedefinieerd te worden.
  • Het staat de bouwer van de iterator vrij om naast de standaardinterface nog andere methodes toe te voegen zoals 'previous()'. Dit is dan echter niet polymorf met andere iteratoren.