namespace cpp {}

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


kennen:stl

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.


kennen:stl [2020-07-27 10:02] (aktuell) – angelegt - Externe Bearbeitung 127.0.0.1
Zeile 1: Zeile 1:
 +====== Schablonen der Standardbibliothek ======
 +> Programme = Algorithmen + Datenstrukturen
 +>>---  Niklaus Wirth
 +
 +===== Konzept =====
 +==== Der Wunsch nach einer allgemeinen Bibliothek ====
 +<code cpp>
 +  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: ...
 +</code>
 +
 +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 [[.:lib:qsort|qsort()]] und [[.:lib:bsearch|bsearch()]] aus <[[.:include:cstdlib|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.
 +
 +==== a) Allgemeinheit: Generizität durch Schablonen ====
 +Datentyp-parametrisierte Klassen und Funktionen ([[.:schablonen|Schablonen]]) 
 +müssen nur einmal geschrieben werden.
 +Diese Beobachtung wurde von Alexander Stepanov und Meng Lee nach Erfahrungen mit 
 +generischen Algorithmen in [[.:begriffe#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]]).  
 +
 +<code cpp>
 +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
 +                                   ... 
 +</code>
 +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. [[.:beispiel:wordcnt|Worthäufigkeiten ermitteln]]).
 +
 +==== b) Begriffe ====
 +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 [[.:operator#Funktionsklammern|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.
 +
 +==== c) Container + Algorithmen + Iteratoren = Effizienz ====
 +<code cpp>
 +Anwenden von           funktion(*iterator)
 +auf einige oder                   | if( praedikat(*iterator) ) ...
 +alle Elemente          ++iterator |
 +im Bereich         first  --------|--> last
 +                    |                 |  
 +                    v                 
 +eines Containers   [0|1|2|3|4|5|6|7|8|9]
 +</code>
 +Um nach einer Datenerfassung Doubletten aus einem [[#sequentielle Container|sequentiellen Container]]
 +zu entfernen,
 +kann man so vorgehen:
 +
 +<code cpp>
 +#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());  
 +}
 +</code>
 +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:
 +
 +<code cpp>
 +v.insert(v.begin(), x); // teuer: O(n)
 +</code>
 +Für das Laufzeitverhalten in Abhängigkeit von der Anzahl n der Elemente
 +wird die O-Notation benutzt. Typische Laufzeit-Komplexitäten sind:
 +
 +| O(1)     | konstant       | Wert am Ende einfügen | billig|
 +| O(log n) | logarithmisch  | Binärsuche|
 +| O(n)     | linear         | sequentielle Suche | vertretbar|
 +| O(n log n)|               | Quick Sort|
 +| O($n^2$)   | quadratisch    | Bubble Sort | teuer|
 +| O($n^3$)   | kubisch        | Multiplikation n-reihiger Matrizen|
 +| O(exp n) | exponentiell   | Logik-Rätsel | nicht beherrschbar|
 +| O(n!)    | kombinatorisch | Rundreiseproblem | schon für kleine n|
 +
 +===== Algorithmen  =====
 +Algorithmen der Standardbibliothek bearbeiten einen oder mehrere durch [[#Iteratoren]]
 +eingegrenzte Bereiche mit gleichartigen Elementen.
 +Die Algorithmen der Standard-Bibliothek (Header 
 +<[[.:include:algorithm|algorithm]]> und
 +<[[.:include:numeric|numeric]]>
 +gehören folgenden Gruppen an:
 +
 +  *  [[.:include:algorithm#Nichtmodifizierende Algorithmen]] ändern weder Werte noch ordnen sie Elemente um. 
 +  *  [[.:include:algorithm#Modifizierende Algorithmen]] können Werte ändern und umordnen. 
 +  *  [[.:include:algorithm#Mutierende Algorithmen]] ändern die Elementreihenfolge, ohne Werte zu ändern, einzufügen oder wegzulassen. 
 +<code cpp>
 +#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
 +}
 +</code>
 +==== Bereiche als Parameter ====
 +Seit C++20 können die Algorithmen auch den Bereich [first,last) als einen einzigen Parameter, ein ''range'' aufnehmen:
 +<code cpp>
 +  std::ranges::copy(array, std::ostream_iterator<float>(std::cout, " ") );
 +</code>
 +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.
 +
 +===== Container =====
 +  * 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.
 +
 +==== Sequentielle Container ====
 +<[[.:include:deque|deque]]>
 +<[[.:include:list|list]]>
 +<[[.:include:vector|vector]]>
 +
 +Sequentielle Container übernehmen Elemente in vorgegebener Reihenfolge
 +und behalten diese Folge bei.
 +Jeder Container hat spezielle Stärken: 
 +  *  Ein [[.:include:vector|vector]]''<T>'' (dynamisches Feld) erlaubt den schnellsten indizierten Zugriff  und kann leicht am Ende wachsen oder schrumpfen,
 +  *  eine [[.:include:deque|deque]]''<T>'' (double-ended queue) kann nach beiden Seiten wachsen oder schrumpfen,
 +  *  eine [[.:include:list|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.
 +<code cpp>
 +std::vector<T>       [0|1|2|3|4] <-->
 +std::deque<T>   <--> [0|1|2|3|4] <-->
 +std::list<T>    <--> [0]=[1]=[2]=[3]=[4] <-->
 +</code>
 +<[[.:include:array|array]]>
 +<[[.:include:bitset|bitset]]>
 +<[[.:include:forward_list|forward_list]]>
 +<[[.:include:initializer_list|initializer_list]]>
 +<[[.:include:string|string]]>
 +<[[.:include:valarray|valarray]]>
 +(Beinahe-Container)
 +
 +"Beinahe"-Container implementieren einige, jedoch nicht alle
 +[[#allgemeine Container-Eigenschaften|allgemeinen Container-Eigenschaften]].
 +
 +Ein [[.:include:array|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 [[.:include:bitset|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 [[.:include:vector|vector]]''<bool>'' gebraucht wird.
 +
 +Die [[.:include:forward_list|forward_list]]''<T>''
 +kann nur in Vorwärtsrichtung durchlaufen werden.
 +Damit gibt es nur Methoden zum Einfügen / Entfernen //nach// einer angegebenen Position.
 +
 +Initialisiererlisten [[.:include:initializer_list|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 [[.:include:string|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 [[.:begriffe#FORTRAN]]) 
 +wurde die Schablone [[.:include:valarray|valarray]]''<T>'' entworfen.
 +Die Implementierung ist (auf bestimmten Rechnern) so optimierbar,
 +dass die Rechenoperationen parallel (und eben nicht sequentiell) ausgeführt werden.
 +
 +==== Assoziative Container ====
 +<[[.:include:map|map]]>
 +<[[.:include:set|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 [[#Funktionsadapter|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) [[.:include:map|map]]''<Key,Value,Compare>'' verwalten Schlüssel-Wert-Paare [[#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 [[.:include:map|multimap]]''<Key,Value,Compare>'' kann mehrere Werte dem gleichen Schlüssel zuordnen.
 +  *  Mengen [[.:include:set|set]]''<T,Compare>'' können als degenerierte assoziative Felder betrachtet werden (nur Schlüssel ohne zugeordneten Wert). 
 +  * In [[.:include:set|multiset]]''<T,Compare>'' dürfen gleiche Werte auch mehrfach vorkommen.
 +<code cpp>
 +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 }
 +</code>
 +Da assoziative Container meist als balancierte Binärbäume implementiert sind,
 +haben Operationen zumeist logarithmisches [[#Laufzeitverhalten]].
 +
 +==== Hash-Container ====
 +<[[.:include:unordered_map|unordered_map]]>
 +<[[.:include:unordered_set|unordered_set]]>
 +
 +Die in C++11 hinzugekommenen Container 
 +[[.:include:unordered_map|unordered_map]]''%%<Key,Value,Hash<Key>>%%''
 +und
 +[[.:include:unordered_set|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.
 +==== Allgemeine Container-Eigenschaften ====
 +=== Typdefinitionen ===
 +
 +| ''%%...............................%%'' | vector | deque | list | set | multiset | map | multimap|
 +| ''value_type''                      | x | x | x | x | x | x | x|
 +| ''reference''                       | x | x | x | x | x | x | x|
 +| ''const_reference''                 | x | x | x | x | x | x | x|
 +| ''iterator''                        | Ran | Ran | Bi | Bi | Bi | Bi | Bi|
 +| ''const_iterator''                  | Ran | Ran | Bi | Bi | Bi | Bi | Bi|
 +| ''reverse_iterator''                | Ran | Ran | Bi | Bi | Bi | Bi | Bi|
 +| ''const_reverse_iterator''          | Ran | Ran | Bi | Bi | Bi | Bi | Bi|
 +| ''size_type''                       | x | x | x | x | x | x | x|
 +| ''difference_type''                 | x | x | x | x | x | x | x|
 +| ''key_type''                        |       | x | x | x | x|
 +| ''key_compare''                           | x | x | x | x|
 +| ''value_compare''                         | x | x | x | x|
 +
 +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:
 +
 +<code cpp>
 +typedef std::vector<double> Container;  // oder std::list<double> ?
 +Container v;
 +Container::iterator first = v.begin();
 +</code>
 +=== Erzeugen, Kopieren, Zerstören ===
 +
 +| ''%%...............................%%'' | vector | deque | list | set | multiset | map | multimap|
 +| ''container()''                     | x | x | x | x | x | x | x|
 +| ''container(anzahl)''               | x | x | x |        |
 +| ''container(anzahl, wert)''         | x | x | x |        |
 +| ''container(original)''             | x | x | x | x | x | x | x|
 +| ''container(anfang, ende)''         | x | x | x | x | x | x | x|
 +| ''~container()''                    | x | x | x | x | x | x | x|
 +
 +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.
 +
 +<code cpp>
 +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
 +}
 +</code>
 +=== Nicht-modifizierender Zugriff (Größe, Vergleiche) ===
 +
 +| ''%%...............................%%'' | vector | deque | list | set | multiset | map | multimap|
 +| ''size()''                          | x | x | x | x | x | x | x|
 +| ''empty()''                         | x | x | x | x | x | x | x |
 +| ''max_size()''                      | x | x | x | x | x | x | x |
 +| ''operator==(container2)''          | x | x | x | x | x | x | x |
 +| ''operator<(container2)''           | x | x | x | x | x | x | x |
 +
 +Container liefern ihre Elementanzahl mit ''c.size()''
 +Bei ''c.size()==0'' trifft ''c.empty()'' zu.
 +
 +<code cpp>
 +void groesse_demo(Container const& c)
 +{
 +  if (c.empty()) std::cout << "Container ist leer\n";
 +  else std::cout << "Container mit " << c.size() << " Elementen\n";
 +}
 +</code>
 +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.
 +
 +<code cpp>
 +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";
 +}
 +</code>
 +=== Nicht-modifizierender Zugriff (assoziative Container) ===
 +
 +| ''%%...............................%%'' | vector | deque | list | set | multiset | map | multimap|
 +| ''value_comp()''                    |       | x | x | x | x |
 +| ''key_comp()''                      |       | x | x | x | x |
 +| ''count(key)''                      |       | x | x | x | x |
 +| ''find(key)''                             | x | x | x | x |
 +| ''lower_bound(key)''                |       | x | x | x | x |
 +| ''upper_bound(key)''                |       | x | x | x | x |
 +| ''equal_range(key)''                |       | x | x | x | x |
 +
 +''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.
 +
 +<code cpp>
 +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";
 +}
 +</code>
 +=== Zuweisungen ===
 +
 +| ''%%...............................%%'' | vector | deque | list | set | multiset | map | multimap|
 +| ''assign(anzahl)''                  | x | x | x |        |
 +| ''assign(anzahl, wert)''            | x | x | x |       | |
 +| ''assign(anfang, ende)''            | x | x | x |       | |
 +| ''operator=(container2)''           | x | x | x | x | x | x | x |
 +| ''swap(container2)''                | x | x | x | x | x | x | x |
 +
 +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.
 +
 +=== Direkter Elementzugriff ===
 +
 +| ''%%...............................%%'' | vector | deque | list | set | multiset | map | multimap|
 +| ''operator[](index)''               | x | x |       | x ||
 +| ''at(index)''                       | x | x |         ||
 +| ''front()''                         | x | x | x |       ||
 +| ''back()''                          | x | x | x |       ||
 +
 +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 [[.:include:vector|vector]] 
 +und [[.:include:deque|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 [[.:include:map|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]
 +
 +<code cpp>
 +void erfassen(std::map<std::string,int>& tabelle, std::string wort)
 +{
 +  ++tabelle[wort];
 +}
 +</code>
 +=== Iterator-Zugriff ===
 +
 +| ''%%...............................%%'' | vector | deque | list | set | multiset | map | multimap |
 +| ''begin()''                         | x | x | x | x | x | x | x |
 +| ''end()''                           | x | x | x | x | x | x | x |
 +| ''rbegin()''                        | x | x | x | x | x | x | x |
 +| ''rend()''                          | x | x | x | x | x | x | x |
 +
 +[[#Iteratoren]]
 +von [[.:include:vector|vector]]
 +und [[.:include:deque|deque]]
 +erlauben wahlfreien Zugriff.
 +Die bidirektionalen Iteratoren der [[#assoziative Container|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.
 +
 +<code cpp>
 +     begin()  ------------>  end()
 +               ++iter      |
 +                           v
 +    [.......................]       Container
 +   ^ :                     ^ :
 +   | :       ++rev_iter    | :
 +   rend() <--------------  rbegin()                
 +</code>
 +
 +=== Einfügen ===
 +
 +| ''%%...............................%%'' | vector | deque | list | set | multiset | map | multimap|
 +| ''insert(position, wert)''          | x | x | x | x | x | x | x |
 +| ''insert_hint(position, wert)''           | x | x | x | x |
 +| ''insert(wert)''                    |       | x | x | x | x |
 +| ''insert(anfang, ende)''            |       | x | x | x | x |
 +| ''insert(position)''                | x | x | x |        |
 +| ''insert(position, anzahl, wert)''  | x | x | x |        |
 +| ''push_front(wert)''                |   | x | x |        |
 +| ''push_back(wert)''                 | x | x | x |        |
 +| ''emplace(position, args)''         | x | x | x | x | x | x | x |
 +| ''emplace_hint(position, wert)''    |       | x | x | x | x |
 +| ''emplace(args)''                         | x | x | x | x |
 +| ''emplace_front(args)''               | x | x |        |
 +| ''emplace_back(args)''              | x | x | x |        |
 +| ''resize(anzahl)''                  | x | x | x |        |
 +| ''resize(anzahl,wert)''             | x | x | x |        |
 +| ''merge(container2)''                     | x | x | x | x |
 +
 +Ein ''wert'' lässt sich an einer durch einen [[#Iteratoren|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.
 +
 +<code cpp>
 +void einfuegen_demo(Container& c)
 +{
 +  Container::value_type wert = c.front();
 +  c.push_back(wert); // c.insert(c.end(), wert);
 +}
 +</code>
 +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 [[kennen:begriffe#C++17]] 
 +das Verschmelzen (Spleißen) von Sequenzen. 
 +Schon vorhandene Elemente verbleiben im Quellcontainer, sofern das Ziel kein "multi"-Container ist:
 +<code cpp>
 +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';
 +}
 +</code>
 +Auch einzelne Knoten lassen sich umhängen:
 +<code cpp>
 +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';
 +}
 +</code>
 +
 +=== Löschen ===
 +
 +| ''%%...............................%%'' | vector | deque | list | set | multiset | map | multimap|
 +| ''clear()''                         | x | x | x | x | x | x | x |
 +| ''erase(position)''                 | x | x | x | x | x | x | x |
 +| ''erase(anfang, ende)''             | x | x | x | x | x | x | x |
 +| ''erase(wert)''                           | x | x | x | x |
 +| ''pop_front()''                       | x | x |          |
 +| ''pop_back()''                      | x | x | x |         |
 +
 +Um ein Element zu löschen, muss dessen ''position'' als 
 +[[#Iteratoren|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.
 +
 +<code cpp>
 +void loeschen_demo(Container& c)
 +{
 +  c.erase(c.begin());  // c.pop_front();
 +  c.clear();           // c.erase(c.begin(), c.end());
 +}
 +</code>
 +
 +
 +==== Laufzeitverhalten ====
 +Containermethoden zeigen folgendes Laufzeitverhalten bei n Elementen im Container:
 +
 +|                    | vector | deque | list | set/multiset | map/multimap | unordered_set | unordered_map |
 +| Indexzugriff       | O(1)   | O(1)  | -    | -            | O(log n)| - | O(1)+ |
 +| Listenoperationen  | O(n)+  | O(n)  | O(1) | O(log n)+    | O(log n)+| O(1)+ | O(1)+ |
 +| Operationen vorn   | -      | O(1)  | O(1) | -            | -| - | - |
 +| Operationen hinten | O(1)+  | O(1)  | O(1) | -            | -| - | - |
 +| Iteratoren         | Ran    | Ran   | Bi   | Bi           | Bi| Bi | Bi|
 +Dabei bedeutet 
 +>  - nicht implementiert wegen schlechten Zeitverhaltens, 
 +>  + durchschnittliches Verhalten, gelegentlich Zusatzaufwand.
 +
 +===== Iteratoren =====
 +<[[.:include:iterator|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. 
 +
 +==== Kategorien  ====
 +Anhand der (hier abgekürzt bezeichneten) Kategorien
 +können Algorithmen mit optimalem Zeitverhalten für die Sequenz
 +umgesetzt werden.
 +
 +| Abkürzung  | Kategorie     | zulässige Operationen |
 +| ''Out'' | Output        | ''* ++''|
 +| ''In''  | Input         | ''%%== != * -> ++%%''|
 +| ''For'' | Forward       | ''%%== != * -> ++ =%%''|
 +| ''Bi''  | Bidirektional | ''%%== != * -> ++ -- =%%''|
 +| ''Ran'' | Random Access | zusätzlich ''%%< <= > >= + - += -= []%%'' |
 +
 +Ausgabe-Iteratoren ''Out'' können Werte zugewiesen bekommen und weitergesetzt werden. 
 +
 +<code cpp>
 +  *iter = wert;
 +  ++iter;
 +</code>
 +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.
 +
 +<code cpp>
 +  while (iter != ende)
 +  {
 +    wert = *iter;
 +    ++iter; 
 +  }
 +</code>
 +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.
 +
 +<code cpp>
 +  while (*iter != wert)
 +  {
 +    *ziel++ = *iter++;
 +  }
 +</code>
 +Bidirektionale Iteratoren ''Bi'' können mittels Dekrement ''%%--%%'' 
 +auch in entgegengesetzter Richtung über die Elemente laufen.
 +
 +<code cpp>
 +  while (first != last)
 +  {
 +    --last;
 +  }
 +</code>
 +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.
 +
 +<code cpp>
 +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];
 +  }
 +}
 +</code>
 +
 +==== Reverse-Iteratoren ====
 +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.
 +
 +<code cpp>
 +     begin()  ------------>  end()
 +               ++iter      |
 +                           v
 +    [.......................]       Container
 +   ^ :                     ^ :
 +   | :       ++rev_iter    | :
 +   rend() <--------------  rbegin()    
 +             --iter             
 +</code>
 +Mit ''rev_iter.base()'' kann der zugehörige Vorwärts-Iterator zurückgewonnen werden.
 +
 +==== Iterator-Adapter ====
 +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)'': 
 +
 +<code cpp>
 + while (first != last) *insert++ = *first++;
 + while (input != ende) *output++ = *input++;
 +</code>
 +Einfüge-Iteratoren sind Iterator-Adapter, 
 +mit denen das Zuweisen von Werten
 +in ein Einfügen in einen Container umgedeutet wird:
 +
 +<code cpp>
 +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);
 +}
 +</code>
 +Mit den Inserter-Funktionen ist es einfach, einen Bereich an einen Container anzuhängen:
 +
 +<code cpp>
 +  std::copy(c.begin(), c.end(), std::back_inserter(c2));
 +</code>
 +Ausgabestrom-Iteratoren geben Elemente aus, auch direkt aus Algorithmen heraus:
 +
 +<code cpp>
 +  std::ostream_iterator<double> output(std::cout, " "); 
 +  std::copy(c.begin(), c.end(), output);
 +</code>
 +Eingabestrom-Iteratoren passen Eingabeströme an das Zeigerkonzept an. 
 +Das Einlesen von Elementen ist auch in Algorithmen möglich.
 +
 +<code cpp>
 +  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;
 +  }
 +</code>
 +
 +===== Hilfsmittel =====
 +<[[.:include:utility|utility]]>
 +
 +Nur die [[#Vergleichsoperatoren]]
 +''=='' und ''<'' müssen selbst definiert werden, 
 +die restlichen sind daraus herleitbar.
 +Für beliebige Wertpaare gibt es den Behälter [[#Paare|pair]]''<U,V>''.
 +[[#Container-Adapter]]
 +(Stapel und Warteschlangen) sowie
 +[[#Funktionsadapter]]
 +ergänzen die Standard Template Library.
 +
 +
 +==== Vergleichsoperatoren ====
 +Um Vergleiche von Objekten selbstdefinierter Typen vorzunehmen,
 +genügt es,  ''<'' und ''=='' zu implementieren:
 +
 +| Operation    | ist gleichwertig zu|
 +|  ''x!=y'' |  ''!(y==x)''|
 +|  ''x<=y'' |  ''!(y<x)''|
 +|  ''x>=y'' |  ''!(x<y)''|
 +|  ''x>y''  |  ''y<x''|
 +
 +Um diese Äquivalenzen zu nutzen, 
 +muss man lediglich die Schablonen 
 +des Namensbereiches ''std::rel_ops'' einbinden((bis [[begriffe#C++17]], ab [[begriffe#C++2a]] ist deren Nutzung geächtet)):
 +
 +<code cpp>
 +#include <utility> // über Algorithmen und Container automatisch
 +using namespace std::rel_ops; // bei Bedarf
 +</code>
 +Für die Vergleichsoperatoren wurde ein Unternamensraum von ''std'' gewählt,
 +um Mehrdeutigkeiten oder falsche Operator-Aufrufe zu vermeiden.
 + 
 +==== Paare ====
 +Paare von Werten unterschiedlichster Typen 
 +kommen an verschiedenen Stellen in der Standardbibliothek vor,
 +z.B. als Elemente ''std::pair<Key const, Value>''
 +eines [[.:include:map|map]]-Containers,
 +aber auch als Rückgabewert des Algorithmus [[.:lib:equal_range|equal_range()]].
 +
 +<code cpp>
 +template <class Typ1, class Typ2>
 +struct pair   
 +{
 +  Typ1 first;
 +  Typ2 second;
 +  // ... Konstruktoren, Vergleiche < ==
 +};
 +</code>
 +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''.
 +
 +==== Container-Adapter ====
 +<[[.:include:queue|queue]]>
 +<[[.:include:stack|stack]]>
 +
 +<code cpp>
 +push(x)               pop()     push(x)    
 +<-- [...............] <--       <--> [...............]
 +                            pop() |
 +     front()       back()             top()
 +</code>
 +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 [[.:include:deque|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 [[.:include:vector|vector]]''<T>'' 
 +bzw. [[#Funktionsadapter|less]]''<T>'' eingesetzt. 
 +
 +Die Container-Adapter besitzen neben Konstruktor und Vergleichen nur wenige Methoden.
 +
 +| ''full()''  | Adapter ist voll|
 +| ''empty()'' | Adapter ist leer |
 +| ''push(x)'' | fügt x ein |
 +| ''pop()''   | löscht erstes Element|
 +| ''top()''   | oberstes Element im Stapel|
 +| ''front()'' | vorderstes /|
 +| ''back()''  | letztes Element in Warteschlange|
 +
 +<code cpp>
 +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();
 +  }
 +}
 +</code>
 +
 +==== Funktionsadapter ====
 +<[[.:include:functional|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
 +[[.:operator#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.
 +
 +| Arithmetik-Funktoren | Vergleichsprädikate     | Logik-Prädikate       |
 +| ''negate<T>''     | ''equal_to<T>''      | ''logical_not<T>''|
 +| ''plus<T>''       | ''not_equal_to<T>''  | ''logical_and<T>''|
 +| ''minus<T>''      | ''less<T>''          | ''logical_or<T>''  |
 +| ''multiplies<T>'' | ''less_equal<T>''    | |
 +| ''divides<T>''    | ''greater<T>''       | |
 +| ''modulus<T>''    | ''greater_equal<T>'' | |
 +
 +Für [[#assoziative Container]] legt ein
 +Prädikattyp die Sortierreihenfolge fest. [[begriffe#C++14]] erlaubt hier, den Typ ''T'' des Funktors wegzulassen: 
 +
 +<code cpp>
 +std::set<int, std::less<>> zahlenmenge;
 +</code>
 +An [[#Algorithmen]]
 +werden Funktoren als Objekt übergeben (deshalb mit Klammern):
 +
 +<code cpp>
 +std::sort(first, last, std::greater<>());
 +</code>
 +
 +Polymorphe Funktionsadapter ''function<//ergebnistyp//(//Typliste//)''> 
 +nehmen sowohl Funktoren, Funktionszeiger als auch [[.:funktion#anonyme Funktionen|Lambda-Ausdrücke]] auf.
 +Ob ihnen ein Wert zugewiesen wurde, kann vor dem Aufruf geprüft werden:
 +
 +<code cpp>
 +std::function<double(double)> f = std::negate<>();
 +f = [](double x) { return std::acos(x); }
 +if (f) std::cout << f(1) << '\n';
 +</code>
 +
 +Binder [[.:lib:bind|bind(f, parameter)]] als flexible Funktionsadapter 
 +koppeln die Parameter eines Funktors ''f'' an Platzhalter für die Argumente des Aufrufs,
 +an Werte, Referenzen [[.:lib:ref|ref(variable)]], konstante Referenzen [[.:lib:ref|cref(variable)]]
 +oder Ergebnisse anderer Binder-Funktoren. 
 +<code cpp>
 +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]
 +</code>
 +==== Platzhalter ====
 +
 +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 [[wpde>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:
 +
 +<code cpp>
 +std::function<bool(double)> greater_than20 = [](double x){ return x > 20; };
 +int n = std::count_if(first,last, std::not1(greater_than20));
 +</code>
 +
 +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.
 +
 +<code cpp>
 +void zeichnen(std::list<Objekt*>& l)
 +{
 +  std::for_each(l.begin(), l.end(), std::mem_fn(&Form::zeichne));
 +}
 +</code>
 +
 +==== Referenzwrapper ====
 +
 +Mit den von den Hilfsfunktionen ''ref(variable)'' und ''cref(variable)'' erzeugten ''reference_wrapper<T>'' 
 +lässt sich ein Multi-Index-Zugriff auf Datenmengen verwirklichen:
 +<code cpp>
 +#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;
 +}
 +</code>
  

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki