C++ Kurs

Iteratoren

Die Themen:

Ein Iterator ist ein Objekt, welches zum Zugriff auf ein Elememt innerhalb einer Datenmenge dient . Eine solche Datenmenge kann z.B. ein Standard-Container oder auch ein Stream sein.

Iterator-Kategorien

Input-Iterator

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 z.B. ein solch reiner Input-Iterator.

Output-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.

Forward-Iterator

Der Forward-Iterator ist eine Kombination aus Input- und Output-Iterator. Auch er kann nur sequentiell vorwärts bewegt werden, erlaubt jetzt aber das Lesen und Schreiben von Daten.

Bidirektionaler Iterator

Der bidirektionale Iterator erweitert die Fähigkeiten des Forward-Iterators um die Möglichkeit, dass er sowohl vorwärts als auch rückwärts sequentiell bewegt werden kann. Solche bidirektionalen Iteratoren haben wir im letzten Kapitel schon bei den Listen, Sets und Maps kennengelernt.

Random-Access Iterator

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.

Iterator Operationen

Die nachfolgenden Tabellen enthalten alle Operationen die mit dem jeweiligen Iterator möglich sind. In der Tabelle gilt, dass ein Iterator alle Operationen des darüber stehenden 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.

Input-Iteratior
*iter aktuelles Element auslesen
iter->member Member des aktuellen Elements lesen
++iter, iter++ ein Element vorwärts
iter1 != iter2
iter1 == iter2
Iteratoren vergleichen
DTYP(iter) Kopierkonstruktor
Output-Iterator
*iter = <wert> aktuelle Element beschreiben
++iter, iter++ ein Element vorwärts
DTYP(iter) Kopierkonstruktor
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
iter -= n
Iterator um n erhöhen/vermindern
iter+n
n+iter
iter-n
Liefert den um n erhöhten/verminderten Iterator
iter1 < iter2
iter1 <= iter2
iter1 > iter2
iter1 >= iter2
Iteratoren vergleichen
HinweisWenn Sie einen Iterator inkrementieren bzw. dekrementieren, so sollten Sie im Regelfall die ++iter bzw. --iter Operation gegenüber der Operation iter++ bzw. iter-- vorziehen. Die ++iter bzw. --iter Operation arbeitet etwas effektiver als ihr Gegenstück.
HinweisBei vielen Standard-Containern können Sie auf die Verwendung von Iteratoren verzichten wenn Sie den Container sequentiell durchlaufen wollen. Hierfür eignet sich die range-for Schleife wesentlich besser. Damit Sie für einen Standard-Container die range-for Schleife verwenden können, muss der Container die Memfunktionen begin() und end() besitzen.

const-Iteratoren

Angenommen, wir wollen eine Template-Funktion für die Ausgabe der in einem Container abgelegten Elemente schreiben. Dann würde wahrscheinlich ein erster Versuch hierfür in etwa wie nachfolgend angegeben aussehen.

PgmHeadertemplate <typename T>
void PrintContainer(const T& cont)
{
  typename T::iterator iter;  // Das geht nicht!
  for (iter=cont.begin(); iter!=cont.end(); ++iter)
    cout << *iter << endl;
}

Doch irgendetwas stimmt an dieser Funktion noch nicht ganz. Als Parameter wurde der Funktion eine Referenz auf einen konstanten Container übergeben, aber der in der Funktion definierte Iterator würde prinzipiell auch Schreiboperationen auf den Container zulassen. Wenn der Inhalt eines Containers konstant ist, so muss ein entsprechender const-Iterator verwendet werden, der nur Lesezugriffe über den Iterator zulässt.

PgmHeadertemplate <typename T> void PrintContainer(const T& cont)
{
  typename T::const_iterator iter;  // Ok
  for (iter=cont.begin(); iter!=cont.end(); ++iter)
    cout << *iter << endl;
}

Iterator-Funktionen

Mit Hilfe der Funktion advance(iter,n) kann ein Input-Iterator iter um n Positionen vorwärts bewegt werden. Ist iter ein bidirektionaler oder Random-Access Iterator, so kann n auch negative Werte annehmen, um den Iterator rückwärts zu bewegen.

