Die Standard Template Library (STL)

Willemers Informatik-Ecke

Inhalt basiert auf dem Buch C++. Der Einstieg und ist bei Wrox im Verlag Wiley-VCH erschienen.



Mehr C++ programmieren? Mit Spaß? Dies ist das Buch für Sie!

Letzte Exemplare!

Die STL ist eine hochflexible Sammlung von Template-Klassen. Leider bringt diese Flexibilität eine Komplexität mit sich, die es dem Anfänger schwer macht, die STL zu verstehen. Das wird vermutlich der Grund sein, warum sie von manchen C++-Programmierern nicht benutzt wird und von einigen C++-Büchern vollständig ignoriert wird.

Herangehensweise

Damit Sie von den Möglichkeiten der STL profitieren können, wähle ich hier einen praxisorientierten, etwas vereinfachten Ansatz. Zuerst werden Sie anhand von Arrays sehen, welche Algorithmen die STL bietet. Danach erst werden Sie die Container kennen lernen. Das sind als Templates definierte Datenbehälter, in denen Sie eigene Daten ablegen können. Die Algorithmen sind eigentlich in erster Linie für diese Container geschrieben worden. Im dritten Schritt werden die Iteratoren näher betrachtet.

Algorithmen und Arrays

Die STL bietet eine Reihe von Algorithmen an, die auf Datencontainern arbeiten. Als einfachsten Datencontainer könnte man ein Array ansprechen, an dem die Algorithmen zunächst betrachtet werden. Um die Algorithmen nutzen zu können, müssen Sie die passende Header-Datei einbinden und den Namensraum auf std setzen:

#include <algorithm>
using namespace std;

Algorithmen und Iteratoren

Die Algorithmen-Bibliothek der STL enthält Funktionen, die den Bereich, auf dem sie arbeiten sollen, als Parameter übergeben bekommen. Die Bereichsgrenzen werden durch Iteratoren bestimmt. Dabei zeigt der Anfangsiterator auf das erste Element und der Enditerator auf das Element hinter dem Ende. Bei einem Array kann ein einfacher Zeiger als Iteratorersatz verwendet werden. Soll der Algorithmus auf dem ganzen Array arbeiten, wird als Anfangsiterator die Adresse des Arrays übergeben. Als Ende-Iterator wird zu dem Zeiger einfach die Anzahl der Elemente des Arrays hinzuaddiert. Damit zeigt der Ende-Iterator hinter das letzte Element.

Suchen

Die Funktion find() sucht in dem Container, dessen Grenzen durch die ersten beiden Parameter angegeben werden, nach einem Element, das im dritten Parameter spezifiziert wird. Der Rückgabewert ist ein Iterator auf das erste gefundene Element. In diesem einfachen Fall, in dem ein Array als Container dient, ist dieser Iterator einfach ein Zeiger. Sollen alle Elemente gefunden werden, kann der zurückgegebene Zeiger inkrementiert und als Anfang der nächsten Suche verwendet werden.

Beispiel

Das folgende Beispielprogramm sucht in dem Integer-Array nach der Zahl 4. Das Ergebnis ist hier ein Zeiger auf einen Integer.

[Suche nach einer Zahl in einem Array (stl/find.cpp)]

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int zahlen[9] = {1,2,3,4,5,6,7,8,9};
    int *found;
    found = find(zahlen, zahlen+9, 4);
    if (found!=zahlen+9)
    {
        cout << "Gefunden: " << *found << endl;
    }
    else
    {
        cout << "Nichts gefunden!" << endl;
    }
}

Fehlschlag

Wurde in dem Bereich kein Wert gefunden, dann ist der Ergebniszeiger identisch zu dem Zeiger des Bereichsendes. Dieser zeigt ja auf das erste Element hinter dem zu suchenden Bereich.

Sortieren

Die Funktion sort() sortiert einen Bereich eines Containers. Wieder wird der Bereich durch die Iteratoren angegeben. Als Container wird der Einfachheit halber wieder ein Array verwendet. Als Iteratoren dienen Zeiger auf int.

[Sortieren eines Arrays (stl/sort.cpp)]

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int zahlen[9] = {3,8,1,9,5,6,4,2,9};
    sort(zahlen, zahlen+9);
    for (int i=0; i<9; i++)
    {
        cout << zahlen[i]<< endl;
    }
}

Voraussetzung

Der Algorithmus sort() arbeitet auf Arrays und
Vektoren, da er einen Direktzugriff über eckige Klammern auf die Elemente benötigt. [1] Ferner kann die Funktion sort() nur für Typen eingesetzt werden, für die der Kleiner-Operator definiert ist.

Kopieren: copy()

Die Funktion copy() kopiert einen Bereich eines Arrays in ein anderes Array.

[Kopieren]

int main()
{
    int zahlen[9] = {1,2,4,9,5,6,7,8,9};
    int ziel[5];
    copy(zahlen, zahlen+5, ziel);
}

Hier werden die ersten fünf Elemente des Arrays zahlen in das Array ziel kopiert. Dabei kontrolliert die Funktion copy() nicht, ob die Kapazität des Ziels überschritten wird. Die Funktion copy() kommt auch mit unterschiedlichen Containern zurecht.

Umdrehen: reverse

Die Funktion reverse() vertauscht die Elemente des Containers in der Art, dass sie nach dem Aufruf in umgekehrter Reihenfolge vorliegen. Das folgende Beispiel verwendet gleich zwei Algorithmen der STL. Zunächst wird das Argument des Programmaufrufs mit dem Aufruf von copy() in ein lokales char-Array namens wort kopiert. Anschließend wird auf dieses Array die Funktion reverse() angewandt, die die Zeichenkette umdreht.

[Übergabeparameter verdrehen (stl/reverse.cpp)]

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int main(int argc, char **argv)
{
char wort[80];

    copy(argv[1], argv[1]+strlen(argv[1])+1, wort);
    reverse(wort, wort+strlen(wort));
    cout << wort << endl;
}

Beim Programmaufruf ist als Parameter ein beliebiger Text zu übergeben. Das Programm gibt als Ergebnis diesen Text in umgekehrter Reihenfolge aus.

Füllen: fill

Die Funktion fill() füllt ein Array mit Werten. Als Parameter werden der Anfang und das Ende des zu füllenden Bereichs angegeben und als dritter Parameter der Wert, mit dem der Container zu füllen ist.

[Füllen]

int main()
{
    int zahlen[9] = {1,2,4,9,5,6,7,8,9};
    fill(zahlen, zahlen+9, 4);
}

Jedes Element des Arrays zahlen wird mit dem Wert 4 gefüllt.

equal()

Mit der Funktion equal() können zwei Bereiche auf Gleichheit geprüft werden. Als Parameter werden zunächst Anfang und Ende des Ausgangsbereichs angegeben. Als dritter Parameter wird der Anfang des Bereichs angegeben, mit dem verglichen werden soll:

if (equal(zahlen, zahlen+3, vgl))

Die Anweisung hinter dem if wird ausgeführt, wenn die ersten drei Werte des Arrays zahlen gleich denen des Arrays vgl sind.

Funktionen als Parameter

