C++-Programmierung/ Die STL

Die STL

Zielgruppe:

Anfänger

Lernziel:
Kennenlernen und Anwenden der Standard-Template-Library.

Container

Containerklassen

In diesem Kapitel soll das Konzept generischer Container vorgestellt werden. Als Container bezeichnet man einen Datentyp, der Daten gleichen Typs in einer bestimmten Struktur zusammenfasst. Generisch bedeutet natürlich, dass die Container als Klassentemplates realisiert sind und der Typ der gespeicherten Daten so frei gewählt werden kann.

Ein einfacher Container trägt den Namen array, es bekommt zwei Templateparameter. Der Erste ist der Datentyp der Array-Elemente, der Zweite ist die Anzahl der Array-Elemente. Ein std::array ist im Grunde nichts anderes, als ein gewöhnliches C-Array, mit den zusätzlichen Eigenschaften eines STL-Containers. Welche das sind, werden wir gleich klären.

Der wohl wichtigste Container ist std::vector. Er ist im Prinzip ein Array, dessen Größe sich zur Laufzeit anpassen lässt. Er bekommt als Templateparameter also nur den Datentyp, die Anzahl der Elemente ist dynamisch. Im folgenden sollen die STL-Container und ihre Verwendung kurz erläutert werden. Folgende Typen stehen zur Verfügung:

Sequentielle Containerklassen

• array
• vector
• list
• forward_list
• deque

Assoziative Containerklassen

• unordered_map
• unordered_multimap
• unordered_multiset
• unordered_set
• map
• multimap
• multiset
• set

Containeradapterklassen (keine C++ Standardbibliothek-Iteratoren)

• priority_queue
• queue
• stack

Container sind Behälter für Objekte. Dabei wird immer eine Kopie des Objektes in dem Container gespeichert. Das hat den Vorteil, dass sich die Speicherverwaltung vereinfacht, denn das Objekt verliert seine Gültigkeit, wenn das Containerobjekt aufgelöst wird. Der Nachteil liegt auf der Hand - durch das Erstellen einer Kopie geht Zeit und Speicherplatz verloren. Es gibt aber auch Wege, Zeiger in Containern zu speichern, was aber an späterer Stelle erläutert werden soll. Ein weiterer Vorteil bei der Verwendung von Containern ist ihre einheitliche Schnittstelle zu Elementfunktionen. Das vereinfacht den Einsatz von bestimmten Algorithmen, wie sie ebenfalls in der STL zu finden sind.

Containereigenschaften

Ein vector ist im Wesentlichen ein dynamisches Feld, das je nach Bedarf seine Größe dynamisch verändern kann. Allerdings sind dabei einige Dinge zu beachten. Auf ein beliebiges Objekt innerhalb des Feldes kann sehr effizient unter direkter Adressierung zugegriffen werden - man spricht daher auch von konstantem Aufwand, da sich die Zugriffszeit nicht ändert, wenn das Feldobjekt wächst. Ebenso ist das Anhängen und Entfernen von Objekten am Ende effizient, nicht so hingegen am Anfang oder in der Mitte (linearer Aufwand). Der Container deque beherrscht ebenso wie vector das schnelle Einfügen von Objekten am Ende und dazu noch am Anfang des Feldes. Hingegen ist auch hier das Einfügen von Objekten in der Mitte sehr aufwendig. Auch dieser Containertyp unterstützt Random-Access-Operatoren, d.h. der Zugriff auf ein beliebiges Element ist sehr effizient. Der dritte sequenzielle Container ist der list-Container. Dieser Typ unterstützt nur sogenannte Bidirectional-Iteratoren. Dadurch ist ein direkter Indexzugriff wie bei den anderen Containern nicht möglich. Der Vorteil dieses Containers ist allerdings das effiziente Einfügen und Entfernen von Objekten an beliebigen Positionen des Feldes. Durch diese deutlichen Unterschiede sollte sich der Programmierer schon bei der Planung des Programms darüber im Klaren sein, welcher Containertyp am besten zu seinen Anforderungen passt.

Grundlegende Mitgliedsfunktionen der sequentiellen Containerklassen

Sequenzielle Container besitzen Funktionen wie front() oder auch back(). Damit kann auf das erste bzw. letzte Element des Containers zugegriffen werden. Darüber hinaus gibt es Funktionen, die das Anhängen und Entfernen von Elementen am Ende eines Feldes erlauben (push_back(), pop_back()). Das Einfügen/Entfernen von Objekten am Anfang wird nur von den Typen deque und list beherrscht (mittels: push_front() und pop_front()). Das direkte Indizieren beherrschen vector und deque (mittels at() bzw. mit operator[]). Die folgende Tabelle soll dies vergleichend veranschaulichen.

	vector	deque	list
front()	x	x	x
back()	x	x	x
push_back()	x	x	x
pop_back()	x	x	x
push_front()	/	x	x
pop_front()	/	x	x
at()	x	x	/
operator[]	x	x	/

Darüber hinaus sind weitere Funktionen definiert, deren konkrete Implementierung vom jeweiligen Containertyp abhängig sind. Als Beispiel sei hier der vector-Container gewählt.

Funktionsname	Beschreibung
assign	Zuweisen von Elementen zum vector
begin	gibt einen Iterator auf das erste Element zurück
capacity	gibt Anzahl an Elementen zurück die vom vector aufgenommen werden können
clear	löscht alle Elemente
empty	gibt wahr zurück wenn Container leer ist
end	gibt einen Iterator auf das letzte Element zurück
erase	löscht das Element oder eine Reihe von Elementen
insert	fügt Elemente in den Container ein
max_size	gibt die maximal mögliche Zahl von Elementen des Containers an
rbegin	gibt einen reverse Iterator auf den Anfang zurück
rend	gibt einen reverse Iterator auf das Ende zurück
reserve	setzt eine minimale Kapazität des Containers
resize	ändert die Größe des Containers
size	gibt aktuelle Größe des Feldes zurück
swap	tauscht den Inhalt des Containers mit einem anderen

Adaptive Container

Dies sind spezielle Container, die auch Containeradapter genannt werden. Insbesondere lassen sich auf diese Container keine Iteratoren definieren. Der Zugriff erfolgt ausschließlich über die Elementfunktionen dieser Typen. In der STL finden sich folgende Typen:

• stack
• queue
• priority_queue

Iteratoren

Ein besonders wichtiges Konzept in der STL sind die Iteratoren. Um maximale Flexibilität zu erreichen, arbeiten die Algorithmen der STL generell nicht direkt auf Containern, sondern greifen mittels Iteratoren auf die Container zu.

Ein Iterator ist einem Zeiger sehr ähnlich. Genaugenommen ist ein Iterator ein verallgemeinerter Zeiger, was im Umkehrschluss auch bedeutet, dass jeder Zeiger ein Iterator ist, wohingegen nicht jeder Iterator zwingend ein Zeiger sein muss.

Mit einem Iterator kann auf eine Datenstruktur in einem Datenverbund zugegriffen werden, ohne dies über einen Index der Datenstruktur zu tun. Die Zugriffe können dabei ohne Kenntnis der Datenstruktur erfolgen, was bei einem gewöhnlichen Zeiger nicht der Fall ist.

Eine Iteration beschreibt in der Informatik den schrittweisen, wiederholten (sequentiellen) Zugriff auf Elemente in einer Datenstruktur. Im folgenden Codebeispiel wird die Iteration über ein Feld aus elementarem Typen int durchgeführt:

#include <iostream>

int main(){
    const int size = 4;
    int array[size] = { 3, 5, 7, 11 };

    for(
        int* i = &array[0];    // alternativ: int* i = array;
        i <= &array[size - 1]; // alternativ: i <= array + size - 1;
        ++i
    ){
        std::cout << *i << ", ";
    }
}

Hierbei fungiert der Zeiger i als Iterator. Allerdings ist diese Vorgehensweise aus vielerlei Gründen fehleranfällig. Außerdem ist sie sehr stark am verwendeten Datentyp orientiert.

Leider bietet C++ für die eingebauten Datentypen erst ab C++11 Abhilfe. Seit dieser Version gibt es im Header iterator die Funktionen std::begin() und std::end(). Sie liefern uns für jede Datenstruktur, die Iteratoren unterstützt, die Adressen des ersten Elements und des Elements, das hinter dem Letzten liegt. Das »hinter dem Letzten« klingt im ersten Moment vielleicht ein wenig verwirrend. Stellen Sie sich das ganze mal so vor:

+----+----+----+----+----+
|  3 |  5 |  7 | 11 |    |
+----+----+----+----+----+
   ^         ^         ^
   |         |         |
 begin     iter       end

Das »Element hinter dem letzten« Existiert natürlich nicht wirklich, aber solange wir es nicht zugreifen, können wir seine Adresse als Endpunkt für unsere iteration (also das durchlaufen der Werte) verwenden. Diese Herangehensweise erlaubt es uns, in dem obigen Beispiel, die -1 beim Vergleich wegzulassen und so statt des Kleiner-oder-gleich-Operators den Kleiner-als-Operator zu verwenden. Alternativ könnten wir außerdem den Ungleichheits-Operator benutzen, denn was wir ausdrücken wollen, ist ja eigentlich: Halte an, wenn alle Daten durchlaufen wurden, also der »Endpunkt« erreicht ist.

Eine weitere Vereinfachung erlaubt uns C++11 beim Datentyp des Operators, den kann der Compiler nämlich auch selbstständig ermitteln. Wir geben daher einfach auto als Datentyp an.

#include <iostream>
#include <iterator>

int main(){
    int array[] = { 3, 5, 7, 11 };

    for(
        auto i = std::begin(array);
        i != std::end(array);
        ++i
    ){
        std::cout << *i << ", ";
    }
}

Beachten Sie an dieser Stelle ganz besonders, dass der Vergleich mit dem Ungleichheits-Operator durchgeführt wird. Das ist typisch für Iteratoren, denn im Gegensatz zu Zeigern, muss für Iteratoren der Kleiner-als-Operator nicht deklariert sein. Da es sich bei unserem Iterator auch um einen Zeiger handelt, würde die Verwendung des Kleiner-als-Operators natürlich funktionieren, es wird jedoch empfohlen immer die allgemeinste mögliche Variante zu verwenden. Auf diese Weise müssen Sie den Code für die Schleife später nicht ändern, falls Sie für Ihre Daten eine andere Struktur (also einen anderen Datentyp) verwenden.

Um es kurz an einem Beispiel zu illustrieren, die STL bietet den Datentyp std::list an. Über dessen Vor- und Nachteile können Sie sich im Kapitel über die STL-Container informieren. Die von std::list verwendeten Iteratoren besitzen keinen Kleiner-als-Operator, daher müssten Sie den Quellcode der Schleife ändern, wenn die den Datentyp in std::list ändern.

#include <iostream>
#include <list>

int main(){
    std::list< int > array = { 3, 5, 7, 11 };

    for(
        auto i = std::begin(array);
        i != std::end(array);
        ++i
    ){
        std::cout << *i << ", ";
    }
}

Damit haben Sie die Grundlagen bezüglich der Verwendung eines gewöhnlichen Zeigers als Iterator. Ich möchte an dieser Stelle noch auf eine weitere Neuheit von C++11 hinweisen. Da die Verwendung dieser Art von Iteration sehr häufig vorkommt, wurde in C++11 die for-Schleife so erweitert, dass Sie eine Datenstruktur direkt Elementweise durchgehen können. Vielleicht kennen Sie dieses Konzept aus einer anderen Programmiersprache als foreach-Schleife.

#include <iostream>
#include <list>

int main(){
    std::list< int > array = { 3, 5, 7, 11 };

    for(auto const& i: array){
        std::cout << i << ", ";
    }
}

Das funktioniert mit allen Datentypen, für die die Funktionen std::begin() und std::end() definiert sind. Wenn in diesem Fall auto als Datentyp angegeben wird, ermittelt der Compiler den Datentyp der Container-Elemente, in diesem Fall also int. Das heißt, es wird für jeden Schleifendurchlauf eine Kopie des aktuellen Elements erzeugt, die dann im Schleifenkörper verwendet wird. Wir haben also exakt die gleiche Situation, wie bei einer Funktionsübergabe mittels Call-by-Value. Wir können den von auto ermittelten Datentyp aber mithilfe von const und & in eine Referenz auf einen konstanten Integer umbiegen.

Natürlich spielt es im Fall des eingebauten Datentyps int keine Rolle ob es sich um eine Referenz handelt, aber auf diese Weise können Sie auch später einen anderen Datentyp verwenden, ohne das Ihr Code langsamer wird. Außerdem ist es wichtig diese Eigenheit von auto immer im Hinterkopf zu haben, denn wenn Sie schreibend auf die Elemente zugreifen wollen, dann brauchen Sie zwingend eine Referenz und wenn Sie nur Lesezugriff wollen, dann sollten Sie in jedem Fall zumindest ein const anhängen, um den Schreibzugriff ausdrücklich zu verbieten.

Grundlegende Eigenschaften von Iteratoren

Jedes Containerklassentemplate außer den Containeradaptern hat zugehörige Iteratortypentemplates.

Diese sind in folgende fünf Kategorien unterteilt:

• Eingabe-Iteratoren (input_iterator) und Ausgabe-Iteratoren (output_iterator)
• Forward-Iteratoren (forward_iterator)
• Bidirektionale Iteratoren (bidirectional_iterator)
• Random-Access-Iteratoren (random_access_iterator)

Ein- und Ausgabe-Iteratoren, sowie Forward-Iteratoren können nur in eine Richtung durchlaufen werden. Während man einen Forward-Iterator allerdings beliebig oft dereferenzieren darf, um auf das Element dahinter zuzugreifen, ist dies bei den Ein- und Ausgabe-Iteratoren nur einmal pro Durchlauf gestattet. Wie die Namen bereits andeuten, darf man über Eingabe-Iteratoren nur lesend und über Ausgabe-Iteratoren nur schreibend zugreifen.

Bidirektionale Iteratoren können von Vorwärts und Rückwärts durchlaufen werden. Random-Access-Iteratoren bieten sogar sogenannten »wahlfreien Zugriff« an. Das bedeutet, man kann von einem gegeben Iterator aus nicht nur den direkten Vorgänger und Nachfolger zugreifen, wie beim bidirektionalen Iteratoren, sondern alle Vorgänger und Nachfolger.

Gewöhnliche Zeiger sind immer Random-Access-Iteratoren, denn wie Sie im ersten Beispiel dieses Kapitels bereits gesehen haben, kann ausgehend vom Zeiger auf das erste Element des Array direkt das letzte Element erreicht werden. Syntaktisch gibt es hierfür zwei Möglichkeiten. Zum einen kann die Anzahl der Elemente minus Eins zu dem Start-Iterator addiert werden, zum anderen kann auch der Indexoperator [] verwendet werden, der als Parameter ebenfalls die Anzahl der Elemente minus Eins erhält.

Generell gilt in der Liste mit den Iterator-Kategorien, ein Iterator der in die Kategorie N fällt, kann auch alles, was in den Kategorien darüber verlangt wird.

Das bedeutet also, ein Datentyp sollte immer Iteratoren bereitstellen, die möglichst weit unten in der Liste stehen, damit man viel mit ihnen machen kann. Ein Algorithmus sollte hingegen immer auf Iteratoren arbeiten, die möglichst weit oben in der Liste stehen, damit er auf möglichst viele Container-Typen angewandt werden kann.

Im folgenden kleinem Beispiel wollen wir den fill-Algorithmus aus <algorithm> verwendet, um alle Elemente zwischen den übergebenen Iteratoren auf einen bestimmten Wert zu setzen.

#include <vector>
#include <algorithm>

int main(){
    std::vector< int > array(400); // Vektor mit 400 Einträgen vom Typ int
    std::fill(array.begin(), array.end(), 7); // Alle Elemente auf 7 setzen
}

Der fill-Algorithmus verlangt mindestens Forward-Iteratoren. std::vector stellt Random-Access-Iteratoren zur Verfügung, erfüllt also deutlich mehr, als hier zwingend nötig wäre. Auch std::list ist mit seinen bidirektionalen Iteratoren noch überqualifiziert und kann daher auf die gleiche Weise verwendet werden.

Beachten Sie, dass die Verwendung der STL-Algorithmen schneller sein kann, als eine Äquivalente for-Schleife. Abhängig vom tatsächlichen Typ der Iteratoren können die STL-Algorithmen unter Umständen optimierte Implementierungen verwenden, die der Compiler bei einer for-Schleifen-Version nicht finden würde.

