Iterator

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

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

[bewerk] Uitleg

Stel je hebt een array waarvan je de elementen wilt doorlopen. Dat 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]);
}

Als je nu in plaats van een array een andere datastructuur wilt 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 geld 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 je 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.

Meer flexibiliteit dus. 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());
}

[bewerk] Gebruik

Iterators worden gebruikt bij tal van containerbibliotheken. De STL in C++ gebruikt ze intensief. Microsoft heeft in zijn Visual Basic zelfs een commando 'ForEach' dat gebruik maakt van een standaard interface om containers te doorlopen. Ook de Javabibliotheek gebruikt iterators voor zijn containers. In C# en .NET zijn iterators zelfs dermate grondig geintegreerd in taal en framework dat 'foreach' automatisch laat itereren over objecten die de interface IEnumerable implementeren.

[bewerk] Implementatie-overwegingen

• 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. Het is echter een veel betere gewoonte om een nieuwe iterator te maken met een toepasselijke naam.
• 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.

Bron(nen):

Erich Gamma - Richard Helm - Ralph Johnson - John Vlissides, Design patterns, Addison Wesley, 1995.