Einige der STL-Funktionen rufen Funktionen auf, die ihnen als Parameter übergeben werden. Ein einfacher Vertreter ist die Funktion find_if(). Ihr dritter Parameter ist eine Funktion, deren Rückgabetyp bool sein muss und deren Parameter dem Typ entsprechen muss, den der Container aufnimmt.

Prädikat

In der Aussagenlogik wird ein boolescher Term als Prädikat bezeichnet. Diese Bezeichnung wird in der STL für Funktionen mit einem Rückgabetyp bool verwendet. Die Funktion find_if() durchsucht wie die Funktion find() einen Bereich eines Containers. Dabei wird als dritter Parameter allerdings nicht ein konstanter Wert übergeben, sondern eine Funktion, die von find_if() für jedes Element des zu durchsuchenden Bereichs aufgerufen wird. Liefert diese Funktion den Wert true, endet die Funktion find_if() und liefert den Iterator (in diesem einfachen Fall einen Zeiger) auf den gefundenen Wert als Rückgabewert. Damit find_if() das zu prüfende Element an das Prädikat übergeben kann, muss es einen Parameter des Typs akzeptieren, deren Variablen der Container als Elemente aufnimmt.

Flexibel

Mit Hilfe der Funktion find_if() kann nach Elementen gesucht werden, die nur in bestimmten Teileigenschaften gleich sind oder die aufgrund von Eigenschaften gesucht werden, die nicht durch die einfache Kombination logische Operatoren auszudrücken sind.

Beispiel

Das folgende Programm verwendet die Funktion istneun() als Prädikat. Die Funktion muss einen Übergabeparameter vom Typ int haben und bool zurückgeben. Wie ihr Name schon andeutet, wird sie wahr, wenn der übergebene Parameter 9 ist.

[Suche nach einer Zahl in einem Array]

#include <iostream>
#include <algorithm>
using namespace std;

bool istneun(int parameter)
{
    return (parameter==9);
}

int main()
{
int zahlen[9] = {1,2,3,9,5,6,7,8,9};
int *found;

    found = find_if(zahlen, zahlen+9, istneun);
    if (found!=zahlen+9)
    {
        cout << *found << " - " << endl;
    }
    else
    {
        cout << "nix" << endl;
    }
}

Da eine Funktion extrem flexibel ist, kann nahezu nach allen Kriterien gesucht werden. Beispielsweise könnte das Prädikat ermitteln, ob die Zahl eine Primzahl ist. In manchen Fällen ist eine Funktion aber immer noch nicht ausreichend flexibel. Betrachten wir den Fall, dass die erste Zahl gesucht wird, die kleiner ist als der Vorgänger im Container. Im vorhergehenden Beispiel wäre dies die 5. Als Funktion könnten Sie das so formulieren:

bool KleinerAlsVorgaenger(int parameter)
{
    static letzter = INT_MIN;
    bool rueckgabe;
    rueckgabe = parameter < letzter;
    letzter = parameter;
    return rueckgabe;
}

Wiederholungsfalle

Tatsächlich funktioniert dies beim ersten Einsatz wunderbar. Allerdings wird die Funktion direkt anschließend unbrauchbar, da sie sich in ihrer statischen Variablen letzter den Wert 5 gemerkt hat. Würde sie erneut für das gleiche Array verwendet, würde bereits die 1 als gesuchte Zahl gemeldet, da sie kleiner als 5 ist. Um diese Problematik zu lösen, könnten Sie die Variable letzter als globale Variable verwenden, die vor dem Aufruf von find_if() zurückgesetzt werden muss. Abgesehen davon, dass globale Variablen vermieden werden sollten, hinterlässt diese Lösung einen faden Nachgeschmack.

Funktionsobjekt

Wenn es um Initialisierungsprobleme geht, bietet sich der Einsatz einer Klasse an. Hier kann im Konstruktor eine Variable leicht zurückgesetzt werden. Um den Anforderungen der Funktion find_if() gerecht zu werden, kann der Funktionsoperator überladen werden. Das vollständige Programm sieht folgendermaßen aus:

[Einsatz eines Funktionsobjekts (stl/findif.cpp)]

#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;

class tKleinerAlsVorgaenger
{
public:
    tKleinerAlsVorgaenger() { letzter = INT_MIN; }
    bool operator()(int a);
private:
    int letzter;
};

bool tKleinerAlsVorgaenger::operator()(int a)
{
    bool rueckgabe;
    rueckgabe = a < letzter;
    letzter = a;
    return rueckgabe;
}

int main()
{
int zahlen[9] = {1,2,3,9,5,6,7,8,9};
int *found;
tKleinerAlsVorgaenger rueckfall;

    found = find_if(zahlen, zahlen+9, rueckfall);
    if (found!=zahlen+9)
    {
        cout << *found << endl;
    }
    else
    {
        cout << "nix" << endl;
    }
}

Randbedingungen

Es sollte allerdings nicht unerwähnt bleiben, dass für jeden Aufruf von find_if() ein neues Objekt der Klasse tKleinerAlsVorgaenger verwendet werden muss, damit der Konstruktor das Datenelement letzter zurücksetzen kann. Alternativ könnte natürlich eine Elementfunktion Reset() in die Klasse eingebaut werden, die das übernimmt. Sie können aber auch die folgende Variante einsetzen:

found = find_if(zahlen, zahlen+9, tKleinerAlsVorgaenger());

Hier wird der Konstruktor der Klasse tKleinerAlsVorgaenger aufgerufen, der ein temporäres Objekt an die Funktion übergibt, die dann wiederum als Prädikat aufgerufen wird. Dann könnte auch die Zeile mit der Definition der Variablen rueckfall weggelassen werden.

for_each

Funktionalität

Die Funktion for_each() führt die Funktion, die sie als dritten Parameter übergeben bekommt, für alle Elemente eines Containers aus, dessen Grenzen sie in den ersten beiden Parametern übergeben bekommt. Das folgende Beispiel ruft für jedes Element die Funktion show() auf, die das Element auf dem Bildschirm ausgibt. Das Ergebnis des Programms ist also eine Ausgabe des Arrays auf dem Bildschirm.

[Ausgabe per for_each (stl/foreach.cpp)]

#include <iostream>
#include <algorithm>
using namespace std;

int show(int a)
{
    cout << a << endl;
}

int main()
{
int zahlen[9] = {1,2,4,9,5,6,7,8,9};

    for_each(zahlen, zahlen+9, show);
}

Der Parameter der Funktion show() muss ein Element des Containers akzeptieren. Der Rückgabewert sollte vom gleichen Typ sein. Die Funktion for_each() reicht den Rückgabewert der letzten Funktion an seinen Aufrufer durch.

Container und Iteratoren

Template-Container

Die Algorithmen der STL sind nicht speziell für Arrays entwickelt worden, sondern für die verschiedenen Container, die die STL dem Programmierer anbietet. Ein Container ist eine Datenstruktur, die andere Daten aufnimmt und organisiert. Ein Beispiel für solch einen Container kann eine Liste oder ein Baum sein. Da die Container auf Templates basieren, können beliebige Datentypen in den Containern abgelegt werden. Wie ein Datenbehälter mit Hilfe von Templates für beliebige Datentypen angelegt werden kann, wurde schon mit der Klasse
Stack gezeigt.

