• Algorithmen und Arrays
• Container und Iteratoren
• vector
• deque
• list
• Container-Adapter
• set / multiset
• map / multimap
• Iteratortypen
• bitset

Herangehensweise

Algorithmen und Arrays

#include <algorithm>
using namespace std;

Algorithmen und Iteratoren

Suchen

Beispiel

[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

Sortieren

[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

Kopieren: copy()

[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

[Ü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

[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()

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

Prädikat

Flexibel

Beispiel

[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

Funktionsobjekt

[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

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

[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

Spezialisierung

Iterator

Die Container-Klasse vector

Flexibles Array

Im folgenden Beispiel werden die Lottozahlen wie bekannt mit einem Array realisiert:

int main() {
    const int MAX = 6;
    int lotto[MAX];

    for (int i=0; i<MAX; i++)
    {
        lotto[i] = 1+i*i;
    }
}

#include <vector>

int main() {
    const int MAX = 6;
    std::vector<int> lotto(MAX);

    for (int i=0; i<MAX; i++)
    {
        lotto[i] = 1+i*i;
    }
}

Dynamik

Im folgenden Beispiel wird der Vektor ohne Angabe einer Größe definiert. Die Vektor-Funktion push_back fügt am Ende jeweils einen Wert zum Vektor hinzu. Die Größe des Vektors ändert sich dabei ständig. Die aktuelle Größe des Vektors liefert dessen Funktion size.

#include <iostream>
#include <vector>

int main() {
    const int MAX = 6;
    std::vector<int> lotto;
    for (int i=0; i<MAX; i++)
    {
        lotto.push_back(1+i*i);
    }
    for (int i=0; i<lotto.size(); i++)
    {
        std::cout << lotto[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "Größe: " << lotto.size() << std::endl;
}

Kapazität und Größe

• Die Information über die Größe liefert die Elementfunktion size(). Die Größe des Arrays kann durch die Elementfunktion resize() verändert werden. Der Parameter gibt die zukünftige Größe an.
• Die Kapazität lässt sich über die Elementfunktion capacity() ermitteln. Mit der Funktion reserve() kann die Kapazität erweitert werden. Der Parameter gibt die zukünftige Kapazität an.

Grenzüberschreitung

#include <vector>

int main()
{
    std::vector<int> v(16);
    v[2000] = 12; // Unkontrollierte Speicherveränderung

Der Zugriff über die rechteckigen Klammern soll möglichst effizient laufen. Also verzichtet C++ auf eine Prüfung. Wenn aber die Überprüfung gewünscht wird, können Sie den Zugriff über die Elementfunktion at ausführen.

#include 

int main()
{
    std::vector v(16);
    v.at(2000) = 12; // Zugriff 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.

Algorithmen

Beispiel

[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

Binäres Suchen

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()

back()

pop_back()

[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

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

Funktionen

gpBeispiel

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

Die Container-Klasse list

Doppelt verkettet

Vor- und Nachteile

Listen-Iteratoren

list<int>::iterator IntegerListenIterator;

begin() und end()

list<int>::iterator Iter;
for(Iter=Liste.begin(); Iter!=Liste.end(); ++Iter)

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);

Das Löschen ist ein wenig kitzlich, da man leicht den Ast absägt, auf dem man sitzt.

for (auto iter=c.begin(); iter!=c.end(); /* nicht inkrementieren */ ) {
  if (kannWeg(iter))
    iter = c.erase(i);
  else
    ++iter;
}

Beispiel

[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

Beispiel

Liste einfügen

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

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

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

Ziel.merge(Quelle);

Container-Adapter

Container-Adapter stack

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.