Programme = Algorithmen + Datenstrukturen

— Niklaus Wirth

  Datenstrukturen:
  k |  Feld, Liste, Baum, Menge, Tabelle, Stapel, Warteschlange, ...
    |      
    |      
    *----- j Algorithmen
   /           suchen, zählen, kopieren, ersetzen, sortieren, ...
i / 
Elementtypen  
  bool, char, int, float, double
  nutzerdefiniert: ...

Eine universelle Bibliothek von Algorithmen und Datenstrukturen für Elemente beliebigen Typs steht vor dem Problem der Komplexität:

• i unterschiedliche Datentypen, j verschiedene Datenbehälter und k Prozeduren erfordern i*j*k Implementierungen.
• Keine Bibliothek wäre vollständig. Jeder neue Elementtyp, jeder neue Container, jeder neue Algorithmus würde eine Welle von Ergänzungen notwendig machen (die dann wegen Zeitmangel vermutlich unterbleiben).
• Einige Aufgaben lassen sich auf bestimmten Datenstrukturen einfacher umsetzen, andere lassen sich nicht vollständig vorausbestimmen. So gibt es unterschiedlichste Sortierkriterien. Die Schnittstellen der allgemeinen Routinen qsort() und bsearch() aus <cstdlib> sind bestenfalls abschreckend.

Eine allgemeine Bibliothek muss

• die häufigsten Problemstellungen abdecken,
• effizient arbeiten,
• aus voneinander unabhängigen, aber dennoch miteinander und mit anderen Programmteilen kombinierbaren Bausteinen bestehen,
• einfach zu ergänzen sein,
• einfach und sicher nutzbar sein.

Datentyp-parametrisierte Klassen und Funktionen (Schablonen) müssen nur einmal geschrieben werden. Diese Beobachtung wurde von Alexander Stepanov und Meng Lee nach Erfahrungen mit generischen Algorithmen in ADA konsequent weitergedacht und in der Standard-Schablonen-Bibliothek (standard template library = STL) umgesetzt. Die STL wurde 1994 in den Standard-Prozess von C++ aufgenommen, als dieser beinahe schon als abgeschlossen betrachtet wurde. Allein ihre Beschreibung nahm im Standard 1998 etwa ein Viertel des Seitenumfangs ein.

Der Template-Mechanismus reduziert die Komplexität auf j+k durch

• datentypunabhängige Container,
• vom Containertyp unabhängige Algorithmen, die auf verallgemeinerte Bereiche (Sequenzen, Wertfolgen) zugreifen,
• Entkopplung der Algorithmen von den Containern durch Iteratoren,
• Hilfsfunktionen und -klassen für bestimmte Nuancen (Aspekte, "Facetten") wie Sortier- und Auswahlkriterien, Speicherverwaltung u.ä. (Hilfsmittel).

Container        Iteratoren        Algorithmen     Hilfsmittel
 
Felder           Zeiger            sort            Funktoren 
vector<T>        random_access     partition       Prädikate 
deque<T>         bidirectional     fill            Binder
list<T>          reverse           copy            Funktions-Adapter 
set<T>           forward           replace         Iterator-Adapter
map<Key, Value>  input             for_each        Container-Adapter
...              output            count           Speicher-Allokatoren
                                   accumulate
                                   ... 

Anstatt alles miteinander zu verzahnen, führt das Trennen der Datenhaltung von den Algorithmen und das Dazwischenschieben der Iterator-Idee zu einer überschaubaren Menge von Bausteinen. Der Nutzer kann diese in unterschiedlicher Weise kombinieren, um seinen beabsichtigten Zweck zu realisieren (z.B. Worthäufigkeiten ermitteln).

Für den Umgang mit den Schablonen der Standard-Bibliothek sind folgende Bezeichnungen wichtig:

• Algorithmus : eine oder mehrere Elementfolgen (Bereiche) bearbeitende Funktion.
• Bereich : durch zwei Iteratoren [first, last) begrenzte Folge von Elementen, dessen rechte Begrenzung last entsprechend mathematischer Notation nicht zur Folge dazugehört; die linke Begrenzung first zeigt auf das erste zu bearbeitende Element der Folge oder ist mit last identisch (leerer Bereich).
• Container : Datenbehälter, der Elemente eines bestimmten Typs als Folge verwaltet; je nach Containerart werden unterschiedliche Speichertechniken (Feld, Liste oder sortierter ausgeglichener Binärbaum) mit entsprechenden Vorzügen und Nachteilen implementiert.
• Iterator : Objekt, mit dem über Folgen von Elementen iteriert und nacheinander auf die Elemente zugegriffen werden kann; besitzt eine einheitliche, an das Zeigerkonzept von C angelehnte Schnittstelle; je nach Containerart kann dies tatsächlich ein Zeiger oder auch etwas viel Komplizierteres ("smart pointer") sein.
• Funktor : Funktionsobjekt, imitiert als Instanz einer Klasse mit überladenem Funktionsoperator das Verhalten einer Funktion, die auf ein oder mehrere Elemente von Bereichen angewendet wird.
• Prädikat : Funktion oder Funktor, welche/r beim Funktionsaufruf einen Wahrheitswert liefert; ergibt true, wenn eine bestimmte Eigenschaft oder Relation auf das oder die Argumente zutrifft.

Anwenden von           funktion(*iterator)
auf einige oder                   | if( praedikat(*iterator) ) ...
alle Elemente          ++iterator |
im Bereich         first  --------|--> last
                    |             |     |  
                    v             v     v 
eines Containers   [0|1|2|3|4|5|6|7|8|9]

Um nach einer Datenerfassung Doubletten aus einem sequentiellen Container zu entfernen, kann man so vorgehen:

#include <algorithm>
 
template <class Container>
void sortiere_und_entferne_Dopplungen(Container& c)
{
  std::sort( c.begin(), c.end() );
  typename Container::iterator neuesEnde = std::unique(c.begin(), c.end());
  c.erase(neuesEnde, c.end());  
}

Sortieren eines Bereiches und einmalige Elemente nach vorn rücken sind als generische Algorithmen formuliert. Iteratoren markieren die Grenzen der zu bearbeitenden Bereiche. Das Entfernen der überzähligen Elemente an Ende des Bereiches muss der Container allerdings selbst durchführen, da nur er über die entsprechenden Methoden verfügt.

Der Container muss vorsortiert werden, weil unique() nur benachbarte Dopplungen entfernt, um schnell zu arbeiten. Erkennen von Doubletten ohne Änderung der Reihenfolge würde eine zum Quadrat der Elementanzahl proportionale Laufzeit erfordern. Algorithmen und Containermethoden wurden so entworfen, dass sie möglichst effizient sind. Container besitzen keine teuren Methoden. So wurde bei vector<T> auf eine Methode push_front() verzichtet, da alle Elemente um einen Platz nach hinten rücken müssten. Wer es dennoch tun will, muss umständlicher schreiben:

v.insert(v.begin(), x); // teuer: O(n)

Für das Laufzeitverhalten in Abhängigkeit von der Anzahl n der Elemente wird die O-Notation benutzt. Typische Laufzeit-Komplexitäten sind:

Algorithmen der Standardbibliothek bearbeiten einen oder mehrere durch Iteratoren eingegrenzte Bereiche mit gleichartigen Elementen. Die Algorithmen der Standard-Bibliothek (Header <algorithm> und <numeric>) gehören folgenden Gruppen an:

• Nichtmodifizierende Algorithmen ändern weder Werte noch ordnen sie Elemente um.
• Modifizierende Algorithmen können Werte ändern und umordnen.
• Mutierende Algorithmen ändern die Elementreihenfolge, ohne Werte zu ändern, einzufügen oder wegzulassen.

#include <algorithm>
#include <iostream>
 
void demo()
{
  float array[] = { 5, 3, 7, 2, 4 };
  float* first = array;
  float* last  = array + sizeof(array)/sizeof(array[0]);
 
  int n = std::count(first, last, 3); // nicht modifizierend
  std::replace(first, last, 7, n);    // modifizierend
  std::sort(first, last);             // mutierend
 
  std::copy(first, last, 
            std::ostream_iterator<float>(std::cout, " ") ); // Ausgabestrom als Iterator
}

Seit C++20 können die Algorithmen auch den Bereich [first,last) als einen einzigen Parameter, ein range aufnehmen:

  std::ranges::copy(array, std::ostream_iterator<float>(std::cout, " ") );

Diese Versionen sind im Namensbereich std::ranges untergebracht. Als std::ranges::range ist jeder Ausdruck r zulässig, auf den std::ranges::begin(r) und std::ranges::end(r) angewendet werden können. Bei fehlerhafter Nutzung liefern diese Concepts aussagekräftigere Fehlermeldungen.