Spezialisierung

Die STL bietet sehr unterschiedliche Container. Sie sind für bestimmte Einsätze spezialisiert. So sind Vektoren optimal, wenn auf die einzelnen Elemente wahlfrei zugegriffen werden muss. Eine Liste ist ideal, wenn die Anzahl der Elemente extrem schwankt, und Bäume eignen sich für Daten, die sortiert abgelegt und schnell aufgefunden werden sollen.

Iterator

Für den Zugriff auf die Elemente der Container verwendet die STL Iteratoren. Sie sind Zeigern sehr ähnlich, sind aber an ihre Container angepasst. Sie bilden das Glied zwischen Container und Anwendung.

Die Container-Klasse vector

Flexibles Array

Der Vektor ist wohl der Container, der am einfachsten zu verstehen ist. Er ähnelt dem Array, ist aber wesentlich flexibler. Wie bei einem Array befinden sich alle Elemente direkt nebeneinander im Speicher, und man kann jeweils über ihre Positionsnummer direkt auf sie zugreifen. Sogar die rechteckigen Klammern arbeiten, wie man es vom Array her kennt. Neu ist, dass die Größe des Vektors nicht zum Übersetzungszeitpunkt durch eine Konstante festgelegt werden muss. Sie kann nicht nur zur Laufzeit berechnet werden; die Größe kann sogar nachträglich verändert werden.

Dimensionen

Ein Vektor ist wie ein Array eine lineare Sequenz von Speicherblöcken. Dabei wird zwischen Größe (size) und Kapazität (capacity) unterschieden. Die Kapazität ist die für den Vektor reservierte Speichermenge. Dadurch kann dem Vektor eine Reserve zugeordnet werden, die erst gefüllt werden kann, bevor eine Vergrößerung dazu führt, dass ein neuer Speicherbereich angelegt und der bisherige Vektor umkopiert werden muss. Die Größe (size) bezieht sich auf die tatsächlich belegten Elemente. Die Information über die Größe liefert die Elementfunktion size(). Die Kapazität lässt sich über die Elementfunktion capacity() ermitteln. Die Größe des Arrays wird mit der Elementfunktion resize() verändert. Mit der Funktion reserve() kann die Kapazität erweitert werden. Beide Funktionen haben einen ganzzahligen Parameter, der die zukünftige Größe angibt.

Beispiel

Im folgenden Beispiel definieren wir einen Vektor und experimentieren ein wenig mit den Eigenheiten.

[Größe und Kapazität eines Vektors]

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int MaxVec = 5;
    vector<int> Zahlen(MaxVec);

    cout << Zahlen.size() << " - " << Zahlen.capacity() << endl;
    Zahlen[MaxVec+1] = 12; // Wird nicht aufgenommen
    Zahlen.at(MaxVec+1) = 12; // Wird geprüft
    Zahlen.reserve(20);  // Kapazität ist nun 20
    cout << Zahlen.size() << " - " << Zahlen.capacity() << endl;
    for(int i=0; i<MaxVec; i++)
    {
        Zahlen[i] = i;
    }
    Zahlen.resize(MaxVec+3); // Hier wird die Größe erhöht
    Zahlen[MaxVec+1] =12; // Nun passt es
    cout << Zahlen.size() << " - " << Zahlen.capacity() << endl;
}

Betrachten wir das Listing Schritt für Schritt:

int MaxVec = 5;
vector<int> Zahlen(MaxVec);

Die Variable MaxVec wird zur Dimensionierung des Vektors verwendet. Bei einem Array ist zu diesem Zweck nur eine Konstante zulässig. In der nachfolgenden Zeile wird ein Vektor definiert. In den spitzen Klammern steht der Datentyp, den der Vektor aufnehmen soll. Hier ist es int. Der Name des Vektors lautet Zahlen. Es folgen nicht die eckigen Klammern eines Arrays, sondern die runden Klammern, die anzeigen, dass ein Konstruktor mit Parametern aufgerufen wird. Mit diesem Wert wird der Vektor also vorbelegt.

Zahlen[MaxVec+1] =12; // Wird nicht aufgenommen

Der Zugriff außerhalb der Kapazität führt durchaus nicht zum Abbruch des Programms. Die Zahl 12 wird außerhalb des reservierten Bereichs abgelegt. Sie können den Wert zwar anschließend auch wieder ausgeben. Er befindet sich aber nicht im Kontrollbereich des Vektors. Bei der nächsten Änderung der Kapazität wird dieser Wert nicht mit übernommen, wenn der Inhalt des bisherigen Vektors kopiert wird. Viel schlimmer ist, dass mit diesem Befehl in nicht festgelegten Speicher geschrieben wird. Auf diese Weise kann eine andere Variable überschrieben oder eine Rücksprungadresse im Stack zerstört werden.

Zahlen.at(MaxVec+1) = 12; // Wird geprüft

Im Gegensatz zu dem Zugriff über die eckigen Klammern wird der Zugriff über die Elementfunktion at() geprüft und löst bei Fehlern eine Ausnahme out_of_range aus (zum Thema Ausnahmebehandlung siehe hier). Solange leicht überschaubar ist, dass Sie die Grenzen des Vektors nicht verletzen, ist die Verwendung der eckigen Klammern angebracht, da der Zugriff durch das Fehlen der Prüfung schneller ist. Ansonsten bewahrt Sie die Funktion at() vor schweren Fehlgriffen.

Zahlen.reserve(20);  // Kapazität ist nun 20

Kapazität

Mit dem Aufruf von reserve() wird die Kapazität erhöht. Das bedeutet, dass so viel Speicher reserviert wird, dass der Vektor nicht umkopiert werden muss, solange die Größe nicht größer wird als dieser Wert. Der Parameter gibt die Zielgröße an, also nicht etwa die Differenz, um die die Kapazität wachsen soll. Die aktuelle Kapazität eines Vektors kann mit der Elementfunktion capacity() ermittelt werden.

Zahlen.resize(MaxVec+3); // Hier wird die Größe erhöht

Größe

Die Größe des Vektors gibt an, wie viele gültige Werte der Vektor enthält. Nur diese Größe wird bei einem automatischen Umkopieren mitgenommen. Der Parameter der Funktion resize() ist wiederum die Zielgröße und nicht der Wert, um den die Größe wachsen soll. Die aktuelle Größe eines Vektors liefert die Funktion size().

Algorithmen

Die Algorithmen-Bibliothek, die oben anhand von Arrays vorgeführt wurden, arbeitet ebenso auf einem Vektor. Eigentlich ist die Algorithmen-Bibliothek der STL sogar in erster Linie für die Container entwickelt worden. Dass sie auch auf Arrays funktionieren, ist eigentlich ein Nebeneffekt.

Beispiel

Betrachten wir also die Sortierung eines Vektors. Zunächst wird der Vektor mit Zufallszahlen gefüllt. Anschließend wird die Funktion sort() mit dem Anfangs- und Enditerator als Parameter aufgerufen.