Auch die Zeiger eines gewöhnlichen Arrays können natürlich verwendet werden, denn sie erfüllen ja die Anforderungen eines Random-Access-Iterators. An dieser Stelle sei noch einmal ausdrücklich auf die Änderungen hingewiesen, die C++11 mit sich bringt. Im Beispiel von eben wurden die Methoden array.begin() und array.end() verwendet. In C++11 sollte man stattdessen die Template-Funktionen std::begin() und std::end() verwenden. Diese sind so implementiert, dass sie die gleichnamigen Methoden aufrufen, haben aber den Vorteil, dass sie auch bei Angabe eines gewöhnlichen Array als Parameter funktionieren. Das Beispiel sieht in C++11 also so aus:

#include <vector>
#include <algorithm>

int main(){
    std::vector< int > array(400);
    std::fill(std::begin(array), std::end(array), 7);
}

Da wir std::vector verwenden, wäre es in diesem Fall natürlich noch sinnvoller, den entsprechenden Konstruktor zu verwenden, um alle Elemente mit dem Wert 7 zu initialisieren. Im folgenden Beispiel werden wir den Container mit 7 initialisieren und anschließend fill verwenden, um die Elemente mit den Indizes 5 bis 12 auf 42 zu setzen.

#include <vector>
#include <algorithm>

int main(){
    std::vector< int > array(400, 7); // 400 Werte mit 7 initialisieren
    std::fill(
        std::begin(array) + 5,        // Werte 5 bis 12
        std::begin(array) + 12,
        42                            // auf 42 setzen
    );
}

Wie Sie sehen, wird mit Hilfe des Plus-Operators vom ersten Iterator des Containers auf einen entfernten Nachfolger zugegriffen. Dies funktioniert nur bei Random-Access-Iteratoren, Sie können in diesem Beispiel also keine std::list verwenden! Dies hat nichts mit dem fill-Algorithmus zu tun, sondern kommt ausschließlich durch die Verwendung des Plus-Operators zu Stande. Sie werden im nächsten Kapitel noch lernen, wie man unter Verwendung anderer STL-Algorithmen auch in dieser Situation eine Version schreiben kann, die nur Forward-Iteratoren verlangt.

Die Art, wie in diesem Fall die Werte gesetzt werden, macht ein wenig Bauchschmerzen. Stellen Sie sich vor, der Fillaufruf würde innerhalb einer Funktion stattfinden und diese würde als Parameter den Start- und End-Index erhalten. Sie können sich sicher vorstellen, dass es leicht passieren kann, dass der zweite versehentlich kleiner als der erste ist. In diesem Fall geraten wir in eine Endlosschleife. Besser wäre es, nur den Start-Iterator anzugeben und dann die Anzahl der Werte. Der fill_n-Algorithmus bietet genau das an.

#include <vector>
#include <algorithm>

int main(){
    std::vector< int > array(400, 7); // 400 Werte mit 7 initialisieren
    std::fill_n(std::begin(array) + 5, 7, 42); // ab Index 5, 7 Werten 42 zuweisen
}

Im Gegensatz zum fill-Algorithmus verlangt std::fill_n übrigens nur Output-Iteratoren. Er lässt sich daher noch für einen sehr interessanten Zweck verwenden: Die Kombination mit einem Ausgabe-Stream!

#include <iostream>
#include <iterator>
#include <algorithm>

int main(){
    std::ostream_iterator< double > iterator(std::cout, "; ");
    std::fill_n(iterator, 5, 0.3);
}

Ausgabe:

0.3; 0.3; 0.3; 0.3; 0.3;

Ein std::ostream_iterator ist ein Output-Iterator, der bei jedem Schreibzugriff den erhaltenen Wert auf den im Konstruktor übergebenen Ausgabe-Stream schreibt und optional noch einen – ebenfalls im Konstruktor übergebenen – Separator anhängt.

Iteratoren im Detail

Wie bereits erwähnt gibt es verschiedene Iterator-Kategorien. Je nachdem, welcher Kategorie ein Iterator angehört, können unterschiedliche Operationen auf ihnen ausgeführt werden.

Allgemeine Eigenschaften

Die quasi definierende Eigenschaft von Iteratoren ist, dass sie inkrementiert werden können. Das bedeutet, dass der Iterator in der Sequenz eine Position weitergesetzt wird. Einen Iterator am Ende eines Containers kann man natürlich nicht inkrementieren, da ja keine weitere Position folgt. Allerdings ist nicht garantiert, dass der Versuch eine Fehlermeldung liefert. Meist wird, wenn nicht gerade eine Debugging-Version der STL verwendet wird, aus Gründen der Effizienz darauf verzichtet, solche Fehler in der STL abzufangen. Deshalb führen solche Fehler im Programm in der Regel zu unvorhersehbarem Verhalten; im schlimmsten Fall sieht es in Tests so aus, als ob das Programm funktionieren würde, beim tatsächlichen Einsatz des Programms tritt aber schwerwiegendes Fehlverhalten auf. Deshalb sollten solche Fehler in jedem Fall vermieden werden.

Iteratoren können sowohl mit dem Präinkrement- als auch mit dem Postinkrement-Operator inkrementiert werden:

template<typename Iterator>
void foo(Iterator i){
    Iterator j, k;
    j = ++i;
    k = i++;
}

Zeigt i ursprünglich z.B. vor das Element 1, führt die erste Zuweisung dazu, dass sowohl i als auch j nun vor Element 2 zeigen. In der zweiten Zuweisung wird i ebenfalls ein Element weitergesetzt (zeigt also hinterher vor Element 3), aber an k wird weiterhin der alte Wert zugewiesen (k zeigt also auf Element 2).

Die zweite wichtige Eigenschaft, die allen Iteratoren gemeinsam ist, ist die Möglichkeit, diese zu dereferenzieren. Dies geht über den Ausdruck *iter. Voraussetzung ist wiederum, dass es sich nicht um den Iterator aufs Ende der Sequenz handelt. Allerdings zeigen sich hier schon Unterschiede zwischen den Kategorien: Bei Ausgabeiteratoren kann an diesen Ausdruck nur zugewiesen werden. Eingabeiteratoren erlauben nur das Lesen dieses Ausdrucks. Alle anderen Iteratoren erlauben sowohl das Lesen als auch das Schreiben. Beispiel:

template<typename OutputIterator, typename InputIterator>
void iter_assign(OutputIterator ziel, InputIterator quelle){
    *ziel = *quelle;
}

Die dritte wichtige Eigenschaft von Iteratoren ist die Möglichkeit, sie zu vergleichen. Insbesondere ist der Vergleich mit einem Iterator, der bekanntermaßen aufs Ende einer Sequenz zeigt die einzige Möglichkeit, einen Iterator aufs Ende einer Sequenz zu erkennen. Hier gibt es bereits die erste Überraschung: Ausgabeiteratoren unterstützen keinen Vergleich! Man kann also insbesondere nicht testen, ob ein Ausgabeiterator das Ende einer Sequenz erreicht hat. Es liegt also immer in der Verantwortung dessen, der einen Algorithmus auf Ausgabeiteratoren aufruft, darauf zu achten, dass nicht über dessen Grenzen hinaus geschrieben wird.

Alle anderen Iteratoren können mittels operator==() und operator!=() verglichen werden. Algorithmen können insbesondere feststellen, ob sie das Ende einer Sequenz erreicht haben, indem sie den Iterator mit dem Ende-Iterator vergleichen, den der Aufrufer zur Verfügung gestellt hat. Die Tatsache, dass das Sequenzende getrennt übergeben wird erlaubt es, Algorithmen problemlos auch auf Teilsequenzen anzuwenden (beispielsweise nur die erste Hälfte der Elemente eines Arrays zu sortieren).

Zudem ist allen Iteratoren gemeinsam, dass man sie kopieren und zuweisen kann. Außerdem kann man alle Iteratoren per Default-Konstruktor erzeugen. Bei den meisten Iteratoren erhält man damit einen "singulären Wert", mit dem man nichts weiter machen kann; das einzige, was man in der Regel mit einem so erzeugten Iterator machen kann, ist ihm einen neuen Wert zuzuweisen (selbst das Vergleichen mit anderen Iteratoren ist möglicherweise nicht erlaubt!).