• Nicht-sortierende sequentielle Container und
• automatisch sortierende assoziative Container sind Datenbehälter für Elemente eines beliebigen Typs.

Gleichartige allgemeine Container-Eigenschaften geben den Containern eine weitgehend einheitliche Benutzerschnittstelle. Bei unzureichendem Laufzeitverhalten sind die Container leicht auswechselbar.

<deque> <list> <vector>

Sequentielle Container übernehmen Elemente in vorgegebener Reihenfolge und behalten diese Folge bei. Jeder Container hat spezielle Stärken:

• Ein vector<T> (dynamisches Feld) erlaubt den schnellsten indizierten Zugriff und kann leicht am Ende wachsen oder schrumpfen,
• eine deque<T> (double-ended queue) kann nach beiden Seiten wachsen oder schrumpfen,
• eine list<T> (doppelt verkette Liste) lässt sich durch das Umhängen von Zeigern gut umordnen, ohne Elemente kopieren oder zuweisen zu müssen, bietet jedoch keinen indizierten Zugriff.

std::vector<T>       [0|1|2|3|4] <-->
std::deque<T>   <--> [0|1|2|3|4] <-->
std::list<T>    <--> [0]=[1]=[2]=[3]=[4] <-->

<array> <bitset> <forward_list> <initializer_list> <string> <valarray> (Beinahe-Container)

"Beinahe"-Container implementieren einige, jedoch nicht alle allgemeinen Container-Eigenschaften.

Ein array<T,N> ist ein Container mit vorbestimmter Anzanl N von Elementen. Er kann also weder wachsen noch schrumpfen. Dafür kommt er ohne dynamischen Speicher aus.

Der bitset<N> ist nur ein Beinahe-Container, da die Anzahl seiner bool-Elemente vor dem Übersetzen feststehen muss. Er kann seine Größe nicht zur Laufzeit ändern, also keine Bits einfügen oder entfernen. Er kann genutzt werden, wenn nicht die Flexibilität eines vector<bool> gebraucht wird.

Die forward_list<T> kann nur in Vorwärtsrichtung durchlaufen werden. Damit gibt es nur Methoden zum Einfügen / Entfernen nach einer angegebenen Position.

Initialisiererlisten initializer_list<T> nehmen Anfangswerte für Container wie {1, 2, 3} auf, um sie zur Anfangswertbelegung an andere Container zu übergeben.

Die Schablone basic_string<CharT> mit ihren zwei Spezialisierungen string und wstring wurde im Standardisierungsprozess mit allgemeinen Containermerkmalen ausgestattet und kann damit als Container für Zeichenfolgen aufgefasst werden. hat jedoch zusätzliche Methoden zur Zeichenkettenverarbeitung wie Suchen und Ersetzen.

Für numerische Anwendungen (eine historische Domäne von FORTRAN) wurde die Schablone valarray<T> entworfen. Die Implementierung ist (auf bestimmten Rechnern) so optimierbar, dass die Rechenoperationen parallel (und eben nicht sequentiell) ausgeführt werden.

<map> <set>

Assoziative Container verbinden die gespeicherten Werte mit Schlüsseln, nach denen die Elemente sortiert gehalten werden. Die natürliche Sortierreihenfolge ist durch den für den Schlüsseltyp Key definierten Operator < über das Prädikat less<Key> gegeben. Ein anderes Sortierkriterium kann als zweistelliges Prädikat Compare festgelegt werden. Als Schlüssel können beliebige Typen dienen, sofern für sie ein Vergleichskriterium definiert ist.

• Tabellen (Zuordnungen) map<Key,Value,Compare> verwalten Schlüssel-Wert-Paare pair<Key,Value>. Jedem Schlüssel ist ein anderer Wert zugeordnet. Sprachen, die sich vorrangig mit Text- und Symbolverarbeitung befassen, bieten häufig ein assoziatives Array oder Dictionary als sehr nützlichen Datentyp an. Man kann sich ein assoziatives Array auch als Feld vorstellen, bei dem der Feldindex keine Ganzzahl sein muss.
• Die multimap<Key,Value,Compare> kann mehrere Werte dem gleichen Schlüssel zuordnen.
• Mengen set<T,Compare> können als degenerierte assoziative Felder betrachtet werden (nur Schlüssel ohne zugeordneten Wert).
• In multiset<T,Compare> dürfen gleiche Werte auch mehrfach vorkommen.