[Sortieren eines Vektors]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int MaxVec = 9;
    vector<int> zahlen(MaxVec);

    srand(0);
    for(int i=0; i<MaxVec; i++)
    {
        zahlen[i] = rand() % 9 + 1;
    }

    sort(zahlen.begin(), zahlen.end());

    for (int i=0; i<MaxVec; i++)
    {
        cout << zahlen[i]<< endl;
    }
}

Iteratoren

Beim Aufruf der Funktion sort() werden die Grenzen nicht, wie beim Array, durch die Zeiger auf die erste und hinter die letzte Position bestimmt. Im Gegensatz zu einer Array-Variablen besteht das Objekt zahlen der Klasse vector ja nicht aus den Datenelementen. Ein Zeiger auf zahlen zeigt auf das Objekt, das die Daten verwaltet. Um die Grenzen des Vektors zu beschreiben, gibt es Iteratoren. Alle Container-Klassen haben die Elementfunktionen begin(), um einen Iterator auf das erste Element zu liefern, und die Elementfunktion end(), die den Iterator zurückgibt, der hinter das letzte Element zeigt. Der Iterator eines Vektors ist einem Zeiger recht ähnlich, da die Struktur linear im Speicher liegt. Man kann nicht nur vorwärts und rückwärts durch den Container laufen, sondern auch direkt auf einzelne Elemente zugreifen. Aufgrund der leichten Handhabbarkeit wird dieser Iterator auch >>Random Access Iterator<< genannt, übersetzt etwa >>Iterator mit wahlfreiem Zugriff<<.

Binäres Suchen

Liegt ein sortierter Bereich in einem Vektor vor, kann mit Hilfe der Funktion binary_search() darin nach einem Wert gesucht werden. Diese Suche ist sehr schnell, aber abhängig davon, dass direkt auf die Elemente eines Containers zugegriffen werden kann. Dementsprechend kann er für Vektoren und auch für Arrays eingesetzt werden, aber nicht für verkettete Listen.

if (binary_search(zahlen.begin(), zahlen.end(), SuchWert))

Die Funktion liefert einen booleschen Wert zurück, je nachdem, ob der Wert gefunden wurde oder nicht. Die nachfolgende Tabelle zeigt die wichtigsten Elementfunktionen des Containers vector in einer Übersicht: [Die wichtigsten Elementfunktionen von vector]
Funktion Bedeutung
begin() Liefert die erste Position des Vektors
end() Zeigt hinter die letzte Position des Vektors
at(int) Geprüfter Zugriff auf Element des Vektors
size() Liefert die Anzahl der Elemente eines Vektors
capacity() Liefert die Kapazität eines Vektors
resize(int) Verändert die Größe
reserve(int) Verändert die Kapazität

Vektor als Stack

push_back()

Für den Vektor sind Funktionen definiert, die es ermöglichen, mit dem Vektor einen Stack zu realisieren. Durch Aufruf der Elementfunktion push_back() können am Ende des Vektors Elemente hinzugefügt werden. Als Parameter wird der Funktion ein Wert des Typs übergeben, über den der Vektor definiert ist. Der Vektor wächst in seiner Größe um eins.

back()

Um das letzte Element zu lesen, gibt es die Funktion back(). Die Funktion hat keine Parameter und liefert nur den Wert des letzten Elements. Der Stack, respektive der Vektor, wird nicht verkleinert.

pop_back()

Mit der Funktion pop_back() wird ein Element vom Stack entfernt. Auch diese Funktion hat keine Parameter. Sie hat den Rückgabetyp void, liefert also weder den Wert des letzten Elements, noch gibt sie an, ob die Operation erfolgreich war. Das ist besonders deswegen bedauerlich, weil beispielsweise der GNU-Compiler bei einem überzähligen Pop die Vektorgröße auf 4.294.967.295 setzt. Der Wert muss also vor dem Aufruf von pop_back() mit der Funktion back() ausgelesen werden. Die Applikation muss sicherstellen, dass kein Pop auf einen leeren Stack ausgeführt wird.

[Stack-Funktionen des Vektors]

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> Zahlen;
    Zahlen.push_back(8);
    Zahlen.push_back(7);
    Zahlen.push_back(6);
    do
    {
        cout << ": " << Zahlen.back();
        Zahlen.pop_back();
    } while (Zahlen.size());
    cout << endl;
}

Die Container-Klasse deque

Der Container deque (Das Wort wird wie >>Deck<< ausgesprochen. Vermutlich wird man Sie besser verstehen, wenn Sie >>double ended queue<< sagen.) verhält sich weit gehend wie ein Vektor. Beispielsweise ist der Indexoperator verfügbar. Sie können also über die eckigen Klammern auf ein Element zugreifen. Allerdings gibt es keine Möglichkeit, die Kapazität festzulegen oder zu erfragen. Der Name >>double ended queue<< (übersetzt etwa: Schlange mit zwei Enden) deutet schon an, dass der Container nicht nur am Ende wachsen kann, sondern auch am Anfang. Sie können sich eine Deque bildlich wie zwei Vektoren vorstellen. Der eine Vektor realisiert den Anfang, der andere das Ende der Deque. Die Indexnummern werden vom ersten Element bis zum letzten durchgezählt. Kommt ein Element am Anfang hinzu, wird die Nummerierung für jedes Element um eins erhöht, und das neue Element bekommt die Nummer 0. Für den Anwender der Deque entsteht der Eindruck, als wären alle Elemente um eine Position verschoben worden.

Hier steht im Buch die Abbildung "Deque" (picdeque)

Funktionen

Um am Anfang der Liste arbeiten zu können, gibt es Funktionen, die denen für das Ende der Liste entsprechen. Die Funktion front() liefert das erste Element. Mit der Funktion push_front() wird am Anfang einer Deque ein neues Element eingehängt. Die Funktion erwartet als Parameter das neue Element. Schließlich gibt es die Funktion pop_front(), die ein Element vom Anfang der Deque entfernt. Um die Operationen am Ende der Deque auszuführen, werden die vom Vektor bekannten Funktionen back(), push_back() und pop_back() verwendet.

gpBeispiel

Das folgende Beispiel zeigt einen FIFO-Puffer (FIFO: first in first out). Jede Warteschlange ist ein FIFO. Wer sich zuerst angestellt hat, kommt auch als erstes an die Reihe. Die Elemente kommen also in der Reihenfolge zum Vorschein, wie sie hineingestellt wurden. Im Beispiel werden tausend mal tausend Elemente in den Puffer geschoben und gleich anschließend wieder herausgeholt. Die Funktion clock() zählt die CPU-Ticks, wird also zur Messung der Laufzeit herangezogen.

[Deque als FIFO (stl/deque.cpp)]

#include <iostream>
#include <deque>
using namespace std;
#include <time.h>

int main()
{
    clock_t start, end;
    start = clock();

    deque<int> Puffer;
    for(int i=0; i<1000; i++)
    {
        for (int j=1; j<1000; j++)
        {
            Puffer.push_front(j);
        }
        do
        {
            Puffer.pop_back();
        } while (Puffer.size());
    }
    end = clock();
    cout << start << ":" << end << endl;
}