Ein- und Ausgabeiteratoren

Die im vorigen Abschnitt beschriebenen Eigenschaften gelten im Wesentlichen für alle Iteratoren. Allerdings hat jede Iteratorkategorie ihre ganz spezifischen Eigenschaften. Die Kategorien sind dabei nicht unabhängig voneinander, sondern bauen aufeinander auf.

Ein- und Ausgabeoperatoren haben nur die oben beschriebenen Fähigkeiten. Hinzu kommen aber zusätzliche Einschränkungen. Eine Sequenz eines reinen Ein- oder Ausgabeoperators darf nur einmal durchlaufen werden. Das bedeutet, dass auf ein bestimmtes Element nur einmal zugegriffen werden kann, je nach Iteratorkategorie lesend oder schreibend. Sobald auf das nächste Element zugegriffen wird, werden alle Iteratoren auf das alte Element ungültig. Der folgende Code ist also nicht zulässig:

template<typename OutputIterator>
void output(OutputIterator ziel){
    *ziel = 1; // Ok
    *ziel = 2; // Fehler: Zweimal auf dasselbe Element zugreifen ist nicht erlaubt!
    ++ziel;    // Ok
    *ziel = 3; // Ok
    OutputIterator kopie = ziel; // Ok
    ++ziel;    // Ok
    *ziel = 4; // Ok
    ++kopie;   // Fehler: kopie ist jetzt ungültig
}

Bei Input- und Outputiteratoren sollten Elementzugriff (also Dereferenzieren und anschließendes Lesen bzw. Zuweisen) und Inkrementieren immer abwechselnd erfolgen, also beispielsweise

*ziel = 1:
++ziel;
*ziel = 2;
++ziel;

aber nicht

*ziel = 1;
++ziel;
++ziel;
*ziel = 2;

Der Ausdruck *iter++ = a (Ausgabeiterator) bzw. a = *iter++ (Eingabeiterator) ist hingegen explizit erlaubt.

Der Grund für diese Einschränkungen liegt darin, dass der Iterator nicht unbedingt auf eine Speicherstruktur zugreifen muss. Beispielsweise kann ein Eingabeiterator von einem Hardware-Gerät lesen, und ein erneuter Leseversuch würde bereits das nächste Zeichen holen. Analog kann ein Ausgabeiterator seine Zeichen an ein Gerät versenden, das es nicht erlaubt, einen einmal gesendeten Wert noch einmal zu verändern.

Vorwärtsiteratoren

Die nächste Iterator-Kategorie sind die Vorwärtsiteratoren. Vorwärtsiteratoren sind sowohl Eingabe- als auch Ausgabeiteratoren. Zusätzlich erlauben sie, eine Sequenz mehrfach zu durchlaufen und Elemente zu überspringen. Die Codebeispiele aus dem letzten Abschnitt sind also für Vorwärtsiteratoren alle zulässig.

Vorwärtsiteratoren sind beispielsweise die passenden Iteratoren für einfach verkettete Listen (eine solche ist nicht im Standard, wird aber z.B. von der SGI-STL zur Verfügung gestellt). In einer einfach verketteten Liste ist es kein Problem, zu einem Element das Nächste zu finden (der Knoten enthält ja bereits einen Zeiger auf dieses). Allerdings ist es nicht möglich, einfach auf das vorherige Element zuzugreifen.

Bidirektionale Iteratoren

Die nächste wichtige Iteratorkategorie sind die bidirektionalen Iteratoren. Bidirektionale Iteratoren sind Vorwärtsiteratoren, die zusätzlich erlauben, in der Sequenz rückwärts zu gehen. Hierfür wird sinnvollerweise der Dekrement-Operator verwendet:

template<typename BidirectionalIterator>
void foo(BidirectionalIterator iter){
    ++iter; // setzt iter eine Position weiter
    --iter; // nun zeigt iter wieder auf dieselbe Position wie am Anfang
}

Selbstverständlich sind auch hier sowohl Prädekrement- als auch Postdekrement-Operator erlaubt.

Bidirektionale Iteratoren werden zum Beispiel in std::list und std::set verwendet.

Iteratoren mit wahlfreiem Zugriff

Schließlich gibt es noch die Iteratoren mit wahlfreiem Zugriff. Dies ist die mächtigste Iteratorklasse. Es handelt sich um bidirektionale Iteratoren, die zusätzlich erlauben, in beliebig großen Schritten in der Sequenz zu springen. Dies wird durch arithmetische Operatoren und den Index-Operator ermöglicht:

template<typename RandomAccessIterator>
void foo(RandomAccessIterator iter){
    iter += 3;       // äquivalent zu ++iter, ++iter, ++iter;
    iter -= 2;       // äquivalent zu --iter, --iter;
    *(iter + 2) = 7; // äquivalent zu tmp=iter, tmp+=2, *tmp = 7;
    *(iter - 1) = 8; // äquivalent zu tmp=iter, --tmp, *tmp = 8;
    iter[3] = 4;     // äquivalent zu *(iter + 3) = 4;
}

Da Iteratoren mit wahlfreiem Zugriff auch Ausgabeiteratoren sind, können sie selbstverständlich mit operator==() und operator!=() verglichen werden. Sofern sie in dieselbe Sequenz (also z.B. in denselben Vektor) zeigen, können sie zusätzlich auch mit den Operatoren operator<(), operator<=(), operator>() und operator>=() verglichen werden. Diese vergleichen die Positionen der Iteratoren in der Sequenz; i1 < i2 liefert also genau dann true, wenn i1 auf eine frühere Stelle in der Sequenz zeigt als i2.

Iteratoren mit wahlfreiem Zugriff werden von std::vector und std::deque zur Verfügung gestellt.

Iterator-Traits

Da Algorithmen als Templates realisiert werden, die über beliebige Iteratoren (einer bestimmten Klasse) funktionieren sollen ist es wichtig, dass der Algorithmus bestimmte Informationen über den Iterator erhalten kann. So kann es z.B. nötig sein, Werte, die vom Iterator geliefert werden, zwischenzuspeichern. Dafür muss der Typ dieses Wertes bekannt sein. Hierzu dienen die Iterator-Traits. Ein Beispiel:

template<typename OutputIterator>
set_to_default(OutputIterator iter){
    typedef typename std::iterator:traits<OutputIterator>::value_type value_type;
    *iter = value_type(); // Default-konstruiere ein value_type
}

Der Typ value_type ist hierbei der Typ der Objekte, auf die mit dem Iterator zugegriffen wird. Neben value_type gibt es noch die Typen reference (eine Referenz auf value_type), pointer (ein Zeiger auf value_type), difference_type (ein Typ, der den Abstand zweier Iteratoren speichern kann) und iterator_category (ein Typ, der die Kategorie des Iterators angibt).

Der Typ iterator_category erlaubt es, Algorithmen für verschiedene Iteratorkategorien zu überladen. Da Algorithmen als Templates definiert werden, ist dies ansonsten nicht möglich. (Die nächste Version des C++-Standards wird dies jedoch durch neue Sprachmittel ermöglichen.) Als Beispiel soll ein Algorithmus dienen, der zu zwei Iteratoren einen Iterator liefert, der genau in der Mitte zwischen zwei gegebenen Iteratoren liegt (bzw. falls die Anzahl gerade ist den letzten Iterator in der ersten Hälfte). Für diesen Algorithmus braucht man nur Vorwärts-Iteratoren. Allerdings kann er mit Random-Access-Iteratoren wesentlich effizienter implementiert werden. Zunächst die beiden Algorithmen, die die eigentliche Arbeit machen:

// Version für Vorwärtsiteratoren
template<typename ForwardIterator>
ForwardIterator internal_middle(ForwardIterator first, ForwardIterator last, std::forward_iterator_tag*){
    ForwardIterator middle = first;
    bool even_step = false;
    while (first != last){
        ++first;
        if(even_step) ++middle;
        even_step = !even_step;
    }
    return middle;
}

template<typename RandomAccessIterator>
RandomAccessIterator internal_middle(
    RandomAccessIterator first,
    RandomAccessIterator last,
    std::random_access_iterator_tag*
){
    return first + (last - first)/2;
}