std::map<std::string, int>    std::multimap<std::string, int> 
                                  Meier   6135
    Meier   6135                  Meier   6134
    Meyer   9999                  Meyer   9999
    Schulze 5180                  Schulze 5180
 
std::set<int>                 std::multiset<int, std::greater<int>>
    { 1 2 3 4 5 }                 { 5 5 4 3 3 }

Da assoziative Container meist als balancierte Binärbäume implementiert sind, haben Operationen zumeist logarithmisches Laufzeitverhalten.

<unordered_map> <unordered_set>

Die in C++11 hinzugekommenen Container unordered_map<Key,Value,Hash<Key>> und unordered_set<T,Hash<T>> und ihre "multi"-Varianten verwenden statt eines Sortierkriteriums einen Hash-Algorithmus, durch den die Position des Elements in konstanter Zeit gefunden wird, also O(1) statt O(log N). Hier kommt es nicht auf die Reihenfolge an, sondern auf Schnelligkeit.

Alle Container stellen einheitliche Typbezeichnungen für Werte, konstante und nichtkonstante Referenzen sowie Vorwärts- und Rückwärts-Iteratoren zur Verfügung. Für Größenangaben des Containers wird size_type als vorzeichenloser, für Abstandsangaben difference_type als vorzeichenbehafteter Ganzzahltyp festgelegt. Assoziative Container definieren zusätzlich den Schlüsseltyp und Typen für Schlüssel- und Wertevergleich. Die Typbezeichnungen erleichtern den Container-Austausch:

typedef std::vector<double> Container;  // oder std::list<double> ?
Container v;
Container::iterator first = v.begin();

Ein neuer Container ist zu Beginn leer. Er kann sich die Inhalte eines gleichartigen Containers original oder eines Bereiches [anfang,ende) kopieren. Sequentielle Container sind in der Lage, eine bestimmte anzahl von Elementen anzulegen und mit demselben wert zu belegen. Die Container besitzen ihre Inhalte und sind dann für deren Freigabe verantwortlich. Die dynamische Speicherverwaltung erfolgt im Hintergrund automatisch, eine Speicherfreigabe durch den Anwender ist nicht erforderlich.

void konstruktor_demo(Container const& c)
{
  Container c0;                       // leer
  Container c1(c);                    // Kopie des Containers
  Container c2(c.rbegin(), c.rend()); // Iteratorbereich rückwärts
}

Container liefern ihre Elementanzahl mit c.size(). Bei c.size()==0 trifft c.empty() zu.

void groesse_demo(Container const& c)
{
  if (c.empty()) std::cout << "Container ist leer\n";
  else std::cout << "Container mit " << c.size() << " Elementen\n";
}

Auf gleichartige Container können Vergleichsoperatoren angewendet werden, sofern für die Elemente die Operatoren == und < definiert sind. Zwei Container gelten als inhaltsgleich, wenn beide Container die gleiche Anzahl von Elementen enthalten und jedes Element des einen mit dem entsprechenden Element des anderen Containers gleich ist. Ein Container wird als (lexikographisch) kleiner eingestuft, sobald beim Durchmustern eines seiner Elemente kleiner ist als das entsprechende Element im anderen Container oder bei bisher gleichwertigen Elementen dieser Container weniger Elemente enthält.

void vergleich_demo(Container const& c)
{
  Container kopie = c;
  if (kopie == c) std::cout << "ok\n";
  if (kopie < c ) std::cout << "Da ist was schiefgegangen\n";
}

value_comp() und key_comp() liefern das Vergleichskriterium für Werte bzw. Schlüssel des assoziativen Containers.

Assoziative Container können effizient bestimmen, wie oft ein Schlüsselwert key im Container enthalten ist. Die Position des (ersten) Elementes bestimmt find(key). Bei Misserfolg gibt die Methode end() zurück. Die erste / letzte Iterator-Position, bei der key eingefügt werden könnte, ohne die Sortierung zu zerstören, liefern die Methoden lower_bound(key) bzw. upper_bound(key). Mit equal_range(key) erhält man beide Grenzen als Iteratorpaar.

void nachschlagen(std::map<std::string,int> const& telefonbuch, std::string name)
{
  std::map<std::string,int>::const_iterator i = telefonbuch.find(name);
  if (i != telefonbuch.end())
    std::cout << i->first << " hat die Nummer " << i->second << '\n';
  else
    std::cout << name << " hat kein Telefon\n";
}

