[X] Aufbau der STL - Teil 2: Iteratoren und Algorithmen
-
Nachdem wir im ersten Teil der Artikelreihe erfahren haben, wie die STL große Datenmengen organisiert und verstaut, kann es nun mit dem zweiten Teil weitergehen, in dem es um die Frage geht, wie man auf die gespeicherten Daten zugreifen kann - und wie sie effektiv verarbeitet werden.
Inhalt
- Iteratoren
- Iterator-Kategorien
- Iterator-Adapter
- Iterator-Hilfsfunktionen
- Algorithmen
1 Iteratoren
Was nützen die besten Container, wenn man nicht problemlos auf ihren Inhalt zugreifen kann? Vektoren und Deques bieten freien Zugriff auf ihre Elemente, sodass es möglich ist, sich per Index durch ihre Daten durchzuhangeln. Allerdings ist es nicht möglich, effektiv auf einer Listen- oder Baumstruktur nach einem bestimmten Index zu suchen.
Am einfachsten wäre es, für jeden Containertyp eigene Zugriffsmethoden zu definieren, die die besonderen Fähigkeiten des jeweiligen Typs ausnutzen - allerdings würde dieser Ansatz die Austauschbarkeit der Containerklassen erschweren. Deshalb geht die STL einen anderen Weg. Jeder Container bringt seine eigene Iterator-Klasse mit. Diese bieten nach außen eine passende Schnittstelle zum Datenzugriff und sind in der Lage, sich korrekt durch die interne Struktur des Containers durchzuhangeln. Die möglichen Operationen auf Iteratoren sind ganz bewusst an die von blanken C-Pointern angelehnt, bieten jedoch im Allgemeinen deutlich "intelligenteres" Verhalten - damit kann man Iteratoren als eine Form von Smart Pointern betrachten.
2 Iterator-Kategorien
Je nach Fähigkeiten werden die verschiedenen Iteratoren in Kategorien eingeordnet. Bei der Einordnung der STL-Iteratoren in diese Kategorien wurde nicht nur darauf Wert gelegt, welche Operationen technisch möglich wären, sondern auch, dass die existierenden Operationen auch relativ schnell umgesetzt werden können - ein Vektor-Iterator kann in konstanter Zeit eine beliebige Position erreichen, ein Listen-Iterator würde lineare Zeit dafür benötigen, deshalb hat er keinen operator+=.
2.1 Output Iterator
Dies ist wohl der primitivste Iterator. Er kann lediglich Daten schlucken und inkrementiert werden, um im Speicher weiterzulaufen - dabei ist das Inkrementieren häufig als leere Operation implementiert und der operator= kümmert sich selber um die Beschaffung des Speichers oder die Weitergabe der empfangenen Daten. Es ist noch nicht einmal möglich, zwei gegebene Output-Iteratoren miteinander zu vergleichen oder festzustellen, ob das Schreiben in den Iterator erfolgreich war.
In diese Kategorie gehören zum Beispiel der Ostream-Iterator oder die Inserter.
2.2 Input Iterator
Diese Klasse ist ähnlich einfach aufgebaut wie die Output Iteratoren. Ein Input Iterator kann Werte ausgeben, inkrementiert werden und mit anderen Iteratoren verglichen werden. Dieser Vergleich hat in der Regel nur Sinn, um die Gültigkeit des Iterators zu kontrollieren.
Der C++-Standard garantiert übrigens nicht, dass Kopien eines Input-Interators unabhängig voneinander genutzt werden können, um denselben Datenvorrat zweimal einzulesen.Der wichtigste Input Iterator ist der Istream-Iterator. Im Hinblick auf seine Zugriffsmöglichkeiten auf die verarbeiteten Werte könnte man einen Set- oder Multiset-Iterator auch in diese Kategorie einordnen.
2.3 Forward Iterator
Ein Forward Iterator vereinigt in sich die Fähigkeiten von Output- und Input-Iterator. Er kann sowohl Daten lesen als auch schreiben und im Gegensatz zum Input-Iterator können sich verschiedene Kopien auch unabhängig voneinander durch die unterliegende Datenstruktur bewegen.
Achtung: Ein Forward Iterator kann nicht als vollwertiger Output Iterator eingesetzt werden, da er im Regelfall nur über eine begrenzt lange Sequenz iterieren kann:
//OK für Output Iterator //Laufzeitfehler für Forward Iterator while(true) *pos++ = getval(); //OK für Forward Iterator //Compilerfehler für Output Iterator while(pos!=end) *pos++ = getval();Die STL verwendet keine eigenen Forward Iteratoren, aber man könnte sie sich z.B. in einer einfach verketteten Liste gut vorstellen.
2.4 Bidirektionaler Iterator
Diese Klasse erweitert den Forward Iterator um die Fähigkeit, "rückwärts" zu laufen. Ein bidirektionaler Iterator kann sowohl inkrementiert als auch dekrementiert werden.
In diese Kategorie gehören die Iteratoren einer Liste und der assoziativen Container - wobei letztere den Schlüsselwert der iterierten Elemente nicht ändern dürfen.
2.5 Random Access Iterator
Random Access Iteratoren sind die mächtigste Kategorie von Iteratoren. Sie können beliebig durch die iterierte Struktur "springen". Zusätzlich zu Operationen, die ein bidirektionaler Iterator unterstützt, bieten sie auch Iterator-Arithmetik nach dem Vorbild der Pointer-Arithmetik von C - sie können um beliebige ganzzahlige Schrittweiten vorwärts und rückwärts durch den Speicher bewegt werden, den Abstand untereinander berechnen und mittels <,<=,>= und > verglichen werden.
In diese Kategorie fallen die Iteratoren eines Vektors oder Deque, aber auch die aus C bekannten Pointer.
3 Iterator Adapter
Adapter werden verwendet, um das Verhalten eines Iterators zu ändern. Sie werden auf eine andere Struktur aufgesetzt und ermöglichen es, diese über die bekannten Iterator-Methoden und -Operatoren zu modifizieren.
3.1 Insert Iteratoren
Inserter sind reine Output-Iteratoren und übersetzen Schreibzugriffe in insert()-Aufrufe des unterliegenden Containers. Mit ihrer Hilfe kann ein Container während der Arbeit erweitert werden. Auf diese Weise kann z.B. ein Algorithmus Werte in den Container einfügen, ohne sich um den verfügbaren Platz Sorgen machen zu müssen.
Außer einem normalen Insert-Iterator gibt es auch noch Back-Inserter (hängen die ankommenden Daten per push_back() an das Ende ihres Containers an) und Front-Inserter (hängen die Daten per push_front() an den Anfang des Containers an). Einen Spezial-Inserter für assoziative Container stelle ich im dritten Teil der Artikelserie vor.
Achtung: Beachten Sie beim Umgang mit Vektoren, dass push_back() und insert() vorhandene Iteratoren ungültig machen können, wenn die vorhandene Kapazität überschritten wird:
vector<int> data(10); generate_n(data.begin(),data.end(),rand);//füllen mit Zufallszahlen //verdopple Vector-Inhalt: //mögliches Problem: undefiniertes Verhalten, wenn data.capacity()<20 copy(data.begin(),data.end(),back_inserter(data));3.2 Reverse Iteratoren
Reverse Iteratoren verwenden als Grundlage einen beliebigen nidirektionalen Iterator und drehen dessen Laufrichtung um (aus ++ wird -- etc.). Auf diese Weise kann ein Algorithmus "rückwärts" durch eine vorgegebene Sequenz laufen (z.B. um das letzte Vorkommen eines Wertes zu finden).
Bei einem Reverse-Iterator muss zwischen der physischen Position und der logischen Position unterschieden werden - beim Dereferenzieren liefern sie jeweils das Element VOR ihrer Basisposition. Auf diese Weise ist es erstens einfacher, das "Ende" einer reversen Sequenz zu kennzeichnen (die Position hinter dem letzten Element einer Sequenz ist definiert, die Position vor dem ersten Element im Allgemeinen nicht), und zweitens enthalten damit ein Bereich und der daraus gebildete reverse Bereich dieselben Elemente in umgekehrter Reihenfolge.
Sämtliche Container der STL können über die Methoden rbegin() und rend() geeignete Reverse-Iteratoren auf den Anfang und das Ende der (rückwärts gelesenen) Elementfolge herausgeben.
3.3 Stream-Iteratoren
Stream-Iteratoren benötigen einen Eingabe- bzw. Ausgabestream und übersetzen Datenzugriffe in dessen operator>> bzw. operator<<. Auf diese Weise wird es möglich, STL-Algorithmen direkt auf Dateien oder der Benutzer-Eingabe (via cin) auszuführen bzw. ihre Resultate direkt auf die Festplatte (über ofstream's) oder den Bildschirm (cout) auszugeben.
Zusätzlich gibt es auch Streambuf-Iteratoren, die direkt auf einem Stream-Puffer operieren (die Stream-Puffer dienen als "Zwischenlager" zwischen den IO-Streams und ihrer externen Datenrepräsentation), um unformatierte char-Sequenzen zu lesen bzw. zu schreiben.
4 Iterator-Hilfsfunktionen
Um die Arbeit mit den Iteratoren etwas zu erleichtern und fehlende Fähigkeiten einiger Iteratorkategorien zu kompensieren, existieren einige Hilfsfunktionen:
- advance(it,num)
Verschiebt den Iterator 'it' um 'num' Positionen nach vorne (bzw. hinten bei negativem Wert). Für Random-Access-Iteratoren wird dafür deren operator+= verwendet, alle anderen Typen werden entsprechend oft inkrementiert oder dekrementiert. - distance(it1,it2)
Bestimmt den Abstand zwischen den Iteratoren 'it1' und 'it2'. Für Random-Access-Iteratoren wird deren operator- verwendet, bei allen anderen Typen wird gezählt, wie oft it1 inkrementiert werden muss, um it2 zu erreichen. - iter_swap(it1,it2)
Vertauscht die Elemente, auf die 'it1' und 'it2' zeigen, miteinander.
5 Algorithmen
Algorithmen sind das "Arbeitspferd" der STL. Mit ihrer Hilfe kann man fast alles mit einem Container anstellen, was man sich vorstellen kann - und wenn etwas noch nicht in der STL vorgesehen ist, lässt sich die nötige Funktion leicht selber schreiben.
Um flexibler zu sein, werden den Algorithmen keine kompletten Container übergeben, sondern Bereiche. Auf diese Weise kann man auch Ausschnitte eines Containers oder Datensammlungen ohne direkte STL-Unterstützung verarbeiten. Ein Bereich wird definiert durch zwei Iteratoren, von denen der erste auf den Anfang und der zweite direkt hinter das Ende der zu bearbeitenden Daten zeigt - bei einem leerer Bereich fallen Anfang und Ende zusammen. Wenn ein Algorithmus mehrere Bereiche parallel bearbeitet, benötigt er häufig nur vom ersten Bereich beide Endpunkte - die Größe aller weiteren verwendeten Bereiche ergibt sich aus dem Zusammenhang (z.B. erwartet copy(), dass der Zielbereich genauso viel Platz bietet wie der Ursprungsbereich). In diesem Fall ist der Aufrufer der Funktion dafür verantwortlich, dass alle weiteren Bereiche genug Elemente enthalten (bei einem reinen "Ausgabebereich" wie für copy() ist es auch möglich, einen Insert-Iterator als Ziel anzugeben).
Wichtig ist bei der Arbeit mit Algorithmen, dass sie die unterliegende Datenstruktur nicht beeinflussen können. Sie können weder Elemente physisch löschen (stattdessen füllen sie Lücken mit nachfolgenden Werten auf und geben einen Iterator auf das "neue" Ende der Sequenz zurück), einfügen (für diesen Zweck können Inserter verwendet werden) noch die Schlüsselwerte eines assoziativen Containers modifizieren (diese sind als const definiert, damit die Ordnung der einzelnen Elemente nicht durcheinandergebracht werden kann).
Hinweis: Von etlichen Algorithmen existieren auch äquivalente Memberfunktion der Container, entweder weil diese Operationen nicht direkt möglich sind (z.B. Modifikationen an Set-Elementen) oder auf der speziellen Containerstruktur effektiver umgesetzt werden können als über die Iteratoren (z.B. Umordnen einer List oder Elementsuche in einem Binärbaum).
Achtung: Wenn ein Algorithmus mit benutzerdefinierten Prädikaten arbeitet, darf er von diesen Kopien anlegen. Deshalb sollten diese ihren internen Status während der Berechnung nicht ändern, da es sonst zu -hmm- merkwürdigen Ergebnissen kommen kann:
class Nth { int goal,count; public: Nth(int n) : goal(n), count(0) {} bool operator() (int) { return ++count == goal; } }; ... list<int> data; for(int i=1;i<=10;++i) data.push_back(i); list<int> pos = remove_if(data.begin(),data.end(),Nth(3)); data.erase(pos,data.end());//physisch löschen ...Je nach Implementation des remove_if()-Algorithmus könnte dieses Programm das dritte UND sechste Element der Liste entfernen.
Die einzelnen Algorithmen unterteilen sich je nach Wirkung in verschiedene Gruppen:
5.1 Nichtmodifizierende Algortihmen
Diese Gruppe verändert die eingegebenen Daten nicht, sondern liest lediglich auf den Daten, um z.B. das größte oder kleinste Element zu bestimmen oder festzustellen, wie oft ein bestimmter Wert in einem Bereich vorkommt.
Zu den nicht-modifizierenden Algorithmen gehören auch einige Suchfunktion für Einzelelemente, Elementsequenzen oder Mengen. Diese geben jeweils einen Iterator auf die gefundene Position zurück - oder das Ende des Suchbereiches, wenn sie keinen Erfolg hatten.
5.2 Modifizierende Algorithmen
Diese Gruppe verändert die Daten im übergebenen Datenbereich, indem sie zum Beispiel Werte kopieren, transformieren oder ersetzen. Dies passiert enweder direkt vor Ort oder während die Daten von einem Bereich in einen anderen kopiert werden.
Der einfachste Algorithmus dieser Gruppe ist copy() - dieser kopiert den Inhalt eines Bereiches in einen anderen Bereich, ohne etwas an den Elementwerten zu verändern. Von vielen anderen Algorithmen existiert neben einer "normalen" Variante, die die Elemente vor Ort modifiziert, ein Kopiervariante, die den Quellbereich unverändert lässt und die modifizierten Werte in einen neuen Bereich überträgt.
5.3 Lösch-Algorithmen
Eine spezielle Gruppe von modifizierenden Algorithmen entfernt einzelne Werte nach speziellen Kriterien aus dem übergebenen Datenbereich. Da ein Iterator keinen Speicher freigeben kann (z.B. im Fall eines Pointers in ein C-Array), geschieht das Löschen, indem hintenstehende Elemente umkopiert werden und am Ende des Ursprungsbereiches einige ungültige Werte stehen bleiben - diese müssen vom Besitzer der Daten noch manuell aufgeräumt werden. Dazu wird der Endpunkt des gekürzten Bereiches als Rückgabewert geliefert.
Nach dem logischen Löschen der Werte müssen entweder die ungültigen Daten echt gelöscht werden, indem man erase() des verwendeten Containers aufruft, oder die neue Endposition wird für weitere Operationen mitgeführt.
vector<int> data; ... vector<int>::iterator pos = remove(data.begin(),data.end(),0);//"löscht" alle Nullwerte data.erase(pos,data.end());//korrigiert Vektorgröße5.4 "mutating"-Algorithmen
Diese Gruppe lässt die Werte des übergebenen Bereiches unverändert, ändert aber nach bestimmten Kriterien ihre Reihenfolge. In diese Gruppe gehören auch Sortier-Algorithmen, die einen Bereich ganz oder teilweise sortieren, und Heap-Algorithmen, die eine spezielle Baumstruktur (Heap) in einem linearen Datenbereich erzeugen und verwalten.
In dieser Gruppe existieren auch drei verschiedene Sortier-Algorithmen, unter denen je nach Bedarf der günstigste ausgewählt werden kann:
- sort()
basiert auf dem QuickSort-Ansatz und ist im Schnitt der schnellste Algorithmus. Bei ungünstigen Eingaben kann das Verfahren jedoch quadratische Laufzeit haben - partial_sort()
basiert auf HeapSort und ist durchschnittlich etwas langsamer als sort(), hat jedoch garantierte Laufzeit von O(n*log n). partial_sort() kann auch verwendet werden, um nur einen Teil der Eingabe zu sortieren. - stable_sort()
basiert auf MergeSort und benötigt zusätzlichen Zwischenspeicher für die sortierten Elemente, um seine volle Geschwindigkeit zu entfalten. Der größte Vorteil dieses Algorithmus besteht darin, dass identische Elemente ihre ursprüngliche Reihenfolge behalten. - Heap-Algorithmen
Mit den Heap-Algorithmen lässt sich eine Datenreihe in zwei Schritten ebenfalls sortieren. make_heap() wandelt eine ungeordnete Reihe in einen Heap um und sort_heap() sortiert anschließend diesen Heap:
template<typename RanIt> void heap_sort(RanIt st,RanIt en) { make_heap(st,en); sort_heap(st,en); }- next_permutation()
Indem alle möglichen Permutationen einer Zahlenfolge durchlaufen werden, trifft man irgendwann auch die korrekt sortierte Folge - auf diese Weise lässt sich der wohl langsamste bekannte Sortieralgorithmus umsetzen:
template<typename BidIt> void slow_sort(BidIt st, BidIt en) { while(next_permutation(st,en)); }5.5 Mengen-Algorithmen
Diese Gruppe implementiert wichtige Mengenoperationen wie Vereinigung, Schnittmenge oder Elementsuche auf Wertebereichen. Sie erwarten als Vorbedingung, dass die übergebenen Bereiche sortiert sind (entsprechend dem als Parameter übergebenen Vergleichskriterium 'pred' - letzteres muss eine Ordnungsrelation (siehe Kapitel 4 im ersten Teil) definieren).
Achtung: Verwenden Sie die Mengen-Algorithmen nicht auf unsortierten Zahlenbereichen; es ist nicht definiert, ob (und wie) sie damit umgehen können.
5.6 Numerische Algorithmen
Header:
#include <numeric>Diese Gruppe wendet verschiedene mathematische Operationen auf Datenbereiche an, entweder um alle Elemente eines Bereiches zusammenzurechnen oder um Teilsummen der Elemente zu ermitteln.
Alle vier numerischen Algorithmen haben eine mathematische Bedeutung, aus der sich auch ihr jeweiliger Name ableiten lässt. Allerdings können ihnen beliebige Rechenfunktionen mitgegeben werden, die die Wirkung beeinflussen.
5.7 for_each()
template<typename It, typename func> func for_each(It st, It en,func op);Der for_each()-Algorithmus ist die "Eier legende Wollmilchsau" der STL. Er wendet die übergebene Operation auf jedes Element des Bereiches [st,en[ an und gibt sie am Ende an den Aufrufer zurück. Indem verschiedenste unäre **RICHTIG?** Funktionen oder Funktoren verwendet werden, kann man nahezu alles mit den Elementen des Ursprungsbereiches anstellen - z.B. den Mittelwert zusammenrechnen, Werte ausgeben oder verarbeiten.
Es gibt drei grundlegende Möglichkeiten, wofür for_each() genutzt werden kann:
- Ausgabe von Werten:
void print(int i) { cout<<i<<" "; } list<int> cont; ... for_each(cont.begin(),cont.end(),print);//gibt Listeninhalt aus //äquivalent: copy(cont.begin(),cont.end(),ostream_iterator<int>(cout," ");- Modifikation der Werte:
void square(int& i) { i*=i; } list<int> cont; ... for_each(cont.begin(),cont.end,square);//quadriert alle Listenelemente //äquivalent: transform(cont.begin(),cont.end(),cont.begin(),cont.begin(),multiplies<int>);- Mitverfolgung des Funktorstatus:
class mean : public unary_function<double,void> { public: mean() : s(0),n(0) {} operator double() {return s/n;} void operator() (double v) { s+=v; ++n; } private: double s; unsigned n; }; list<double> cont; ... mean mv = for_each(cont.begin(),cont.end(),mean());//Mittelwert aller Elemente berechnen cout<<mv<<endl; //äquivalent: double mv = accumulate(cont.begin(),cont.end(),0) / distance(cont.begin(),connt.end());Natürlich lassen sich diese Einsatzmöglichkeiten auch kombinieren, indem zum Beispiel ein Funktor die übergebenen Werte ändert UND mitprotokolliert.
Ausblick
Mit den Iteratoren und Algorithmen haben wir alle grundlegenden Informationen, um die STL in der Praxis anwenden zu können. Allerdings gibt es in der Standardbibliothek noch etliche weitere Klassen, die zusammen mit der STL (oder auch unabhängig davon) verwendet werden können. Diese werde ich im dritten Teil der Serie behandeln.
Außerdem werde ich im nächsten Monat erklären, wie man eigene Klassen und Funktionen so entwirft, dass sie sich in die bestehende Bibliothek integrieren lassen.
-
Für die Länge des Artikels sind die paar Fehler nicht sehr ins Gewicht fallend, weshalb du im Diktat ne 1 bekommen hättest.
zwei Sachen noch:
was ist eine "unäre" Funktion? im grunde genommen interessiert es mich nicht, aber "unär" hab ich noch nie gehört. guck mal nach, obs richtig geschrieben ist. davon habe ich keine ahnung.
"mutating" algorithmus... lateinisch mutare: wechseln, ändern, verwandeln. was besseres fällt mir auch nicht ein. "wechselnder algorithmus", falls das den inhalt trifft.
denk an die entfernung der kor- und anm-tags, wenn der artikel rausgeht!
Mr. B
-
Also besser wäre "einstellige" Funktionen und "einstellige" Funktionsobjekte. Dann gibts ja noch die "binären" bzw. "zweisteligen" Varianten mit zwei Parametern. So steht es in Bjarnes dt. Übersetzung und im C++ Std-Lib Buch vom Springer Verlag.
"unäre" hab ich auch noch nie gehört.
-
Irgendwie hab ich das gefühl da hat jemand beim leo nach geguckt:
Da wird unary als unär übersetzt *g*
//Edit: Btw hätte ich auch da nach geschaut :p
BR
-
Unär, binär und tertiär sind völlig normale Begriffe in der Informatik; ich zumindest habe so einige Bücher im Regal stehen, in denen diese Wörter genutzt werden. Die würde ich auch nicht mit "einfach", "zweifach" und "dreifach" übersetzen, allenfalls vielleicht eine per Nebensatz kurz eingestreute Erläuterung für diejenigen, die damit (noch) nichts anfangen können!
-
Reyx schrieb:
Unär, binär und tertiär sind völlig normale Begriffe in der Informatik; ich zumindest habe so einige Bücher im Regal stehen, in denen diese Wörter genutzt werden. Die würde ich auch nicht mit "einfach", "zweifach" und "dreifach" übersetzen, allenfalls vielleicht eine per Nebensatz kurz eingestreute Erläuterung für diejenigen, die damit (noch) nichts anfangen können!
Sehe ich auch so, in 'C++ Lernen und Professionell anwenden' steht das auch so mit unär drin. Steht das nicht sogar bei Meyers?MfG
GPC
-
Nachdem wir im ersten Teil der Artikelreihe erfahren haben, wie die STL große Datenmengen organisiert und verstaut, kann es nun mit dem zweiten Teil weitergehen, in dem es um die Frage geht, wie man auf die gespeicherten Daten zugreifen kann - und wie sie effektiv verarbeitet werden.
Inhalt
- Iteratoren
- Iterator-Kategorien
- Iterator-Adapter
- Iterator-Hilfsfunktionen
- Algorithmen
1 Iteratoren
Was nützen die besten Container, wenn man nicht problemlos auf ihren Inhalt zugreifen kann? Vektoren und Deques bieten freien Zugriff auf ihre Elemente, sodass es möglich ist, sich per Index durch ihre Daten durchzuhangeln. Allerdings ist es nicht möglich, effektiv auf einer Listen- oder Baumstruktur nach einem bestimmten Index zu suchen.
Am einfachsten wäre es, für jeden Containertyp eigene Zugriffsmethoden zu definieren, die die besonderen Fähigkeiten des jeweiligen Typs ausnutzen - allerdings würde dieser Ansatz die Austauschbarkeit der Containerklassen erschweren. Deshalb geht die STL einen anderen Weg. Jeder Container bringt seine eigene Iterator-Klasse mit. Diese bieten nach außen eine passende Schnittstelle zum Datenzugriff und sind in der Lage, sich korrekt durch die interne Struktur des Containers durchzuhangeln. Die möglichen Operationen auf Iteratoren sind ganz bewusst an die von blanken C-Pointern angelehnt, bieten jedoch im Allgemeinen deutlich "intelligenteres" Verhalten - damit kann man Iteratoren als eine Form von Smart Pointern betrachten.
2 Iterator-Kategorien
Je nach Fähigkeiten werden die verschiedenen Iteratoren in Kategorien eingeordnet. Bei der Einordnung der STL-Iteratoren in diese Kategorien wurde nicht nur darauf Wert gelegt, welche Operationen technisch möglich wären, sondern auch, dass die existierenden Operationen auch relativ schnell umgesetzt werden können - ein Vektor-Iterator kann in konstanter Zeit eine beliebige Position erreichen, ein Listen-Iterator würde lineare Zeit dafür benötigen, deshalb hat er keinen operator+=.
2.1 Output-Iterator
Dies ist wohl der primitivste Iterator. Er kann lediglich Daten schlucken und inkrementiert werden, um im Speicher weiterzulaufen - dabei ist das Inkrementieren häufig als leere Operation implementiert und der operator= kümmert sich selber um die Beschaffung des Speichers oder die Weitergabe der empfangenen Daten. Es ist noch nicht einmal möglich, zwei gegebene Output-Iteratoren miteinander zu vergleichen oder festzustellen, ob das Schreiben in den Iterator erfolgreich war.
In diese Kategorie gehören zum Beispiel der Ostream-Iterator oder die Inserter.
2.2 Input-Iterator
Diese Klasse ist ähnlich einfach aufgebaut wie die Output-Iteratoren. Ein Input-Iterator kann Werte ausgeben, inkrementiert werden und mit anderen Iteratoren verglichen werden. Dieser Vergleich hat in der Regel nur Sinn, um die Gültigkeit des Iterators zu kontrollieren.
Der C++-Standard garantiert übrigens nicht, dass Kopien eines Input-Interators unabhängig voneinander genutzt werden können, um denselben Datenvorrat zweimal einzulesen.Der wichtigste Input-Iterator ist der Istream-Iterator. Im Hinblick auf seine Zugriffsmöglichkeiten auf die verarbeiteten Werte könnte man einen Set- oder Multiset-Iterator auch in diese Kategorie einordnen.
2.3 Forward-Iterator
Ein Forward-Iterator vereinigt in sich die Fähigkeiten von Output- und Input-Iterator. Er kann sowohl Daten lesen als auch schreiben und im Gegensatz zum Input-Iterator können sich verschiedene Kopien auch unabhängig voneinander durch die unterliegende Datenstruktur bewegen.
Achtung: Ein Forward-Iterator kann nicht als vollwertiger Output-Iterator eingesetzt werden, da er im Regelfall nur über eine begrenzt lange Sequenz iterieren kann:
//OK für Output-Iterator //Laufzeitfehler für Forward-Iterator while(true) *pos++ = getval(); //OK für Forward-Iterator //Compilerfehler für Output-Iterator while(pos!=end) *pos++ = getval();Die STL verwendet keine eigenen Forward-Iteratoren, aber man könnte sie sich z.B. in einer einfach verketteten Liste gut vorstellen.
2.4 Bidirektionaler Iterator
Diese Klasse erweitert den Forward-Iterator um die Fähigkeit, "rückwärts" zu laufen. Ein bidirektionaler Iterator kann sowohl inkrementiert als auch dekrementiert werden.
In diese Kategorie gehören die Iteratoren einer Liste und der assoziativen Container - wobei letztere den Schlüsselwert der iterierten Elemente nicht ändern dürfen.
2.5 Random-Access-Iterator
Random-Access-Iteratoren sind die mächtigste Kategorie von Iteratoren. Sie können beliebig durch die iterierte Struktur "springen". Zusätzlich zu Operationen, die ein bidirektionaler Iterator unterstützt, bieten sie auch Iterator-Arithmetik nach dem Vorbild der Pointer-Arithmetik von C - sie können um beliebige ganzzahlige Schrittweiten vorwärts und rückwärts durch den Speicher bewegt werden, den Abstand untereinander berechnen und mittels <,<=,>= und > verglichen werden.
In diese Kategorie fallen die Iteratoren eines Vektors oder Deque, aber auch die aus C bekannten Pointer.
3 Iterator-Adapter
Adapter werden verwendet, um das Verhalten eines Iterators zu ändern. Sie werden auf eine andere Struktur aufgesetzt und ermöglichen es, diese über die bekannten Iterator-Methoden und -Operatoren zu modifizieren.
3.1 Insert-Iteratoren
Inserter sind reine Output-Iteratoren und übersetzen Schreibzugriffe in insert()-Aufrufe des unterliegenden Containers. Mit ihrer Hilfe kann ein Container während der Arbeit erweitert werden. Auf diese Weise kann z.B. ein Algorithmus Werte in den Container einfügen, ohne sich um den verfügbaren Platz Sorgen machen zu müssen.
Außer einem normalen Insert-Iterator gibt es auch noch Back-Inserter (hängen die ankommenden Daten per push_back() an das Ende ihres Containers an) und Front-Inserter (hängen die Daten per push_front() an den Anfang des Containers an). Einen Spezial-Inserter für assoziative Container stelle ich im dritten Teil der Artikelserie vor.
Achtung: Beachten Sie beim Umgang mit Vektoren, dass push_back() und insert() vorhandene Iteratoren ungültig machen können, wenn die vorhandene Kapazität überschritten wird:
vector<int> data(10); generate_n(data.begin(),data.end(),rand);//füllen mit Zufallszahlen //verdopple Vector-Inhalt: //mögliches Problem: undefiniertes Verhalten, wenn data.capacity()<20 copy(data.begin(),data.end(),back_inserter(data));3.2 Reverse-Iteratoren
Reverse-Iteratoren verwenden als Grundlage einen beliebigen bidirektionalen Iterator und drehen dessen Laufrichtung um (aus ++ wird -- etc.). Auf diese Weise kann ein Algorithmus "rückwärts" durch eine vorgegebene Sequenz laufen (z.B. um das letzte Vorkommen eines Wertes zu finden).
Bei einem Reverse-Iterator muss zwischen der physischen Position und der logischen Position unterschieden werden - beim Dereferenzieren liefern sie jeweils das Element VOR ihrer Basisposition. Auf diese Weise ist es erstens einfacher, das "Ende" einer reversen Sequenz zu kennzeichnen (die Position hinter dem letzten Element einer Sequenz ist definiert, die Position vor dem ersten Element im Allgemeinen nicht), und zweitens enthalten damit ein Bereich und der daraus gebildete reverse Bereich dieselben Elemente in umgekehrter Reihenfolge.
Sämtliche Container der STL können über die Methoden rbegin() und rend() geeignete Reverse-Iteratoren auf den Anfang und das Ende der (rückwärts gelesenen) Elementfolge herausgeben.
3.3 Stream-Iteratoren
Stream-Iteratoren benötigen einen Eingabe- bzw. Ausgabestream und übersetzen Datenzugriffe in dessen operator>> bzw. operator<<. Auf diese Weise wird es möglich, STL-Algorithmen direkt auf Dateien oder der Benutzer-Eingabe (via cin) auszuführen bzw. ihre Resultate direkt auf die Festplatte (über ofstream's) oder den Bildschirm (cout) auszugeben.
Zusätzlich gibt es auch Streambuf-Iteratoren, die direkt auf einem Stream-Puffer operieren (die Stream-Puffer dienen als "Zwischenlager" zwischen den IO-Streams und ihrer externen Datenrepräsentation), um unformatierte char-Sequenzen zu lesen bzw. zu schreiben.
4 Iterator-Hilfsfunktionen
Um die Arbeit mit den Iteratoren etwas zu erleichtern und fehlende Fähigkeiten einiger Iterator-Kategorien zu kompensieren, existieren einige Hilfsfunktionen:
- advance(it,num)
Verschiebt den Iterator 'it' um 'num' Positionen nach vorne (bzw. hinten bei negativem Wert). Für Random-Access-Iteratoren wird dafür deren operator+= verwendet, alle anderen Typen werden entsprechend oft inkrementiert oder dekrementiert. - distance(it1,it2)
Bestimmt den Abstand zwischen den Iteratoren 'it1' und 'it2'. Für Random-Access-Iteratoren wird deren operator- verwendet, bei allen anderen Typen wird gezählt, wie oft it1 inkrementiert werden muss, um it2 zu erreichen. - iter_swap(it1,it2)
Vertauscht die Elemente, auf die 'it1' und 'it2' zeigen, miteinander.
5 Algorithmen
Algorithmen sind das "Arbeitspferd" der STL. Mit ihrer Hilfe kann man fast alles mit einem Container anstellen, was man sich vorstellen kann - und wenn etwas noch nicht in der STL vorgesehen ist, lässt sich die nötige Funktion leicht selbst schreiben.
Um flexibler zu sein, werden den Algorithmen keine kompletten Container übergeben, sondern Bereiche. Auf diese Weise kann man auch Ausschnitte eines Containers oder Datensammlungen ohne direkte STL-Unterstützung verarbeiten. Ein Bereich wird definiert durch zwei Iteratoren, von denen der erste auf den Anfang und der zweite direkt hinter das Ende der zu bearbeitenden Daten zeigt - bei einem leerer Bereich fallen Anfang und Ende zusammen. Wenn ein Algorithmus mehrere Bereiche parallel bearbeitet, benötigt er häufig nur vom ersten Bereich beide Endpunkte - die Größe aller weiteren verwendeten Bereiche ergibt sich aus dem Zusammenhang (z.B. erwartet copy(), dass der Zielbereich genauso viel Platz bietet wie der Ursprungsbereich). In diesem Fall ist der Aufrufer der Funktion dafür verantwortlich, dass alle weiteren Bereiche genug Elemente enthalten (bei einem reinen "Ausgabebereich" wie für copy() ist es auch möglich, einen Insert-Iterator als Ziel anzugeben).
Wichtig ist bei der Arbeit mit Algorithmen, dass sie die unterliegende Datenstruktur nicht beeinflussen können. Sie können weder Elemente physisch löschen (stattdessen füllen sie Lücken mit nachfolgenden Werten auf und geben einen Iterator auf das "neue" Ende der Sequenz zurück), einfügen (für diesen Zweck können Inserter verwendet werden) noch die Schlüsselwerte eines assoziativen Containers modifizieren (diese sind als const definiert, damit die Ordnung der einzelnen Elemente nicht durcheinander gebracht werden kann).
Hinweis: Von etlichen Algorithmen existieren auch äquivalente Memberfunktion der Container, entweder weil diese Operationen nicht direkt möglich sind (z.B. Modifikationen an Set-Elementen) oder auf der speziellen Containerstruktur effektiver umgesetzt werden können als über die Iteratoren (z.B. Umordnen einer List oder Elementsuche in einem Binärbaum).
Achtung: Wenn ein Algorithmus mit benutzerdefinierten Prädikaten arbeitet, darf er von diesen Kopien anlegen. Deshalb sollten diese ihren internen Status während der Berechnung nicht ändern, da es sonst zu -hmm- merkwürdigen Ergebnissen kommen kann:
class Nth { int goal,count; public: Nth(int n) : goal(n), count(0) {} bool operator() (int) { return ++count == goal; } }; ... list<int> data; for(int i=1;i<=10;++i) data.push_back(i); list<int>[kor]::iterator[/kor] pos = remove_if(data.begin(),data.end(),Nth(3)); data.erase(pos,data.end());//physisch löschen ...Je nach Implementation des remove_if()-Algorithmus könnte dieses Programm das dritte UND sechste Element der Liste entfernen.
Die einzelnen Algorithmen unterteilen sich je nach Wirkung in verschiedene Gruppen:
5.1 Nichtmodifizierende Algorithmen
Diese Gruppe verändert die eingegebenen Daten nicht, sondern liest lediglich auf den Daten, um z.B. das größte oder kleinste Element zu bestimmen oder festzustellen, wie oft ein bestimmter Wert in einem Bereich vorkommt.
Zu den nicht-modifizierenden Algorithmen gehören auch einige Suchfunktion für Einzelelemente, Elementsequenzen oder Mengen. Diese geben jeweils einen Iterator auf die gefundene Position zurück - oder das Ende des Suchbereiches, wenn sie keinen Erfolg hatten.
5.2 Modifizierende Algorithmen
Diese Gruppe verändert die Daten im übergebenen Datenbereich, indem sie zum Beispiel Werte kopieren, transformieren oder ersetzen. Dies passiert entweder direkt vor Ort oder während die Daten von einem Bereich in einen anderen kopiert werden.
Der einfachste Algorithmus dieser Gruppe ist copy() - dieser kopiert den Inhalt eines Bereiches in einen anderen Bereich, ohne etwas an den Elementwerten zu verändern. Von vielen anderen Algorithmen existiert neben einer "normalen" Variante, die die Elemente vor Ort modifiziert, eine Kopiervariante, die den Quellbereich unverändert lässt und die modifizierten Werte in einen neuen Bereich überträgt.
5.3 Lösch-Algorithmen
Eine spezielle Gruppe von modifizierenden Algorithmen entfernt einzelne Werte nach speziellen Kriterien aus dem übergebenen Datenbereich. Da ein Iterator keinen Speicher freigeben kann (z.B. im Fall eines Pointers in ein C-Array), geschieht das Löschen, indem hinten stehende Elemente umkopiert werden und am Ende des Ursprungsbereiches einige ungültige Werte stehen bleiben - diese müssen vom Besitzer der Daten noch manuell aufgeräumt werden. Dazu wird der Endpunkt des gekürzten Bereiches als Rückgabewert geliefert.
Nach dem logischen Löschen der Werte müssen entweder die ungültigen Daten echt gelöscht werden, indem man erase() des verwendeten Containers aufruft, oder die neue Endposition wird für weitere Operationen mitgeführt.
vector<int> data; ... vector<int>::iterator pos = remove(data.begin(),data.end(),0);//"löscht" alle Nullwerte data.erase(pos,data.end());//korrigiert Vektorgröße5.4 "mutating"-Algorithmen
Diese Gruppe lässt die Werte des übergebenen Bereiches unverändert, ändert aber nach bestimmten Kriterien ihre Reihenfolge. In diese Gruppe gehören auch Sortier-Algorithmen, die einen Bereich ganz oder teilweise sortieren, und Heap-Algorithmen, die eine spezielle Baumstruktur (Heap) in einem linearen Datenbereich erzeugen und verwalten.
In dieser Gruppe existieren auch drei verschiedene Sortier-Algorithmen, unter denen je nach Bedarf der günstigste ausgewählt werden kann:
- sort()
basiert auf dem QuickSort-Ansatz und ist im Schnitt der schnellste Algorithmus. Bei ungünstigen Eingaben kann das Verfahren jedoch quadratische Laufzeit haben - partial_sort()
basiert auf HeapSort und ist durchschnittlich etwas langsamer als sort(), hat jedoch garantierte Laufzeit von O(n*log n). partial_sort() kann auch verwendet werden, um nur einen Teil der Eingabe zu sortieren. - stable_sort()
basiert auf MergeSort und benötigt zusätzlichen Zwischenspeicher für die sortierten Elemente, um seine volle Geschwindigkeit zu entfalten. Der größte Vorteil dieses Algorithmus besteht darin, dass identische Elemente ihre ursprüngliche Reihenfolge behalten. - Heap-Algorithmen
Mit den Heap-Algorithmen lässt sich eine Datenreihe in zwei Schritten ebenfalls sortieren. make_heap() wandelt eine ungeordnete Reihe in einen Heap um und sort_heap() sortiert anschließend diesen Heap:
template<typename RanIt> void heap_sort(RanIt st,RanIt en) { make_heap(st,en); sort_heap(st,en); }- next_permutation()
Indem alle möglichen Permutationen einer Zahlenfolge durchlaufen werden, trifft man irgendwann auch die korrekt sortierte Folge - auf diese Weise lässt sich der wohl langsamste bekannte Sortieralgorithmus umsetzen:
template<typename BidIt> void slow_sort(BidIt st, BidIt en) { while(next_permutation(st,en)); }5.5 Mengen-Algorithmen
Diese Gruppe implementiert wichtige Mengenoperationen wie Vereinigung, Schnittmenge oder Elementsuche auf Wertebereichen. Sie erwarten als Vorbedingung, dass die übergebenen Bereiche sortiert sind (entsprechend dem als Parameter übergebenen Vergleichskriterium 'pred' - letzteres muss eine Ordnungsrelation (siehe Kapitel 4 im ersten Teil) definieren).
Achtung: Verwenden Sie die Mengen-Algorithmen nicht auf unsortierten Zahlenbereichen; es ist nicht definiert, ob (und wie) sie damit umgehen können.
5.6 Numerische Algorithmen
Header:
#include <numeric>Diese Gruppe wendet verschiedene mathematische Operationen auf Datenbereiche an, entweder um alle Elemente eines Bereiches zusammenzurechnen oder um Teilsummen der Elemente zu ermitteln.
Alle vier numerischen Algorithmen haben eine mathematische Bedeutung, aus der sich auch ihr jeweiliger Name ableiten lässt. Allerdings können ihnen beliebige Rechenfunktionen mitgegeben werden, die die Wirkung beeinflussen.
5.7 for_each()
template<typename It, typename func> func for_each(It st, It en,func op);Der for_each()-Algorithmus ist die "Eier legende Wollmilchsau" der STL. Er wendet die übergebene Operation auf jedes Element des Bereiches [st,en[ an und gibt sie am Ende an den Aufrufer zurück. Indem verschiedenste unäre Funktionen oder Funktoren verwendet werden, kann man nahezu alles mit den Elementen des Ursprungsbereiches anstellen - z.B. den Mittelwert zusammenrechnen, Werte ausgeben oder verarbeiten.
Es gibt drei grundlegende Möglichkeiten, wofür for_each() genutzt werden kann:
- Ausgabe von Werten:
void print(int i) { cout<<i<<" "; } list<int> cont; ... for_each(cont.begin(),cont.end(),print);//gibt Listeninhalt aus //äquivalent: copy(cont.begin(),cont.end(),ostream_iterator<int>(cout," ");- Modifikation der Werte:
void square(int& i) { i*=i; } list<int> cont; ... for_each(cont.begin(),cont.end,square);//quadriert alle Listenelemente //äquivalent: transform(cont.begin(),cont.end(),cont.begin(),cont.begin(),multiplies<int>);- Mitverfolgung des Funktorstatus:
class mean : public unary_function<double,void> { public: mean() : s(0),n(0) {} operator double() {return s/n;} void operator() (double v) { s+=v; ++n; } private: double s; unsigned n; }; list<double> cont; ... mean mv = for_each(cont.begin(),cont.end(),mean());//Mittelwert aller Elemente berechnen cout<<mv<<endl; //äquivalent: double mv = accumulate(cont.begin(),cont.end(),0) / distance(cont.begin(),connt.end());Natürlich lassen sich diese Einsatzmöglichkeiten auch kombinieren, indem zum Beispiel ein Funktor die übergebenen Werte ändert UND mitprotokolliert.
Ausblick
Mit den Iteratoren und Algorithmen haben wir alle grundlegenden Informationen, um die STL in der Praxis anwenden zu können. Allerdings gibt es in der Standardbibliothek noch etliche weitere Klassen, die zusammen mit der STL (oder auch unabhängig davon) verwendet werden können. Diese werde ich im dritten Teil der Serie behandeln.
Außerdem werde ich im nächsten Monat erklären, wie man eigene Klassen und Funktionen so entwirft, dass sie sich in die bestehende Bibliothek integrieren lassen.
-
Es waren noch ein paar kleine Tippfehler drin.
Außerdem hast du bei den Iterator-Typen manchmal einen Bindestrich verwendet und manchmal nicht; ich habe mal bei allen einen Bindestrich hingemacht. Ich hoffe, es stört dich nicht, dass ich bei diesen Bindestrichen keine kor-Tags verwendet habe, aber das wäre _etwas_ zu viel Arbeit gewesen.Dann ist mir auch noch etwas in einem deiner Beispiel-Codes aufgefallen:
Unter Punkt 5 entfernst du mit remove_if Elemente einer Liste, nimmst den Rückgabewert aber wieder in einer Liste auf. Da hast du wahrscheinlich einfach das ::iterator vergessen, oder? Ich habe es jedenfalls so verbessert, du kannst es dir ja nochmal anschauen...
-
-predator-: Da du es angestrichen hast: Kannst du mir den Unterschied zwischen "selbst" und "selber" erklären?
-
Michael E. schrieb:
Kannst du mir den Unterschied zwischen "selbst" und "selber" erklären?
"Selber" ist meines Wissens umgangssprachlich. Ansonsten haben die zwei Wörter die gleiche Bedeutung.
-
-predator- schrieb:
Michael E. schrieb:
Kannst du mir den Unterschied zwischen "selbst" und "selber" erklären?
"Selber" ist meines Wissens umgangssprachlich. Ansonsten haben die zwei Wörter die gleiche Bedeutung.
genau so ist est.
edit: danke, predator, habe die paar sachen wirklich übersehen...
Mr. B
-
Mr. B schrieb:
Für die Länge des Artikels sind die paar Fehler nicht sehr ins Gewicht fallend, weshalb du im Diktat ne 1 bekommen hättest.
Naja, ein paar Fehler aus dem ersten Teil hatte ich während der Arbeit schon berichtigt (daß, muß etc)
was ist eine "unäre" Funktion? im grunde genommen interessiert es mich nicht, aber "unär" hab ich noch nie gehört. guck mal nach, obs richtig geschrieben ist. davon habe ich keine ahnung.
unär = einstellig (sprich - nimmt genau einen Parameter). Ich habe eigentlich gehofft, daß das selbsterklärend ist.
"mutating" algorithmus... lateinisch mutare: wechseln, ändern, verwandeln. was besseres fällt mir auch nicht ein. "wechselnder algorithmus", falls das den inhalt trifft.
Wirklich passend ist die Bezeichnung nicht.
-predator- schrieb:
Unter Punkt 5 entfernst du mit remove_if Elemente einer Liste, nimmst den Rückgabewert aber wieder in einer Liste auf. Da hast du wahrscheinlich einfach das ::iterator vergessen, oder? Ich habe es jedenfalls so verbessert, du kannst es dir ja nochmal anschauen...
Stimmt, das ist mir anscheinend entgangen.
----
Nachdem wir im ersten Teil der Artikelreihe erfahren haben, wie die STL große Datenmengen organisiert und verstaut, kann es nun mit dem zweiten Teil weitergehen, in dem es um die Frage geht, wie man auf die gespeicherten Daten zugreifen kann - und wie sie effektiv verarbeitet werden.
Inhalt
- Iteratoren
- Iterator-Kategorien
- Iterator-Adapter
- Iterator-Hilfsfunktionen
- Algorithmen
1 Iteratoren
Was nützen die besten Container, wenn man nicht problemlos auf ihren Inhalt zugreifen kann? Vektoren und Deques bieten freien Zugriff auf ihre Elemente, sodass es möglich ist, sich per Index durch ihre Daten durchzuhangeln. Allerdings ist es nicht möglich, effektiv auf einer Listen- oder Baumstruktur nach einem bestimmten Index zu suchen.
Am einfachsten wäre es, für jeden Containertyp eigene Zugriffsmethoden zu definieren, die die besonderen Fähigkeiten des jeweiligen Typs ausnutzen - allerdings würde dieser Ansatz die Austauschbarkeit der Containerklassen erschweren. Deshalb geht die STL einen anderen Weg. Jeder Container bringt seine eigene Iterator-Klasse mit. Diese bieten nach außen eine passende Schnittstelle zum Datenzugriff und sind in der Lage, sich korrekt durch die interne Struktur des Containers durchzuhangeln. Die möglichen Operationen auf Iteratoren sind ganz bewusst an die von blanken C-Pointern angelehnt, bieten jedoch im Allgemeinen deutlich "intelligenteres" Verhalten - damit kann man Iteratoren als eine Form von Smart Pointern betrachten.
2 Iterator-Kategorien
Je nach Fähigkeiten werden die verschiedenen Iteratoren in Kategorien eingeordnet. Bei der Einordnung der STL-Iteratoren in diese Kategorien wurde nicht nur darauf Wert gelegt, welche Operationen technisch möglich wären, sondern auch, dass die existierenden Operationen auch relativ schnell umgesetzt werden können - ein Vektor-Iterator kann in konstanter Zeit eine beliebige Position erreichen, ein Listen-Iterator würde lineare Zeit dafür benötigen, deshalb hat er keinen operator+=.
2.1 Output-Iterator
Dies ist wohl der primitivste Iterator. Er kann lediglich Daten schlucken und inkrementiert werden, um im Speicher weiterzulaufen - dabei ist das Inkrementieren häufig als leere Operation implementiert und der operator= kümmert sich selber um die Beschaffung des Speichers oder die Weitergabe der empfangenen Daten. Es ist noch nicht einmal möglich, zwei gegebene Output-Iteratoren miteinander zu vergleichen oder festzustellen, ob das Schreiben in den Iterator erfolgreich war.
In diese Kategorie gehören zum Beispiel der Ostream-Iterator oder die Inserter.
2.2 Input-Iterator
Diese Klasse ist ähnlich einfach aufgebaut wie die Output-Iteratoren. Ein Input-Iterator kann Werte ausgeben, inkrementiert werden und mit anderen Iteratoren verglichen werden. Dieser Vergleich hat in der Regel nur Sinn, um die Gültigkeit des Iterators zu kontrollieren.
Der C++-Standard garantiert übrigens nicht, dass Kopien eines Input-Interators unabhängig voneinander genutzt werden können, um denselben Datenvorrat zweimal einzulesen.Der wichtigste Input-Iterator ist der Istream-Iterator. Im Hinblick auf seine Zugriffsmöglichkeiten auf die verarbeiteten Werte könnte man einen Set- oder Multiset-Iterator auch in diese Kategorie einordnen.
2.3 Forward-Iterator
Ein Forward-Iterator vereinigt in sich die Fähigkeiten von Output- und Input-Iterator. Er kann sowohl Daten lesen als auch schreiben und im Gegensatz zum Input-Iterator können sich verschiedene Kopien auch unabhängig voneinander durch die unterliegende Datenstruktur bewegen.
Achtung: Ein Forward-Iterator kann nicht als vollwertiger Output-Iterator eingesetzt werden, da er im Regelfall nur über eine begrenzt lange Sequenz iterieren kann:
//OK für Output-Iterator //Laufzeitfehler für Forward-Iterator while(true) *pos++ = getval(); //OK für Forward-Iterator //Compilerfehler für Output-Iterator while(pos!=end) *pos++ = getval();Die STL verwendet keine eigenen Forward-Iteratoren, aber man könnte sie sich z.B. in einer einfach verketteten Liste gut vorstellen.
2.4 Bidirektionaler Iterator
Diese Klasse erweitert den Forward-Iterator um die Fähigkeit, "rückwärts" zu laufen. Ein bidirektionaler Iterator kann sowohl inkrementiert als auch dekrementiert werden.
In diese Kategorie gehören die Iteratoren einer Liste und der assoziativen Container - wobei letztere den Schlüsselwert der iterierten Elemente nicht ändern dürfen.
2.5 Random-Access-Iterator
Random-Access-Iteratoren sind die mächtigste Kategorie von Iteratoren. Sie können beliebig durch die iterierte Struktur "springen". Zusätzlich zu Operationen, die ein bidirektionaler Iterator unterstützt, bieten sie auch Iterator-Arithmetik nach dem Vorbild der Pointer-Arithmetik von C - sie können um beliebige ganzzahlige Schrittweiten vorwärts und rückwärts durch den Speicher bewegt werden, den Abstand untereinander berechnen und mittels <,<=,>= und > verglichen werden.
In diese Kategorie fallen die Iteratoren eines Vektors oder Deque, aber auch die aus C bekannten Pointer.
3 Iterator-Adapter
Adapter werden verwendet, um das Verhalten eines Iterators zu ändern. Sie werden auf eine andere Struktur aufgesetzt und ermöglichen es, diese über die bekannten Iterator-Methoden und -Operatoren zu modifizieren.
3.1 Insert-Iteratoren
Inserter sind reine Output-Iteratoren und übersetzen Schreibzugriffe in insert()-Aufrufe des unterliegenden Containers. Mit ihrer Hilfe kann ein Container während der Arbeit erweitert werden. Auf diese Weise kann z.B. ein Algorithmus Werte in den Container einfügen, ohne sich um den verfügbaren Platz Sorgen machen zu müssen.
Außer einem normalen Insert-Iterator gibt es auch noch Back-Inserter (hängen die ankommenden Daten per push_back() an das Ende ihres Containers an) und Front-Inserter (hängen die Daten per push_front() an den Anfang des Containers an). Einen Spezial-Inserter für assoziative Container stelle ich im dritten Teil der Artikelserie vor.
Achtung: Beachten Sie beim Umgang mit Vektoren, dass push_back() und insert() vorhandene Iteratoren ungültig machen können, wenn die vorhandene Kapazität überschritten wird:
vector<int> data(10); generate_n(data.begin(),data.end(),rand);//füllen mit Zufallszahlen //verdopple Vector-Inhalt: //mögliches Problem: undefiniertes Verhalten, wenn data.capacity()<20 copy(data.begin(),data.end(),back_inserter(data));3.2 Reverse-Iteratoren
Reverse-Iteratoren verwenden als Grundlage einen beliebigen bidirektionalen Iterator und drehen dessen Laufrichtung um (aus ++ wird -- etc.). Auf diese Weise kann ein Algorithmus "rückwärts" durch eine vorgegebene Sequenz laufen (z.B. um das letzte Vorkommen eines Wertes zu finden).
Bei einem Reverse-Iterator muss zwischen der physischen Position und der logischen Position unterschieden werden - beim Dereferenzieren liefern sie jeweils das Element VOR ihrer Basisposition. Auf diese Weise ist es erstens einfacher, das "Ende" einer reversen Sequenz zu kennzeichnen (die Position hinter dem letzten Element einer Sequenz ist definiert, die Position vor dem ersten Element im Allgemeinen nicht), und zweitens enthalten damit ein Bereich und der daraus gebildete reverse Bereich dieselben Elemente in umgekehrter Reihenfolge.
Sämtliche Container der STL können über die Methoden rbegin() und rend() geeignete Reverse-Iteratoren auf den Anfang und das Ende der (rückwärts gelesenen) Elementfolge herausgeben.
3.3 Stream-Iteratoren
Stream-Iteratoren benötigen einen Eingabe- bzw. Ausgabestream und übersetzen Datenzugriffe in dessen operator>> bzw. operator<<. Auf diese Weise wird es möglich, STL-Algorithmen direkt auf Dateien oder der Benutzer-Eingabe (via cin) auszuführen bzw. ihre Resultate direkt auf die Festplatte (über ofstream's) oder den Bildschirm (cout) auszugeben.
Zusätzlich gibt es auch Streambuf-Iteratoren, die direkt auf einem Stream-Puffer operieren (die Stream-Puffer dienen als "Zwischenlager" zwischen den IO-Streams und ihrer externen Datenrepräsentation), um unformatierte char-Sequenzen zu lesen bzw. zu schreiben.
4 Iterator-Hilfsfunktionen
Um die Arbeit mit den Iteratoren etwas zu erleichtern und fehlende Fähigkeiten einiger Iterator-Kategorien zu kompensieren, existieren einige Hilfsfunktionen:
- advance(it,num)
Verschiebt den Iterator 'it' um 'num' Positionen nach vorne (bzw. hinten bei negativem Wert). Für Random-Access-Iteratoren wird dafür deren operator+= verwendet, alle anderen Typen werden entsprechend oft inkrementiert oder dekrementiert. - distance(it1,it2)
Bestimmt den Abstand zwischen den Iteratoren 'it1' und 'it2'. Für Random-Access-Iteratoren wird deren operator- verwendet, bei allen anderen Typen wird gezählt, wie oft it1 inkrementiert werden muss, um it2 zu erreichen. - iter_swap(it1,it2)
Vertauscht die Elemente, auf die 'it1' und 'it2' zeigen, miteinander.
5 Algorithmen
Algorithmen sind das "Arbeitspferd" der STL. Mit ihrer Hilfe kann man fast alles mit einem Container anstellen, was man sich vorstellen kann - und wenn etwas noch nicht in der STL vorgesehen ist, lässt sich die nötige Funktion leicht selbst schreiben.
Um flexibler zu sein, werden den Algorithmen keine kompletten Container übergeben, sondern Bereiche. Auf diese Weise kann man auch Ausschnitte eines Containers oder Datensammlungen ohne direkte STL-Unterstützung verarbeiten. Ein Bereich wird definiert durch zwei Iteratoren, von denen der erste auf den Anfang und der zweite direkt hinter das Ende der zu bearbeitenden Daten zeigt - bei einem leerer Bereich fallen Anfang und Ende zusammen. Wenn ein Algorithmus mehrere Bereiche parallel bearbeitet, benötigt er häufig nur vom ersten Bereich beide Endpunkte - die Größe aller weiteren verwendeten Bereiche ergibt sich aus dem Zusammenhang (z.B. erwartet copy(), dass der Zielbereich genauso viel Platz bietet wie der Ursprungsbereich). In diesem Fall ist der Aufrufer der Funktion dafür verantwortlich, dass alle weiteren Bereiche genug Elemente enthalten (bei einem reinen "Ausgabebereich" wie für copy() ist es auch möglich, einen Insert-Iterator als Ziel anzugeben).
Wichtig ist bei der Arbeit mit Algorithmen, dass sie die unterliegende Datenstruktur nicht beeinflussen können. Sie können weder Elemente physisch löschen (stattdessen füllen sie Lücken mit nachfolgenden Werten auf und geben einen Iterator auf das "neue" Ende der Sequenz zurück), einfügen (für diesen Zweck können Inserter verwendet werden) noch die Schlüsselwerte eines assoziativen Containers modifizieren (diese sind als const definiert, damit die Ordnung der einzelnen Elemente nicht durcheinander gebracht werden kann).
Hinweis: Von etlichen Algorithmen existieren auch äquivalente Memberfunktion der Container, entweder weil diese Operationen nicht direkt möglich sind (z.B. Modifikationen an Set-Elementen) oder auf der speziellen Containerstruktur effektiver umgesetzt werden können als über die Iteratoren (z.B. Umordnen einer List oder Elementsuche in einem Binärbaum).
Achtung: Wenn ein Algorithmus mit benutzerdefinierten Prädikaten arbeitet, darf er von diesen Kopien anlegen. Deshalb sollten diese ihren internen Status während der Berechnung nicht ändern, da es sonst zu -hmm- merkwürdigen Ergebnissen kommen kann:
class Nth { int goal,count; public: Nth(int n) : goal(n), count(0) {} bool operator() (int) { return ++count == goal; } }; ... list<int> data; for(int i=1;i<=10;++i) data.push_back(i); list<int>::iterator pos = remove_if(data.begin(),data.end(),Nth(3)); data.erase(pos,data.end());//physisch löschen ...Je nach Implementation des remove_if()-Algorithmus könnte dieses Programm das dritte UND sechste Element der Liste entfernen.
Die einzelnen Algorithmen unterteilen sich je nach Wirkung in verschiedene Gruppen:
5.1 Nichtmodifizierende Algorithmen
Diese Gruppe verändert die eingegebenen Daten nicht, sondern liest lediglich auf den Daten, um z.B. das größte oder kleinste Element zu bestimmen oder festzustellen, wie oft ein bestimmter Wert in einem Bereich vorkommt.
Zu den nicht-modifizierenden Algorithmen gehören auch einige Suchfunktion für Einzelelemente, Elementsequenzen oder Mengen. Diese geben jeweils einen Iterator auf die gefundene Position zurück - oder das Ende des Suchbereiches, wenn sie keinen Erfolg hatten.
5.2 Modifizierende Algorithmen
Diese Gruppe verändert die Daten im übergebenen Datenbereich, indem sie zum Beispiel Werte kopieren, transformieren oder ersetzen. Dies passiert entweder direkt vor Ort oder während die Daten von einem Bereich in einen anderen kopiert werden.
Der einfachste Algorithmus dieser Gruppe ist copy() - dieser kopiert den Inhalt eines Bereiches in einen anderen Bereich, ohne etwas an den Elementwerten zu verändern. Von vielen anderen Algorithmen existiert neben einer "normalen" Variante, die die Elemente vor Ort modifiziert, eine Kopiervariante, die den Quellbereich unverändert lässt und die modifizierten Werte in einen neuen Bereich überträgt.
5.3 Lösch-Algorithmen
Eine spezielle Gruppe von modifizierenden Algorithmen entfernt einzelne Werte nach speziellen Kriterien aus dem übergebenen Datenbereich. Da ein Iterator keinen Speicher freigeben kann (z.B. im Fall eines Pointers in ein C-Array), geschieht das Löschen, indem hinten stehende Elemente umkopiert werden und am Ende des Ursprungsbereiches einige ungültige Werte stehen bleiben - diese müssen vom Besitzer der Daten noch manuell aufgeräumt werden. Dazu wird der Endpunkt des gekürzten Bereiches als Rückgabewert geliefert.
Nach dem logischen Löschen der Werte müssen entweder die ungültigen Daten echt gelöscht werden, indem man erase() des verwendeten Containers aufruft, oder die neue Endposition wird für weitere Operationen mitgeführt.
vector<int> data; ... vector<int>::iterator pos = remove(data.begin(),data.end(),0);//"löscht" alle Nullwerte data.erase(pos,data.end());//korrigiert Vektorgröße5.4 "mutating"-Algorithmen
Diese Gruppe lässt die Werte des übergebenen Bereiches unverändert, ändert aber nach bestimmten Kriterien ihre Reihenfolge. In diese Gruppe gehören auch Sortier-Algorithmen, die einen Bereich ganz oder teilweise sortieren, und Heap-Algorithmen, die eine spezielle Baumstruktur (Heap) in einem linearen Datenbereich erzeugen und verwalten.
In dieser Gruppe existieren auch drei verschiedene Sortier-Algorithmen, unter denen je nach Bedarf der günstigste ausgewählt werden kann:
- sort()
basiert auf dem QuickSort-Ansatz und ist im Schnitt der schnellste Algorithmus. Bei ungünstigen Eingaben kann das Verfahren jedoch quadratische Laufzeit haben - partial_sort()
basiert auf HeapSort und ist durchschnittlich etwas langsamer als sort(), hat jedoch garantierte Laufzeit von O(n*log n). partial_sort() kann auch verwendet werden, um nur einen Teil der Eingabe zu sortieren. - stable_sort()
basiert auf MergeSort und benötigt zusätzlichen Zwischenspeicher für die sortierten Elemente, um seine volle Geschwindigkeit zu entfalten. Der größte Vorteil dieses Algorithmus besteht darin, dass identische Elemente ihre ursprüngliche Reihenfolge behalten. - Heap-Algorithmen
Mit den Heap-Algorithmen lässt sich eine Datenreihe in zwei Schritten ebenfalls sortieren. make_heap() wandelt eine ungeordnete Reihe in einen Heap um und sort_heap() sortiert anschließend diesen Heap:
template<typename RanIt> void heap_sort(RanIt st,RanIt en) { make_heap(st,en); sort_heap(st,en); }- next_permutation()
Indem alle möglichen Permutationen einer Zahlenfolge durchlaufen werden, trifft man irgendwann auch die korrekt sortierte Folge - auf diese Weise lässt sich der wohl langsamste bekannte Sortieralgorithmus umsetzen:
template<typename BidIt> void slow_sort(BidIt st, BidIt en) { while(next_permutation(st,en)); }5.5 Mengen-Algorithmen
Diese Gruppe implementiert wichtige Mengenoperationen wie Vereinigung, Schnittmenge oder Elementsuche auf Wertebereichen. Sie erwarten als Vorbedingung, dass die übergebenen Bereiche sortiert sind (entsprechend dem als Parameter übergebenen Vergleichskriterium 'pred' - letzteres muss eine Ordnungsrelation (siehe Kapitel 4 im ersten Teil) definieren).
Achtung: Verwenden Sie die Mengen-Algorithmen nicht auf unsortierten Zahlenbereichen; es ist nicht definiert, ob (und wie) sie damit umgehen können.
5.6 Numerische Algorithmen
Header:
#include <numeric>Diese Gruppe wendet verschiedene mathematische Operationen auf Datenbereiche an, entweder um alle Elemente eines Bereiches zusammenzurechnen oder um Teilsummen der Elemente zu ermitteln.
Alle vier numerischen Algorithmen haben eine mathematische Bedeutung, aus der sich auch ihr jeweiliger Name ableiten lässt. Allerdings können ihnen beliebige Rechenfunktionen mitgegeben werden, die die Wirkung beeinflussen.
5.7 for_each()
template<typename It, typename func> func for_each(It st, It en,func op);Der for_each()-Algorithmus ist die "Eier legende Wollmilchsau" der STL. Er wendet die übergebene Operation auf jedes Element des Bereiches [st,en[ an und gibt sie am Ende an den Aufrufer zurück. Indem verschiedenste unäre Funktionen oder Funktoren verwendet werden, kann man nahezu alles mit den Elementen des Ursprungsbereiches anstellen - z.B. den Mittelwert zusammenrechnen, Werte ausgeben oder verarbeiten.
Es gibt drei grundlegende Möglichkeiten, wofür for_each() genutzt werden kann:
- Ausgabe von Werten:
void print(int i) { cout<<i<<" "; } list<int> cont; ... for_each(cont.begin(),cont.end(),print);//gibt Listeninhalt aus //äquivalent: copy(cont.begin(),cont.end(),ostream_iterator<int>(cout," ");- Modifikation der Werte:
void square(int& i) { i*=i; } list<int> cont; ... for_each(cont.begin(),cont.end,square);//quadriert alle Listenelemente //äquivalent: transform(cont.begin(),cont.end(),cont.begin(),cont.begin(),multiplies<int>);- Mitverfolgung des Funktorstatus:
class mean : public unary_function<double,void> { public: mean() : s(0),n(0) {} operator double() {return s/n;} void operator() (double v) { s+=v; ++n; } private: double s; unsigned n; }; list<double> cont; ... mean mv = for_each(cont.begin(),cont.end(),mean());//Mittelwert aller Elemente berechnen cout<<mv<<endl; //äquivalent: double mv = accumulate(cont.begin(),cont.end(),0) / distance(cont.begin(),connt.end());Natürlich lassen sich diese Einsatzmöglichkeiten auch kombinieren, indem zum Beispiel ein Funktor die übergebenen Werte ändert UND mitprotokolliert.
Ausblick
Mit den Iteratoren und Algorithmen haben wir alle grundlegenden Informationen, um die STL in der Praxis anwenden zu können. Allerdings gibt es in der Standardbibliothek noch etliche weitere Klassen, die zusammen mit der STL (oder auch unabhängig davon) verwendet werden können. Diese werde ich im dritten Teil der Serie behandeln.
Außerdem werde ich im nächsten Monat erklären, wie man eigene Klassen und Funktionen so entwirft, dass sie sich in die bestehende Bibliothek integrieren lassen.
-
Setzt du den Artikel dann bitte heute Abend noch auf [X]?
Ich würde gerne gleich Morgen früh veröffentlichen.
-
Nachdem wir im ersten Teil der Artikelreihe erfahren haben, wie die STL große Datenmengen organisiert und verstaut, kann es nun mit dem zweiten Teil weitergehen, in dem es um die Frage geht, wie man auf die gespeicherten Daten zugreifen kann - und wie sie effektiv verarbeitet werden.
Inhalt
- Iteratoren
- Iterator-Kategorien
- Iterator-Adapter
- Iterator-Hilfsfunktionen
- Algorithmen
1 Iteratoren
Was nützen die besten Container, wenn man nicht problemlos auf ihren Inhalt zugreifen kann? Vektoren und Deques bieten freien Zugriff auf ihre Elemente, sodass es möglich ist, sich per Index durch ihre Daten durchzuhangeln. Allerdings ist es nicht möglich, effektiv auf einer Listen- oder Baumstruktur nach einem bestimmten Index zu suchen.
Am einfachsten wäre es, für jeden Containertyp eigene Zugriffsmethoden zu definieren, die die besonderen Fähigkeiten des jeweiligen Typs ausnutzen - allerdings würde dieser Ansatz die Austauschbarkeit der Containerklassen erschweren. Deshalb geht die STL einen anderen Weg. Jeder Container bringt seine eigene Iterator-Klasse mit. Diese bieten nach außen eine passende Schnittstelle zum Datenzugriff und sind in der Lage, sich korrekt durch die interne Struktur des Containers durchzuhangeln. Die möglichen Operationen auf Iteratoren sind ganz bewusst an die von blanken C-Pointern angelehnt, bieten jedoch im Allgemeinen deutlich "intelligenteres" Verhalten - damit kann man Iteratoren als eine Form von Smart Pointern betrachten.
2 Iterator-Kategorien
Je nach Fähigkeiten werden die verschiedenen Iteratoren in Kategorien eingeordnet. Bei der Einordnung der STL-Iteratoren in diese Kategorien wurde nicht nur darauf Wert gelegt, welche Operationen technisch möglich wären, sondern auch, dass die existierenden Operationen auch relativ schnell umgesetzt werden können - ein Vektor-Iterator kann in konstanter Zeit eine beliebige Position erreichen, ein Listen-Iterator würde lineare Zeit dafür benötigen, deshalb hat er keinen operator+=.
2.1 Output-Iterator
Dies ist wohl der primitivste Iterator. Er kann lediglich Daten schlucken und inkrementiert werden, um im Speicher weiterzulaufen - dabei ist das Inkrementieren häufig als leere Operation implementiert und der operator= kümmert sich selber um die Beschaffung des Speichers oder die Weitergabe der empfangenen Daten. Es ist noch nicht einmal möglich, zwei gegebene Output-Iteratoren miteinander zu vergleichen oder festzustellen, ob das Schreiben in den Iterator erfolgreich war.
In diese Kategorie gehören zum Beispiel der Ostream-Iterator oder die Inserter.
2.2 Input-Iterator
Diese Klasse ist ähnlich einfach aufgebaut wie die Output-Iteratoren. Ein Input-Iterator kann Werte ausgeben, inkrementiert werden und mit anderen Iteratoren verglichen werden. Dieser Vergleich hat in der Regel nur Sinn, um die Gültigkeit des Iterators zu kontrollieren.
Der C++-Standard garantiert übrigens nicht, dass Kopien eines Input-Interators unabhängig voneinander genutzt werden können, um denselben Datenvorrat zweimal einzulesen.Der wichtigste Input-Iterator ist der Istream-Iterator. Im Hinblick auf seine Zugriffsmöglichkeiten auf die verarbeiteten Werte könnte man einen Set- oder Multiset-Iterator auch in diese Kategorie einordnen.
2.3 Forward-Iterator
Ein Forward-Iterator vereinigt in sich die Fähigkeiten von Output- und Input-Iterator. Er kann sowohl Daten lesen als auch schreiben und im Gegensatz zum Input-Iterator können sich verschiedene Kopien auch unabhängig voneinander durch die unterliegende Datenstruktur bewegen.
Achtung: Ein Forward-Iterator kann nicht als vollwertiger Output-Iterator eingesetzt werden, da er im Regelfall nur über eine begrenzt lange Sequenz iterieren kann:
//OK für Output-Iterator //Laufzeitfehler für Forward-Iterator while(true) *pos++ = getval(); //OK für Forward-Iterator //Compilerfehler für Output-Iterator while(pos!=end) *pos++ = getval();Die STL verwendet keine eigenen Forward-Iteratoren, aber man könnte sie sich z.B. in einer einfach verketteten Liste gut vorstellen.
2.4 Bidirektionaler Iterator
Diese Klasse erweitert den Forward-Iterator um die Fähigkeit, "rückwärts" zu laufen. Ein bidirektionaler Iterator kann sowohl inkrementiert als auch dekrementiert werden.
In diese Kategorie gehören die Iteratoren einer Liste und der assoziativen Container - wobei letztere den Schlüsselwert der iterierten Elemente nicht ändern dürfen.
2.5 Random-Access-Iterator
Random-Access-Iteratoren sind die mächtigste Kategorie von Iteratoren. Sie können beliebig durch die iterierte Struktur "springen". Zusätzlich zu Operationen, die ein bidirektionaler Iterator unterstützt, bieten sie auch Iterator-Arithmetik nach dem Vorbild der Pointer-Arithmetik von C - sie können um beliebige ganzzahlige Schrittweiten vorwärts und rückwärts durch den Speicher bewegt werden, den Abstand untereinander berechnen und mittels <,<=,>= und > verglichen werden.
In diese Kategorie fallen die Iteratoren eines Vektors oder Deque, aber auch die aus C bekannten Pointer.
3 Iterator-Adapter
Adapter werden verwendet, um das Verhalten eines Iterators zu ändern. Sie werden auf eine andere Struktur aufgesetzt und ermöglichen es, diese über die bekannten Iterator-Methoden und -Operatoren zu modifizieren.
3.1 Insert-Iteratoren
Inserter sind reine Output-Iteratoren und übersetzen Schreibzugriffe in insert()-Aufrufe des unterliegenden Containers. Mit ihrer Hilfe kann ein Container während der Arbeit erweitert werden. Auf diese Weise kann z.B. ein Algorithmus Werte in den Container einfügen, ohne sich um den verfügbaren Platz Sorgen machen zu müssen.
Außer einem normalen Insert-Iterator gibt es auch noch Back-Inserter (hängen die ankommenden Daten per push_back() an das Ende ihres Containers an) und Front-Inserter (hängen die Daten per push_front() an den Anfang des Containers an). Einen Spezial-Inserter für assoziative Container stelle ich im dritten Teil der Artikelserie vor.
Achtung: Beachten Sie beim Umgang mit Vektoren, dass push_back() und insert() vorhandene Iteratoren ungültig machen können, wenn die vorhandene Kapazität überschritten wird:
vector<int> data(10); generate_n(data.begin(),data.end(),rand);//füllen mit Zufallszahlen //verdopple Vector-Inhalt: //mögliches Problem: undefiniertes Verhalten, wenn data.capacity()<20 copy(data.begin(),data.end(),back_inserter(data));3.2 Reverse-Iteratoren
Reverse-Iteratoren verwenden als Grundlage einen beliebigen bidirektionalen Iterator und drehen dessen Laufrichtung um (aus ++ wird -- etc.). Auf diese Weise kann ein Algorithmus "rückwärts" durch eine vorgegebene Sequenz laufen (z.B. um das letzte Vorkommen eines Wertes zu finden).
Bei einem Reverse-Iterator muss zwischen der physischen Position und der logischen Position unterschieden werden - beim Dereferenzieren liefern sie jeweils das Element VOR ihrer Basisposition. Auf diese Weise ist es erstens einfacher, das "Ende" einer reversen Sequenz zu kennzeichnen (die Position hinter dem letzten Element einer Sequenz ist definiert, die Position vor dem ersten Element im Allgemeinen nicht), und zweitens enthalten damit ein Bereich und der daraus gebildete reverse Bereich dieselben Elemente in umgekehrter Reihenfolge.
Sämtliche Container der STL können über die Methoden rbegin() und rend() geeignete Reverse-Iteratoren auf den Anfang und das Ende der (rückwärts gelesenen) Elementfolge herausgeben.
3.3 Stream-Iteratoren
Stream-Iteratoren benötigen einen Eingabe- bzw. Ausgabestream und übersetzen Datenzugriffe in dessen operator>> bzw. operator<<. Auf diese Weise wird es möglich, STL-Algorithmen direkt auf Dateien oder der Benutzer-Eingabe (via cin) auszuführen bzw. ihre Resultate direkt auf die Festplatte (über ofstream's) oder den Bildschirm (cout) auszugeben.
Zusätzlich gibt es auch Streambuf-Iteratoren, die direkt auf einem Stream-Puffer operieren (die Stream-Puffer dienen als "Zwischenlager" zwischen den IO-Streams und ihrer externen Datenrepräsentation), um unformatierte char-Sequenzen zu lesen bzw. zu schreiben.
4 Iterator-Hilfsfunktionen
Um die Arbeit mit den Iteratoren etwas zu erleichtern und fehlende Fähigkeiten einiger Iterator-Kategorien zu kompensieren, existieren einige Hilfsfunktionen:
- advance(it,num)
Verschiebt den Iterator 'it' um 'num' Positionen nach vorne (bzw. hinten bei negativem Wert). Für Random-Access-Iteratoren wird dafür deren operator+= verwendet, alle anderen Typen werden entsprechend oft inkrementiert oder dekrementiert. - distance(it1,it2)
Bestimmt den Abstand zwischen den Iteratoren 'it1' und 'it2'. Für Random-Access-Iteratoren wird deren operator- verwendet, bei allen anderen Typen wird gezählt, wie oft it1 inkrementiert werden muss, um it2 zu erreichen. - iter_swap(it1,it2)
Vertauscht die Elemente, auf die 'it1' und 'it2' zeigen, miteinander.
5 Algorithmen
Algorithmen sind das "Arbeitspferd" der STL. Mit ihrer Hilfe kann man fast alles mit einem Container anstellen, was man sich vorstellen kann - und wenn etwas noch nicht in der STL vorgesehen ist, lässt sich die nötige Funktion leicht selbst schreiben.
Um flexibler zu sein, werden den Algorithmen keine kompletten Container übergeben, sondern Bereiche. Auf diese Weise kann man auch Ausschnitte eines Containers oder Datensammlungen ohne direkte STL-Unterstützung verarbeiten. Ein Bereich wird definiert durch zwei Iteratoren, von denen der erste auf den Anfang und der zweite direkt hinter das Ende der zu bearbeitenden Daten zeigt - bei einem leerer Bereich fallen Anfang und Ende zusammen. Wenn ein Algorithmus mehrere Bereiche parallel bearbeitet, benötigt er häufig nur vom ersten Bereich beide Endpunkte - die Größe aller weiteren verwendeten Bereiche ergibt sich aus dem Zusammenhang (z.B. erwartet copy(), dass der Zielbereich genauso viel Platz bietet wie der Ursprungsbereich). In diesem Fall ist der Aufrufer der Funktion dafür verantwortlich, dass alle weiteren Bereiche genug Elemente enthalten (bei einem reinen "Ausgabebereich" wie für copy() ist es auch möglich, einen Insert-Iterator als Ziel anzugeben).
Wichtig ist bei der Arbeit mit Algorithmen, dass sie die unterliegende Datenstruktur nicht beeinflussen können. Sie können weder Elemente physisch löschen (stattdessen füllen sie Lücken mit nachfolgenden Werten auf und geben einen Iterator auf das "neue" Ende der Sequenz zurück), einfügen (für diesen Zweck können Inserter verwendet werden) noch die Schlüsselwerte eines assoziativen Containers modifizieren (diese sind als const definiert, damit die Ordnung der einzelnen Elemente nicht durcheinander gebracht werden kann).
Hinweis: Von etlichen Algorithmen existieren auch äquivalente Memberfunktion der Container, entweder weil diese Operationen nicht direkt möglich sind (z.B. Modifikationen an Set-Elementen) oder auf der speziellen Containerstruktur effektiver umgesetzt werden können als über die Iteratoren (z.B. Umordnen einer List oder Elementsuche in einem Binärbaum).
Achtung: Wenn ein Algorithmus mit benutzerdefinierten Prädikaten arbeitet, darf er von diesen Kopien anlegen. Deshalb sollten diese ihren internen Status während der Berechnung nicht ändern, da es sonst zu -hmm- merkwürdigen Ergebnissen kommen kann:
class Nth { int goal,count; public: Nth(int n) : goal(n), count(0) {} bool operator() (int) { return ++count == goal; } }; ... list<int> data; for(int i=1;i<=10;++i) data.push_back(i); list<int>::iterator pos = remove_if(data.begin(),data.end(),Nth(3)); data.erase(pos,data.end());//physisch löschen ...Je nach Implementation des remove_if()-Algorithmus könnte dieses Programm das dritte UND sechste Element der Liste entfernen.
Die einzelnen Algorithmen unterteilen sich je nach Wirkung in verschiedene Gruppen:
5.1 Nichtmodifizierende Algorithmen
Diese Gruppe verändert die eingegebenen Daten nicht, sondern liest lediglich auf den Daten, um z.B. das größte oder kleinste Element zu bestimmen oder festzustellen, wie oft ein bestimmter Wert in einem Bereich vorkommt.
Zu den nicht-modifizierenden Algorithmen gehören auch einige Suchfunktion für Einzelelemente, Elementsequenzen oder Mengen. Diese geben jeweils einen Iterator auf die gefundene Position zurück - oder das Ende des Suchbereiches, wenn sie keinen Erfolg hatten.
5.2 Modifizierende Algorithmen
Diese Gruppe verändert die Daten im übergebenen Datenbereich, indem sie zum Beispiel Werte kopieren, transformieren oder ersetzen. Dies passiert entweder direkt vor Ort oder während die Daten von einem Bereich in einen anderen kopiert werden.
Der einfachste Algorithmus dieser Gruppe ist copy() - dieser kopiert den Inhalt eines Bereiches in einen anderen Bereich, ohne etwas an den Elementwerten zu verändern. Von vielen anderen Algorithmen existiert neben einer "normalen" Variante, die die Elemente vor Ort modifiziert, eine Kopiervariante, die den Quellbereich unverändert lässt und die modifizierten Werte in einen neuen Bereich überträgt.
5.3 Lösch-Algorithmen
Eine spezielle Gruppe von modifizierenden Algorithmen entfernt einzelne Werte nach speziellen Kriterien aus dem übergebenen Datenbereich. Da ein Iterator keinen Speicher freigeben kann (z.B. im Fall eines Pointers in ein C-Array), geschieht das Löschen, indem hinten stehende Elemente umkopiert werden und am Ende des Ursprungsbereiches einige ungültige Werte stehen bleiben - diese müssen vom Besitzer der Daten noch manuell aufgeräumt werden. Dazu wird der Endpunkt des gekürzten Bereiches als Rückgabewert geliefert.
Nach dem logischen Löschen der Werte müssen entweder die ungültigen Daten echt gelöscht werden, indem man erase() des verwendeten Containers aufruft, oder die neue Endposition wird für weitere Operationen mitgeführt.
vector<int> data; ... vector<int>::iterator pos = remove(data.begin(),data.end(),0);//"löscht" alle Nullwerte data.erase(pos,data.end());//korrigiert Vektorgröße5.4 Reihenfolge-Algorithmen
Diese Gruppe lässt die Werte des übergebenen Bereiches unverändert, ändert aber nach bestimmten Kriterien ihre Reihenfolge. In diese Gruppe gehören auch Sortier-Algorithmen, die einen Bereich ganz oder teilweise sortieren, und Heap-Algorithmen, die eine spezielle Baumstruktur (Heap) in einem linearen Datenbereich erzeugen und verwalten.
In dieser Gruppe existieren auch drei verschiedene Sortier-Algorithmen, unter denen je nach Bedarf der günstigste ausgewählt werden kann:
- sort()
basiert auf dem QuickSort-Ansatz und ist im Schnitt der schnellste Algorithmus. Bei ungünstigen Eingaben kann das Verfahren jedoch quadratische Laufzeit haben - partial_sort()
basiert auf HeapSort und ist durchschnittlich etwas langsamer als sort(), hat jedoch garantierte Laufzeit von O(n*log n). partial_sort() kann auch verwendet werden, um nur einen Teil der Eingabe zu sortieren. - stable_sort()
basiert auf MergeSort und benötigt zusätzlichen Zwischenspeicher für die sortierten Elemente, um seine volle Geschwindigkeit zu entfalten. Der größte Vorteil dieses Algorithmus besteht darin, dass identische Elemente ihre ursprüngliche Reihenfolge behalten. - Heap-Algorithmen
Mit den Heap-Algorithmen lässt sich eine Datenreihe in zwei Schritten ebenfalls sortieren. make_heap() wandelt eine ungeordnete Reihe in einen Heap um und sort_heap() sortiert anschließend diesen Heap:
template<typename RanIt> void heap_sort(RanIt st,RanIt en) { make_heap(st,en); sort_heap(st,en); }- next_permutation()
Indem alle möglichen Permutationen einer Zahlenfolge durchlaufen werden, trifft man irgendwann auch die korrekt sortierte Folge - auf diese Weise lässt sich der wohl langsamste bekannte Sortieralgorithmus umsetzen:
template<typename BidIt> void slow_sort(BidIt st, BidIt en) { while(next_permutation(st,en)); }5.5 Mengen-Algorithmen
Diese Gruppe implementiert wichtige Mengenoperationen wie Vereinigung, Schnittmenge oder Elementsuche auf Wertebereichen. Sie erwarten als Vorbedingung, dass die übergebenen Bereiche sortiert sind (entsprechend dem als Parameter übergebenen Vergleichskriterium 'pred' - letzteres muss eine Ordnungsrelation (siehe Kapitel 4 im ersten Teil) definieren).
Achtung: Verwenden Sie die Mengen-Algorithmen nicht auf unsortierten Zahlenbereichen; es ist nicht definiert, ob (und wie) sie damit umgehen können.
5.6 Numerische Algorithmen
Header:
#include <numeric>Diese Gruppe wendet verschiedene mathematische Operationen auf Datenbereiche an, entweder um alle Elemente eines Bereiches zusammenzurechnen oder um Teilsummen der Elemente zu ermitteln.
Alle vier numerischen Algorithmen haben eine mathematische Bedeutung, aus der sich auch ihr jeweiliger Name ableiten lässt. Allerdings können ihnen beliebige Rechenfunktionen mitgegeben werden, die die Wirkung beeinflussen.
5.7 for_each()
template<typename It, typename func> func for_each(It st, It en,func op);Der for_each()-Algorithmus ist die "Eier legende Wollmilchsau" der STL. Er wendet die übergebene Operation auf jedes Element des Bereiches [st,en[ an und gibt sie am Ende an den Aufrufer zurück. Indem verschiedenste unäre Funktionen oder Funktoren verwendet werden, kann man nahezu alles mit den Elementen des Ursprungsbereiches anstellen - z.B. den Mittelwert zusammenrechnen, Werte ausgeben oder verarbeiten.
Es gibt drei grundlegende Möglichkeiten, wofür for_each() genutzt werden kann:
- Ausgabe von Werten:
void print(int i) { cout<<i<<" "; } list<int> cont; ... for_each(cont.begin(),cont.end(),print);//gibt Listeninhalt aus //äquivalent: copy(cont.begin(),cont.end(),ostream_iterator<int>(cout," ");- Modifikation der Werte:
void square(int& i) { i*=i; } list<int> cont; ... for_each(cont.begin(),cont.end,square);//quadriert alle Listenelemente //äquivalent: transform(cont.begin(),cont.end(),cont.begin(),cont.begin(),multiplies<int>);- Mitverfolgung des Funktorstatus:
class mean : public unary_function<double,void> { public: mean() : s(0),n(0) {} operator double() {return s/n;} void operator() (double v) { s+=v; ++n; } private: double s; unsigned n; }; list<double> cont; ... mean mv = for_each(cont.begin(),cont.end(),mean());//Mittelwert aller Elemente berechnen cout<<mv<<endl; //äquivalent: double mv = accumulate(cont.begin(),cont.end(),0) / distance(cont.begin(),connt.end());Natürlich lassen sich diese Einsatzmöglichkeiten auch kombinieren, indem zum Beispiel ein Funktor die übergebenen Werte ändert UND mitprotokolliert.
Ausblick
Mit den Iteratoren und Algorithmen haben wir alle grundlegenden Informationen, um die STL in der Praxis anwenden zu können. Allerdings gibt es in der Standardbibliothek noch etliche weitere Klassen, die zusammen mit der STL (oder auch unabhängig davon) verwendet werden können. Diese werde ich im dritten Teil der Serie behandeln.
Außerdem werde ich im nächsten Monat erklären, wie man eigene Klassen und Funktionen so entwirft, dass sie sich in die bestehende Bibliothek integrieren lassen.