Die beiden Funktionen unterscheiden sich außer in der Implementierung auch im letzten Argument: Es handelt sich um einen Zeiger auf einen "Marker-Typ". Für jede Iterator-Kategorie gibt es einen eigenen "Marker-Typ". Das Überladen nach Iterator-Kategorie kann nun über die folgende Funktion simuliert werden, die dann vom Benutzer aufgerufen wird:

template<typename ForwardIterator>
ForwardIterator middle(ForwardIterator first, ForwardIterator last){
    return internal_middle(
        first,
        last,
        (typename std::iterator_traits<ForwardIterator>::iterator_category*)0
    );
}

Wird nun middle mit Vorwärts-Iteratoren aufgerufen, so ist iterator_category ein typedef für forward_iterator_tag, weshalb die erste Version von internal_middle aufgerufen wird. Ruft man hingegen middle mit einem Iterator mit wahlfreiem Zugriff auf, ist iterator_category ein typedef für random_access_iterator_tag, und entsprechend wird die zweite Form von internal_middle verwendet.

Was aber passiert, wenn man einen bidirektionalen Iterator verwendet? Ein bidirektionaler Iterator ist ja auch immer ein Vorwärtsiterator, aber kein Iterator mit wahlfreiem Zugriff. Also sollte die erste Version von internal_middle aufgerufen werden. Dies ist in der Tat der Fall: std::bidirectional_iterator_tag ist von std::forward_iterator_tag abgeleitet, sodass die erste Version aufgerufen wird.

Wird middle hingegen mit einem reinen Eingabe- oder Ausgabe-Iterator aufgerufen, bekommt man eine Fehlermeldung. Das soll auch so sein, da ja der Algorithmus für solche Iteratoren nicht funktioniert.

Iterator-Adapter

Iterator-Adapter sind spezielle Iteratoren, die ein Iterator-Interface für andere Iteratoren bereitstellen.

Rückwärtsiteratoren

Bei bidirektionalen Iteratoren und Iteratoren mit wahlfreiem Zugriff kann die Sequenz in beide Richtungen durchlaufen werden. Algorithmen durchlaufen den übergebenen Bereich jedoch in der Regel immer vorwärts (wenngleich es Ausnahmen gibt). Deshalb gibt es Rückwärtsiteratoren, die eine gegebene Sequenz in umgekehrter Richtung durchlaufen. Die Reverse-Iteratoren werden über einen Iterator-Adapter definiert, aber normalerweise kommt man mit diesem nicht direkt in Berührung, da die Container praktischerweise den passenden Rückwärtsiterator-Typ als container::reverse_iterator zur Verfügung stellen. Zudem können über c.rbegin() und c.rend() die Grenzen der umgedrehten Sequenz abgerufen werden.

Es ist möglich, einen beliebigen Iterator in einen Rückwärtsiterator umzuwandeln. Jedoch ist hierbei eine Stolperfalle zu beachten: *reverse_iterator(iter) greift nicht auf dasselbe Element der Sequenz zu wie *iter, sondern auf das vorhergehende Element. Dies ist leicht zu verstehen, wenn wir uns das Bild von weiter oben wieder in Erinnerung rufen:

  +---+---+---+---+---+---+---+
  | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
  +---+---+---+---+---+---+---+
  ^           ^               ^
  |           |               |
begin        iter            end

Der Ausdruck *iter greift auf das nachfolgende Element zu, also auf Element 4. Die umgedrehte Sequenz sieht aber folgendermaßen aus:

  +---+---+---+---+---+---+---+
  | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
  +---+---+---+---+---+---+---+
  ^               ^           ^
  |               |           |
rbegin          riter        rend

wobei rbegin = reverse_iterator(end), riter = reverse_iterator(iter) und rend = reverse_iterator(begin). Auch in der umgedrehten Sequenz zeigt der Iterator zwischen die Elemente 3 und 4. Hier ist aber das Element 3 das folgende Element, weshalb *riter auch auf dieses zugreift.

Das folgende Programm demonstriert dies noch einmal mit einem Vektor:

#include <iostream>
#include <ostream>
#include <vector>

int main(){
    typedef std::vector<int> intvec;
    intvec v(7);
    for(int i = 0; i < 7; ++i)
        v[i] = i + 1;
    intvec::iterator iter = v.begin() + 3;
    std::cout << *iter << std::endl;              // gibt 4 aus
    std::cout << *intvec::reverse_iterator(iter); // gibt 3 aus
}

Einfügeiteratoren

Einfügeiteratoren erlauben es, neue Elemente in einen bestehenden Container einzufügen. Es gibt zwei verschiedene Adapter: insert_iterator erlaubt das Einfügen an einer vorgegebenen Stelle, back_insert_iterator fügt immer am Ende eines Containers ein. Um die Konstruktion solcher Iteratoren zu vereinfachen, gibt es die Hilfsfunktionen inserter und back_inserter. Ein Beispiel:

std::vector<int> v; // ein leerer Vektor
int array1[] = { 1, 2, 3 };
int array2[] = { 4, 5, 6 };
int array3[] = { 7, 8, 9 };
std::copy(array1, array1 + 3, std::back_inserter(v));
// jetzt: v = 1, 2, 3
std::copy(array2, array2 + 3, std::back_inserter(v));
// jetzt: v = 1, 2, 3, 4, 5, 6
std::copy(array3, array3 + 3, std::inserter(v, v.begin()+2);
// jetzt: v = 1, 2, 7, 8, 9, 3, 4, 5, 6

Stream-Iteratoren

Stream-Iteratoren sind Iterator-Adapter, die es STL-Algorithmen erlauben, direkt auf Ein-/Ausgabestreams zu arbeiten. Stream-Iteratoren sind stets reine Eingabe- oder Ausgabeiteratoren.

Zur Eingabe dienen die Iterator-Typen std::istream_iterator<T> und std::istreambuf_iterator<C>. Ein istream_iterator benutzt zum Lesen des Streams die Eingabe-Operatoren (also is >> var), um Objekte des Typs T zu lesen. Deshalb kann er für jeden Typ definiert werden, für den ein Eingabe-Operator existiert. Ein istreambuf_iterator hingegen liest die Rohzeichen direkt aus den Stream-Puffer. Deshalb muss der Zeichentyp mit dem des Streams übereinstimmen (also z.B. char für std::cin und wchar_t für std::wcin). Der End-Iterator wird in beiden Fällen über den Default-Konstruktor definiert. Das Ende der Sequenz ist dann erreicht, wenn das Lesen eines weiteren Objekts vom angegebenen Typ fehlschlägt. Das kann bedeuten, dass das Dateiende erreicht wurde, aber auch, dass ein Fehler beim Lesen der Datei aufgetreten ist. Oder für istream_iterator, dass eine unpassende Zeichenkette aufgetreten ist (also z.B. beim Einlesen von int-Objekten eine Zeichenkette, die keine Zahl darstellt). Was der Grund ist, muss am Stream-Objekt überprüft werden.

Das folgende Beispiel liest eine Liste von Ganzzahlen aus der Standardeingabe in einen Vektor:

#include <iostream>
#include <iterator>
#include <vector>

int main(){
    std::vector<int> v;
    std::copy(
        std::istream_iterator<int>(std::cin), // Lese ints von std::cin
        std::istream_iterator<int>(),         // Enditerator
        std::back_inserter(v)                 // Ziel
    );
}

Zur Ausgabe dienen die Typen std::ostream_iterator<T> und std::ostreambuf_iterator<C>. Ersterer benutzt wiederum die Ausgabeoperatoren, während der Zweite direkt auf den Rohdaten im Stream-Puffer arbeitet. Da es sich um reine Ausgabe-Iteratoren handelt, gibt es keine Ende-Iteratoren. Eine Besonderheit von std::ostream_iterator ist, dass man bei der Erzeugung zusätzlich zum Datenstrom, auf den die Objekte ausgegeben werden sollen, auch noch eine Zeichenkette angeben kann, die nach jedem Objekt ausgegeben wird.

Das folgende Beispiel liest Strings von der Standardeingabe und gibt sie jeweils in einer eigenen Zeile wieder auf der Standardausgabe aus:

#include <iostream>
#include <iterator>
#include <string>

int main(){
    std::copy(
        std::istream_iterator<std::string>(std::cin),
        std::istream_iterator<std::string>(),
        std::ostream_iterator<std::string>(std::cout, "\n")
    );
}

Algorithmen

Algorithmen

Zielsetzung

Die Algorithmen der C++ Standardbibliothek sind mächtige Werkzeuge, die aus Funktionen aufgebaut sind und numerische oder generelle Verarbeitung von Sequenzen ermöglichen. Diese Sequenzen sind durch einen Start/End-Iterator oder selten einen Start-Iterator und eine Anzahl definiert.

Die Algorithmen sind für den Einsatz mit den Standardcontainern der Standardbibliothek konzipiert, müssen aber nicht so verwendet werden, da sie ausschließlich Sequenzen verarbeiten, die durch Iteratoren dargestellt werden.

Einfach ausgedrückt: Standardcontainer, Funktionsobjekte, Prädikatoren, Iteratoren (...) sind für sich alleine wunderbare Konzepte, aber nur mit den richtigen Algorithmen ergeben sie überhaupt einen Sinn. Wenn Daten gesammelt und gespeichert werden, soll höchstwahrscheinlich auch irgendwann etwas damit gemacht werden. Um diese Verwendung zu vereinfachen und nach Möglichkeit fehleranfällige selbstgebaute Schleifen zu vermeiden, bietet die Standardbibliothek vorgefertigte Algorithmen an.

Intervalle, Sequenzen und Bereiche

Im folgenden werden Intervalle, bzw. Bereiche zwischen Iteratoren Sequenzen genannt und in Textschreibweise dargestellt. Eckige Klammern bezeichnen dabei Bereiche einschließlich der Grenzwerte, runde Klammern Intervalle ausschließlich der Grenzwerte. [a, b) ist also ein Intervall, das a enthält und b nicht. Diese Schreibweise ist in der Mathematik und in Referenzwerken zu C++ üblich, daher wird sie auch hier verwendet. In der Standardbibliothek ist eine Sequenz ein Abschnitt, der durch einen Startiterator und Enditerator begrenzt wird, der Enditerator ist jedoch meistens das erste Element hinter dem letzten Wert der Sequenz!

Referenz

Function for_each(InputIterator first, InputIterator last, Function f);

Die Funktion f wird auf alle Elemente in [first,last) angewandt. Der allgemeinste Algorithmus.

Zählen/Finden/Vergleichen

void count(InputIterator first, InputIterator last, const T& value, Size& n);

Zählt akkumulierend die Vorkommen eines Werts. Addiert auf n die Anzahl der Elemente in [first,last), die den Wert value haben.

void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n);

