C++-Programmierung/ Die STL/ Iteratoren
Ein besonders wichtiges Konzept in der STL sind die Iteratoren. Um maximale Flexibilität zu erreichen, arbeiten die Algorithmen der STL generell nicht direkt auf Containern, sondern greifen mittels Iteratoren auf die Container zu.
Ein Iterator ist einem Zeiger sehr ähnlich. Genaugenommen ist ein Iterator ein verallgemeinerter Zeiger, was im Umkehrschluss auch bedeutet, dass jeder Zeiger ein Iterator ist, wohingegen nicht jeder Iterator zwingend ein Zeiger sein muss.
Mit einem Iterator kann auf eine Datenstruktur in einem Datenverbund zugegriffen werden, ohne dies über einen Index der Datenstruktur zu tun. Die Zugriffe können dabei ohne Kenntnis der Datenstruktur erfolgen, was bei einem gewöhnlichen Zeiger nicht der Fall ist.
Eine Iteration beschreibt in der Informatik den schrittweisen, wiederholten (sequentiellen) Zugriff auf Elemente in einer Datenstruktur. Im folgenden Codebeispiel wird die Iteration über ein Feld aus elementarem Typen int durchgeführt:
#include <iostream>
int main(){
const int size = 4;
int array[size] = { 3, 5, 7, 11 };
for(
int* i = &array[0]; // alternativ: int* i = array;
i <= &array[size - 1]; // alternativ: i <= array + size - 1;
++i
){
std::cout << *i << ", ";
}
}
Hierbei fungiert der Zeiger i als Iterator. Allerdings ist diese Vorgehensweise aus vielerlei Gründen fehleranfällig. Außerdem ist sie sehr stark am verwendeten Datentyp orientiert.
Leider bietet C++ für die eingebauten Datentypen erst ab C++11 Abhilfe. Seit dieser Version gibt es im Header iterator die Funktionen std::begin() und std::end(). Sie liefern uns für jede Datenstruktur, die Iteratoren unterstützt, die Adressen des ersten Elements und des Elements, das hinter dem Letzten liegt. Das »hinter dem Letzten« klingt im ersten Moment vielleicht ein wenig verwirrend. Stellen Sie sich das ganze mal so vor:
+----+----+----+----+----+ | 3 | 5 | 7 | 11 | | +----+----+----+----+----+ ^ ^ ^ | | | begin iter end
Das »Element hinter dem letzten« Existiert natürlich nicht wirklich, aber solange wir es nicht zugreifen, können wir seine Adresse als Endpunkt für unsere iteration (also das durchlaufen der Werte) verwenden. Diese Herangehensweise erlaubt es uns, in dem obigen Beispiel, die -1 beim Vergleich wegzulassen und so statt des Kleiner-oder-gleich-Operators den Kleiner-als-Operator zu verwenden. Alternativ könnten wir außerdem den Ungleichheits-Operator benutzen, denn was wir ausdrücken wollen, ist ja eigentlich: Halte an, wenn alle Daten durchlaufen wurden, also der »Endpunkt« erreicht ist.
Eine weitere Vereinfachung erlaubt uns C++11 beim Datentyp des Operators, den kann der Compiler nämlich auch selbstständig ermitteln. Wir geben daher einfach auto als Datentyp an.
#include <iostream>
#include <iterator>
int main(){
int array[] = { 3, 5, 7, 11 };
for(
auto i = std::begin(array);
i != std::end(array);
++i
){
std::cout << *i << ", ";
}
}
Beachten Sie an dieser Stelle ganz besonders, dass der Vergleich mit dem Ungleichheits-Operator durchgeführt wird. Das ist typisch für Iteratoren, denn im Gegensatz zu Zeigern, muss für Iteratoren der Kleiner-als-Operator nicht deklariert sein. Da es sich bei unserem Iterator auch um einen Zeiger handelt, würde die Verwendung des Kleiner-als-Operators natürlich funktionieren, es wird jedoch empfohlen immer die allgemeinste mögliche Variante zu verwenden. Auf diese Weise müssen Sie den Code für die Schleife später nicht ändern, falls Sie für Ihre Daten eine andere Struktur (also einen anderen Datentyp) verwenden.
Um es kurz an einem Beispiel zu illustrieren, die STL bietet den Datentyp std::list an. Über dessen Vor- und Nachteile können Sie sich im Kapitel über die STL-Container informieren. Die von std::list verwendeten Iteratoren besitzen keinen Kleiner-als-Operator, daher müssten Sie den Quellcode der Schleife ändern, wenn die den Datentyp in std::list ändern.
#include <iostream>
#include <list>
int main(){
std::list< int > array = { 3, 5, 7, 11 };
for(
auto i = std::begin(array);
i != std::end(array);
++i
){
std::cout << *i << ", ";
}
}
Damit haben Sie die Grundlagen bezüglich der Verwendung eines gewöhnlichen Zeigers als Iterator. Ich möchte an dieser Stelle noch auf eine weitere Neuheit von C++11 hinweisen. Da die Verwendung dieser Art von Iteration sehr häufig vorkommt, wurde in C++11 die for-Schleife so erweitert, dass Sie eine Datenstruktur direkt Elementweise durchgehen können. Vielleicht kennen Sie dieses Konzept aus einer anderen Programmiersprache als foreach-Schleife.
#include <iostream>
#include <list>
int main(){
std::list< int > array = { 3, 5, 7, 11 };
for(auto const& i: array){
std::cout << i << ", ";
}
}
Das funktioniert mit allen Datentypen, für die die Funktionen std::begin() und std::end() definiert sind. Wenn in diesem Fall auto als Datentyp angegeben wird, ermittelt der Compiler den Datentyp der Container-Elemente, in diesem Fall also int. Das heißt, es wird für jeden Schleifendurchlauf eine Kopie des aktuellen Elements erzeugt, die dann im Schleifenkörper verwendet wird. Wir haben also exakt die gleiche Situation, wie bei einer Funktionsübergabe mittels Call-by-Value. Wir können den von auto ermittelten Datentyp aber mithilfe von const und & in eine Referenz auf einen konstanten Integer umbiegen.
Natürlich spielt es im Fall des eingebauten Datentyps int keine Rolle ob es sich um eine Referenz handelt, aber auf diese Weise können Sie auch später einen anderen Datentyp verwenden, ohne das Ihr Code langsamer wird. Außerdem ist es wichtig diese Eigenheit von auto immer im Hinterkopf zu haben, denn wenn Sie schreibend auf die Elemente zugreifen wollen, dann brauchen Sie zwingend eine Referenz und wenn Sie nur Lesezugriff wollen, dann sollten Sie in jedem Fall zumindest ein const anhängen, um den Schreibzugriff ausdrücklich zu verbieten.
Grundlegende Eigenschaften von Iteratoren
[Bearbeiten]Jedes Containerklassentemplate außer den Containeradaptern hat zugehörige Iteratortypentemplates.
Diese sind in folgende fünf Kategorien unterteilt:
- Eingabe-Iteratoren (
input_iterator) und Ausgabe-Iteratoren (output_iterator) - Forward-Iteratoren (
forward_iterator) - Bidirektionale Iteratoren (
bidirectional_iterator) - Random-Access-Iteratoren (
random_access_iterator)
Ein- und Ausgabe-Iteratoren, sowie Forward-Iteratoren können nur in eine Richtung durchlaufen werden. Während man einen Forward-Iterator allerdings beliebig oft dereferenzieren darf, um auf das Element dahinter zuzugreifen, ist dies bei den Ein- und Ausgabe-Iteratoren nur einmal pro Durchlauf gestattet. Wie die Namen bereits andeuten, darf man über Eingabe-Iteratoren nur lesend und über Ausgabe-Iteratoren nur schreibend zugreifen.
Bidirektionale Iteratoren können von Vorwärts und Rückwärts durchlaufen werden. Random-Access-Iteratoren bieten sogar sogenannten »wahlfreien Zugriff« an. Das bedeutet, man kann von einem gegeben Iterator aus nicht nur den direkten Vorgänger und Nachfolger zugreifen, wie beim bidirektionalen Iteratoren, sondern alle Vorgänger und Nachfolger.
Gewöhnliche Zeiger sind immer Random-Access-Iteratoren, denn wie Sie im ersten Beispiel dieses Kapitels bereits gesehen haben, kann ausgehend vom Zeiger auf das erste Element des Array direkt das letzte Element erreicht werden. Syntaktisch gibt es hierfür zwei Möglichkeiten. Zum einen kann die Anzahl der Elemente minus Eins zu dem Start-Iterator addiert werden, zum anderen kann auch der Indexoperator [] verwendet werden, der als Parameter ebenfalls die Anzahl der Elemente minus Eins erhält.
Generell gilt in der Liste mit den Iterator-Kategorien, ein Iterator der in die Kategorie N fällt, kann auch alles, was in den Kategorien darüber verlangt wird.
Das bedeutet also, ein Datentyp sollte immer Iteratoren bereitstellen, die möglichst weit unten in der Liste stehen, damit man viel mit ihnen machen kann. Ein Algorithmus sollte hingegen immer auf Iteratoren arbeiten, die möglichst weit oben in der Liste stehen, damit er auf möglichst viele Container-Typen angewandt werden kann.
Im folgenden kleinem Beispiel wollen wir den fill-Algorithmus aus <algorithm> verwendet, um alle Elemente zwischen den übergebenen Iteratoren auf einen bestimmten Wert zu setzen.
#include <vector>
#include <algorithm>
int main(){
std::vector< int > array(400); // Vektor mit 400 Einträgen vom Typ int
std::fill(array.begin(), array.end(), 7); // Alle Elemente auf 7 setzen
}
Der fill-Algorithmus verlangt mindestens Forward-Iteratoren. std::vector stellt Random-Access-Iteratoren zur Verfügung, erfüllt also deutlich mehr, als hier zwingend nötig wäre. Auch std::list ist mit seinen bidirektionalen Iteratoren noch überqualifiziert und kann daher auf die gleiche Weise verwendet werden.
Beachten Sie, dass die Verwendung der STL-Algorithmen schneller sein kann, als eine Äquivalente for-Schleife. Abhängig vom tatsächlichen Typ der Iteratoren können die STL-Algorithmen unter Umständen optimierte Implementierungen verwenden, die der Compiler bei einer for-Schleifen-Version nicht finden würde.
Auch die Zeiger eines gewöhnlichen Arrays können natürlich verwendet werden, denn sie erfüllen ja die Anforderungen eines Random-Access-Iterators. An dieser Stelle sei noch einmal ausdrücklich auf die Änderungen hingewiesen, die C++11 mit sich bringt. Im Beispiel von eben wurden die Methoden array.begin() und array.end() verwendet. In C++11 sollte man stattdessen die Template-Funktionen std::begin() und std::end() verwenden. Diese sind so implementiert, dass sie die gleichnamigen Methoden aufrufen, haben aber den Vorteil, dass sie auch bei Angabe eines gewöhnlichen Array als Parameter funktionieren. Das Beispiel sieht in C++11 also so aus:
#include <vector>
#include <algorithm>
int main(){
std::vector< int > array(400);
std::fill(std::begin(array), std::end(array), 7);
}
Da wir std::vector verwenden, wäre es in diesem Fall natürlich noch sinnvoller, den entsprechenden Konstruktor zu verwenden, um alle Elemente mit dem Wert 7 zu initialisieren. Im folgenden Beispiel werden wir den Container mit 7 initialisieren und anschließend fill verwenden, um die Elemente mit den Indizes 5 bis 12 auf 42 zu setzen.
#include <vector>
#include <algorithm>
int main(){
std::vector< int > array(400, 7); // 400 Werte mit 7 initialisieren
std::fill(
std::begin(array) + 5, // Werte 5 bis 12
std::begin(array) + 12,
42 // auf 42 setzen
);
}
Wie Sie sehen, wird mit Hilfe des Plus-Operators vom ersten Iterator des Containers auf einen entfernten Nachfolger zugegriffen. Dies funktioniert nur bei Random-Access-Iteratoren, Sie können in diesem Beispiel also keine std::list verwenden! Dies hat nichts mit dem fill-Algorithmus zu tun, sondern kommt ausschließlich durch die Verwendung des Plus-Operators zu Stande. Sie werden im nächsten Kapitel noch lernen, wie man unter Verwendung anderer STL-Algorithmen auch in dieser Situation eine Version schreiben kann, die nur Forward-Iteratoren verlangt.
Die Art, wie in diesem Fall die Werte gesetzt werden, macht ein wenig Bauchschmerzen. Stellen Sie sich vor, der Fillaufruf würde innerhalb einer Funktion stattfinden und diese würde als Parameter den Start- und End-Index erhalten. Sie können sich sicher vorstellen, dass es leicht passieren kann, dass der zweite versehentlich kleiner als der erste ist. In diesem Fall geraten wir in eine Endlosschleife. Besser wäre es, nur den Start-Iterator anzugeben und dann die Anzahl der Werte. Der fill_n-Algorithmus bietet genau das an.
#include <vector>
#include <algorithm>
int main(){
std::vector< int > array(400, 7); // 400 Werte mit 7 initialisieren
std::fill_n(std::begin(array) + 5, 7, 42); // ab Index 5, 7 Werten 42 zuweisen
}
Im Gegensatz zum fill-Algorithmus verlangt std::fill_n übrigens nur Output-Iteratoren. Er lässt sich daher noch für einen sehr interessanten Zweck verwenden: Die Kombination mit einem Ausgabe-Stream!
#include <iostream>
#include <iterator>
#include <algorithm>
int main(){
std::ostream_iterator< double > iterator(std::cout, "; ");
std::fill_n(iterator, 5, 0.3);
}
0.3; 0.3; 0.3; 0.3; 0.3;
Ein std::ostream_iterator ist ein Output-Iterator, der bei jedem Schreibzugriff den erhaltenen Wert auf den im Konstruktor übergebenen Ausgabe-Stream schreibt und optional noch einen – ebenfalls im Konstruktor übergebenen – Separator anhängt.
Iteratoren im Detail
[Bearbeiten]Wie bereits erwähnt gibt es verschiedene Iterator-Kategorien. Je nachdem, welcher Kategorie ein Iterator angehört, können unterschiedliche Operationen auf ihnen ausgeführt werden.
Allgemeine Eigenschaften
[Bearbeiten]Die quasi definierende Eigenschaft von Iteratoren ist, dass sie inkrementiert werden können. Das bedeutet, dass der Iterator in der Sequenz eine Position weitergesetzt wird. Einen Iterator am Ende eines Containers kann man natürlich nicht inkrementieren, da ja keine weitere Position folgt. Allerdings ist nicht garantiert, dass der Versuch eine Fehlermeldung liefert. Meist wird, wenn nicht gerade eine Debugging-Version der STL verwendet wird, aus Gründen der Effizienz darauf verzichtet, solche Fehler in der STL abzufangen. Deshalb führen solche Fehler im Programm in der Regel zu unvorhersehbarem Verhalten; im schlimmsten Fall sieht es in Tests so aus, als ob das Programm funktionieren würde, beim tatsächlichen Einsatz des Programms tritt aber schwerwiegendes Fehlverhalten auf. Deshalb sollten solche Fehler in jedem Fall vermieden werden.
Iteratoren können sowohl mit dem Präinkrement- als auch mit dem Postinkrement-Operator inkrementiert werden:
template<typename Iterator>
void foo(Iterator i){
Iterator j, k;
j = ++i;
k = i++;
}
Zeigt i ursprünglich z.B. vor das Element 1, führt die erste Zuweisung dazu, dass sowohl i als auch j nun vor Element 2 zeigen. In der zweiten Zuweisung wird i ebenfalls ein Element weitergesetzt (zeigt also hinterher vor Element 3), aber an k wird weiterhin der alte Wert zugewiesen (k zeigt also auf Element 2).
Die zweite wichtige Eigenschaft, die allen Iteratoren gemeinsam ist, ist die Möglichkeit, diese zu dereferenzieren. Dies geht über den Ausdruck *iter. Voraussetzung ist wiederum, dass es sich nicht um den Iterator aufs Ende der Sequenz handelt. Allerdings zeigen sich hier schon Unterschiede zwischen den Kategorien: Bei Ausgabeiteratoren kann an diesen Ausdruck nur zugewiesen werden. Eingabeiteratoren erlauben nur das Lesen dieses Ausdrucks. Alle anderen Iteratoren erlauben sowohl das Lesen als auch das Schreiben. Beispiel:
template<typename OutputIterator, typename InputIterator>
void iter_assign(OutputIterator ziel, InputIterator quelle){
*ziel = *quelle;
}
Die dritte wichtige Eigenschaft von Iteratoren ist die Möglichkeit, sie zu vergleichen. Insbesondere ist der Vergleich mit einem Iterator, der bekanntermaßen aufs Ende einer Sequenz zeigt die einzige Möglichkeit, einen Iterator aufs Ende einer Sequenz zu erkennen. Hier gibt es bereits die erste Überraschung: Ausgabeiteratoren unterstützen keinen Vergleich! Man kann also insbesondere nicht testen, ob ein Ausgabeiterator das Ende einer Sequenz erreicht hat. Es liegt also immer in der Verantwortung dessen, der einen Algorithmus auf Ausgabeiteratoren aufruft, darauf zu achten, dass nicht über dessen Grenzen hinaus geschrieben wird.
Alle anderen Iteratoren können mittels operator==() und operator!=() verglichen werden. Algorithmen können insbesondere feststellen, ob sie das Ende einer Sequenz erreicht haben, indem sie den Iterator mit dem Ende-Iterator vergleichen, den der Aufrufer zur Verfügung gestellt hat. Die Tatsache, dass das Sequenzende getrennt übergeben wird erlaubt es, Algorithmen problemlos auch auf Teilsequenzen anzuwenden (beispielsweise nur die erste Hälfte der Elemente eines Arrays zu sortieren).
Zudem ist allen Iteratoren gemeinsam, dass man sie kopieren und zuweisen kann. Außerdem kann man alle Iteratoren per Default-Konstruktor erzeugen. Bei den meisten Iteratoren erhält man damit einen "singulären Wert", mit dem man nichts weiter machen kann; das einzige, was man in der Regel mit einem so erzeugten Iterator machen kann, ist ihm einen neuen Wert zuzuweisen (selbst das Vergleichen mit anderen Iteratoren ist möglicherweise nicht erlaubt!).
Ein- und Ausgabeiteratoren
[Bearbeiten]Die im vorigen Abschnitt beschriebenen Eigenschaften gelten im Wesentlichen für alle Iteratoren. Allerdings hat jede Iteratorkategorie ihre ganz spezifischen Eigenschaften. Die Kategorien sind dabei nicht unabhängig voneinander, sondern bauen aufeinander auf.
Ein- und Ausgabeoperatoren haben nur die oben beschriebenen Fähigkeiten. Hinzu kommen aber zusätzliche Einschränkungen. Eine Sequenz eines reinen Ein- oder Ausgabeoperators darf nur einmal durchlaufen werden. Das bedeutet, dass auf ein bestimmtes Element nur einmal zugegriffen werden kann, je nach Iteratorkategorie lesend oder schreibend. Sobald auf das nächste Element zugegriffen wird, werden alle Iteratoren auf das alte Element ungültig. Der folgende Code ist also nicht zulässig:
template<typename OutputIterator>
void output(OutputIterator ziel){
*ziel = 1; // Ok
*ziel = 2; // Fehler: Zweimal auf dasselbe Element zugreifen ist nicht erlaubt!
++ziel; // Ok
*ziel = 3; // Ok
OutputIterator kopie = ziel; // Ok
++ziel; // Ok
*ziel = 4; // Ok
++kopie; // Fehler: kopie ist jetzt ungültig
}
Bei Input- und Outputiteratoren sollten Elementzugriff (also Dereferenzieren und anschließendes Lesen bzw. Zuweisen) und Inkrementieren immer abwechselnd erfolgen, also beispielsweise
*ziel = 1:
++ziel;
*ziel = 2;
++ziel;
aber nicht
*ziel = 1;
++ziel;
++ziel;
*ziel = 2;
Der Ausdruck *iter++ = a (Ausgabeiterator) bzw. a = *iter++ (Eingabeiterator) ist hingegen explizit erlaubt.
Der Grund für diese Einschränkungen liegt darin, dass der Iterator nicht unbedingt auf eine Speicherstruktur zugreifen muss. Beispielsweise kann ein Eingabeiterator von einem Hardware-Gerät lesen, und ein erneuter Leseversuch würde bereits das nächste Zeichen holen. Analog kann ein Ausgabeiterator seine Zeichen an ein Gerät versenden, das es nicht erlaubt, einen einmal gesendeten Wert noch einmal zu verändern.
Vorwärtsiteratoren
[Bearbeiten]Die nächste Iterator-Kategorie sind die Vorwärtsiteratoren. Vorwärtsiteratoren sind sowohl Eingabe- als auch Ausgabeiteratoren. Zusätzlich erlauben sie, eine Sequenz mehrfach zu durchlaufen und Elemente zu überspringen. Die Codebeispiele aus dem letzten Abschnitt sind also für Vorwärtsiteratoren alle zulässig.
Vorwärtsiteratoren sind beispielsweise die passenden Iteratoren für einfach verkettete Listen (eine solche ist nicht im Standard, wird aber z.B. von der SGI-STL zur Verfügung gestellt). In einer einfach verketteten Liste ist es kein Problem, zu einem Element das Nächste zu finden (der Knoten enthält ja bereits einen Zeiger auf dieses). Allerdings ist es nicht möglich, einfach auf das vorherige Element zuzugreifen.
Bidirektionale Iteratoren
[Bearbeiten]Die nächste wichtige Iteratorkategorie sind die bidirektionalen Iteratoren. Bidirektionale Iteratoren sind Vorwärtsiteratoren, die zusätzlich erlauben, in der Sequenz rückwärts zu gehen. Hierfür wird sinnvollerweise der Dekrement-Operator verwendet:
template<typename BidirectionalIterator>
void foo(BidirectionalIterator iter){
++iter; // setzt iter eine Position weiter
--iter; // nun zeigt iter wieder auf dieselbe Position wie am Anfang
}
Selbstverständlich sind auch hier sowohl Prädekrement- als auch Postdekrement-Operator erlaubt.
Bidirektionale Iteratoren werden zum Beispiel in std::list und std::set verwendet.
Iteratoren mit wahlfreiem Zugriff
[Bearbeiten]Schließlich gibt es noch die Iteratoren mit wahlfreiem Zugriff. Dies ist die mächtigste Iteratorklasse. Es handelt sich um bidirektionale Iteratoren, die zusätzlich erlauben, in beliebig großen Schritten in der Sequenz zu springen. Dies wird durch arithmetische Operatoren und den Index-Operator ermöglicht:
template<typename RandomAccessIterator>
void foo(RandomAccessIterator iter){
iter += 3; // äquivalent zu ++iter, ++iter, ++iter;
iter -= 2; // äquivalent zu --iter, --iter;
*(iter + 2) = 7; // äquivalent zu tmp=iter, tmp+=2, *tmp = 7;
*(iter - 1) = 8; // äquivalent zu tmp=iter, --tmp, *tmp = 8;
iter[3] = 4; // äquivalent zu *(iter + 3) = 4;
}
Da Iteratoren mit wahlfreiem Zugriff auch Ausgabeiteratoren sind, können sie selbstverständlich mit operator==() und operator!=() verglichen werden. Sofern sie in dieselbe Sequenz (also z.B. in denselben Vektor) zeigen, können sie zusätzlich auch mit den Operatoren operator<(), operator<=(), operator>() und operator>=() verglichen werden. Diese vergleichen die Positionen der Iteratoren in der Sequenz; i1 < i2 liefert also genau dann true, wenn i1 auf eine frühere Stelle in der Sequenz zeigt als i2.
Iteratoren mit wahlfreiem Zugriff werden von std::vector und std::deque zur Verfügung gestellt.
Iterator-Traits
[Bearbeiten]Da Algorithmen als Templates realisiert werden, die über beliebige Iteratoren (einer bestimmten Klasse) funktionieren sollen ist es wichtig, dass der Algorithmus bestimmte Informationen über den Iterator erhalten kann. So kann es z.B. nötig sein, Werte, die vom Iterator geliefert werden, zwischenzuspeichern. Dafür muss der Typ dieses Wertes bekannt sein. Hierzu dienen die Iterator-Traits. Ein Beispiel:
template<typename OutputIterator>
set_to_default(OutputIterator iter){
typedef typename std::iterator:traits<OutputIterator>::value_type value_type;
*iter = value_type(); // Default-konstruiere ein value_type
}
Der Typ value_type ist hierbei der Typ der Objekte, auf die mit dem Iterator zugegriffen wird. Neben value_type gibt es noch die Typen reference (eine Referenz auf value_type), pointer (ein Zeiger auf value_type), difference_type (ein Typ, der den Abstand zweier Iteratoren speichern kann) und iterator_category (ein Typ, der die Kategorie des Iterators angibt).
Der Typ iterator_category erlaubt es, Algorithmen für verschiedene Iteratorkategorien zu überladen. Da Algorithmen als Templates definiert werden, ist dies ansonsten nicht möglich. (Die nächste Version des C++-Standards wird dies jedoch durch neue Sprachmittel ermöglichen.) Als Beispiel soll ein Algorithmus dienen, der zu zwei Iteratoren einen Iterator liefert, der genau in der Mitte zwischen zwei gegebenen Iteratoren liegt (bzw. falls die Anzahl gerade ist den letzten Iterator in der ersten Hälfte). Für diesen Algorithmus braucht man nur Vorwärts-Iteratoren. Allerdings kann er mit Random-Access-Iteratoren wesentlich effizienter implementiert werden. Zunächst die beiden Algorithmen, die die eigentliche Arbeit machen:
// Version für Vorwärtsiteratoren
template<typename ForwardIterator>
ForwardIterator internal_middle(ForwardIterator first, ForwardIterator last, std::forward_iterator_tag*){
ForwardIterator middle = first;
bool even_step = false;
while (first != last){
++first;
if(even_step) ++middle;
even_step = !even_step;
}
return middle;
}
template<typename RandomAccessIterator>
RandomAccessIterator internal_middle(
RandomAccessIterator first,
RandomAccessIterator last,
std::random_access_iterator_tag*
){
return first + (last - first)/2;
}
Die beiden Funktionen unterscheiden sich außer in der Implementierung auch im letzten Argument: Es handelt sich um einen Zeiger auf einen "Marker-Typ". Für jede Iterator-Kategorie gibt es einen eigenen "Marker-Typ". Das Überladen nach Iterator-Kategorie kann nun über die folgende Funktion simuliert werden, die dann vom Benutzer aufgerufen wird:
template<typename ForwardIterator>
ForwardIterator middle(ForwardIterator first, ForwardIterator last){
return internal_middle(
first,
last,
(typename std::iterator_traits<ForwardIterator>::iterator_category*)0
);
}
Wird nun middle mit Vorwärts-Iteratoren aufgerufen, so ist iterator_category ein typedef für forward_iterator_tag, weshalb die erste Version von internal_middle aufgerufen wird. Ruft man hingegen middle mit einem Iterator mit wahlfreiem Zugriff auf, ist iterator_category ein typedef für random_access_iterator_tag, und entsprechend wird die zweite Form von internal_middle verwendet.
Was aber passiert, wenn man einen bidirektionalen Iterator verwendet? Ein bidirektionaler Iterator ist ja auch immer ein Vorwärtsiterator, aber kein Iterator mit wahlfreiem Zugriff. Also sollte die erste Version von internal_middle aufgerufen werden. Dies ist in der Tat der Fall: std::bidirectional_iterator_tag ist von std::forward_iterator_tag abgeleitet, sodass die erste Version aufgerufen wird.
Wird middle hingegen mit einem reinen Eingabe- oder Ausgabe-Iterator aufgerufen, bekommt man eine Fehlermeldung. Das soll auch so sein, da ja der Algorithmus für solche Iteratoren nicht funktioniert.
Iterator-Adapter
[Bearbeiten]Iterator-Adapter sind spezielle Iteratoren, die ein Iterator-Interface für andere Iteratoren bereitstellen.
Rückwärtsiteratoren
[Bearbeiten]Bei bidirektionalen Iteratoren und Iteratoren mit wahlfreiem Zugriff kann die Sequenz in beide Richtungen durchlaufen werden. Algorithmen durchlaufen den übergebenen Bereich jedoch in der Regel immer vorwärts (wenngleich es Ausnahmen gibt). Deshalb gibt es Rückwärtsiteratoren, die eine gegebene Sequenz in umgekehrter Richtung durchlaufen. Die Reverse-Iteratoren werden über einen Iterator-Adapter definiert, aber normalerweise kommt man mit diesem nicht direkt in Berührung, da die Container praktischerweise den passenden Rückwärtsiterator-Typ als container::reverse_iterator zur Verfügung stellen. Zudem können über c.rbegin() und c.rend() die Grenzen der umgedrehten Sequenz abgerufen werden.
Es ist möglich, einen beliebigen Iterator in einen Rückwärtsiterator umzuwandeln. Jedoch ist hierbei eine Stolperfalle zu beachten: *reverse_iterator(iter) greift nicht auf dasselbe Element der Sequenz zu wie *iter, sondern auf das vorhergehende Element. Dies ist leicht zu verstehen, wenn wir uns das Bild von weiter oben wieder in Erinnerung rufen:
+---+---+---+---+---+---+---+ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | +---+---+---+---+---+---+---+ ^ ^ ^ | | | begin iter end
Der Ausdruck *iter greift auf das nachfolgende Element zu, also auf Element 4. Die umgedrehte Sequenz sieht aber folgendermaßen aus:
+---+---+---+---+---+---+---+ | 7 | 6 | 5 | 4 | 3 | 2 | 1 | +---+---+---+---+---+---+---+ ^ ^ ^ | | | rbegin riter rend
wobei rbegin = reverse_iterator(end), riter = reverse_iterator(iter) und rend = reverse_iterator(begin). Auch in der umgedrehten Sequenz zeigt der Iterator zwischen die Elemente 3 und 4. Hier ist aber das Element 3 das folgende Element, weshalb *riter auch auf dieses zugreift.
Das folgende Programm demonstriert dies noch einmal mit einem Vektor:
#include <iostream>
#include <ostream>
#include <vector>
int main(){
typedef std::vector<int> intvec;
intvec v(7);
for(int i = 0; i < 7; ++i)
v[i] = i + 1;
intvec::iterator iter = v.begin() + 3;
std::cout << *iter << std::endl; // gibt 4 aus
std::cout << *intvec::reverse_iterator(iter); // gibt 3 aus
}
Einfügeiteratoren
[Bearbeiten]Einfügeiteratoren erlauben es, neue Elemente in einen bestehenden Container einzufügen. Es gibt zwei verschiedene Adapter: insert_iterator erlaubt das Einfügen an einer vorgegebenen Stelle, back_insert_iterator fügt immer am Ende eines Containers ein. Um die Konstruktion solcher Iteratoren zu vereinfachen, gibt es die Hilfsfunktionen inserter und back_inserter. Ein Beispiel:
std::vector<int> v; // ein leerer Vektor
int array1[] = { 1, 2, 3 };
int array2[] = { 4, 5, 6 };
int array3[] = { 7, 8, 9 };
std::copy(array1, array1 + 3, std::back_inserter(v));
// jetzt: v = 1, 2, 3
std::copy(array2, array2 + 3, std::back_inserter(v));
// jetzt: v = 1, 2, 3, 4, 5, 6
std::copy(array3, array3 + 3, std::inserter(v, v.begin()+2);
// jetzt: v = 1, 2, 7, 8, 9, 3, 4, 5, 6
Stream-Iteratoren
[Bearbeiten]Stream-Iteratoren sind Iterator-Adapter, die es STL-Algorithmen erlauben, direkt auf Ein-/Ausgabestreams zu arbeiten. Stream-Iteratoren sind stets reine Eingabe- oder Ausgabeiteratoren.
Zur Eingabe dienen die Iterator-Typen std::istream_iterator<T> und std::istreambuf_iterator<C>. Ein istream_iterator benutzt zum Lesen des Streams die Eingabe-Operatoren (also is >> var), um Objekte des Typs T zu lesen. Deshalb kann er für jeden Typ definiert werden, für den ein Eingabe-Operator existiert. Ein istreambuf_iterator hingegen liest die Rohzeichen direkt aus den Stream-Puffer. Deshalb muss der Zeichentyp mit dem des Streams übereinstimmen (also z.B. char für std::cin und wchar_t für std::wcin). Der End-Iterator wird in beiden Fällen über den Default-Konstruktor definiert. Das Ende der Sequenz ist dann erreicht, wenn das Lesen eines weiteren Objekts vom angegebenen Typ fehlschlägt. Das kann bedeuten, dass das Dateiende erreicht wurde, aber auch, dass ein Fehler beim Lesen der Datei aufgetreten ist. Oder für istream_iterator, dass eine unpassende Zeichenkette aufgetreten ist (also z.B. beim Einlesen von int-Objekten eine Zeichenkette, die keine Zahl darstellt). Was der Grund ist, muss am Stream-Objekt überprüft werden.
Das folgende Beispiel liest eine Liste von Ganzzahlen aus der Standardeingabe in einen Vektor:
#include <iostream>
#include <iterator>
#include <vector>
int main(){
std::vector<int> v;
std::copy(
std::istream_iterator<int>(std::cin), // Lese ints von std::cin
std::istream_iterator<int>(), // Enditerator
std::back_inserter(v) // Ziel
);
}
Zur Ausgabe dienen die Typen std::ostream_iterator<T> und std::ostreambuf_iterator<C>. Ersterer benutzt wiederum die Ausgabeoperatoren, während der Zweite direkt auf den Rohdaten im Stream-Puffer arbeitet. Da es sich um reine Ausgabe-Iteratoren handelt, gibt es keine Ende-Iteratoren. Eine Besonderheit von std::ostream_iterator ist, dass man bei der Erzeugung zusätzlich zum Datenstrom, auf den die Objekte ausgegeben werden sollen, auch noch eine Zeichenkette angeben kann, die nach jedem Objekt ausgegeben wird.
Das folgende Beispiel liest Strings von der Standardeingabe und gibt sie jeweils in einer eigenen Zeile wieder auf der Standardausgabe aus:
#include <iostream>
#include <iterator>
#include <string>
int main(){
std::copy(
std::istream_iterator<std::string>(std::cin),
std::istream_iterator<std::string>(),
std::ostream_iterator<std::string>(std::cout, "\n")
);
}