Wenn Sie statt deque den Container list aus dem nächsten Abschnitt verwenden, werden Sie feststellen, dass die Deque wesentlich schneller ist. Der Grund liegt in der internen Struktur. Die Messung zeigt, dass es wichtig ist, zu wissen, welcher Container für die gewünschte Anwendung optimal ist. Die folgende Aufstellung fasst die Funktionen zusammen, mit denen am Anfang und am Ende Elemente ein- und ausgehängt werden können:

push_front(obj)
Am Anfang der Liste wird ein Objekt eingefügt.
push_back(obj)
Am Ende der Liste wird ein Objekt eingefügt.
pop_front(obj)
Am Anfang der Liste wird ein Objekt entnommen.
pop_back(obj)
Am Ende der Liste wird ein Objekt entnommen.
front(obj)
Liefert eine Referenz auf das Element am Anfang der Liste.
back(obj)
Liefert eine Referenz auf das Element am Ende der Liste.
Es ist zwar möglich, Elemente aus der Mitte einzufügen und zu löschen, das ist allerdings weniger effizient. Sind diese Operationen häufiger erforderlich, sollte der Container list verwendet werden. Das Einfügen erfolgt über die Elementfunktion insert(). Elemente werden mit erase() wieder gelöscht.

Die Container-Klasse list

Doppelt verkettet

Während der Vektor einem Array gleicht, ähnelt der Container list eher einer doppelt verketteten Liste und dürfte in den meisten Fällen auch so implementiert sein. Eine verkettete Liste wurde bereits bei der Programmierung des Stacks an verschiedenen Stellen des Buches vorgestellt. Dabei zeigt jedes Element mit einem Zeiger auf das nachfolgende Element. Die Elemente können vereinzelt an beliebiger Stelle im Speicher stehen. Darum muss dieser Container auch nicht umkopiert werden, wenn er wächst. Ein neues Element wird angefordert und in die Kette integriert. Um an das letzte Element zu gelangen, muss sich das Programm von Element zu Element durchhangeln. Eine doppelt verkettete Liste ist so aufgebaut, dass jedes Element zwei Zeiger besitzt. Der eine Zeiger zeigt auf den Nachfolger, der andere auf den Vorgänger in der Liste. Das führt zu einem gewissen Mehraufwand beim Einhängen neuer Elemente. Dafür ist es leichter möglich, an beiden Enden Elemente an- oder abzuhängen und in beiden Richtungen zu navigieren.

Vor- und Nachteile

Gegenüber der Deque oder dem Vektor ist eine Liste vor allem dann im Vorteil, wenn in der Mitte der Liste neue Elemente eingehängt oder gelöscht werden sollen. In einer Liste müssen die anderen Elemente ja nicht verschoben zu werden, um Platz zu schaffen oder eine Lücke zu schließen. Beim Einfügen mit insert() wird Platz für ein Element angefordert. Es wird an der Stelle in die Kette eingehängt, die der Iterator bezeichnet. Die Nachbarelemente müssen nicht nebeneinander angeordnet sein, und darum müssen sie auch nicht verschoben werden. Das Gleiche gilt für das Löschen aus der Mitte der Liste mit erase(). Die Lücke muss nicht aufgefüllt werden. Der Preis dafür ist, dass es nicht sehr effizient ist, auf ein bestimmtes Element der Liste über seine Position zuzugreifen. Um das fünfzigste Element zu erreichen, muss sich das Programm fünfzigmal weiterhangeln. Aus diesem Grund unterstützt die Liste einen Zugriff über die eckigen Klammern nicht.

Listen-Iteratoren

Um eine Stelle in der Liste zu bezeichnen, an der neue Elemente eingefügt oder existierende gelöscht werden sollen, benötigen Sie einen Iterator. Jeder Container enthält die Definition für einen auf ihn passenden Iterator unter dem Namen iterator. Um einen solchen Iterator zu definieren, muss zunächst der Containertyp genannt werden. Dann folgen zwei Doppelpunkte, um anzuzeigen, dass der in dieser Klasse definierte Iteratortyp gemeint ist, und dann natürlich der Name des Iterators. Die folgende Zeile definiert einen Iterator für eine Integer-Liste:

list<int>::iterator IntegerListenIterator;

begin() und end()

Um die Iteratoren zu benutzen, müssen sie initialisiert werden. Sie werden zunächst typischerweise auf den Anfang der Liste gesetzt. Den Anfangsiterator eines Containers liefert immer die Elementfunktion begin(). Um durch den Container zu laufen, wird der Iterator inkrementiert. Die Elementfunktion end() des Containers liefert die Iteratorposition hinter dem letzten Element. Sobald also der Laufparameter gleich dem Rückgabewert von end() ist, ist der Durchlauf beendet. Daraus ergibt sich folgende typische for-Schleife zum Durchlaufen einer Liste:

list<int>::iterator Iter;
for(Iter=Liste.begin(); Iter!=Liste.end(); ++Iter)
Wird innerhalb einer solchen Schleife eine Position gefunden, an der ein neues Element eingefügt werden soll, so wird Iter als erster Parameter für die Elementfunktion insert() verwendet. Der Iterator zeigt auf das Listenelement, vor dem das neue Element eingefügt werden soll.

Liste.insert(Iter, NeuesElement);

Zum Entfernen eines Elements aus der Liste wird die Funktion erase() verwendet. Ihr einziger Parameter ist der Iterator, der auf das Listenelement zeigt, das Sie löschen wollen. Da dieser Iterator durch das Löschen ungültig wird, liefert die Funktion erase() den Iterator, der auf das nun nächste Element zeigt. Dieser Iterator wird dann benötigt, wenn nach dem Löschen die Liste weiter durchlaufen werden soll.

Iter = Liste.erase(Iter);

Beispiel

Im folgenden Listing wird ein wenig mit einer Liste herumgespielt, um die verschiedenen Funktionsaufrufe zu demonstrieren.

[Listenspielereien]

#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> zahlen;
    list<int>::iterator lIter; // Iterator definieren

    srand(0);
    for(int i=0; i<10; i++)
    {
        zahlen.push_back( rand() % 9 + 1 );
    }
    // Durchlaufen und anzeigen
    for(lIter=zahlen.begin(); lIter!=zahlen.end(); ++lIter)
    {
        cout << *lIter << endl;
    }
    // vor jeder 8 eine -1 einfügen und jede 2 löschen
    for(lIter=zahlen.begin(); lIter!=zahlen.end(); ++lIter)
    {
        if (8==*lIter)
        {
            zahlen.insert(lIter, -1);
        }
        else if (2==*lIter)
        {
            lIter = zahlen.erase(lIter);
        }
    }
    // Durchlaufen und anzeigen
    for(lIter=zahlen.begin(); lIter!=zahlen.end(); ++lIter)
    {
        cout << *lIter << endl;
    }
}

Auch hier wird das Programm Schritt für Schritt erläutert. Das Listing beginnt mit der Definition der Liste:

list<int> zahlen;

Die Liste nimmt int-Werte auf. Sie soll Zahlen enthalten, darum heißt sie etwas phantasielos zahlen.