Zählt akkumulierend das Erfülltsein eines Prädikats. Addiert auf n die Anzahl der Elemente in [first,last), für die pred den Wert true hat.

ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);

Findet Paare gleicher aufeinanderfolgender Elemente. Liefert den ersten Iterator i in [first,last-1), so dass *i==*(i+1).

ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate bpred);

Wie die erste Instanz, nur dass die Paare nicht durch ==, sondern über das Prädikat bestimmt werden, also über bpred(*i,*(i+1))==true.

InputIterator find(InputIterator first, InputIterator last, const T &value);

Liefert einen Iterator auf das erste Element in [first,last), das den Wert value hat.

InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

Liefert einen Iterator auf das erste Element in [first,last), für das pred den Wert true hat.

InputIterator search_n*(InputIterator first, InputIterator last, Size n, const T &value);

Sucht nach einer Untersequenz aus n Vorkommen des Werts value und liefert einen Iterator auf das erste der n Elemente.

pair<InputIterator1,InputIterator2> mismatch(InputIterator first1, InputIterator1 last1, InputIterator first2);

Vergleicht paarweise die Sequenzen [first1,last1) und [first2,first2+(last1-first1)). Gibt ein Paar von Iteratoren für das erste ungleiche Elementpaar zurück. Sind die beiden Sequenzen komplett gleich, zeigen die zurückgegebenen Iteratoren hinter die Sequenzen.

pair<InputIterator1,InputIterator2> mismatch(InputIterator first1, InputIterator1 last1, InputIterator first2, BinaryPredicate bpred);

Wie die erste Instanz, nur dass gleiche Paare nicht durch == bestimmt werden, sondern über bpred(*i,*(i+1))==true.

bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator first2);

Liefert true genau dann, wenn die Sequenzen [first1,last1) und [first2,first2+(last1-first1)) elementweise gleich sind.

bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator first2, BinaryPredicate bpred);

Wie die erste Instanz, nur dass statt == das binäre Prädikat bpred benutzt wird.

ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2);

Sucht die erste Stelle in [first1,last1), ab der [first2,first2+(last1-first1)) als Untersequenz in [first1,last1) vorkommt. Gibt es keine solche Stelle, wird last1 zurückgegeben.

ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate bpred);

Wie die erste Instanz, nur dass für eine Untersequenz nicht elementweise ==, sondern das binäre Prädikat bpred erfüllt sein muss.

ForwardIterator1 find_end*(ForwardIterator1 first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2);

Wie search, liefert aber das letzte Vorkommen der zweiten Sequenz als Untersequenz in der ersten.

ForwardIterator1 find_end*(ForwardIterator1 first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate bpred);

Wie die erste Instanz, nur dass für eine Untersequenz nicht elementweise ==, sondern das binäre Prädikat bpred erfüllt sein mu&szlig.

ForwardIterator1 find_first_of*(ForwardIterator1 first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2);

Liefert einen Iterator auf das erste Element in [first1,last1), das auch in [first2,first2+(last1-first1)) vorkommt.

ForwardIterator1 find_first_of*(ForwardIterator1 first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate bpred);

Wie die erste Instanz, nur dass das Erfülltsein von bpred für ein Elementpaar ausschlaggebend ist.

Kopieren

OutputIterator copy(InputIterator first1, InputIterator last1, OutputIterator first2);

Kopiert die Sequenz [first1,last1) auf die Sequenz [first2,first2+(last1-first1)). Die Sequenzen werden dabei von links nach rechts durchlaufen. Es wird first2+(last1-first1) zurückgeliefert. Vorsicht: wenn first2 ein Element von [first1,last1) ist, sollte man die Funktion copy_backward benutzen, wenn die Zielsequenz in [first1,last1) liegt muss man es.

BidirectionalIterator2 copy_backward(BidirectionalIterator1 first1, BidirectionalIterator1 last1, BidirectionalIterator2 last2);

Kopiert die Sequenz [first1,last1) auf die Sequenz [last2-(last1-first1),last2). Die Sequenzen werden dabei von rechts nach links durchlaufen. Es wird last2-(last1-first1) zurückgeliefert.

Transformieren

OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unop);

Transformiert die Elemente aus [first,last) durch Anwendung von unop und schreibt sie nach [result,result+(last-first)). Liefert result+(last-first) zurück.

OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binop);

Kombiniert je ein Element aus [first1,last1) und [first2,first2+(last1-first1)) über binop und schreibt das Ergebnis nach [result,result+(last-first)). Liefert result+(last-first) zurück.

Ersetzen

void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);

Ersetzt in [first,last) jedes Vorkommen von old_value durch new_value.

void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);

Ersetzt in [first,last) jedes Element, das pred erfüllt, durch den Wert new_value.

OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value);

Kopiert die Sequenz [first,last) nach [result,result+(last-first)), wobei aber alle Vorkommen des Werts old_value durch den Wert new_value ersetzt werden. Gibt result+(last-first) zurück.

OutputIterator replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);

Kopiert die Sequenz [first,last) nach [result,result+(last-first)), wobei alle Elemente, die das Prädikat pred erfüllen, durch den Wert new_value ersetzt werden.

Füllen

void fill(ForwardIterator first, ForwadIterator last, const T& value);

Überschreibt alle Elemente in [first,last) mit dem Wert value.

OutputIterator fill_n(OutputIterator first, Size n, const T& value);

Überschreibt die n Elemente in [first,first+n) mit dem Wert value. Gibt first+n zurück.

void generate(ForwardIterator first, ForwardIterator last, Generator gen);

Ruft das parameterlose Funktions-Objekt gen auf und überschreibt alle Elemente in [first,last) mit dem zurückgegebenen Wert.

OutputIterator generate_n(OutputIterator first, Size n, Generator gen);

Überschreibt die n Elemente in [first,first+n) mit dem von gen zurückgegebenen Wert. Gibt first+n zurück.

Entfernen

ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);

Entfernt aus [first,last) alle Elemente mit dem Wert value. Gibt einen Iterator hinter die gekürzte Sequenz zurück.

ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);

Entfernt aus [first,last) alle Elemente, die das Prädikat pred erfüllen. Gibt einen Iterator hinter die gekürzte Sequenz zurück.

OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);

Entfernt durch Kopieren, d.h. ohne die Quellsequenz zu verändern. Kopiert die Elemente aus [first,last), die nicht den Wert value haben, in eine zusammenhängende Sequenz ab result. Gibt einen Iterator hinter die resultierende Sequenz zurück.

OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);

Wie remove_copy, kopiert aber die Elemente, die das Prädikat pred nicht erfüllen.

ForwardIterator unique(ForwardIterator first, ForwardIterator last);

Entfernt aus allen Untersequenzen von [first,last), die aus gleichen Elementen bestehen, jeweils alle Elemente bis auf das erste.

ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate bpred);

Entfernt aus allen Untersequenzen von [first,last), für die für aufeinanderfolgende Elemente bpred erfüllt ist, alle Elemente außer dem ersten.

OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result);

Entfernt doppelte durch Kopieren. Kopiert von [first,last) in eine Sequenz ab result, wobei von mehreren aufeinanderfolgenden gleichen Elementen nur das erste übernommen wird.

OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate bpred);

Kopiert von [first,last) in eine Sequenz ab result, wobei von Untersequenzen, in denen aufeinanderfolgende Elemente bpred erfüllen, nur jeweils das erste Element übernommen wird.

Reihenfolge ändern

void swap(T& a, T& b);

Vertauscht zwei Elemente.

void iter_swap(ForwardIterator1 a, ForwardIterator2 b);

Vertauscht zwei Elemente über Iteratoren auf sie.

ForwardIterator2 swap_ranges(ForwardIterator first1, ForwardIterator last1, ForwardIterator2 first2);

Vertauscht die Elemente der Sequenzen [first1,last1) und [first2,first2+(last1-first1)). Es wird first2+(last1-first1) zurückgeliefert. Das Ergebnis ist nicht definiert, wenn sich die beiden Sequenzen überlappen.

void reverse(BidirectionalIterator first, BidirectionalIterator last);

Kehrt die Reihenfolge in der Sequenz [first,last) durch Vertauschungen um.

OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);

Kopiert [first,last) nach [result,result+(last-first)) in umgekehrter Reihenfolge.

void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);

Voraussetzung: first<=middle<=last. Rotiert die Elemente in [first,last) um last-middle Positionen nach rechts. Die Sequenzen [first,middle) und [middle,last) tauschen dabei also die Plätze.

OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);

Rotiert durch Kopieren. Kopiert [middle,last) nach [result,result+(last-middle)) und [first,middle) nach [result+(last-middle),result+(last-first)).

void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);

Permutiert die Elemente in [first,last) pseudo-zufällig durch last-first-1 Vertauschungen.

void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand);

Wie die erste Instanz, wobei die Vertauschungen durch das Funktions-Objekt rand bestimmt werden. Es erhält RandomAccessGenerator::distance_type n als Parameter und muss einen pseudo-zufälligen Wert in [0,n-1] liefern.

BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

Partitioniert [first,last) so, dass hinterher alle Elemente, die pred erfüllen, vor all denen stehen, die pred nicht erfüllen.

BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

Wie partition, aber die relative Ordnung innerhalb der beiden Teile bleibt erhalten.

Sortieren

Es gibt fast alle Operationen in Paaren, von denen die erste für die Ordnung auf dem Grundtyp T mit dem Operator < arbeitet, die zweite mit einem zweistelligen Prädikat Compare. Compare repräsentiert eine vollständige Ordnung in Form von <, nicht <=. Mit not(a<b) and not(b<a) kann auf Gleichheit getestet werden.

void sort(RandomAccessIterator first, RandomAccessIterator last);

Sortiert [first,last) mit etwa der Ordnung O(n·log n) unter Verwendung von T<T für die Vergleiche.

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Sortiert [first,last) mit etwa der Ordnung O(n·log n) unter Verwendung von comp für die Vergleiche.

void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

Sortiert [first,last) mit < und erhält die relative Reihenfolge gleicher Elemente. Es wird ca. O(n·log n) oder bei Speichermangel O(n·log2 n) Zeit benötigt.

void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);

Die ersten middle-first Elemente aus [first,last) werden nach [first,middle) sortiert. Die restlichen Elemente landen in unbestimmter Reihenfolge in [middle,last).

void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);

Sortiert die ersten m:=min(last-first,result_last-result_first) Elemente und schreibt sie nach [result_first,result_first+m). Es wird result_first+m zurückgegeben. Benötigt ca. (last-first)·log m Vergleiche.

RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

Tauscht das Element nach *nth, das nach vollständiger Sortierung von [first,last) dort stehen würde. Außerdem sind nachher alle Elemente in [first,nth) kleiner als alle Elemente in [nth,last).

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

Suchen

Alle Algorithmen arbeiten zwar auch mit Vorwärts-Iteratoren, benötigen dazu aber O(n), da sie ggf. wieder links neu aufsetzen müssen. Mit Random-Access-Iteratoren wird nur O(log n) benötigt.

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

Liefert einen Iterator auf die erste Position in [first,last), in die der Wert value eingefügt werden könnte, ohne die Ordnung zu verletzen.

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);

Liefert einen Iterator auf die letzte Position in [first,last), in die der Wert value eingefügt werden könnte, ohne die Ordnung zu verletzen.

ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

pair<ForwardIterator,ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value);

Liefert begrenzende Iteratoren für die größte Untersequenz von [first,last), in die value an jede Stelle eingefügt werden könnte, ohne die Ordnung zu verletzen.

pair<ForwardIterator,ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);

Liefert true genau dann, wenn es in [first,last) ein Element mit dem Wert value gibt. (Gleichheit wird wie üblich über not(a<b) and not(b<a) bestimmt.)

bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

Verschmelzen

OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator last);

Verschmilzt zwei sortierte Sequenzen [first1,last1) und [first2,last2) in eine Sequenz ab last. Elemente aus der ersten Sequenz erscheinen dabei immer vor gleichen Elementen aus der zweiten Sequenz. Die Quellsequenzen dürfen sich nicht überlappen.

OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);

Verschmilzt die aufeinanderfolgenden sortierten Sequenzen [first,middle) und [middle,last) zu einer sortierten Sequenz [first,last). Elemente aus der ersten Sequenz erscheinen dabei vor gleichen Elementen aus der zweiten Sequenz. Es wird normalerweise O(n), bei Speichermangel O(n·log n) Zeit benötigt.

void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

Mengen-Operationen auf sortierten Sequenzen

bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

Test: [first2,last2) Teilmenge von [first1,last1) unter Verwendung von operator <.

bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);

Test: [first2,last2) Teilmenge von [first1,last1) unter Verwendung von comp.

OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

Bildet die sortierte Vereinigung von [first1,last1) und [first2,last2) und schreibt sie in eine Sequenz ab result. Bei mehrfach vorkommenden Elementen wird das erste aus der ersten Sequenz übernommen.

OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

Bildet die sortierte Schnittmenge von [first1,last1) und [first2,last2) und schreibt sie in eine Sequenz ab result. Es wird immer das jeweilige Element aus der ersten Sequenz übernommen.

OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

Bildet die sortierte Mengendifferenz [first1,last1) \ [first2,last2) und schreibt sie in eine Sequenz ab result.

OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

Bildet die sortierte symmetrische Mengendifferenz ([first1,last1) vereinigt [first2,last2)) \ ([first1,last1) geschnitten first2,last2)) und schreibt sie in eine Sequenz ab result.

OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

Heap-Operationen

Ein Heap ist eine speziell organisierte Sequenz. Das vorderste Element ist immer das größte. Es kann mit pop_heap so entfernt werden, dass die resultierende Sequenz wieder ein Heap ist. Mit push_heap kann ein beliebiges Element so eingefügt werden, dass wieder ein Heap entsteht. Beide Operationen benötigen nur O(log n) Zeit. Eine normale Sequenz muss zunächst mit make_heap umgewandelt werden.

void make_heap(RandomAccessIterator first, RandomAccessIterator last);

Wandelt die Sequenz [first,last) in einen Heap um.