PgmHeader// 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.

PgmHeader// 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 mittels iter_swap(iter1,iter2) auch noch zwei Elemente vertauscht werden, deren Positionen über Forward-Iteratoren definiert sind.

PgmHeader// Erstes und letztes Element tauschen
list<int> myList;
iter_swap(myList.begin(),--myList.end());
HinweisWie Sie aus den Beispielen vielleicht entnommen haben, können Sie immer einen bidirektionalen oder Random-Access Iterator angeben, wenn ein Forward-, Output- oder Input-Iterator erforderlich ist.

Iterator-Adapter

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 die Wirkungsweise der Iterator-Adapter nachvollzogen werden kann, werden wir die Behandlung 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 dest);

Der copy-Algorithmus kopiert aus einem Container die Elemente im Bereich [first...last) in einen anderen Container ab der Position dest. 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.

PgmHeader// Zwei Container definieren/initialisieren
using cType = std::deque<int>;
cType cont1 {1,2,3,4,5,6};
cType cont2 {11,22,33};
// 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 using-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.

Reverse-Iterator

Mit Hilfe 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.

PgmHeader// Zwei Container definieren/initialisieren
using cType = std::deque<int>;
cType cont1 {1,2,3,4,5,6};
cType cont2 {11,22,33};
// 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

Insert-Iteratoren

Während 'normale' Iteratoren die bisherigen Elemente in einem Container überschreiben, fügen Insert-Iteratoren (auch Inserter genannt) die neuen Elemente 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.

AchtungSelbstverständlich muss der Container die Funktionalität bereitstellen, 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.

front_inserter

Der front_inserter dient zum Einfügen von Elementen am Beginn eines Containers. Der Aufruf der Memberfunktion front_inserter(container) erzeugt einen entsprechenden front_inserter Iterator, der immer auf den Beginn des Containers container verweist. Der Grund dafür, dass der Inhalt des Quell-Containers cont2 im nachfolgenden Beispiel in umgekehrter Reihenfolge an den Anfang des Ziel-Containers cont1 kopiert wird liegt darin, dass die Elemente aus cont2 nacheinander ausgelesen werden und jeweils an den Anfang des Containers cont1 eingefügt werden.

PgmHeader// 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 dient, wie unschwer zu erraten ist, dazu, Elemente ans Ende eines Containers anzufügen. Hier stehen die Elemente des Quell-Containers natürlich in der ursprünglichen Reihenfolge am Ende des Ziel-Containers.

PgmHeader// 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.

PgmHeader// Container-Definitionen wie oben
...
// Mit front inserter einfügen
std::copy(cont2.begin(), cont2.end(), std::inserter(cont1,cont1.begin()+2));
Inhalt von cont1 nach dem Kopieren:
1 2 11 22 33 3 4 5 6

HinweisIn den obigen Beispielen wurden beim Aufruf des copy-Algorithmus immer die vereinfachten Iterator-Definitionen verwendet. Die explizite Definition eines Iterators sieht folgendermaßen aus:

using cType = std::deque<int> cType;    // Synonym fuer Containertyp
std::front_insert_iterator<cType> fiter(container);
std::back_insert_iterator<cType>  biter(container);
std::insert_iterator<cType>       iiter(container,pos);

Stream-Iteratoren

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- als 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 C-String del (Typ ist const char*) voneinander getrennt werden. 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 schon erfahren haben, ist der Bezeichner value_type ein Synonym für den Datentyp der Elemente im Container.

PgmHeader// 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> consoleIter(cout,", ");
// Container cont1 in Datei übertragen
std::copy(cont1.begin(), cont1.end(), fileIter);
// Container auf Standardausgabe
std::copy(cont1.begin(), cont1.end(), consoleIter);
// Gleichbedeutend mit
std::copy(cont1.begin(), cont1.end(), std::ostream_iterator<int>(cout,", "));

Das Gegenstück, der istream_iterator

istream_iterator<DTYP> 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.

PgmHeader// 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 ist darauf zu 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 im nächsten Kapitel nochmals den Funktionsobjekten zu.

Wenn Sie wollen, können Sie 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.