list<int>::iterator lIter; // Iterator definieren

Als Nächstes wird ein Iterator angelegt. Er soll später durch die Liste laufen und die Basis für das Einfügen und Löschen von Elementen bilden. Vorher soll aber zunächst die Liste gefüllt werden:

for(int i=0; i<10; i++)
{
    zahlen.push_back( rand() % 9 + 1 );
}

In dieser for-Schleife werden einfach zehn Zufallszahlen gebildet und mit Hilfe der Elementfunktion push_back() an das Ende der Liste angehängt.

// Durchlaufen und anzeigen
for(lIter=zahlen.begin(); lIter!=zahlen.end(); ++lIter)
{
    cout << *lIter << endl;
}

Hier sehen Sie die Funktionsweise des Iterators. Als Startanweisung wird der Iterator auf den Anfang des Containers gesetzt. Die Elementfunktion begin() gibt einen Iterator zurück, der auf den Anfang eines Containers zeigt. Die Elementfunktion end() liefert die Position hinter dem letzten Element. Sobald der Iterator das Ende der Liste erreicht hat, wird er den gleichen Wert haben, den die Funktion end() liefert. Solange der Iterator ungleich dem Rückgabewert von end() ist, wird die Schleife nicht verlassen. Der Iterator kann durch den Inkrementierungsoperator erhöht werden. Innerhalb der Schleife zeigt sich eine weitere Eigenschaft des Iterators. Er kann beim Zugriff auf das Objekt wie ein Zeiger verwendet werden. Dem Iterator wird ein Stern vorangestellt, um das Element zu erreichen, auf das er zeigt. Anschließend beginnt wiederum eine Schleife, die durch die Liste läuft. Hier soll zur Demonstration des Einfügens und Löschens vor jede 8 eine -1 eingefügt werden und jede 2 gelöscht werden.

