C++-Programmierung: Standard Template Library

Alte Seite

Diese Seite gehört zum alten Teil des Buches und wird nicht mehr gewartet. Die Inhalte sollen in das neue Buch einfließen: C++-Programmierung/ Inhaltsverzeichnis.
Eine aktuelle Seite zum gleichen Thema ist unter C++-Programmierung/ Die STL verfügbar.

Einleitung

Die STL (Standard Template Library) ist eine Sammlung von verschiedenen Klassentemplates und generischen Algorithmen. Diese Bibliothek wurde geschaffen, um oft wiederkehrende Aufgaben zu generalisieren und wurde als Erweiterung in den C++-Standard aufgenommen. Das hat den Vorteil, dass ein Standard geschaffen wird, der als Referenz für viele Aufgaben dienen kann. Beispielsweise muss ein Programmierer nicht mehr über die Begrenzungen eines Feldes nachdenken. Benutzt er stattdessen den Standardkontainer zum Speichern beliebiger Datentypen, bekommt er diese Funktionalität automatisch zur Verfügung gestellt. Ein einfaches Beispiel ist der Standardvektor:

'"`UNIQ--source-00000000-QINU`"'

Das hat den Vorteil, dass gegenüber einem C-Array int array[10]; die Größe nicht von vornherein festgelegt werden muss. Dies geht allerdings etwas auf Kosten der Performance des Programms.

Weitere wichtige Bestandteile der STL sind neben den Kontainern Iteratoren, adaptierte Kontainer, Funktionsobjekte und Algorithmen.

Die C++ Standardbibliothek beinhaltet deutlich mehr Algorithmen und Templates als in der STL von Hewlett-Packard enthalten, als diese in den Standard einfloß. Daher ist es oft mißverständlich was mit STL gemeint ist. Üblicherweise ist mit STL: 'Die Templates für Datensammlungen in der C++ Standardbibliothek' gemeint. Siehe hierzu auch STL auf Wikipedia

Funktionsobjekte

Jedes Objekt, das operator() implementiert, ist ein Funktor bzw "Funktionsobjekt". Die STL verwendet Funktoren zum Sortieren in Algorithmen oder Kontainern. 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-Kontainerklassen von Wert und können zur Modifikation, Überprüfung und für Anpassungen gesammelter Objekte in Kontainern 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 Kontainerinhalte von einem Startiterator bis zu einem Enditerator, wendet auf jeden Eintrag einen Funktor an, siehe Algorithmen):

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 Kontainer 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-)Kontainerklasse 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-Kontainerklassen möglich; zum Beispiel ein typedef list<MeinKontainerEintragsTyp> listDaten, der dann eine Sortierung anhand verschiedener Mitglieder von MeinKontainerEintragsTyp 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>

Kontainerklassen

In diesem Kapitel soll das Konzept generischer Kontainer vorgestellt werden. Die C++ Standardbibliothek stellt folgende Typen zur Verfügung:

Sequentielle Kontainerklassen

• vector
• deque
• list

Assoziative Kontainerklassen

• hash_map
• hash_multimap
• hash_multiset
• hash_set
• map
• multimap
• multiset
• set