void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

void push_heap(RandomAccessIterator first, RandomAccessIterator last);

Fügt das Element *(last-1) in den Heap [first,last-1) ein. Der resultierende Heap ist [first,last).

void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

void pop_heap(RandomAccessIterator first, RandomAccessIterator last);

Vertauscht *first und *(last-1), so dass [first,last-1) wieder ein Heap wird.

void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

Sortiert den Heap [first,last). Die relative Reihenfolge gleicher Elemente bleibt nicht erhalten.

void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

Weitere Operationen

ForwardIterator min_element(ForwardIterator first, ForwardIterator last);

Liefert einen Iterator auf das erste Element in [first,last), für das es kein kleineres gibt.

ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

ForwardIterator max_element(ForwardIterator first, ForwardIterator last);

Liefert einen Iterator auf das erste Element in [first,last), für das es kein größeres gibt.

ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

Liefert true genau dann, wenn die Sequenz [first1,last1) bezüglich < lexikographisch kleiner ist als die Sequenz [first2,last2).

bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

Erzeugt die nächste Permutation der Sequenz [first,last) in der lexikographischen Ordnung auf den Permutationen, die durch < auf den Elementen induziert wird. Gibt genau dann false zurück, wenn die letzte Permutation erreicht war, und transformiert die Sequenz in die erste Permutation.

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

Wie next_permutation, erzeugt aber die vorherige Permutation.

bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

Numerische Operationen

T accumulate(InputIterator first, InputIterator last, T init);

Summiert init und die Elemente in [first,last) mit +.

T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binop);

Wie die erste Instanz, nur dass binop statt + verwendet wird.

T inner_product(InputIterator first1, InputIterator last1, InputIterator first2, T init);

Berechnet ein Skalarprodukt. Liefert init plus die Summe der Produkte gleichpositionierter Elemente in [first1,last1) und [first2,last2).

T inner_product(InputIterator first1, InputIterator last1, InputIterator first2, T init, BinaryOperation1 plus, BinaryOperation times);

Wie die erste Instanz, nur dass plus statt + und times statt * verwendet wird.

OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result);

Füllt [result,result+(last-first)) mit den Partialsummen der Elemente aus [first,last), d.h. *result=*first, *(result+1)=*first+*(first+1), etc. Die beiden Sequenzen dürfen gleich sein.

OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binop);

Wie die erste Instanz, nur dass binop statt + verwendet wird. OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);

Füllt [result+1,result+(last-first) mit den Differenzen aufeinanderfolgender Elemente aus [first,last), also *(result+1)=*(first+1)-*first, etc.

OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binop);

Wie die erste Instanz, nur dass binop statt - verwendet wird.

Funktionsobjekte

Jedes Objekt, das operator() implementiert, ist ein Funktor bzw "Funktionsobjekt". Die STL verwendet Funktoren zum Sortieren in Algorithmen oder Containern. Grundsätzlich ist ein Funktor eine einfache operator() - Überladung in einem definierten Typ.

Beispiel einer Typdefinition, Implementation von operator() und eines Aufrufs:

class MeinFunktor{
public: 
    unsigned operator() (unsigned a, unsigned b){
        return (a + b);
    }
};
 
int main(){
    MeinFunktor fX;         // Instantiierung
    unsigned x = 19;              
    unsigned y = 19;
    unsigned z = fX(x, y);  // Aufruf, 'z' enthält nun 38
    return (static_cast<int> (z));
}

Funktionsobjekte sind für die Verwendung der STL-Containerklassen von Wert und können zur Modifikation, Überprüfung und für Anpassungen gesammelter Objekte in Containern verwendet werden, wir verwenden im Folgenden einen Funktor, der eine Referenz auf einen vorzeichenlosen Integraltyp erhält, dann übergeben wir den Konstruktor des Funktors an die for_each Funktion aus <algorithm> (durchläuft alle Containerinhalte von einem Startiterator bis zu einem Enditerator, wendet auf jeden Eintrag einen Funktor an:

class AnpassFunktor(){
public: 
    void operator() (unsigned & a){
        if (a > 50) a = 0;  // Alle Werte über 50 werden auf 0 gesetzt
    }
};

int main(){
    std::vector<unsigned> contZahlen;  // STL-Vektor für unsere Zahlen
           // Hier wird der Container gefüllt
    std::for_each(contZahlen.begin(), contZahlen.end(), AnpassFunktor());
           // Nun ist jeder Wert über 50 auf 0 gesetzt worden
}

Ein weiterer üblicher Anwendungsfall ist die Übergabe einer (STL-)Vergleichsfunktion an eine (STL-)Containerklasse um diese nach gewissen Vorgaben zu untersuchen. In gewissen Fällen ist durch derartige Verfahren ein erheblicher Übersichtlichkeitsgewinn bei der Entwicklung von großen Sammlungen komplexerer Typen in STL-Containerklassen möglich; zum Beispiel ein typedef list<MeinContainerEintragsTyp> listDaten, der dann eine Sortierung anhand verschiedener Mitglieder von MeinContainerEintragsTyp benötigt.

Die STL stellt dem Programmierer eine Sammlung von Funktionen zur Verfügung die helfen Funktionsobjekte zu erstellen. Diese Vorlagen befinden sich in <functional>

Zeichenketten

C++ unterstützt Zeichenketten wie im klassischen C auf Basis von Arrays. Außerdem gibt es in der STL einen eigenen Stringtypen und zwar basic_string. Hiervon wiederum gibt es zwei Spezialisierungen, string für char-Zeichenketten und wstring für wchar_t-Zeichenketten.

basic_string ist ein STL-Container und die Iteratoren und Algorithem der STL können mit diesem Container-Typen umgehen. Darüber hinaus gibt es noch weitere Eigenschaften und Fähigkeiten der Zeichenketten.

So sind weitere Zeichenkettentypen durchweg möglich: basic_string verwendet die Klasse char_traits um Attribute von Zeichen zu definieren aus denen eine Zeichenkette bestehen kann.

Durch viele bereits eingebaute Vergleichsoperatoren und Hilfsfunktionen inklusive dynamischer Längenanpassung und Teil-/Substring-Ersetzung sind die STL-Zeichenketten auf Basis von basic_string noch einfacher als die klassischen mit "char *".

In diesem Buch gibt es ein Grundlagenkapitel zum Umgang Zeichenketten. Dort gibt es viele Beispiele zur Verwendung von string.

Ein-/Ausgabe

	Dieses Kapitel ist leider noch nicht vorhanden…
	Wenn Sie Lust haben können Sie das Kapitel [[C++-Programmierung/ {{{Name}}}/ {{{Kapitel}}}|{{{Kapitel}}}]] selbst schreiben oder einen Beitrag dazu leisten.

Lokalisierung

	Dieses Kapitel ist leider noch nicht vorhanden…
	Wenn Sie Lust haben können Sie das Kapitel [[C++-Programmierung/ {{{Name}}}/ {{{Kapitel}}}|{{{Kapitel}}}]] selbst schreiben oder einen Beitrag dazu leisten.

Numerik

	Dieses Kapitel ist leider noch nicht vorhanden…
	Wenn Sie Lust haben können Sie das Kapitel [[C++-Programmierung/ {{{Name}}}/ {{{Kapitel}}}|{{{Kapitel}}}]] selbst schreiben oder einen Beitrag dazu leisten.

Ausnahmen

	Dieses Kapitel ist leider noch nicht vorhanden…
	Wenn Sie Lust haben können Sie das Kapitel [[C++-Programmierung/ {{{Name}}}/ {{{Kapitel}}}|{{{Kapitel}}}]] selbst schreiben oder einen Beitrag dazu leisten.

Runtime Type Information

	Dieses Kapitel ist leider noch nicht vorhanden…
	Wenn Sie Lust haben können Sie das Kapitel [[C++-Programmierung/ {{{Name}}}/ {{{Kapitel}}}|{{{Kapitel}}}]] selbst schreiben oder einen Beitrag dazu leisten.

Zusammenfassung

	Zu diesem Abschnitt existiert leider noch keine Zusammenfassung…
	Wenn Sie Lust haben können Sie die [[C++-Programmierung/ {{{Name}}}/ Zusammenfassung|Zusammenfassung zum Abschnitt {{{Name}}}]] selbst schreiben oder einen Beitrag dazu leisten.