layout: true name: blank styling: styling.css styling-by: Martin Weitzel .stylehint[ Styled with [{{styling}}]({{styling}}) by {{styling-by}} ] --- layout: true name: plain copyright: (CC) BY-SA branding: [Dipl.-Ing. Martin Weitzel](http://tbfe.de) customer: [für MicroConsult Training & Consulting GmbH](http://microconsult.de) {{header}} .pagefooter[ {{copyright}}: {{branding}} {{customer}} .microconsult-logo[] ] --- layout: true name: linkinfo copyright: (CC) BY-SA branding: [Dipl.-Ing. Martin Weitzel](http://tbfe.de) customer: [für MicroConsult Training & Consulting GmbH](http://microconsult.de) {{header}} .infographic[ [](InfoGraphics/{{graphic}}.png "Click to open – add [CTRL+] SHIFT for new [tabbed] window") ] .pagefooter[ {{copyright}}: {{branding}} {{customer}} .microconsult-logo[] ] --- layout: true name: withinfo copyright: (CC) BY-SA branding: [Dipl.-Ing. Martin Weitzel](http://tbfe.de) customer: [für MicroConsult Training & Consulting GmbH](http://microconsult.de) {{header}} .infolink.right[ [Click here for Info-Graphic {{graphic}}](InfoGraphics/{{graphic}}.png "add [CTRL+] SHIFT for own [tabbed] window") {{section}} ] .pagefooter[ {{copyright}}: {{branding}} {{customer}} .microconsult-logo[] ] --- layout: false template: blank [C++ STL]: 00_topics.html#agenda # [C++ STL] – Iterators and Algorithms .center[(Day 2, Part 1)] .pull-left[ -------------------------------------------------------------------------------- **ITERATORS** * [Principle of Iterators ](#stl_iterator_principles) * [Iterator Categories ](#stl_iterator_categories) * [Iterator Traits ](#stl_iterator_traits) -------------------------------------------------------------------------------- ] .pull-right[ -------------------------------------------------------------------------------- **ALGORITHMS** * [Iterator-Interface to Algorithms ](#stl_algorithm_interface) * [Callbacks from Algorithms ](#stl_algorithm_callbacks) * [A Standard Algorithms Tour ](#stl_algorithm_tour) -------------------------------------------------------------------------------- ] .center[**NOTE**] At first this part puts the focus on Iterators – providing the "glue" between algorithms – and then takes a closer view on algorithms, especially with respect to their use of iterators and various forms of call-backs to adapt their behaviour in detail. --- template: plain name: stl_iterator_principles header: ## Principle of Iterators [Gof Iterator Pattern]: http://www.informit.com/articles/article.aspx?p=1407357&seqNum=4 [Duck-Typing]: https://en.wikipedia.org/wiki/Duck_typing Iterators provide a helping mechanism for container traversal, i.e. * processing all elements in a container, * either in a specific order,._[] * or simply with the guarantee each element is visited exactly once. .N[ Note that STL-Iterators share the idea of the [GoF Iterator Pattern] but are far from its proposed implementation. ] STL style Iterators * access the current element via the overloaded `operator*`; * advance to the next element via the overloaded `operator++`; * end of traversal by comparison with a special end-point iterator and do all of this expecting an interface in the vein of [Duck-Typing]. .F[: Then, of course, there needs to be an ordering criteria, which for sequential containers may be the sequential order created by insertion, and also trivially exists for the traditional *ordered associative* containers based on binary trees, **but not** for the hash-based containers (i.e. `std::unordered_set` and `std::unordered_map` and their `multi`-variants). ] --- template: linkinfo graphic: STL-ContainerIterators name: visualising_iterators header: ### Visualising Iterators Often iterators are visualised in graphics to support understanding their principle. * One common abstraction is to show iterators **pointing to** an element – the element they would return when dereferenced. * Another possible abstraction is to show iterators pointing **in between** elements – right before the element they would advance over next. --- template: plain header: #### Visualising Iterators *Pointing To* Elements [Undefined Behaviour]: http://en.cppreference.com/w/cpp/language/ub ##### Advantages * It **is by far the most common** visualisation. * It is immediately clear which element `operator*` will access. ##### Disadvantages * Developers might first need to learn thinking in "asymmetric borders"._[] * One more element must be assumed beyond the container-end to * visualise the iterator end position, and also * show how an iterator interacts with an empty container. * It must be made absolutely clear that this is a virtual element, **introduced only for the purpose of visualisation**. .W[ **Therefore:** Any attempt to access that *"non-existing end point"* Element is [Undefined Behaviour] according to the ISO Standard. ] .F[: After being accustomed to that kind of thinking it often becomes second nature and thinking in symmetric borders may start feel unnatural. ] --- template: plain header: #### Visualising Iterators *Pointing Between* Elements [Undefined Behaviour]: http://en.cppreference.com/w/cpp/language/ub ##### Advantages * No virtual elements outside the container need to be assumed. * Ranges (of affected elements) are visualised in a most natural way. * It usually goes without saying that the iterator must not be moved outside of the container. .W[ **Nevertheless:** Any attempt to move the iterator beyond the container borders [Undefined Behaviour] according to the ISO Standard. ] ##### Disadvantages * In common C++ literature this visualisation is hardly ever used. * The *move direction* of the iterator must always be indicated to understand which element `operator*` will access. --- template: linkinfo graphic: STL-IteratorCategories name: stl_iterator_categories header: ## Iterator Categories ------------------------------------------------------------------------ * [Forward Iterators ](#forward_iterators) ------------------------------------------------------------------------ * [Bidirectional Iterators ](#bidirectional_iterators) ------------------------------------------------------------------------ * [Random Access Iterators ](#random_access_iterators) ------------------------------------------------------------------------ --- template: withinfo graphic: STL-IteratorCategories section: Unidirectional Iterators name: forward_iterators header: ### Forward Iterators [ForwardIterator]: http://en.cppreference.com/w/cpp/concept/ForwardIterator Iterators modelling the [ForwardIterator] concept may (only) be advanced into one direction – i.e. forward from the begin to the end of a container. Of the STL containers only one has iterators in that category, which is * `std::forward_list
::iterator` including the respective `const_`-variant. --- template: withinfo graphic: STL-IteratorCategories section: Bidirectional Iterators name: bidirectional_iterators header: ### Bidirectional Iterators [BidirectionalIterator]: http://en.cppreference.com/w/cpp/concept/BidirectionalIterator Iterators modelling the [BidirectionalIterator] concept may be advanced in both directions – forward from the begin to the end of a container, or backward from the end (= reverse begin) to the begin (= reverse end). .N[ The [BidirectionalIterator] concept **includes** the capabilities of the [ForwardIterator Concept](#forward_iterators). ] Of the STL containers seven have iterators of that category, which are * `std::list
::iterator` * and iterators of all eight associative containers, including the respective `const_`-, `reverse_`-, and `const_reverse_`-variants. --- template: withinfo graphic: STL-IteratorCategories section: Random Access Iterators name: random_access_iterators header: ### Random Access Iterators [RandomAccessIterator]: http://en.cppreference.com/w/cpp/concept/RandomAccessIterator Iterators modelling the [RandomAccessIterator] concept may efficiently access elements at any given (valid) position in a container. .N[ The [RandomAccessIterator] concept **includes** the capabilities of the [BidirectionalIterator Concept](#bidirectional_iterators). ] Besides addition and subtraction of integral numbers (which move the iterator back or forth over that distance) by subtraction the size of the enclosed range._[] can be determined. .F[: As in stead "size of enclosed range" also the wording "number of enclosed elements" is a meaningful description, this again is a case where visualising iterators as pointing **in between** elements is much more natural. ] Of the STL containers three have iterators of that category, which are * `std::array
::iterator`, * `std::vector
::iterator` are * `std::deque
::iterator` including the respective `const_`-, `reverse_`-, and `const_reverse_`-variants. --- template: plain header: ### Limit-Checking of Random-Access Iterators With respect to the following it should be noted that the ISO standard specifies *Minimum-Requirements* only, which allow an highly efficient implementation, even if this is traded for safety. .W[ When a Random Access Iterators participates in an operation that moves it outside the container borders the result is undefined. ] Valid positions are also end-point positions, i.e. one beyond the container end for regular iterators and its begin for the `reverse_`-variants. .W[ On subtraction the result is only meaningful if the involved iterators refer (to elements of._[]) the same container (including the end-point positions). ] For any two iterators pointing to elements of different containers (of the same type – otherwise it were a compile time error) it is guaranteed that they never compare equal. .F[: If the visualisation of iterators **pointing to** elements is preferred. ] --- template: plain name: stl_iterator_traits header: ## Iterator Traits [Meta-Programming]: https://en.wikibooks.org/wiki/C%2B%2B_Programming/Templates/Template_Meta-Programming [Type Traits] in general are an advanced concept with many uses in compile time [Meta-Programming], but not limited to that area. With respect to iterators only some minimal basic knowledge needs to be acquired, which then can then be applied in ["cookbook-style"](#stl_iterator_cookbook_use) where necessary. .N[ The class `std::iterator_traits` provides type conversions from an iterator (type) to several related types, like the type resulting from dereferencing. ] Its basic use is shown in an example on the next page. .I[ For more information on iterator traits see: http://en.cppreference.com/w/cpp/iterator/iterator_traits ] --- template: plain name: stl_iterator_cookbook_use header: ### Cookbook-Style Use of Iterator Traits Typically iterator traits come in handy when algorithms are implemented. If an algorithm * shall not only work with iterators from the STL containers, * but also for native pointers (into native array) it may be difficult ar first glance to determine the type of a derefenrenced iterator in a generic way. The following shows an elegant._[] solution applying `std::iterator_traits`: ``` template< … , typename Iterator, … > void foo( … , Iterator it, … ) { typename std::iterator_traits
::value_type temp = *it++; … } ``` .F[: Less elegant solutions might overload `foo` for pointer types. ] --- template: linkinfo graphic: STL-IteratorUsages name: stl_algorithm_interface header: ## Iterator Interface to Algorithms ---------------------------------------------------------------------------- * [Iterators glueing … ](#iterators_as_glue) * [… Containers with … ](#container_axis) * [… Algorithms ](#algorithm_axis) ---------------------------------------------------------------------------- * [Input-Iterators ](#input_iterators) * [Output-Iterators ](#output_iterators) ---------------------------------------------------------------------------- * [Successful und … ](#success_from_searching) * [… Failed Search ](#failure_from_searching) ---------------------------------------------------------------------------- * [Fill State and … ](#state_from_filling) * [… Removal Indication ](#removing_logically_only) ---------------------------------------------------------------------------- --- template: withinfo graphic: STL-IteratorUsages section: Iterators as "Glue" name: iterators_as_glue header: ### Iterators Glueing Containers with Algorithms *Without* Iterators glueing containers with algorithms for * approximately 40 algorithm (-families) and * 12 containers in the ISO-Standard for C++98 about 480 (= 12 × 40) implementations would be necessary.._[] .F[: Even considering the fact that not every algorithm makes sense for every container there would still be several hundred implementations be required. ] --- template: withinfo graphic: STL-IteratorUsages section: Container Dimension name: container_axis header: ### Container-Axis With C+98 three sequential and four associative containers were standardized. C++11 now has a total of five sequential und eight associative containers. (C++14 hat has not added more containers) --- template: withinfo graphic: STL-IteratorUsages section: Algorithm-Dimension name: algorithm_axis header: ### Algorithm-Axis Depending on how is counted int the ISO-Standard for C++98 there are about Many algorithms come in "families" as eg.: * A basic variant._[] * A variant ending in `_if` for flexibly specifying predicates * A variant ending in `_copy` to save the result in a new container * A variant ending in `_copy_if` to combined the last two .F[: Not for any basic algorithm the following three variants make sense, so not all the other three will be present. But if the second **and** the third exist then also the fourth is present. ] --- template: withinfo graphic: STL-IteratorUsages section: Input Iterators name: input_iterators header: ### Input Iterators Input Iterators *alternately* have to be._[] * dereferenced (`*`) for *read access* and * *incremented* (`++`)for stepping to the next element. .W[ If this rule is violated not for ever kind of container a problem will show. Therefore algorithms based on input iterators need be thoroughly tested. ] .F[: The usual combinations of dereferencing with prefix and postfix increment are typically provided but the semantically correct implementation can become tricky, especially if copying of the element type should be avoided. Especially storing a reference to the result of dereferencing – which technically would defer the actual dereferencing to the point of use of the reference – may lead to surprises and hence needs to be avoided. ] --- template: withinfo graphic: STL-IteratorUsages section: Output Iterators name: output_iterators header: ### Output Iterators Output-Iteratoren sind *abwechselnd* * für den *Schreib-Zugriff* zu dereferenzieren (`*`) * und *weiter zu schalten* (`++`). .W[ Bei Nichtbeachtung dieser Anwendungsvorschrift betrifft das Fehlverhalten oft nicht alle Arten von Containern, so dass Verstöße nur bei ausreichenden Tests auffallen. ] --- template: withinfo graphic: STL-IteratorUsages section: Return Success from Search name: success_from_searching header: ### Erfolgreiche Suche Beim Suchen (und verwandten Container-Operationen) wird der Erfolg dadurch angezeigt, dass der als Rückgabewert gelieferte Iterator * auf eine gültige Position im zur Bearbeitung übergebenen Daten-Bereich zeigt. .W[ Wird nur ein Teilbereich eines Containers `c` übergeben, der sich nicht bis zu dessen Ende erstreckt, darf zur Prüfung auf Erfolg oder Misserfolg nicht mit `c.end()` verglichen werden. ] --- template: withinfo graphic: STL-IteratorUsages section: Return Failure from Search name: failure_from_searching header: ### Gescheiterte Suche Beim Suchen wird der Misserfolg damit angezeigt, dass der als Rückgabewert gelieferte Iterator * immer auf die Endposition des zur Bearbeitung übergebenen Bereichs zeigt. .W[ Beim Suchen in einem leeren Container oder Bereich wird stets die Endposition des Containers bzw. des Bereichs geliefert. ] --- template: withinfo graphic: STL-IteratorUsages section: Return State from Filling name: state_from_filling header: ### Zustandsanzeige nach Füllen Beim Füllen eines Containers ist es üblich, dass Algorithmen * den (neuen) Füllstand des Containers durch einen entsprechenden Iterator als Rückgabewert anzeigen. .N[ Dies ist sinnvoll und praktisch, um den Container ab dieser Stelle später weiter füllen zu können. ] --- template: withinfo graphic: STL-IteratorUsages name: removing_logically_only section: Return "New End" when "Removing" Elements header: ### Löschungs-Anzeige durch neues (logisches) Ende Da die Algorithmen für eine große Zahl von Containern funktionieren sollen, finden gibt es einige aus pragmatischer Sicht sinnvolle aber Besonderheiten. Eine davon betrifft die Tatsache, dass "löschende" Algorithmen nicht davon ausgehen, den bearbeiteten Container verkleinern zu können. .N[ Dadurch funtionieren diese Algorithmen auch für die eingebauten Arrays und die STL-Klasse `std::array`. ] Beim Löschen von Elementen aus Containern wird nur "logisch gelöscht", d.h. * die enthaltenen Elemente erden ggf. anders angeordnet, und * als Rückgabewert ein Iterator geliefert, der das "neue Ende" bezeichnet. --- template: plain name: iterators_in_algorithms header: ## Iteratoren und Algorithmen Die konsequente Verwendung von Iteratoren bei der Implementierung aller STL-Algorithmen verschafft eine besondere Flexibilität. Iteratoren sind in der Regel einfache (Helfer-) Klassen, welche abhängig vom Container, für den sie jeweils zuständig sind, eine vollkommen unterschiedliche Implementierung besitzen können. .N[ Damit können die Daten, die ein STL-Algorithmus bearbeitet, aus ganz unterschiedlichen Quellen stammen und ebenso die gelieferten Ergebnisse an ganz unterschiedlichen Zielen abgelegt werden. ] --- template: plain header: ### Beispiel: Implementierung des `copy`-Algorithmus Zum besseren Verständnis, wie mittels Iteratoren die Algorithmen eine besondere Flexibilität erzielen, ist ein Blick auf eine mögliche Implementierung des `copy`-Algorithmus hilfreich:._[] ``` template
T2 my_copy(T1 from, T1 upto, T2 dest) { while (from != upto) *dest++ = *from++; return dest; } ``` .F[: Damit dieser Algorithmus ggf. per *Copy&Paste* in ein Programm übernommen und ausprobiert werden kann, wurde er vorsorglich `my_copy` genannt, so dass auch bei `using namespace std;` ein Konflikt mit `std::copy` ausgeschlossen ist. ] --- template: plain header: #### Kopieren der Elemente eines `std::set` in einen `std::vector` Die gerade gezeigte Funktion kann problemlos zwischen zwei unterschiedlichen Containern kopieren: ``` std::vector
v; std::set
s; … v.resize(s.size()); std::copy(s.begin(), s.end(), v.begin()); ``` Da von einen normalen Iterator – wie von `v.begin()` geliefert – nur bereits vorhandene Elemente überschrieben aber keine neuen Elemente angefügt werden können, ist es wichtig, den Ziel-Container vor dem Kopieren auf die notwendige (Mindest-) Größe zu bringen. --- template: plain header: #### Anhängen an Vektoren ##### Hilfsklasse: `back_insert_iterator` Ohne den Ziel-Container zuvor auf eine passende Größe zu bringen, lässt sich eine sichere Variante des Kopierens auch erreichen, indem neue Elemente mit `push_back` angefügt werden:._[] ``` std::copy(s.begin(), s.end(), std::back_insert_iterator
>(v) ); ``` .N[ Da die in diesem und vielen folgenden Beispielen an Algorithmen übergebenen Argumentlisten recht lang sind, erfolgt ein Umbruch innerhalb der Argument-Liste, um die Lesbarkeit zu verbessern. ] Dabei werden auch unterschiedliche Formatierungs-Stile demonstriert.._[] .F[: Die oben verwendete asymmetrische Klammerung der Argumentliste ist sicher Geschmackssache, dupliziert aber den oft auch bei geschweiften Klammern üblichen Stil. ] --- template: plain header: ##### Hilfsfunktion: `back_inserter` Die – redundant erscheinende – Angabe von `int` als Datentyp des Containers `v` ist technisch der Tatsache geschuldet, dass ein (temporäres) Objekt der Template-Klasse `std::back_insert_iterator` erzeugt werden muss und der Konstrukor aus dem Argumenttyp nicht auf den Instanziierungs-Typ schließen kann. Eine Hilfsfunktion._[] vermeidet diese Redundanz: ``` std::copy(s.begin(), s.end(), std::back_inserter(v)); ``` .F[: Diese Funktion ist zwar Bestandteil der Standard-Bibliothek, muss also nicht selbst implementiert werden, ihre Implementierung ist aber insofern interessant, als die zugrundeliegende Technik in ähnlich gelagerten Fällen zur Vermeidung redundanter Typangaben eingesetzt werden kann: ``` template
inline std::back_inserter_iterator
std::back_inserter(T &c) { return std::back_insert_iterator
(c); } ``` ] --- template: plain header: #### Am Anfang oder Ende sequenzieller Container einfügen Selbstverständlich funktionert der `std::back_inserter_iterator` bzw. die Hilfsfunktion `std::back_inserter` auch für die Klassen * `std::list` und * `std::deque` und es existiert auch ein `std::front_insert_iterator` sowie eine Hilfsfunktion `std::front_inserter`, welche mit den Klassen * `std::list`, * `std::deque` und * `std::forward_list` verwendbar ist.._[] .F[: Allgemeiner ausgedrückt ist die Anforderung beim `std::back_insert_iterator`, dass für den zur Instanziierung verwendeten Container eine Member-Function `push_back` existiert, und beim `std::front_insert_iterator` entsprechend, dass `push_front` existiert. ] --- template: plain header: #### In assoziative Container einfügen ##### Hilfsklasse: `insert_iterator` Hiermit können z.B. alle Elemente einer Liste wie folgt in ein `std::set` übertragen werden – wobei Duplikate natürlich nicht übernommen werden:._[] ``` std::list
li; … std::set
s; std::copy(li.begin(), li.end(), std::insert_iterator
>(s) ); ``` .F[: Es sei denn, es handelt sich um ein `std::multiset`. ] --- template: plain header: ##### Hilfsfunktion: `inserter` Auch hier gibt es eine Hilfsfunktion zur Vermeidung der (eigentlich redundanten) Angabe des Container-Typs: ``` std::set
s; std::copy(li.begin(), li.end(), std::inserter(s, s.begin())); ``` Etwas ungewöhnlich ist hier das zusätzliche Argument. Dessen Zweck ist es, einen Optimierungshinweis._[] zu geben, den der Insert-Iterator ggf. verwendet, um die Suche nach der Einfügeposition abzukürzen. .N[ Üblicherweise wird – wenn kein wirklicher Hinweis gegeben werden kann – der Beginn-Iterator des jeweiligen Sets verwendet. ] .F[: Da es sich nur um einen Hinweis handelt, ist die Angabe unkritisch, auch wenn man einen falschen Hinweis gibt (oder keinen passenden Hinweise angibt, obwohl einer existiert). Dann bleibt lediglich eine Optimierungs-Chance ungenutzt … ] --- template: plain header: #### Stream-Iteratoren So wie ein Back- oder Front-Insert-Iterator letzten Endes (bei der dereferenzierten Zuweisung) eine `push_back`- bzw. `push_front`-Operation für den betroffenen Container ausführt, lassen sich auch andere Operationen in den (überladenen) Operatoren spezieller Iteratoren unterbringen. ##### In Stream schreiben mit `std::ostream_iterator`: Das folgende Beispiel kopiert den Inhalt einer `std::forward_list` auf die Standard-Ausgabe und fügt nach jedem Wert ein Semikolon ein: ``` std::forward_list
fli; … std::copy(fli.begin(), fli.end(), std::ostream_iterator
(std::cout, ";") ); ``` --- template: plain header: ##### Aus Stream lesen mit `std::istream_iterator`: Das folgende Beispiel._[] kopiert Worte von der Standardeingabe bis EOF in eine `std::forward_list`: ``` std::forward_list
fli; copy(std::istream_iterator
(std::cin), std::istream_iterator
(), std::front_inserter(fli) ); ``` .F[: Zumeist ist es zwar ausreichend, das obige Beispiel mehr oder weniger "kochrezeptartig" und ggf. sinngemäß verändert anzuwenden, dennoch taucht häufig die Frage auf, wie es denn "hinter den Kulissen" funktioniert. Daher als Hinweis das folgende: Offensichtlich gibt es zwei Konstruktoren, von denen einer ein `std::istream`-Objekt als Argument erhält. Ein auf diese Weise erzeugter Input-Stream-Iterator liefert im Vergleich mit einem per Default-Konstruktor erzeugten Gegenstück zunächst `false`. Die Operationen `*` und `++` werden auf eine Eingabe mit `operator>>` abgebildet, wobei die eingelesene Variable genau den Typ hat, der zur Instanziierung der Template verwendet wurde. Sobald der Eingabestrom den *good*-Zustand verlässt, liefert der damit verbundene Istream-Iterator beim erneuten Vergleich mit dem per Default-Konstruktor erstellten `true`. ] --- template: plain header: #### Zeiger als Iteratoren Da die für Iteratoren implementierten Operationen syntaktisch wie semantisch denen für Zeiger entsprechen, können auch klassische Arrays bearbeitet werden. ##### Kopieren AUS klassischem Array Mit einem klassischen Array ``` double data[100]; std::size_t ndata{0}; ``` und der Annahme, dass nach dessen Befüllen die ersten `ndata` Einträge tatsächlich gültige Werte enthalten: ``` std::copy(&data[0], &data[ndata], … ); ``` Oder: ``` std::copy(data, data + ndata, … ); ``` --- template: plain header: ##### Kopieren IN klassisches Array Mit einem klassischen Array als Ziel der Kopie: ``` const auto endp = copy( … , … , &data[0]); ``` Umrechnung des Füllstatus-Iterators in Anzahl gültiger Elemente: ``` ndata = endp - data; // oder: ... endp - &data[0] ``` Hier findet allerdings keinerlei Überlaufkontrolle statt! .W[ Enthält der ausgelesene Container mehr Elemente als `data` aufnehmen kann, könnten **dahinter** (= an größeren Adressen im Speicher) liegende Variablen überschrieben werden. ] --- template: plain header: #### Kopieren zwischen verschiedenen Container-Typen ``` using namespace std; vector
v; // from standard input float-s appended to vector ... copy(istream_iterator
(cin), istream_iterator
(), back_inserter(v)); // ... to classic array (widening to double) ... double data[100]; const auto N = sizeof data / sizeof data[0]; // ... (protecting against overflow) ... if (v.size() < N) v.resize(N); // ... (remembering filling state) ... const auto endp = copy(v.begin(), v.end(), data); // ... to set (truncating to integer) ... set
s; copy(data, endp, inserter(s, s.begin())); // ... to stdout with semicolon and space after each value copy(s.begin(), s.end(), ostream_iterator
(cout, "; ")); ``` .F[: Im Rahmen der Zuweisungskompatibilität erfolgt beim Kopieren zwischen unterschiedlichen Containern auch die Typ-Konvertierung des Elementtyps. ] --- template: plain header: #### Kopieren zwischen gleichartigen Container-Typen [PODs]: http://www.cplusplus.com/reference/type_traits/is_pod/ Obwohl mit dem `std::copy`-Algorithmus *1:1-Kopien* gleichartiger Container problemlos möglich sind, wird hier eine Zuweisung eher sinnvoll sein, also: ``` std::vector
v1, v2; … v2 = v1; ``` Und nicht (evtl. nach einem `v2.clear()`): ``` std::copy(v1.begin(), v1.end(), std::back_inserter(v2)); ``` .N[ Insbesondere kann der spezifisch für eine Container-Klasse definierte Zuweisungs-Operator spezielle Eigenschaften der jeweiligen Abspeicherungsart berücksichtigen.._[] ] .F[: Im Gegensatz zum generischen Kopieren werden dabei oft [PODs] (plain old data types) als Elementtyp erkannt und dann eine unterschiedliche Spezialisierung verwendet, welche die Operation in ein `std::memmove` oder `std::memcpy` überführt. ] --- template: plain header: #### Einige typische Beispiele für Algorithmen Die folgenden Programmfragmente gehen aus von einem STL-Container ``` std::vector
v; ``` der anschließend mit Datenwerten gefüllt wurde. ##### Zählen der Elemente mit dem Wert 542 ``` auto n = std::count(v.begin(), v.end(), 542); ``` ##### Suchen des ersten Elements mit dem Wert 542 ``` const auto f = std::find(v.begin(), v.end(), 542); if (f != v.end()) { … // (first) matching element located } else { … // NO matching element exists } ``` --- template: plain header: ##### Löschen aller Elemente mit dem Wert 542 ``` const auto end = std::remove(v.begin(), v.end(), 542); ``` Die Variable `end` enthält nun einen Iterator, der das neue (logische) Ende des (von der Anzahl der Elemente gesehen größeren) Containers bezeichnet. ``` // nicht mehr zum Inhalt zu zaehlende Elemente loeschen v.erase(end, v.end()); ``` .N[ Code wie der gerade gezeigte ist vor allem in generischen Templates zweckmäßig, bei denen die eigentliche Container-Klasse – also der exakte Datentyp von `v` – möglichst flexibel bleiben soll. ] Wird ein bestimmter, typischer und auch häufiger Anwendungsfall von solchen Templates deutlich sub-optimal behandelt, kann ggf. eine entsprechende Spezialisierung erfolgen. --- template: plain name: generic_vs_specific header: ##### STL Algorithmen vs. spezifische Member-Funktionen Steht die Klasse des Containers fest, gibt es alternativ zum generischen Algorithmen eventuell auch spezifische Member-Funktionen. Diese sind dann meist einacher und auch effizienter. Beispielsweise muss nach der Anwendung **generischer** löschender Algorithmen – wie zuvor gerade gezeigt – ein Container mit dynamischer Größe in der Regel noch auf den tasächlichen Inhalt reduziert werden. .pull-left[ Unübersichtlich (und in der Regel auch weniger ineffizient): ``` v.erase( std::remove(v.begin(), v.end()), 542); ``` ] .pull-right[ Leichter verständlich und stets effizient ist der folgende Code: ``` v.remove(542); ``` ] In beiden Fällen ist zwar der Container-Typ eingeschränkt, aber es besteht Flexibilität in Bezug auf den *Daten*-Typ der Container-*Elemente*.._[] .F[: Ausgeschlossen ist hier z.B. die Verwendung eines `std::array`, da dieses eine zur Compile-Zeit festgelegte Größe hat, die zur Laufzeit unveränderlich ist. ] --- template: plain name: stl_algorithm_callbacks header: ## Callbacks from Algorithms --------------------------------------------------------------------------------- * [Generelle Möglichkeiten für Callbacks ](#callbacks_general) * [Callback mit Funktor ](#callback_with_functor) * [Callback mit Lambda ](#callback_with_lambda) * [C++14 Erweiterungen für Lambdas ](#cpp14_lambda_extensions) * [Prädikate für Algorithmen (generell) ](#predicates_general) * [Prädikate für Algorithmen (Beispielserie) ](#predicate_examples)) * [Algorithmen vs. spezifische Member-Funktionen ](#generic_vs_specific) --------------------------------------------------------------------------------- --- template: plain name: callbacks_general header: ### Generelle Möglichkeiten für Callbacks Prinzipiell sind Algorithmen zwar Code aus einer Bibliothek, häufig enthalten diese aber "*Callbacks*" an die Applikation. Dafür existieren drei Möglichkeiten: * Klassische (C-) Funktionen und Übergabe als Funktionszeiger: * hierbei wird nur Name der Funktion angegeben; * die anschließenden runden Klammern entfallen. * Objekte mit überladener `operator()` Member-Funktion – sogenannte Funktoren: * oft wird eine Objekt-Instanz direkt bei der Argumentübergabe erzeugt; * in diesem Fall enthalten nachfolgenden runde Klammern * die Argumentliste Konstruktors oder * bleiben leer (= Default Konstruktor) * C++11 Lambdas --- template: plain name: callback_with_functor header: ### Callback mit Funktor Ein typisches Beispiel ist der Algorithmus `std::for_each`, der intern eine Schleife ausführt in der alle Elemente eines Containers dem *Call-Back* als Argument übergeben werden. Zunächst ein Funktor (der alle Argumente einfach nur ausibt): ``` struct PrintWords { // in a struct everything is public by default void operator()(const std::string &e) { cout << ": " << e << "\n"; } }; ``` .N[ Hinter dem **Klassennamen** des Funktors **stehen dann runde oder geschweifte Klammern**, um ein (temporäres) Objekt zu erzeugen. ] ``` std::for_each(v.begin(), v.end(), PrintWords()); // (old) C++ Style ``` ``` std::for_each(v.begin(), v.end(), PrintWords{}); // since C++11 also ``` .F[: Statt eines temporären Objekts kann natürlich auch vorab ein Objekt angelegt und dieses dann (ohne folgende Klammern!) übergeben werden. ] --- template: plain name: callback_with_function header: #### Vergleich mit Funktion Mit einer Funktion sieht das Beispiel so aus:.[] ``` void print_words(const std::string &e) { cout << ": " << e << "\n"; }; ``` .N[ Hier sind **keine** Klammern zu schreiben, da der **Name** der Funktion weitergegeben wird – ihr Aufruf erfolgt erst im Rahmen des Call-Backs. ] ``` std::for_each(v.begin(), v.end(), print_words); ``` .F[: As an advanced feature that should not go completely without noting (though it will not be covered further here) consider an addition to C++11, a new utility type able to wrap any *Callable*, be it functors, functions, or lambdas (of matching signature). While `std::function` may loosen coupling (which is often desirable) also note that it will typically **introduce an extra level of indirection for the at actual call**, leading to less locality in the code (usually **not** desirable). ``` std::function
myCallBack; … // then, at a later point: // ---------------------- more flexibility through reduced coupling myCallBack = print_words; // or: ... = PrintWords(); // = PrintWords{} // = [](const auto &e) { cout << ": " << e << "\n"; } // ----------------------- at the price of an extra indirection std::for_each(v.begin(), v.end(), myCallBack); // (not very visible in the code) ``` ] --- template: plain header: #### Lokale Daten in Funktoren Einer der Vorteile von Funktoren ist, dass sich im Funktor lokale Variable sauber kapseln lassen. Hierzu ein leicht modifiziertes Beispiel, bei dem der Funktor die Argumente durchnummeriert: ``` struct PrintWordsEnumerated { void operator()(const std::string &s) { std::cout << ++n << ": " << s << "\n"; } PrintWordsEnumerated() : n(0) {} private: int n; }; ``` --- template: plain header: #### Parameterübergabe an Funktor Über zusätzliche Member-Daten, die im Konstruktor des Funktors initialisiert werden, lassen sich auch Argumente aus der Aufruf-Umgebung weiterreichen: ``` struct PrintWordsEnumerated { void operator()(const std::string &e) { os << ++n << ": " << e << "\n"; } PrintWordsEnumerated(std::ostream &os_) : n(0), os(os_) {} private: int n; std::ostream &os; }; ``` Diese sind dann bei der Verwendung zu versorgen: ``` std::for_each(v.begin(), v.end(), PrintWordsEnumerated(std::cout)); // (old) C++ style ``` ``` std::for_each(v.begin(), v.end(), PrintWordsEnumerated{std::cout}); // since C++11 also ``` --- template: plain header: #### Parameter aus Aufrufumgebung Die mit der Übergabe von Parametern geschaffene Flexibilität ist spätestens dann wichtig, wenn es sich um Informationen handelt, die in der Aufruf-Umgebung in lokalen Variablen oder Argumenten vorliegen: ``` void foo(std::ostream &output) { … std::for_each(v.begin(), v.end(), PrintWordsEnumerated(output)); … } ``` .N[ Dies ist nur noch mit Funktoren (und Lambdas) sauber abzubilden, mit einer Funktion scheidet diese Technik aus. ] --- template: plain header: #### Datentypen in Funktoren Diese richten sich nach der gewünschten Zugriffsart: |Zugriffsart |Daten-Member |Konstruktor-Argument | |------------------|------------------|------------------------------| |über Kopie |(konstanter) Wert |Wert oder (konstante) Referenz| |direkt, nur lesend|konstante Referenz|(konstante) Referenz | |auch schreibend |Referenz |Referenz | Referenzen für Daten-Member dürfen keinesfalls mit Wertübergabe im Konstruktor kombiniert werden: ``` class SomeFunctor { … T data1; const T &data2; public: … SomeFunctor(const T& d1, T d2) : data1(d1) // OK , data2(d2) // SERIOUS PROBLEM HERE !! {} }; ``` --- template: plain name: callback_with_lambda header: ### Callback mit Lambda Die in C++ neu eingeführte Lambdas haben gegenüber Funktoren den Vorteil, dass der ausgeführte Code direkt als Parameter des aufgerufenen Algorithmus zu sehen ist und nicht an einer mehr oder weniger weit davon entfernten Stelle steht.._[] #### Grundlegendes Beispiel mit Lambda Im einfachsten Fall greift das Lambda nur auf das vom Aufrufer übergebene Argument und evtl. globale Variable bzw. Objekte zu: ``` std::for_each(v.begin(), v.end(), [](const std::string &s) { std::cout << s << '\n'; } ); ``` .F[: Mit modernen IDEs, welche die Implementierung einer Funktion oder Klasse als Pop-Up zeigen, sobald man kurze Zeit den Mauszeiger darüber ruhen lässt, spielt dieser Nachteil aber nur eine geringe Rolle. ] --- template: plain header: #### Lambda mit Capture List Zum Zugriff in den Sichtbarkeitsbereich des umgebenden Blocks muss die *Capture-List* verwendet werden: ``` void foo(std::ostream &output) { … std::for_each(v.begin(), v.end(), [&output](const std::string &s) { output << s << '\n'; } ); ``` Darin werden die übergebenen Bezeichner aufgelistet, ggf. mit vorangestelltem `&`-Zeichen, wenn Referenz-Übergabe erfolgen soll. --- template: plain header: #### Lambda mit privaten Daten Ein Funktor kann problemlos private Daten besitzen, welche ausschließlich dem überladenen Funktionsaufruf zur Verfügung stehen. In C++11 sind die Möglichkeiten zur Kapselung in dieser Hinsicht für ein Lambda etwas eingeschränkt: lokale Daten können nicht wirklich privat sein sondern sind auch in der Aufrufumgebung sichtbar: ``` void foo(std::ostream &output) { … int line_nr = 0; std::for_each(v.begin(), v.end(), [&line_nr, &output](const std::string &s) { output << ++line_nr << s << '\n'; } ); … } ``` Obiges zeichnet zugleich den allgemeinen Weg vor, wie ein Lambda auf seine Aufrufumgebung nicht nur lesend sondern auch modifizierend einwirken kann. --- template: plain name: cpp14_lambda_extensions header: ### C++14 Extensions to Lambdas With C++14 lambdas have been further extended:._[] * Lambdas may use [`auto` as argument type](#cpp14_lambda_auto_arg), thus allowing generic lambdas, similar to functors with a templated `operator()`. * The capture list may define so-called [init-captures](#cpp14_lambda_init), giving the same options as local (independent) data members of a functor, with (possibly context dependant) initialisation. .F[: For the curious: C++14 also fixed a minor oversight in the lambda syntax specification of C++11: While the idea was to allow the lambda argument list to be completely dropped if empty, including its parentheses if empty, that was forgotten in the syntax for `mutable` lambdas. ] --- template: plain name: cpp14_lambda_auto_arg header: #### C++14 `auto`-typed Lambda Arguments Prior to C++14 argument types of lambdas had to be spelled out explicitly, which could sometimes be wordy and inconvenient:._[] ``` std::map
m; … std::map
other; std::copy_if(m.cbegin(), m.cend(), std::inserter(other), [](const std::pair
&e) { return e.second != 0; }); ``` Clearly, in the above scenario `auto`-typed arguments for lambdas offer a big simplification: ``` std::copy_if(m.cbegin(), m.cend(), std::inserter(other), [](const auto &e) { return e.second != 0; }); ``` .F[: The problem could be slightly alleviated if there were a type definition for the map, say `C`, allowing to refer to the element type inside as `C::value_type` (or if `C` were a dependant type as `typename C::value_type`). ] --- template: plain header: #### C++14 Lambda Init-Captures This C++14 extension allows a third form of capture: ``` // assuming local scope here SomeType local; … … [local]( … ) { // capturing by value-copy … // access local copy read-only } … … [local]( … ) mutable { // capturing by value-copy … // access local copy modifiable } … … [&local]( … ) { // capturing by reference … // access and possibly modify local in outer scope } … … [mine = local]( … ) { // init-capture (C++14 only) … // access mine modifiable, initial value from local } … ``` The initialisation of init-captures may also use arbitrary expressions. ``` … [mine = 2*local + 1] ( … ) { … } … … [mine = std::make_shared
(local)] ( … ) { … } … ``` --- template: plain header: #### Extended Type Deduction for C++14 Lambdas With the extensions to lambdas in C++14 also two new contexts for type deduction were introduced: * In case of `auto`-typed lambda arguments the type deduction rules are the same as for template functions (and hence **not** exactly the same as for `auto`-typed variables!) * In case of init-captures the type of the newly introduced identifier is determined is like for `auto`-typed variables. --- template: plain header: #### Init-Captures and Move-Construction Init-captures solve a problem that lay outside the capabilities of lambdas as defined by C++11: * When capturing by value-copy, only the copy-constructor applies. * In an init-capture, if the initialising expression is a temporary, the move construction may take place – given a move constructor exists and the compiler does not choose to prefer [(N)RVO]. Therefore only init-captures allow the following (assuming `local` is a move-only type._[] or it is its last use and copying is expensive): ``` … [mine = std::move(local)] ( … ) { … } … ``` .F[: Like e.g. `std::unique_ptr`, `std::thread`. ] [(N)RVO]: http://en.wikipedia.org/wiki/Return_value_optimization [ugly work-around]: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3610.html --- template: plain header: #### C++14 Init-Capture Pitfalls One possible pitfall with init-captures is illustrated below. .W[ Classic (C-style) arrays are treated as value objects captured by value-copy but decay to pointers (to the first element) in init-captures.._[] ] But also be sure to understand there are scenarios in which you explicitly **would want to avoid copying** e.g. to improve performance or reduce memory footprint! .pull-left[ Secure capturing of value-copies: ``` auto foo() { int data[] = {2, 3, 5, 7}; return [data]( … ) { … // lambda-body }; } ``` ] .pull-right[ Reference to invalidated stack: ``` auto foo() { int data[] = {2, 3, 5, 7}; return [d = data]( … ) { … // lambda-body }; } ``` ] .F[: This might be used as an argument to prefer `std::array` over classic arrays, as then in both cases the content would be copied. ] --- template: plain name: predicates_general header: ### Prädikate für Algorithmen (generell) Viele STL-Algorithmen haben eine Variante, in der man ein Auswahlkriterium (Prädikat) flexibel angeben kann. Es handelt sich dabei typischerweise um die Algorithmus-Variante, die mit `_if` endet. Als Beispiel zur Verdeutlichung des Prinzips kann wieder die Implementierung eines Algorithmus zum Kopieren von einem Container in einen anderen dienen, diesmal beschränkt auf ausgewählte Elemente:._[] ``` template
T2 my_copy_if(T1 from, T1 upto, T2 dest, T3 pred) { while (from != upto) { const auto tmp = *from++; if (pred(tmp)) *dest++ = tmp; } return dest; } ``` .F[: In die STL wurde der Algorithmus `std::copy_if` erst mit C++11 aufgenommen. Allerdings erfüllt das seit C++98 vorhandene `std::remove_copy_if` denselben Zweck, wenn man das Prädikat invertiert angibt. ] --- template: plain header: #### Möglichkeiten zur Übergabe von Prädikaten Da es sich um eine Template handelt, gilt für das Prädikat `pred` lediglich, dass als aktuelles Argument etwas "Aufrufbares" (callable) anzugeben ist. Damit kommen * [Funktionszeiger](#predicate_fptr), * [Funktoren](#predicate_functor) und * [C++11-Lambdas](#predicate_lambda) in Frage, sofern diese als Rückgabewert ein `bool` liefern.._[] .F[: Oder präziser: einen Typ, der ggf. in `bool` umgewandelt wird. ] Im folgenden werden in einem Container mit Ganzzahlen alle Elemente mit einem Wert kleiner als 42 gezählt. --- template: plain name: predicate_fptr header: #### Prädikat mit Funktionszeiger übergeben Zunächst muss die Funktion definiert werden: ``` bool lt42(int n) { return n < 42; } ``` Dann kann sie als Prädikat dienen: ``` … std::count_if( … , … , lt42); ``` .W[ Viele Compiler generieren hier grundsätzlich einen Funktionsaufruf, womit diese Variante zur Laufzeit recht ineffizient sein kann.._[] ] .F[: Die GNU-Compiler erzeugen seit einigen Jahren zumindest auf den höheren Optimierungsstufen aber deutlich besseren Code, indem sie bei sichtbarer Funktionsdefinition in Fällen wie dem Obigen eine Inline-Umsetzung vornehmen, selbst wenn die Funktion `lt42` nicht mit `inline` markiert wurde. ] --- template: plain name: predicate_functor header: #### Prädikat mit Funktor übergeben Zunächst muss die Funktor-Klasse definiert werden: ``` struct Lt42 { bool operator()(int n) const { return n < 42; } }; ``` Dann wird sie als Prädikat zu einem temporären Objekt instanziiert: ``` … std::count_if( … , … , Lt42()); ``` .N[ Ist der Funktionsaufruf-Operator explizit oder wie oben implizit `inline`,._[] wird der erzeugte Code schneller (und oft sogar kleiner) sein als bei Übergabe eines Prädikats mittels Funktionszeiger. ] .F[: In Bezu auf den GCC (g++) sei aber daran erinnert, dass bei ausgeschalteter Optimierung (`-O0`) grundsätzlich *keine* Funktion als `inline`-Funktion umgesetzt wird. ] --- template: plain name: predicate_lambda header: #### Prädikat mit C++11-Lambda übergeben Hier ist das Prädikat unmittelbar bei der Übergabe zu sehen: ``` … std::count_if( … , … , [](int n) { return n < 42; }); ``` #### Alternative mit Standard-Bibliotheksfunktion Diese mit C++98 eingeführte Möglichkeit wirkt sehr unleserlich und wird evtl. auch aus diesem Grund nur selten benutzt: ``` … std::count_if( … , … , std::bind2nd(std::less
(), 42)); ``` --- template: plain name: predicate_examples header: ### Prädikate für Algorithmen (Beispielserie) Abschließend eine weitere Beispielserie zum Vergleich der verschiedenen Möglichkeiten, Algorithmen mit Prädikaten als Bedingungstests zu versorgen: In der ersten Gruppe geschieht dies ohne jegliche Flexibilität – alles ist für den jeweiligen Einzelfall "hart kodiert". * [Funktionszeiger ](#predicate_specific_fptr) * [Funktor ](#predicate_specific_functor) * [Lambda ](#predicate_specific_lambda) In der zweiten Gruppe (für welche Funktionszeiger bereits nicht mehr mächtig genug sind), besteht mehr Flexibilität – wobei teilweise ähnliche Techniken aus einem unterschiedlichen Grund zur Anwendung kommen. * [Parametrisierter Funktor ](#predicate_parametrized_functor) * [Zugriff auf lokale Daten mit Funktor ](#predicate_capturing_functor) * [Zugriff auf lokale Daten mit Lambda ](#predicate_capturing_lambda) --- template: plain name: predicate_specific_fptr header: #### Prädikat mit spezifischem Funktionszeiger Dies ist die aus der C-Programmierung bekannte Technik. Das Beispiel gibt alle Elemente mit einem Wert ungleich 524 aus: ``` bool notEq524(int n) { return n != 524; } void foo(const std::vector
&v) { … std::copy_if(v.begin(), v.end(), std::ostream_iterator
(std::cout, " "), notEq524 ); … } ``` --- template: plain name: predicate_specific_functor header: #### Prädikat mit spezifischem Funktor Dies ist eine für C++-typische Technik. Auch dieses Beispiel gibt alle Elemente mit einem Wert ungleich 524 aus: ``` struct NotEq524 { bool operator()(int n) const { return n != 524; } }; void foo(const std::vector
&v) { … copy_if(v.begin(), v.end(), std::ostream_iterator
(std::cout, " "), NotEq524() ); … } ``` --- template: plain name: predicate_specific_lambda header: #### Prädikat mit spezifischem Lambda Und ein drittes Mal mit einem (C++11) Lambda. Wiederum werden alle Elemente mit einem Wert ungleich 524 ausgegeben: ``` void foo(const std::vector &v) { … std::copy_if(v.begin(), v.end(), std::ostream_iterator
(std::cout, " "), [](int n) { return n != 524; } ); … } ``` --- template: plain name: predicate_parametrized_functor header: #### Prädikat mit allgemeiner verwendbarem Funktor Der im folgenden verwendete Funktor kann in allen Vergleichen benutzt werden, welche auf die Prüfung hinauslaufen, ob eine Ganzzahl ungleich zu einem gegebenen Wert ist: ``` class NotEq { const int cmp; public: NotEq(int c) : cmp(c) {} bool operator()(int n) const { return n != cmp; } }; … void foo(const std::vector &v) { … std::copy_if(v.begin(), v.end(), std::ostream_iterator
(std::cout, " "), NotEq(524) // classic C++ // or: NotEq{524} // since C++11 ); … } ``` --- template: plain name: predicate_capturing_functor header: #### Prädikat mit Funktor und Zugriff auf lokalen Kontext Um auf lokale Variablen oder Parameter._[] einer aufrufenden Funktion zugreifen zu können, muss ein Funktor entsprechende Daten-Member besitzen und sein Konstruktor muss diese initialisieren: ``` void foo(const std::vector &v, int hide) { … std::copy_if(v.begin(), v.end(), std::ostream_iterator
(cout, " "), NotEq(hide) // classic C++ // or: NotEq{hide} // since C++11 ); … } ``` .F[: Die Parameter einer Funktion entsprechen nahezu ihren lokalen Variablen. Es kommt lediglich die (garantierte) Initialisierung mit vom Aufrufer anzugebenden Werten hinzu. ] --- template: plain name: predicate_capturing_lambda header: #### Prädikat mit Lambda und Zugriff auf lokalen Kontext Um auf lokale Variablen oder Parameter._[] einer aufrufenden Funktion zugreifen zu können, muss ein Lambda die Capture-List verwenden: ``` void foo(const std::vector &v, int hide) { … std::copy_if(v.begin(), v.end(), std::ostream_iterator
(std::cout, " "), [hide](int n) { return n != hide; } ); … } ``` .N[ Lambdas in Member-Funktionen einer Klasse können hier auch `this` angeben. Damit besteht innerhalb des Lambdas Zugriff auf alle Member (Daten und Funktionen) desjenigen Objekts, für welches die das Lambda enthaltende Member-Funktion ausgeführt wird. ] .F[: Die Parameter einer Funktion entsprechen nahezu ihren lokalen Variablen. Es kommt lediglich die (garantierte) Initialisierung mit vom Aufrufer anzugebenden Werten hinzu. ] --- template: plain name: summary header: ## Summary This part * first covered the various [Iterator categories](#stl_iterator_categories), * then compared [Call-Backs from Standard Algorithms](#stl_algorithm_interface) in the form * [Functors](#callback_with_lambda) (= classes with overloaded `operator()`), * [Functions](#callback_with_function) (= classic C function pointers), and * [Lambdas](#callback_with_lambda) (= function literals, as introduced with C++11) ------------------------------------------------------------------------------- What to do next? * [Go back to the Agenda](00_topics.html#agenda) and chose a specific part … * … or [continue with next part](04_day2.html), * … or with the next (and last) page of this part. --- template: plain name: stl_algorithm_tour header: ## A Standard Algorithms Tour The tour will be presented "life" – feel free to request stops and/or deeper coverage at points of specific interest, simply by asking questions. [Generic Numeric Operations]: http://en.cppreference.com/w/cpp/numeric#Generic_numeric_operations .I[ Please gather here for coach to show you around :-) … at http://en.cppreference.com/w/cpp/algorithm ] In case you are ahead of time and have to wait for the tour to start, these are the major pre-planned stops (= STL algorithms grouped by purpose): * [Non-Modifying](http://en.cppreference.com/w/cpp/algorithm#Non-modifying_sequence_operations) and [Modifying Sequence Operations](http://en.cppreference.com/w/cpp/algorithm#Modifying_sequence_operations) * [Partitioning](http://en.cppreference.com/w/cpp/algorithm#Partioning_operations) and [Sorting Operations](http://en.cppreference.com/w/cpp/algorithm#Sorting_operations) * [Binary Search](http://en.cppreference.com/w/cpp/algorithm#Binary_search_operations_.28on_sorted_ranges.29) and [Set Operations](http://en.cppreference.com/w/cpp/algorithm#Set_operations_.28on_sorted_ranges.29) on Sorted Ranges * [Heap](http://en.cppreference.com/w/cpp/algorithm#Heap_operations) and [Minimum/Maximum Operations](http://en.cppreference.com/w/cpp/algorithm#Minimum.2Fmaximum_operations) * [Numeric Operations](http://en.cppreference.com/w/cpp/algorithm#Numeric_operations) * [Operations on Uninitialized Memory](http://en.cppreference.com/w/cpp/algorithm#Operations_on_uninitialized_memory) * [Classic C Library](http://en.cppreference.com/w/cpp/algorithm#C_library) .F[: For more exploration and gathering practical experience view the [Micro Projects](x2_day2.html#stl_algorithm_micro_projects) on STL algorithms. ]