Kontaineradapterklassen (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, das 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 sogennante 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 Kontainerklassen

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 beherscht (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 Kontainer

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 kann man die Typen

• stack
• queue
• priority_queue

finden.

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, generell gesehen, ein verallgemeinerter Zeiger, mit dem auf eine Datenstruktur in einem Datenverbund zugegriffen werden kann, ohne dies über einen Index der Datenstruktur zu tun. Die Zugriffe können ohne Kenntniss der Datenstruktur erfolgen.

Iteration beschreibt in der Informatik den schrittweisen, wiederholten (sequentiellen) Zugriff auf Elemente in einer Datenstruktur. Im folgenden Codebeispiel 1 zur Iteration über ein Feld aus elementarem Typen int

void f()
{
   const int sizeArr = 400;
   int Arr[sizeArr];
   for (int * pIt = &Arr[0]; pIt <= &Arr[sizeArr-1]; pIt ++)
   {  
       *pIt = 1900;  // Iterator ist ein Zeiger auf ein int
   }
   // Alle Werte in Arr auf 1900 gesetzt
}

Diese Vorgehensweise ist starr, unübersichtlich, nicht generisch und fehleranfällig. Außerdem würden Sie nicht gerade dieses Kapitel lesen, wenn es Ihnen besser gefällt so vorzugehen.

Grundlegende Eigenschaften von Iteratoren

Jedes Kontainerklassentemplate, außer den Kontaineradaptern, hat zugehörige Iteratortypentemplates.

Bei den Iteratoren gibt es folgende Kategorien:

• Eingabe-Iteratoren (input_iterator): lesenden Zugriff für einen einzelnen Durchlauf
• Ausgabe-Iteratoren (output_iterator): schreibender Zugriff für einen einzelnen Durchlauf
• Forward-Iteratoren (forward_iterator): sequenzieller Zugriff mit relativem Bezug auf Iteratoren, in eine Richtung
• Bidirektionale Iteratoren (bidirectional_iterator): wie Forward-Iteratoren jedoch in beide Richtungen
• Iteratoren mit wahlfreiem Zugriff (random_iterator): wahlfreier Zugriff, auch mit Index-Operator ([])

Dabei ist nicht jeder Iteratortyp für jeden Kontainertyp geeignet. z.B. kann der sehr spezielle Iterator für wahlfreien Zugriff nicht auf einen list-Kontainer angewendet werden, aber auf einen vector-Kontainer. Der Eingabe-Iterator ist dagegen sehr allgemein und lässt sich somit auf jeden Kontainertyp anwenden.

Normale Zeiger sind ebenfalls Iteratoren im Sinne der STL; es handelt sich um Iteratoren mit wahlfreiem Zugriff.

In Funktionsobjekte wurde bereits der Algorithmus for_each angewendet um über die Elemente eines vector zu iterieren und einen Funktor für jedes Element im vector aufzurufen.

Nun greifen wir obiges Beispiel auf, Codebeispiel 2:

void f()
{
   vector<int> Arr(400);  // Vektor mit 400 Einträgen vom Typ int
   vector<int>::iterator vIt(Arr.begin());  // Iterator am Anfang des Vektors
   for (;vIt != Arr.end(); vIt++)
   {  
       *vIt = 1900;  // Element verwenden und auf 1900 setzen
   }
   // Alle Werte in Arr auf 1900 gesetzt
}

Der Vorteil bei dieser Vorgehensweise ist, daß Arr eine variable Größe hat, benutzerdefinierte Typen einfach verwendet werden können.

Diese Lösung hat noch nicht die notwendige Eleganz eines Programms, das die Vorlagenbibliothek verwendet, verdeutlicht aber die Anwendung eines Iterators, im folgenden Codebeispiel 3 wird fill aus <algorithm> verwendet.

void f()
{
   vector<int> Arr(400);  // Vektor mit 400 Einträgen vom Typ int
   fill(Arr.begin(), Arr.end(), 1900);
   // Alle Werte in Arr auf 1900 gesetzt
}

Hier verwendet der Algorithmus der Standardbibliothek Iteratoren, die von Ihnen vorgegeben werden, wendet operator ++ an und setzt den Wert entsprechend. Der Typ des Kontainers ist irrelevant für den Algorithmus! Dies ist auch ein dringender Hinweis die Mittel der Standardbibliothek anzuwenden, in vielen Fällen gibt es schon eine Lösung für einfache Vorgänge und 5 Minuten lesen und nachschlagen ersparen später 5 Stunden Wartung und Fehlersuche. Damit wir dieses Beispiel und den Hinweis komplettieren, Codebeispiel 4, nur bedingt zum Iterator:

void f()
{
   vector<int> Arr(400, 1900);  // Vektor mit 400 Einträgen vom Typ int, jeder Eintrag initialisert auf 1900
}

Da Zeiger, wie erwähnt, ebenfalls Iteratoren sind, können Algorithmen auch problemlos auf Arrays angewandt werden:

void f()
{
  int const arrsize = 400;
  int array[arrsize];
  std::fill(array, array+arrsize, 1900);
}

Hier fällt auf, daß der zweite Zeiger nicht auf das letzte Feld des Arrays (array[arrsize-1]) zeigt, sondern ein Feld weiter! Diese Eigenschaft gilt allgemein für Iteratoren: Auch container.end() ist kein Iterator auf ein Element des Containers.

Diese Eigenschaft der Iteratoren lässt sich – wie auch einige andere Eigenschaften von Iteratoren – besser verstehen, wenn man sich die Iteratoren als auf Objektgrenzen zeigend vorstellt. Im Folgenden ein Beispiel:

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

In diesem Beispiel haben wir eine Sequenz (z.B. ein Array oder eine Liste) von 7 Elementen. Der begin-Iterator zeigt auf den Anfang der Sequenz, der end-Iterator auf ihr Ende, und der Iterator iter zeigt zwischen das dritte und vierte Element. Dereferenzieren eines Iterators liefert in diesem Bild das direkt auf den Iterator folgende Element, also liefert *begin das Element 1 und *iter das Element 4. Es ist offensichtlich, dass auf end kein Element folgt, dementsprechend kann dieser Iterator nicht dereferenziert werden. Algorithmen operieren nun auf den Objekten zwischen den beiden übergebenen Iteratoren. Beispielsweise wird

std::fill(begin, iter, 42);

die ersten drei Elemente mit 42 füllen; der Wert von *iter wird dadurch nicht verändert, da er bereits außerhalb dieses Bereichs liegt. Umgekehrt wird

std::fill(iter, end, 39);

die Elemente 4 bis 7 auf 39 setzen.

std::fill(begin, end, 0);

setzt schließlich alle Elemente der Sequenz auf 0.

Für die Verwendung von Algorithmen mit Arrays ist es nützlich, die beiden folgenden Funktionstemplates zu benutzen:

template<typename T, std::size_t size>
 T* begin(T (&array)[size])
{
  return array;
}

template<typename T, std::size_t size>
 T* end(T (&array)[size])
{
  return array+size;
}

Mit diesen Hilfstemplates können Algorithmen auf Arrays ebenso bequem aufgerufen werden wie auf Containern:

void f()
{
  int array[400];
  std::fill(begin(array), end(array), 1900);
}

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 weiter gesetzt 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-Operator als auch mit dem Postinkrement-Iterator 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, dann 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 End-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 Inkrement 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 beliebigen 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 muß 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 amsonsten 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, und deshalb wird die erste Version von internal_middle aufgerufen. Ruft man hingegen middle mit einem Iterator mit wahlfreiem Zugriff auf, dann 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. Un dies ist in der Tat der Fall: std::bidirectional_iterator_tag ist von std::forward_iterator_tag abgeleitet, so dass die erste Version aufgerufen wird.

Wird middle hingegen mit einem reinen Eingabe- oder Ausgabe-Iterator aufgerufen, so 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 enen 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 End-Iteratoren. Eine Besonderheit von std::ostream_iterator ist, dass man bei der Erzeugung zusätzlich zum Stream, 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

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 Standardkontainern der Standardbibliothek konzipiert, müssen aber nicht so verwendet werden, da sie ausschließlich Sequenzen verarbeiten, die durch Iteratoren dargestellt werden.

Einfach ausgedrückt: Standardkontainer, 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, dass 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 daß *i==*(i+1).

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

Wie die erste Instanz, nur daß 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 daß 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 daß 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 daß für eine Untersequenz nicht elementweise ==, sondern das binäre Prädikat bpred erfüllt sein mu&szlig.

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 daß 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 daß 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 muß einen pseudo-zufälligen Wert in [0,n-1] liefern.

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

Partitioniert [first,last) so, daß 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.

Sortierte Sequenzen

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

Binäre Suche

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, daß die resultierende Sequenz wieder ein Heap ist. Mit push_heap kann ein beliebiges Element so eingefügt werden, daß wieder ein Heap entsteht. Beide Operationen benötigen nur O(log n) Zeit. Eine normale Sequenz muß 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 daß [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 daß 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 daß 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 daß 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 daß binop statt - verwendet wird.

Boost / TR1

Momentan wird ein neuer Standard für C++ entwickelt. Der Entwurf nennt sich C++0x, in der Idee, daß noch vor 2010 ein neuer, offizieller Standard für C++ veröffentlicht wurde. Ob dies so kommt, oder ob es sich weiter hinausziehen wird, ist momentan (Mitte '07) nicht klar. Klar ist aber, daß sehr viele Teile der boost-Bibliothek im Technischen Report 1 (TR1) für den neuen C++-Standard auftauchen und aufgenommen werden. Die boost-Bibliothek ist ein wichtiger Anlaufpunkt für Erweiterungen der C++ Standardbibliothek und deren Templates.

Hoch zu Inhaltsverzeichnis