if (8==*lIter)
{
    zahlen.insert(lIter, -1);

Ob das Listenelement eine 8 enthält, wird wieder geprüft, indem mit dem Stern über den Iterator zugegriffen wird. Dann wird die Elementfunktion insert() der Liste aufgerufen. Als ersten Parameter enthält sie den aktuellen Iterator. Das neue Element wird an der Position des Iterators eingefügt - und damit vor dem aktuellen Element. Der zweite Parameter von insert() enthält das neu einzufügende Objekt, hier die -1.

lIter = zahlen.erase(lIter);

Zum Löschen wird die Funktion erase() verwendet. Als Parameter bekommt sie den Iterator auf das Objekt, das gelöscht werden soll. Der Iterator, der als Parameter übergeben wird, wird nach dem Aufruf ungültig. Das Element, auf das er zeigte, wurde ja gelöscht. Der Rückgabewert von erase() liefert aber den nächsten gültigen Iterator. Durch Zuweisung des Rückgabewertes an den bisherigen Iterator kann mit ihm einfach weitergearbeitet werden.

Umhängen von Elementen: splice

Mit der Elementfunktion splice() werden Elemente einer Liste in eine andere Liste verschoben. Derartige Vorgänge lassen sich mit Listen extrem effizient realisieren, weil die eigentlichen Daten nicht bewegt werden müssen, sondern nur ein paar Zeiger umgehängt werden. Je nach ihren Parametern führt die Funktion splice() leicht abgewandelte Operationen aus. So können einzelne Elemente, aber auch ganze Listen umgehängt werden.

Beispiel

Um die verschiedenen Varianten zu demonstrieren, werden zwei Listen vorbereitet. Die Liste Quelle enthält die Elemente 0, 1, 2, 3 und die Liste Ziel die Elemente 100 und 200. Der Iterator Pos zeigt auf das Element 200 der Liste Ziel. Der Iterator QuellAnf zeigt auf 1, der Iterator QuellEnde auf 3.

Liste einfügen

Die Funktion splice() fügt in die aktuelle Liste vor der Position Pos die Elemente der Liste OrgList ein.

void splice(iterator Pos, list<T>& Quelle);

Der Iterator Pos muss ein Iterator der Liste sein, für die splice() ausgeführt wird. Der Aufruf lautet:

Ziel.splice(Pos, Quelle);

Danach enthält die Liste Ziel die Elemente 100, 0, 1, 2, 3, 200. Die Liste Quelle ist anschließend leer.

Einzelelement umhängen

Mit der Funktion splice() kann auch ein einzelnes Element von einer Liste in die andere umgehängt werden.

void splice(iterator Pos, list<T>& Quelle, iterator QuellAnf);

Mit diesen Parametern fügt die Funktion splice() in die aktuelle Liste vor der Position Pos das Element ein, das an der Position QuellAnf der Liste Quelle steht. Dabei wird das Element QuellAnf aus der Liste Quelle entfernt. Der Aufruf lautet:

Ziel.splice(Pos, Quelle, QuellAnf);

Danach enthält die Liste Ziel die Elemente 100, 1, 200. Die Liste Quelle enthält 0, 2, 3.

Teilliste umhängen

In der letzten Variante werden aufeinander folgende Elemente der Liste Quelle umgehängt.

void splice(iterator Pos, list<T>& Quelle, 
            iterator QuellAnf, iterator QuellEnde);

In dieser Variante werden alle Elemente der Liste Quelle von QuellAnf bis QuellEnde an die Position Pos umgehängt. Wie bei den Iteratoren üblich, zeigt auch hier QuellEnde als Endebegrenzer auf die Position hinter dem letzten Element, das mitgenommen wird.

Ziel.splice(Pos, Quelle, QuellAnf, QuellEnde);

Danach enthält die Liste Ziel die Elemente 100, 1, 2, 200. Die Liste Quelle enthält 0, 3.

Mischen sortierter Listen

Die Elementfunktion merge() erlaubt es, in eine sortierte Liste eine andere sortierte Liste einzusortieren. Die Zielliste enthält dann alle Elemente in sortierter Reihenfolge. Die eingefügte Liste ist nach dem Aufruf leer.

Ziel.merge(Quelle);

Container-Adapter

Container-Adapter basieren auf Containern, um spezielle Schnittstellen zu liefern. So kann ein Stack beispielsweise mit Hilfe eines Vektors realisiert werden. Der Stack bietet dem Benutzer nur eine eingeschränkte Schnittstelle an. Ein Adapter besitzt keine Iteratoren. Auf der Basis der sequenziellen Container vector, deque und list werden die Container-Adapter stack, queue und prioritiy_queue definiert.

Container-Adapter stack

Ein Stack speichert seine Elemente in der Reihenfolge ihres Eintreffens und gibt sie in umgekehrter Reihenfolge wieder heraus. Er entspricht also einem Stapel, auf den nur von oben zugegriffen werden kann. Der Container-Adapter stack bietet als Schnittstelle die folgenden drei Funktionen an:
push(obj)
Das Objekt wird auf den Stack gelegt.
top()
Das oberste Objekt des Stapels wird als Rückgabewert geliefert. Es wird jedoch nicht vom Stack entfernt.
pop()
Das oberste Objekt wird vom Stack entfernt. Es gibt keinen Rückgabewert.
Um also ein Objekt vom Stack zu lesen und herunterzunehmen, müssen die Funktionen top() und pop() nacheinander aufgerufen werden. Ein kleines Beispiel zeigt, wie ein solcher Stack verwendet wird.

[Stack-Adapter (stl/stack.cpp)]

#include <iostream>
#include <stack>
using namespace std;

int main()
{
   stack<int> Stapel;
   Stapel.push(3);
   Stapel.push(2);
   Stapel.push(1);
   while (!Stapel.empty())
   {
       cout << Stapel.top() << endl;
       Stapel.pop();
   }
}

Standardmäßig wird ein Stack auf der Basis einer Deque implementiert. Wollen Sie den Stack als Liste repräsentiert wissen, müssen Sie auch list einbinden. Schließlich wird bei der Definition des Stacks angegeben, welcher Container als Basis dient. Sie müssen folgende Änderungen vornehmen:

#include <list>
#include <stack>
...
   stack<int, list<int> > Stapel;

Das Leerzeichen zwischen den beiden Kleiner-Zeichen vor dem Wort >>Stapel<< sollten Sie nicht vergessen. Es kann Ihnen sonst passieren, dass einer der Compiler das doppelte Größer-Zeichen für einen Umleitungsoperator hält.

Der Container-Adapter queue

Analog zum Stack gibt es einen Adapter, der als FIFO arbeitet: die Queue. Eine Queue besitzt zusätzlich zu den Funktionen des Container-Adapters stack die Funktionen front() und back(), die jeweils ein Element zurückgeben. Dafür gibt es die Funktion top() nicht mehr.
push(obj)
Ein Objekt wird hinten in den Puffer hineingeschoben.
pop()
entnimmt vorne das zuerst eingefügte Objekt.
front()
liefert eine Referenz auf das vorderste Element.
back()
liefert eine Referenz auf das zuletzt eingestellte Element.

[Queue (stl/queue.cpp)]

#include <iostream>
//#include <list>
#include <queue>
using namespace std;

int main()
{
   queue<int> FIFO;
//   queue<int, list<int> > FIFO;
   FIFO.push(4);
   FIFO.push(3);
   FIFO.push(2);
   FIFO.push(1);
   while (!FIFO.empty())
   {
       cout << FIFO.front() << endl;
       FIFO.pop();
   }
}

Die auskommentierten Zeilen können Sie verwenden, um die Queue auf Basis einer Liste einzusetzen. Standardmäßig wird eine Deque verwendet.

Container-Adapter priority_queue

Dieser Adapter unterscheidet sich von einer queue dadurch, dass die eingeschobenen Elemente eine Priorität mitbekommen. Dabei sind die Funktionen mit denen eines Stacks vergleichbar. Die Warteschlange wird als priority_queue definiert. Der Unterschied zeigt sich im internen Verhalten: Die Warteschlange prüft die Elemente mit Hilfe des Kleiner-Operators auf ihre Priorität und liefert das Element mit der höchsten Priorität als Erstes wieder aus. In dem folgenden Beispiel werden ganze Zahlen in die Warteschlange geschoben, die dann sortiert wieder herausgegeben werden. In einem realen Einsatz würden Sie natürlich eine Datenklasse definieren, die den Kleiner-Operator überlädt und damit die Prioritäten liefern kann.

[Priority-Queue (stl/pqueue.cpp)]

#include <iostream>
#include <queue>
using namespace std;

int main()
{
   priority_queue<int> FIFO;
   FIFO.push(4);
   FIFO.push(7);
   FIFO.push(5);
   FIFO.push(1);
   while (!FIFO.empty())
   {
       cout << FIFO.top() << endl;
       FIFO.pop();
   }
}

Die Container-Klassen set und multiset

Der Container set stellt die eingefügten Elemente sofort in einer sortierten Reihenfolge ab. In einem set darf jedes Element nur einmal auftreten. In einem multiset dürfen Elemente dagegen mehrfach auftreten. Der Container set ist ein assoziativer Container. Das heißt, dass er die Elemente nach einem Schlüsselwert in einem Binärbaum sortiert.

Vor- und Nachteile

Wenn Sie Daten nach einem Sortierkriterium in einer Struktur ablegen wollen und schnell wieder auf sie zugreifen wollen, dann ist der Container set die ideale Struktur. In einer Liste erfolgt das unsortierte Einfügen zwar sehr effizient, aber das Auffinden der entsprechenden Position kostet zu viel Zeit, und das Sortieren muss nachträglich durch den Aufruf von sort() erfolgen.

Einfügen und Löschen

Die Operationen für das Einfügen, insert(), und das Löschen, erase(), benötigen beim Container set nun keinen Iterator mehr, sondern erwarten den Wert, der eingefügt oder gelöscht werden soll. Die Funktion insert() liefert einen Iterator zurück, der auf das neu eingefügte Element zeigt. Das folgende Beispiel fügt zufällige Zahlen in ein Set ein. Doppelte Zahlen werden nicht eingefügt, da es sich um ein Set und nicht um ein Multi-Set handelt. Anschließend wird die Zahl 4 aus dem Set wieder gelöscht.

[Einfügen und Löschen in set (stl/set.cpp)]

#include <iostream>
#include <set>
using namespace std;

void show(set<int> &zahlen)
{
    set<int>::iterator iter;
    for(iter=zahlen.begin(); iter!=zahlen.end(); ++iter)
    {
        cout << *iter << " - " ;
    }
    cout << endl;
}

int main()
{
    set<int> zahlen;
    int neuzahl;
    srand(0);
    for(int i=0; i<10; i++)
    {
        neuzahl = rand() % 9 + 1 ;
        zahlen.insert(neuzahl);
        cout << neuzahl << " - " ;
    }
    cout << endl;
    show(zahlen);
    zahlen.erase(4);
    show(zahlen);
}

Suchen

Das Suchen in einem Binärbaum ist sehr effizient. Darum ist die Elementfunktion find() des Containers set auch wesentlich schneller als die allgemeine Funktion find(), die für alle Container gedacht ist. Die Funktion erwartet als Parameter den zu suchenden Wert und liefert als Ergebnis einen Iterator, der auf das Element zeigt. Gibt es das Element im Container set nicht, ist der Iterator identisch zu dem Rückgabewert der Elementfunktion end().

Sortierung

Damit der Container set Elemente in der richtigen Reihenfolge einsortieren kann, muss für den Typ der Elemente das Kleiner-Zeichen definiert sein. Alternativ kann beim Anlegen eines Containers set ein Prädikat für den Typ angegeben werden, das die Kleiner-Relation ersetzt. Dazu wird eine Klasse als Funktionsobjekt gebildet, die den Vergleich liefert. Im folgenden Beispiel wird ein Prädikat erstellt, das statt eines Kleiner-Vergleichs, eine Größer-Relation bildet. Dadurch wird die Reihenfolge des Sets umgedreht.

[Vergleichsklasse (stl/setsort.cpp)]

#include <iostream>
#include <set>
using namespace std;

class Anders
{
public:
    bool operator() (int a, int b)
    {
        return a > b;
    }
};

void show(set<int,Anders> &zahlen)
{
    set<int>::iterator iter;
    for(iter=zahlen.begin(); iter!=zahlen.end(); ++iter)
    {
        cout << *iter << " - " ;
    }
    cout << endl;
}

int main()
{
    set<int,Anders> zahlen;
    srand(0);
    for(int i=0; i<10; i++)
    {
        zahlen.insert( rand() % 9 + 1 );
    }
    show(zahlen);
}

Die Klasse Anders wird als zweiter Template-Parameter verwendet. Dadurch werden die Elemente in diesem Fall absteigend sortiert. Bei der Klasse Anders handelt es sich um ein ganz typisches Funktionsobjekt. Sie sehen, dass der Aufrufoperator definiert wurde. Da der Rückgabetyp bool ist, handelt es sich um ein Prädikat. An der Funktion show() ist auch zu sehen, wie ein Container als Parameter an eine Funktion übergeben wird.

Die Container-Klassen map und multimap

Der Container map nimmt zwei Arten von Elementen auf. Die erste Art ist der Suchschlüssel, der wie bei einem Set in einem Binärbaum abgestellt wird. Die zweite Art ist das eigentliche Datenelement, das durch den Schlüssel gefunden werden soll. So werden bei der Definition eines Map-Containers zwei Typen angegeben: der erste für den Schlüssel, der zweite für den Wert. Die eckigen Klammern werden von der Map so überladen, dass der Schlüssel dazwischen angegeben wird. Der gesamte Ausdruck bezeichnet dann das Datenelement. Auf diese Weise kann sehr anschaulich mit der Map programmiert werden.

[Beispiel für Map (stl/map.cpp)]

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main()
{
    map<string,string> Kennzeichen;
    Kennzeichen["HH"] = "Hansestadt Hamburg";
    cout << Kennzeichen["HH"] << endl;
    cout << "Größe: " << Kennzeichen.size() << endl;
    cout << Kennzeichen["HG"] << endl;
    cout << "Größe: " << Kennzeichen.size() << endl;
}

Wenn Sie das Programm laufen lassen, erhalten Sie die folgende Ausgabe:

Hansestadt Hamburg
Größe: 1

Größe: 2

find()

Ganz offensichtlich wird also für den Schlüssel HG allein durch die Verwendung in den eckigen Klammern ein Element angelegt. Wollen Sie lediglich prüfen, ob es ein solches Element überhaupt gibt, sollten Sie die Elementfunktion find() verwenden:

if (Kennzeichen.find("KI")==Kennzeichen.end())
{
    cout << "Nicht gefunden!" << endl;
}

Iteratortypen

Iteratoren bieten die Möglichkeit, in standardisierter Form auf Elemente eines Containers zuzugreifen. Da auf die verschiedenen Container auf unterschiedliche Weise zugegriffen wird, liefert jeder Container den zu ihm passenden Iteratortyp unter dem Namen iterator mit.

Schnittstelle

Damit bilden die Iteratoren die Verbindung für die STL-Algorithmus-Funktionen, um auf die Container zuzugreifen. Auf diese Weise kann der Container ausgetauscht werden, ohne dass die STL-Funktion davon betroffen ist. Allerdings eignen sich nicht alle Container für jeden Zugriff. So werden verschiedene Arten von Iteratoren unterschieden, je nachdem, welche Zugriffsmöglichkeiten sie anbieten. Die Arten der Iteratoren sind der RandomAccessIterator, der BidirectionalIterator, der ForwardIterator, der InputIterator und der OutputIterator. Tabelle (tabiter1) zeigt die Operationen, die mit den jeweiligen Iteratortypen möglich sind. [Iteratoren]
Output Input Forward Bidirectional RandomAccess
Lesen =*p =*p =*p =*p
Zugriff -> -> -> ->, []
Schreiben *p= *p= *p= *p=
Iteration ++ ++ ++ ++, -- ++, --, +, -, +=, -=
Vergleich ==, != ==, != ==, != ==, !=, <, >, <=, >=

Containerabhängigkeit

Hinter dem Typ iterator, den der Container anbietet, steckt einer der oben genannten Iteratoren. Welchen Iterator der Container anbieten kann, hängt natürlich mit den Möglichkeiten des Zugriffs zusammen, die der Container bietet. Tabelle (tabiter2) zeigt, welcher Container welchen Iterator anbietet.
Container Iterator
vector RandomAccessIterator
deque RandomAccessIterator
string RandomAccessIterator
list BidirectionalIterator

[Container und Iteratoren]
Container Iterator
map BidirectionalIterator
multimap BidirectionalIterator
set BidirectionalIterator
multiset BidirectionalIterator

Die Template-Klasse bitset

Konstruktion

Die Template-Klasse bitset gehört ebenfalls zur STL, ist aber kein Container, denn sie nimmt keine Benutzertypen auf, um sie zu organisieren. Sie bietet vielmehr eine Möglichkeit, Bitstrukturen zu verwalten. Der Parameter, den das Template erhält, ist kein Datentyp, sondern eine ganzzahlige Konstante, die angibt, wie viele Bits das Bitset enthält.

Bitoperationen

Sie können einzelne Bits mit der Elementfunktion set() setzen und mit reset() löschen. Die Elementfunktion flip() schaltet ein Bit um. Als Parameter wird die Position des gewünschten Bits angegeben. Wird kein Parameter angegeben, wird die Funktion auf alle Bits des Bitsets angewandt.

Prüfen

Die Elementfunktion test() liefert einen bool-Wert, der angibt, ob das Bit, dessen Position als Parameter übergeben wird, gesetzt ist. [Bitset-Funktionen]
Wirkung
bool test(size_t pos) gibt true zurück, wenn Bit gesetzt ist
bitset<N> set(size_t pos, int var=1) Setzt das Bit an Position pos
bitset<N> reset(size_t pos, int var=0) Löscht das Bit an Position pos
bitset<N> flip(size_t pos) Schaltet das Bit an Position pos um

Indexoperator

Das Bitset kann mit Hilfe des Indexoperators wie ein Array behandelt werden. Dadurch werden die Zugriffe anschaulicher. Die Elementfunktion count() liefert die Anzahl der gesetzten Bits eines Bitsets, die Funktion size() dessen Größe in Bits. Die Funktion any() liefert true, wenn mindestens ein Bit des Bitsets gesetzt ist. Die Funktion none() wird wahr, wenn keines der Bits gesetzt ist. [Weitere Bitset Funktionen]
Funktion Wirkung
size_t count() Anzahl der gesetzten Bits des Bitsets
size_t size() Anzahl der Bits des Bitsets
bool any() gibt true zurück, wenn eines der Bits gesetzt ist
bool none() gibt true zurück, wenn keines der Bits gesetzt ist
Das Bitset kennt die Funktionen to_ulong() und to_string(), um das komplette Bitset in eine ganze Zahl oder in eine Zeichenkette zu überführen.
[1]
Konkret gesagt: Er benötigt Random-Access-Iteratoren. Was es mit diesen Iteratoren auf sich hat, wird im Zuge des Kapitels noch geklärt.


Informatik-Ecke Einstieg in C++ (C) Copyright 2005, 2014 Arnold Willemer