Iterator-Kategorien
const-Iteratoren
Iterator-Funktionen
Iterator-Adapter
Stream-Iteratoren
Input-Iteratoren erlauben nur Lesezugriffe und können nur sequentiell vorwärts bewegt werden. Einmal gelesene Elemente können nicht erneut gelesen werden. Reine Input-Iteratoren kommen selten vor. Ein Iterator mit dessen Hilfe von der Standard-Eingabe (i.d.R. Tastatur) eingelesen wird, ist ein solch reiner Input-Iterator.
Er ist das Gegenstück zum Input-Iterator, erlaubt nur Schreibzugriffe und kann ebenfalls nur sequentiell vorwärts bewegt werden. Auch reine Output-Iteratoren kommen eher selten vor. Als Beispiel für einen solchen reinen Output-Iterator mag ein Iterator dienen, der auf die Standardausgabe (i.d.R Bildschirm) schreibt. Auch wenn über den gleichen Iterator zweimal der gleiche 'Wert' geschrieben wird, so erscheint z.B. auf dem Bildschirm das geschriebene Datum zweimal.
Der Forward-Iterator ist eine Kombination aus Input- und Output-Iterator. Auch er kann nur sequentiell vorwärts bewegt werden, jetzt aber lesend und schreibend.
Der bidirektionale Iterator erweitert die Fähigkeiten des Forward-Iterators um die Möglichkeit, sequentiell sowohl vorwärts wie auch rückwärts bewegt werden zu können. Solche bidirektionalen Iteratoren haben Sie in der letzten Lektion schon bei den Listen, Sets und Maps kennen gelernt.
Der flexibelste Iterator ist der Random-Access Iterator. Er kann nicht nur sequentiell bewegt werden sondern gestattet es auch, durch eine entsprechende Additionen bzw. Subtraktionen eines Wertes den Iterator beliebig zu verschieben.
Die nachfolgende Tabelle enthält alle Operationen die mit dem jeweiligen Iterator möglich sind. In der Tabelle gilt, dass ein Iterator alle Operationen des darüber liegenden Iterators plus seine eigenen Operationen erlaubt, d.h. ein bidirektionaler Iterator enthält alle Operationen eines Forward-Iterators, der wiederum alle Operationen eines Input- und Output-Iterators enthält.
|
|
||||||||||||||||||||
Forward-Iteratior |
|
iter1 = iter2 |
Zuweisung |
DTYP() |
Standard-Konstruktor |
Bidirektionaler Iterator
|
|
--iter, iter-- |
Ein Element zurück |
Random-Access Iterator
|
|
iter[n] |
Zugriff auf Element pos+n |
iter += n |
Iterator um n erhöhen/vermindern |
iter+n |
Liefert den um n erhöhten/verminderten Iterator |
iter1 < iter2 |
Iteratoren vergleichen |
|
|
Angenommen, Sie wollen eine Template-Funktion für die Ausgabe der in einem Container abgelegten Elemente schreiben. Dann würde mit Ihrem bisherigen Wissen die Funktion in etwa wie nachfolgend angegeben aussehen.
 template <typename T> void PrintContainer(const T& cont)
{
typename T::iterator iter; // FEHLER!
for (iter=cont.begin(); iter!=cont.end(); ++iter)
cout << *iter << endl;
}
|
Doch irgend etwas stimmt an dieser Funktion noch nicht ganz. Als Parameter übergeben Sie der Funktion eine Referenz auf einen konstanten Container. Aber der in der Funktion definierte Iterator würde prinzipiell auch Schreiboperationen auf den Container zulassen.
Wenn ein Container konstant ist, so muss auch der Iterator auf diesen Container konstant sein. Dazu stellte die Standard Bibliothek entsprechende const-Iteratoren zur Verfügung, die nur Lesezugriffe über den Iterator zulassen.
template <typename T> void PrintContainer(const T& cont)
{
typename T::const_iterator iter; // Ok
for (iter=cont.begin(); iter!=cont.end(); ++iter)
cout << *iter << endl;
}
|
Mithilfe der Funktion advance(iter,n) kann ein Input-Iterator iter um n Positionen vorwärts verschoben werden. Ist iter ein bidirektionaler oder Random-Access Iterator, so kann n auch negative Werte annehmen um den Iterator rückwärts zu verschieben.
// Listen-Iterator (bidirektional!) list<DTYP>::iterator iter; // Um vier Positionen vorwärts advance(iter,4); // Um fünf Positionen zurück advance(iter,-5); |
Um die Anzahl der Elemente in einem Bereich, der durch zwei Input-Iteratoren definiert ist, zu bestimmen, wird die Funktion distance(iter1,iter2) verwendet. Sie können diese Funktion z.B. dazu verwenden, um zu erfahren, an wievielter Stelle ein Element in einem Container steht. Geben dazu Sie für den ersten Parameter einfach den Iterator begin() an.
// Iteratoren initialisieren std::set<...>::iterator lowerPos = ...; std::set<...>::iterator upperPos = ...; // Anzahl der Elemente im Bereich [lowerPos,upperPos) ausgeben cout << distance(lowerPos,upperPos) << endl; |
Und zu guter Letzt können Sie mittels iter_swap(iter1,iter2) auch noch zwei Elemente vertauschen, deren Positionen über Forward-Iteratoren definiert sind.
// Erstes und letztes Element tauschen
list<int> myList;
iter_swap(myList.begin(),--myList.end());
|
|
|
Obwohl Iterator-Adapter erst im Zusammenhang mit den später beschriebenen Algorithmen so richtig Sinn machen, werden Sie an dieser Stelle aufgeführt, um das Thema Iteratoren zusammenhängend zu beschreiben. Damit Sie die Wirkungsweise der Iterator-Adapter nachvollziehen können, werden wir die Beschreibung eines einfachen Algorithmus, des copy-Algorithmus, vorziehen. Der copy-Algorithmus hat folgende Deklaration:
| template<class InputIterator, class OutputIterator> OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result); |
Der copy-Algorithmus kopiert aus einem Container die Elemente im Bereich [first...last) in einen anderen Container ab der Position result. Hierbei muss der Ziel-Container aber groß genug sein, um die kopierten Elemente auch aufnehmen zu können. Die Deklaration des copy-Algorithmus ist in der Header-Datei algorithm enthalten.
// Felder für Initialisierung der Container int array1[] = {1,2,3,4,5,6}; int array2[] = {11,22,33}; // Zwei Container definieren/initialisieren typedef std::deque<int> cType; cType cont1(array1, array1+sizeof(array1)/sizeof(int)); cType cont2(array2, array2+sizeof(array2)/sizeof(int)); // 2. Container in 1. Container umkopieren std::copy(cont2.begin(), cont2.end(), cont1.begin()); Inhalt von cont1 nach dem Kopieren:
11 22 33 4 5 6
|
Im Beispiel wird der komplette Container cont2, also von cont2.begin() bis ausschließlich cont2.end(), an den Anfang des Containers cont1 kopiert. Der Datentyp der beiden Container wird über eine typedef-Anweisung festgelegt. Dies erleichtert uns gleich Definition der Iterator-Adapter.
Nach dem wir uns jetzt die Grundlage geschaffen haben, können wir zu den Iterator-Adaptern übergehen.
Alle Iterator-Adapter (bis auf den Reverse-Iterator) sind in der Header-Datei iterator definiert und liegen im Namensraum std. Der Reverse-Iterator dagegen gehört immer zum entsprechenden Container auf den er angewandt wird.
Mithilfe des Reverse-Iterators wird der Inhalt eines Containers in umgekehrter Reihenfolge durchlaufen. Wird z.B. der copy-Algorithmus aus dem obigen Beispiel mit Reverse-Iteratoren für die Bereichsangabe aufgerufen, so wird der Inhalt des Containers cont2 in umgekehrter Reihenfolge in den Container cont1 kopiert.
// Felder für Initialisierung der Container int array1[] = {1,2,3,4,5,6}; int array2[] = {11,22,33}; // Zwei Container definieren/initialisieren typedef std::deque<int> cType; cType cont1(array1, array1+sizeof(array1)/sizeof(int)); cType cont2(array2, array2+sizeof(array2)/sizeof(int)); // 2. Container in 1. Container umkopieren std::copy(cont2.rbegin(), cont2.rend(), cont1.begin()); Inhalt von cont1 nach dem Kopieren:
33 22 11 4 5 6
|
Während 'normale' Iteratoren das bisherige Element in einem Container überschreiben, fügen Insert-Iteratoren (auch Inserter genannt) das neue Element in den Container ein. Aus diesem Grund sind über Inserter auch nur schreibende Operationen erlaubt
Die C++ Standard Bibliothek stellt drei verschiedene Inserter zur Verfügung: front_inserter, back_inserter und den allgemeinen inserter. Die Inserter verwenden dazu je nach Containertyp entsprechende Memberfunktionen.
|
|
front_inserter
Der front_inserter fügt die einzufügenden Elemente am Beginn des Containers ein. Der Aufruf der Memberfunktion front_inserter(container) erzeugt einen entsprechenden front_inserter Iterator, der auf den Beginn des Containers container verweist. Beachten Sie im nachfolgenden Beispiel, dass der Inhalt des Quell-Containers cont2 in umgekehrter Reihenfolge an den Anfang des Ziel-Containers cont1 kopiert wird. Dieses Verhalten liegt darin begründet, dass die Elemente aus cont2 nacheinander ausgelesen werden und jeweils an den Anfang des Containers cont1 eingefügt werden.
// Container-Definitionen wie oben ... // Mit front_inserter einfügen std::copy(cont2.begin(), cont2.end(), std::front_inserter(cont1)); Inhalt von cont1 nach dem Kopieren:
33 22 11 1 2 3 4 5 6
|
back_inserter
Der back_inserter fügt, wie unschwer zu erraten ist, die Elemente ans Ende des Containers an. Hier stehen die Elemente des Quell-Containers natürlich in der ursprünglichen Reihenfolge am Ende des Ziel-Container.
// Container-Definitionen wie oben ... // Mit back_inserter einfügen std::copy(cont2.begin(), cont2.end(), std::back_inserter(cont1)); Inhalt von cont1 nach dem Kopieren:
1 2 3 4 5 6 11 22 33
|
Allgemeiner inserter
Der allgemeine Inserter inserter(container, pos) kann Elemente an beliebiger Position pos in den Container container einfügen.
// Container-Definitionen wie oben ... // Mit front inserter einfügen std::copy(cont2.begin(), cont2.end(), std::inserter(cont1,comt1.begin()+2)); Inhalt von cont1 nach dem Kopieren:
1 2 11 22 33 3 4 5 6
|
|
|
Nun folgt wahrscheinlich eines der Aha-Erlebnisse bei der Anwendung von Iteratoren. Die Stream-Iteratoren erlauben Algorithmen als Ziel bzw. Quelle einen Stream einzusetzen. Die C++ Standard-Bibliothek kennt sowohl ostream- wie auch istream-Iteratoren.
Der ostream_iterator
| ostream_iterator<DTYP> iter(ostream,del); |
überträgt Daten des Datentyps DTYP in den Ausgabestream ostream, wobei die einzelnen Daten durch den String del voneinander getrennt werden. del ist vom Typ const char*. Wird ein solcher Iterator als Ziel des copy-Algorithmus verwendet, so kann mit einer einzigen Zeile der komplette Inhalt eines Containers z.B. in eine Datei oder auf die Standardausgabe übertragen werden (siehe nachfolgendes Beispiel). Beachten Sie auch, wie der Datentyp DTYP festgelegt wird. Wie Sie weiter vorne ja schon erfahren haben, ist der Bezeichner value_type ein Synonym für den Datentyp der Elemente im Container.
// Datei öffnen std::ofstream outfile("container.dat"); // Iterator für Datei-Stream definieren, cType ist Datentyp des Containers std::ostream_iterator<cType::value_type> fileIter(outfile," "); // Iterator für Standardausgabe definieren std::ostream_iterator<cType::value_type> consolIter(cout,", "); // Container cont1 in Datei übertragen std::copy(cont1.begin(), cont1.end(), fileIter); // Container auf Standardausgabe std::copy(cont1.begin(), cont1.end(), consolIter); // Gleichbedeutend mit std::copy(cont1.begin(), cont1.end(), std::ostream_iterator<int>(cout,", ")); |
Das Gegenstück, der istream_iterator
| iostream_iteratorDTYP> iter(istream); |
liest Daten des Datentyps DTYP aus dem Eingabestream istream. Wird ein solcher Iterator als Quelle für den copy-Algorithmus verwendet, kann mit einer einzigen Zeile eine komplette Datei in einen Container übertragen werden. Das Ende einer Eingabe wird durch den End-of-Stream Iterator gekennzeichnet.
// Datei öffnen std::ifstream infile("container.dat"); // Iterator für Datei-Stream std::istream_iterator<cType::value_type> fileIter(infile); // End-of-stream Iterator std::istream_iterator<cType::value_type> eosIter; // Komplette Datei in Container einlesen std::copy(fileIter, eosIter, std::front_inserter(cont1)); |
Wird der istream_iterator als Quelle innerhalb des copy-Algorithmus eingesetzt, so müssen Sie darauf achten, dass der Ziel-Container auch alle Eingaben aufnehmen kann. Am sichersten fahren Sie hier, wenn Sie als Ziel einen der Inserter einsetzen, so wie im obigen Beispiel.
Damit beenden wird das Thema Iteratoren, ganz ohne weiteres Beispiel und Übung, und wenden uns in der nächsten Lektion nochmals den Funktionsobjekten zu.
Ach ja, wenn Sie wollen können Sie doch noch eine kleine Übung machen. Versuchen Sie einmal mit zwei Anweisungen von der Standard-Eingabe beliebig viele int-Werte einzulesen und diese in einer Datei abzulegen. Die erste Anweisung ist hierbei die Anweisung zum Öffnen der Datei. Hier können Sie sich einmal meine Lösung ansehen.
Wenn
Sie einen Iterator inkrementieren bzw. dekrementieren, so
sollten Sie im Regelfall die ++iter bzw. --iter Operation der
Operation iter++ bzw. iter-- vorziehen. Die ++iter bzw. --iter
Operation arbeitet etwas schneller als ihr Gegenstück.
Selbstverständlich
muss der Container die Funktionalität bereit stellen, die der
Inserter benötigt. So können Sie z.B. den front_inserter
nicht auf einen Vektor anwenden sondern nur auf ein Deque oder
eine Liste, da ein Vektor das Einfügen von Elementen am
Containeranfang nicht erlaubt.