4. Aufbau der STL - Teil 2: Iteratoren und Algorithmen

Aufbau der STL - Teil 2: Iteratoren und Algorithmen

  • C

    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

    1. Iteratoren
    2. Iterator-Kategorien
    3. Iterator-Adapter
    4. Iterator-Hilfsfunktionen
    5. 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

    Header:

    #include <algortihm>
//für alle Algorithmen außer Kapitel 5.6

    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öße

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

    0
  • ?

    🕶 👍

    0
  • C

    Noch eine kleine Ergänzung, auf die ich erst durch Nachfragen aus der "Bevölkerung" gekommen bin:

    um die STL-Algorithmen nutzen zu können, benötigt man den Header <algorithm> (außer den numierischen Algorithmen, die in <numeric> ausgelagert wurden).

    0
Anmelden zum Antworten