Een iterator is een object dat gebruikt wordt om de elementen van een (sequentiële) container te "overlopen", of "elk om beurt te behandelen".
t uitschrijft:
void print(int t[], int n) { // of int *t
for (int i=0; i<n; i++)
cout << t[i] << endl;
}
Het aantal elementen n moet als parameter meegegeven worden, omdat in C++ een tabel
zelf zijn grootte niet kent.
Dit kan herschreven worden met een schuivende pointer:
void print(int *t, int n) {
for (int i=0; i<n; i++) {
cout << *t << endl;
t++;
}
}
Dit is zeker geen verbetering aangezien zowel i als t verhoogd (opgeschoven)
moeten worden.
Deze versie is beter:
void print(int *t, int n) {
int *end = t + n; // wijst VOORBIJ einde tabel
while (t < end) {
cout << *t << endl;
t++;
}
}
De truc zit er hem in dat je eerst een eindpointer berekent, die net VOORBIJ het laatste
element van de tabel wijst.
Een volgende stap is dat de procedure de eindpointer niet zelf berekent, maar direct als argument meekrijgt i.p.v. de lengte:
void print(int *begin, int *end) {
for (int *p = begin; p < end; p++)
cout << *p << endl;
}
ofwel
void print(int *begin, int *end) {
while (begin < end) {
cout << *begin << endl;
begin++;
}
}
Om een tabel t van lengte n af te drukken roept men dus
print(t, t+n) op.
Merk op dat dit algoritme ook geldig is wanneer n==0, dankzij de keuze
om de eindpointer voorbij het laatste element te laten wijzen.
Het koppel begin, end bepaalt een (sub)range of (sub)reeks, i.e. een deel van
de volledige tabel.
Omdat begin wel nog tot de reeks behoort, en end niet, zou men dit wiskundig
als een gesloten-open interval kunnen voorstellen: [begin, end[. In de informaticawereld
noteert men dit echter als [begin, end).
Twee ontaarde gevallen: [t, t+n) is de volledige tabel t, en [t, t)
is een ledige reeks.
struct knoop {
int data;
knoop *volgende;
};
Bij een klassieke enkelgelinkte lijst spreekt men af dat voor het laatste element van een lijst geldt: laatste.volgende==0, en manipuleert men de lijst via zijn "koppointer", de pointer naar
de eerste knoop. De lijst is "leeg" indien de koppointer 0 is.
Een lijst (met koppointer) l kan dan afgedrukt worden door:
void print(knoop *l) { // l is koppointer
while (l != 0) {
cout << l->data << endl;
l = l->volgende;
}
}
Dit algoritme is niet handig om slechts een gedeelte van de lijst af te drukken.
Men kan beter expliciet de eindpointer als argument meegeven:
void print(knoop *begin, knoop *end) { // begin is koppointer
while (begin != end) {
cout << begin->data << endl;
begin = begin->volgende;
}
}
(waarbij l vervangen werd door begin).
Om een lijst l volledig af te drukken roept men dan print(l,0) op.
print-versie voor tabellen met die voor gelinkte lijsten.
Je ziet dat ze zeer sterk op elkaar gelijken.
Drie verschillen:
< versus != in de while-voorwaarde
*begin versus begin->data
begin++ versus begin=begin->volgende
!=
i.p.v. < schrijven.
Beide andere verschillen kunnen weggewerkt worden door een iterator
voor de gelinkte lijst te maken die wijst naar een knoop uit de lijst.
Dankzij operator overloading kan men ervoor zorgen dat een
iterator een normale pointer imiteert: opschuiven door operator++,
waarde teruggeven door operator*, vergelijken door operator!=:
struct intlistiterator {
knoop *k; // iterator wijst naar knoop k
intlistiterator(knoop *k_) { k = k_; } // constructor
void operator++() { k = k->volgende; } // naar volgende : "iteratie"
int operator*() { return k->data; } // waarde : "dereferentie"
};
bool operator!=(intlistiterator it1, intlistiterator it2) { return it1.k!=it2.k; }
(opm. dit is een simplificatie!)
Het algoritme om een gelinkte lijst af te drukken kan hiermee geschreven worden als
void print(intlistiterator begin, intlistiterator end) { // begin is koppointer
while (begin != end) {
cout << *begin << endl;
begin++;
}
}
Deze versie is identiek aan die voor tabellen, op de datatypes van de argumenten na!!
Nog frappanter wordt het indien men een inttabeliterator definieert door:
typedef int *inttabeliterator;Dankzij templates kan men ook dit probleem oplossen. De uiteindelijke versie luidt:
template <class IT>
void print(IT begin, IT end) { // begin is koppointer
while (begin != end) {
cout << *begin << endl;
begin++;
}
}
Deze versie werkt zowel voor int-tabellen (met IT == int*) als voor gelinkte lijsten van int's (met IT == intlistiterator),
en zelfs voor containers met andere soorten elementen (bv. tabel van double).
Besluit: door het concept iterator in te voeren heeft men ervoor gezorgd dat het print-algoritme voor verschillende soorten containers werkt. Men kan hetzelfde doen voor alle algoritmes die containerelementen sequentieel overlopen (bv. zoeken, sommeren, ...)
Dankzij iteratoren zijn containers en algoritmen van elkaar losgekoppeld. Men moet dus niet elk algoritme voor elke containerklasse specializeren.
vector<T>, list<T>, deque<T>
enz., waarbij template-parameter T het type van de elementen bepaalt.
Elke containerklasse definieert zijn eigen iteratortype:
vector<T>::iterator, list<T>::iterator, deque<T>::iterator, enz.
Zoals hierboven beschreven gedragen deze iteratoren zich als "smart pointers".
Elke container bevat methodes begin() en end() die iteratoren
teruggeven naar het eerste element en VOORBIJ het laatste element van de container.
Voorbeeld:
list<double> l;
// ... vul op
list::iterator it = l.begin();
while (it != l.end()) {
cout << *it << endl;
it++;
}
Indien men een container op verschillende manieren wil overlopen kan men verschillende
iteratorklassen maken. Zo voorzien de meeste containers een reverse_iterator
om de elementen in omgekeerde volgorde te doorlopen.
De "beginpointer" wijst dan naar het laatste element, de "eindpointer" VOOR het eerste element, en de
operator++ keert terug naar het vorige!
De containers voorzien hiertoe lidfuncties rbegin() en rend().
[W. Schepens sept. 2003, sept. 2006]