Bei einer Zuweisung übernimmt ein Container alle Elemente vom rechsseitigen Container. Ein globaler Tausch swap(c,c2) würde dreimaligen Aufwand für Kopie, Zuweisung und Destruktion aller Elemente erfordern. Der Methodenaufruf c.swap(c2) erledigt das durch internen Zeigertausch in konstanter Zeit.

Der Referenzzugriff auf das erste bzw. letzte Element mit front() und back() darf nur erfolgen, wenn ein solches Element existiert (size()>0).

Beim Index-Zugriff in vector und deque sollte sichergestellt sein, dass index<size() gilt. Beim Zugriff mit dem Index-Operator [] muss dies der Anwender sicherstellen. Die Methode at() prüft dies und wirft bei Verletzung der Bedingung eine out_of_range-Ausnahme.

Der Indexzugriff m[key] in eine map liefert den zu dem Schlüssel key zugeordneten Wert. Existiert kein Element mit dem angegebenen Schlüssel, wird es automatisch angelegt und ein Standardwert zugeordnet.

Tatsächlich ist [] etwas mehr als eine bequeme Notation für insert. Das Ergebnis von m[k] ist äquivalent zum Ergebnis von *(m.insert(make_pair(k,V())).first).second, wobei V() der Standardwert des Datentyps des zum Schlüssel gehörenden Wertes ist. Wer diese Äquivalenz versteht, hat wohl auch assoziative Arrays verstanden.

— Bjarne Stroustrup [Die C++ Programmiersprache 17.4.1.7]

void erfassen(std::map<std::string,int>& tabelle, std::string wort)
{
  ++tabelle[wort];
}

Iteratoren von vector und deque erlauben wahlfreien Zugriff. Die bidirektionalen Iteratoren der assoziativen Container erlauben keine Schlüsseländerungen, da dies Elemente umordnen würde.

Die Methode begin() liefert einen Iterator auf das erste, end() einen Iterator hinter das letzte Element des Containers. Bei leeren Containern sind die Ergebnisse beider Methoden identisch. Reverse-Iteratoren durchlaufen den Container in der umgekehrten Elementfolge: rbegin() verweist auf das letzte Element im Container, rend() auf die Position vor das erste Element.

     begin()  ------------>  end()
     |           ++iter      |
     v                       v
    [.......................]       Container
   ^ :                     ^ :
   | :       ++rev_iter    | :
   rend() <--------------  rbegin()                

Ein wert lässt sich an einer durch einen Iterator gegebenen position in einen Container einfügen. Eine ganzer Bereich [anfang,ende) kann als Kopie eingefügt werden. Für assoziative Container dient position nur als Hinweis, wo mit der Suche nach der geeigneten Stelle zum Einfügen begonnen werden soll, die "hint"-Varianten können eventuell schneller sein, wenn die richtige Position angegeben wurde. Die emplace-Methoden übernehmen die geeigneten Parameter, um ein neues Container-Element direkt im Container zu erschaffen. Damit werden unnötige Kopien bzw. Verschiebungen vermieden.

void einfuegen_demo(Container& c)
{
  Container::value_type wert = c.front();
  c.push_back(wert); // c.insert(c.end(), wert);
}

Größenänderungen resize() fügen bei Bedarf neue Elemente mit Standardwert oder angegebenem wert am Ende ein oder entfernen überzählige Elemente am Ende des Containers.

Assoziative und ungeordnete Container beherrschen seit C++17 das Verschmelzen (Spleißen) von Sequenzen. Schon vorhandene Elemente verbleiben im Quellcontainer, sofern das Ziel kein "multi"-Container ist:

void verschmelzen_demo(Container& target, Container& source)
{
    target.merge(source);
    for (auto [k,v] : target) std::cout << k << ' ' << v << '\n';
    std::cout << "\nnot merged, target already contained:\n";
    for (auto [k,v] : source) std::cout << k << ' ' << v << '\n';
}

Auch einzelne Knoten lassen sich umhängen:

void umhaengen(Container& target, Container& source)
{
  target.insert(source.extract(src.find(1))); 
  target.insert(source.extract(2));           
  auto r = target.insert(source.extract(3)); // scheitert, wenn Schlüssel 3 schon in dst (kein multimap)
  if (!r.inserted)                           // r hält entnommenen Knoten
  {
    r.node.key() = 4;                        // anderen Schlüssel wählen, dann einfügen
    target.insert(r.position, std::move(r.node));
  }  
  for (auto [k,v] : target) std::cout << k << ' ' << v << '\n';
}

Um ein Element zu löschen, muss dessen position als Iterator angegeben werden. Auch ein Teilbereich [anfang,ende) eines Containers kann entfernt werden. Für assoziative Container löscht c.erase(wert) alle Elemente mit dem angegebenen Schlüssel.

void loeschen_demo(Container& c)
{
  c.erase(c.begin());  // c.pop_front();
  c.clear();           // c.erase(c.begin(), c.end());
}

Containermethoden zeigen folgendes Laufzeitverhalten bei n Elementen im Container:

Dabei bedeutet

- nicht implementiert wegen schlechten Zeitverhaltens,
+ durchschnittliches Verhalten, gelegentlich Zusatzaufwand.

<iterator>

Die Container und Algorithmen verbindenden Iteratoren gehören Kategorien mit unterschiedlichen Fähigkeiten an. Reverse-Iteratoren durchlaufen Bereiche in umgekehrter Folge. Iterator-Adapter bieten eine zeigerartige Schnittstelle für Einfügeoperationen, Eingabe- und Ausgabeströme an.

Anhand der (hier abgekürzt bezeichneten) Kategorien können Algorithmen mit optimalem Zeitverhalten für die Sequenz umgesetzt werden.

Ausgabe-Iteratoren Out können Werte zugewiesen bekommen und weitergesetzt werden.

  *iter = wert;
  ++iter;

Eingabe-Iteratoren In dienen dem Lesen von Werten. Ein Vergleich mit einem anderen Iterator ist möglich, um z.B. ein Ende zu definieren. Ein zweiter Durchlauf mit einer Kopie kann andere Werte liefern. Wandert der Iterator über zusammengesetzte Typen, ist der Komponentenzugriff mit dem Pfeil-Operator möglich.

  while (iter != ende)
  {
    wert = *iter;
    ++iter; 
  }

Vorwärts-Iteratoren For haben alle Fähigkeiten von Ein- und Ausgabe-Iteratoren. Sie lassen sich zuweisen und kopieren. Im Gegensatz zu Ein- und Ausgabe-Iteratoren ist festgelegt, dass Kopien über die gleichen Elemente wie die Vorlage wandern, mehrere Durchläufe sind möglich.

  while (*iter != wert)
  {
    *ziel++ = *iter++;
  }

Bidirektionale Iteratoren Bi können mittels Dekrement -- auch in entgegengesetzter Richtung über die Elemente laufen.

  while (first != last)
  {
    --last;
  }

Sofern die Iteratoren als Klassen definiert sind, sind die Präfixvarianten von Inkrement bzw. Dekrement gegenüber den Postfixvarianten effizienter, da kein temporärer Iterator für den Ergebniswert gebildet werden muss. Wo möglich, sollte ++iter statt iter++ verwendet werden.

Iteratoren mit wahlfreiem Zugriff Ran können wie Zeiger direkt an eine beliebige Stelle positioniert werden. Auch der Feldzugriff ist möglich. Abstandsberechnungen sind sehr einfach, Tests auf davor / dahinter erfolgen mit den Vergleichsoperatoren.

void iterator_demo(Container const& c)  // vector<T> / deque<T>
{
  Container::iterator first = c.begin();
  Container::iterator last  = c.end();
  Container::difference_type n = last - first;
  if (n > 0)
  { 
    last = first + n/2;
    Container::value_type mitte = *last;  // mitte = first[n/2];
  }
}

Rückwärts-Iteratoren reverse_iterator<Iterator> laufen in umgekehrter Richtung über einen Bereich. Mit ihrer Hilfe ist es problemlos möglich, die Verarbeitungsreihenfolge umzukehren, ohne neue Algorithmen implementieren zu müssen. Jedes Weitersetzen wird einfach in ein Zurücksetzen umgedeutet. Wegen der "Halboffen"-Eigenschaft der Bereiche ist ihr Bezugspunkt jedoch um ein Element verschoben.

     begin()  ------------>  end()
     |           ++iter      |
     v                       v
    [.......................]       Container
   ^ :                     ^ :
   | :       ++rev_iter    | :
   rend() <--------------  rbegin()    
             --iter             

Mit rev_iter.base() kann der zugehörige Vorwärts-Iterator zurückgewonnen werden.

Iterator-Adapter vereinheitlichen Einfügen, Ein- und Ausgaben unter Ausnutzung der Zeigerschreibweise. So verallgemeinert, sind diese Operationen weiter nichts als eine Anwendung des Kopier-Algorithmus copy(anfang, ende, ziel):

 while (first != last) *insert++ = *first++;
 while (input != ende) *output++ = *input++;

Einfüge-Iteratoren sind Iterator-Adapter, mit denen das Zuweisen von Werten in ein Einfügen in einen Container umgedeutet wird:

void inserter_demo(Container const& c)
{
  Container::value_type wert = c.front()
  Container c2;
  Container::iterator position = c2.begin();
 
  std::insert_iterator<Container> hier = inserter(c2, position); 
  std::front_insert_iterator<Container> vorn = front_inserter(c2); 
  std::back_insert_iterator<Container> hinten = back_inserter(c2); 
 
  *hier   = wert;  // c2.insert(position, wert);
  *vorn   = wert;  // c2.push_front(wert); 
  *hinten = wert;  // c2.push_back(wert);
}

Mit den Inserter-Funktionen ist es einfach, einen Bereich an einen Container anzuhängen:

  std::copy(c.begin(), c.end(), std::back_inserter(c2));

Ausgabestrom-Iteratoren geben Elemente aus, auch direkt aus Algorithmen heraus:

  std::ostream_iterator<double> output(std::cout, " "); 
  std::copy(c.begin(), c.end(), output);

Eingabestrom-Iteratoren passen Eingabeströme an das Zeigerkonzept an. Das Einlesen von Elementen ist auch in Algorithmen möglich.

  double summe = 0.0;
  std::istream_iterator<double> input(std::cin);
  std::istream_iterator<double> ende;
 
  while (input != ende) // summe = std::accumulate(input, ende, 0.0); 
  {
    summe += *input;
    ++input;
  }

<utility>

Nur die Vergleichsoperatoren == und < müssen selbst definiert werden, die restlichen sind daraus herleitbar. Für beliebige Wertpaare gibt es den Behälter pair<U,V>. Container-Adapter (Stapel und Warteschlangen) sowie Funktionsadapter ergänzen die Standard Template Library.

Um Vergleiche von Objekten selbstdefinierter Typen vorzunehmen, genügt es, < und == zu implementieren:

Um diese Äquivalenzen zu nutzen, muss man lediglich die Schablonen des Namensbereiches std::rel_ops einbinden¹⁾:

#include <utility> // über Algorithmen und Container automatisch
using namespace std::rel_ops; // bei Bedarf

Für die Vergleichsoperatoren wurde ein Unternamensraum von std gewählt, um Mehrdeutigkeiten oder falsche Operator-Aufrufe zu vermeiden.

Paare von Werten unterschiedlichster Typen kommen an verschiedenen Stellen in der Standardbibliothek vor, z.B. als Elemente std::pair<Key const, Value> eines map-Containers, aber auch als Rückgabewert des Algorithmus equal_range().

template <class Typ1, class Typ2>
struct pair   
{
  Typ1 first;
  Typ2 second;
  // ... Konstruktoren, Vergleiche < ==
};

Zwei Paare sind gleich, wenn beide Bestandteile gleich sind. Die Sortierung von Paaren erfolgt zuerst nach der Komponente first, bei wertgleicher Komponente first nach dem Bestandteil second.

<queue> <stack>

push(x)               pop()     push(x)    
<-- [...............] <--       <--> [...............]
     |             |            pop() |
     front()       back()             top()

Stapel stack<T,Container> und Warteschlangen queue<T,Container> sind Container-Adapter. Ihre Funktionalität kann von einem beliebigen Container geliefert werden, der aber vom Adapter vollständig umhüllt wird. Der Standard-Containertyp ist deque<T>.

Prioritätswarteschlangen priority_queue<T,Container,Compare> ordnen Elemente mit großen Werten (=Prioritäten) so ein, dass sie zuerst wieder herauskommen. Fehlen Angaben zum Containertyp bzw. zum Vergleichskriterium, werden vector<T> bzw. less<T> eingesetzt.

Die Container-Adapter besitzen neben Konstruktor und Vergleichen nur wenige Methoden.

void umstapeln(std::stack<double> s)
{
  std::queue<double> q;
 
  while (!s.empty() && !q.full())
  {
    q.push( s.top() );
    s.pop();
  }
  while (!q.empty())
  {
    std::cout << q.front() << '\n';
    q.pop();
  }
}

<functional>

Funktionen, die als Wahrheitswert liefern, ob eine Bedingung erfüllt ist, werden Prädikate genannt. Erwarten Algorithmen Funktionen als Parameter, müssen das nicht unbedingt Funktionen sein. Es kann sich auch um Objekte handeln, die die Schnittstelle einer Funktion besitzen. Dazu sind bei diesen Objekten die Funktionsklammern operator() überladen.

Neben Prädikaten definiert die Standardbibliothek auch arithmetische Funktionsobjekte (Funktoren). Die Funktoren negate<T> und logical_not<T> sind einstellig, d.h. sie verarbeiten nur ein Argument. Die anderen Funktoren sind zweistellig.

Für assoziative Container legt ein Prädikattyp die Sortierreihenfolge fest. C++14 erlaubt hier, den Typ T des Funktors wegzulassen:

std::set<int, std::less<>> zahlenmenge;

An Algorithmen werden Funktoren als Objekt übergeben (deshalb mit Klammern):

std::sort(first, last, std::greater<>());

Polymorphe Funktionsadapter function<ergebnistyp(Typliste)> nehmen sowohl Funktoren, Funktionszeiger als auch Lambda-Ausdrücke auf. Ob ihnen ein Wert zugewiesen wurde, kann vor dem Aufruf geprüft werden:

std::function<double(double)> f = std::negate<>();
f = [](double x) { return std::acos(x); }
if (f) std::cout << f(1) << '\n';

Binder bind(f, parameter) als flexible Funktionsadapter koppeln die Parameter eines Funktors f an Platzhalter für die Argumente des Aufrufs, an Werte, Referenzen ref(variable), konstante Referenzen cref(variable) oder Ergebnisse anderer Binder-Funktoren.

using namespace std::placeholders;
std::transform(c.begin(), c.end(),                            // fuer alle c[i]
               c.begin(),                                     //   c[i] = multiply(7, c[i]) 
               std::bind(std::multiplies<double>(), 7, _1) ); //     also 7 * c[i]

Die im besonderen Namensraum definierten placeholders _1, _2, usw. leiten das erste, zweite, … Argument des Binderaufrufs weiter an die angegebene Position. In funktionalen Sprachen wird die Reduktion der Parameteranzahl (bis auf einen) als Currying bezeichnet.

Negierer kehren die Ergebniswerte eines Prädikates um. Die Funktionen not1(op) und not2(op) erstellen Negierer für ein- bzw. zweistellige Prädikate. Um alle Elemente zu zählen, die nicht größer als 20 sind, könnte man schreiben:

std::function<bool(double)> greater_than20 = [](double x){ return x > 20; };
int n = std::count_if(first,last, std::not1(greater_than20));

Methoden von Objekten werden eingekapselt, damit die korrekte (möglicherweise virtuelle) Methode mit den richtigen Objektzeigern bzw. -referenzen aufgerufen wird. Für Objektzeiger liefert mem_fn() einen entsprechenden Adapter.

void zeichnen(std::list<Objekt*>& l)
{
  std::for_each(l.begin(), l.end(), std::mem_fn(&Form::zeichne));
}

Mit den von den Hilfsfunktionen ref(variable) und cref(variable) erzeugten reference_wrapper<T> lässt sich ein Multi-Index-Zugriff auf Datenmengen verwirklichen:

#include <algorithm>
#include <chrono>
#include <functional>
#include <iostream>
#include <vector>
 
int main()
{
  std::vector<int> o = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  std::vector<std::reference_wrapper<int>> v(begin(o), end(o));
  std::vector<std::reference_wrapper<int>> p(begin(v), end(v));
 
  unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
  shuffle (begin(v), end(v), std::default_random_engine(seed));
  std::partition(begin(p), end(p), [](int n){ return n%2 == 0; });
 
  for (int n: o) std::cout << n << ' '; std::cout << "original\n";
  for (int n: v) std::cout << n << ' '; std::cout << "gemischt\n"; 
  for (int n: p) std::cout << n << ' '; std::cout << "geteilt: gerade/ungerade\n";
  return 0;
}