namespace cpp

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


kennen:include:algorithm

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

kennen:include:algorithm [2017-02-19 13:21] (aktuell)
Zeile 1: Zeile 1:
 +====== <​algorithm>​ ======
 +Typ-parametrisierte [[..:​stl#​Algorithmen]]:​
 +| [[#​nichtmodifizierende Algorithmen]]| [[#​Prädikatenlogik]],​ [[#​Suchen]], ​ [[#​Vergleichen]]|
 +| [[#​modifizierende Algorithmen]]| [[#​Tauschen]],​ [[#​Kopieren]],​ [[#​Verschieben]],​ [[#​Füllen]],​ [[#​Ersetzen]],​ [[#​Entfernen]],​ [[#​Umwandeln]]|
 +| [[#​mutierende Algorithmen]]| [[#​Umkehren]],​ [[#​Rotieren]],​ [[#​Durcheinanderbringen]],​ [[#​Sortieren]],​ [[#​Aufteilen]],​ [[#​Mischen]],​ [[#​Mengenoperationen]],​ [[#​Heapoperationen]]|
 +
 +Die Iterator-[[..:​stl#​Kategorien]] ''​Out'',​ ''​In'',​ ''​For'',​ ''​Bi''​ und ''​Ran''​ zeigen an, welche Operationen auf den Bereichen erforderlich sind. 
 +Die Einleitung ''​template <​...>''​ wurde der Übersichtlichkeit halber bei allen Schablonen weggelassen.
 +===== Nicht-modifizierende Algorithmen =====
 +==== Ausführen und Zählen ====
 +<code cpp>
 +Function for_each (In first, In last, Function f) 
 +</​code>​
 +[[..:​lib:​for_each|Beschreibung]]:​
 + ​Wendet ''​f''​ auf jedes Element ''​x''​ des Bereiches [first,​last) an.
 + ​Obwohl der Algorithmus die Elemente nicht verändert, ist es dem Funktions(objekt)aufruf ''​f(x)''​ ausdrücklich erlaubt.
 +
 +<code cpp>
 +difference_type count (In first, In last, T wert) 
 +</​code>​
 +[[..:​lib:​count|Beschreibung]]:​
 + ​Liefert die Anzahl der Elemente des Bereiches [first,​last) mit dem wert. 
 +
 +<code cpp>
 +difference_type count_if (In first, In last, Pred pred) 
 +</​code>​
 +[[..:​lib:​count_if|Beschreibung]]:​
 + ​Liefert die Anzahl der Elemente ''​e''​ des Bereiches [first,​last),​ auf die das Prädikat ''​pred(e)''​ zutrifft.
 +
 +==== Prädikatenlogik ====
 +<code cpp>
 +bool all_of (In first, In last, Pred pred) 
 +</​code>​
 +[[..:​lib:​all_of|Beschreibung]]:​
 + ​Prüft,​ ob alle Elemente ''​e''​ des Bereiches [first,​last) das Prädikat ''​pred(e)''​ erfüllen.
 + Bei leerem Bereich liefert die Funktion ''​true''​. ​
 +
 +<code cpp>
 +bool any_of (In first, In last, Pred pred) 
 +</​code>​
 +[[..:​lib:​any_of|Beschreibung]]:​
 + ​Prüft,​ ob irgendein Element ''​e''​ des Bereiches [first,​last) das Prädikat ''​pred(e)''​ erfüllt.
 + Bei leerem Bereich liefert die Funktion ''​false''​. ​
 +
 +<code cpp>
 +bool none_of (In first, In last, Pred pred) 
 +</​code>​
 +[[..:​lib:​none_of|Beschreibung]]:​
 + ​Prüft,​ ob kein Element ''​e''​ des Bereiches [first,​last) das Prädikat ''​pred(e)''​ erfüllt.
 + Bei leerem Bereich liefert die Funktion ''​true''​. ​
 +
 +==== Suchen ====
 +<code cpp>
 +In find (In first, In last, T wert) 
 +</​code>​
 +[[..:​lib:​find|Beschreibung]]:​
 + ​Liefert einen Iterator auf das erste Element des Bereiches [first,​last) mit dem ''​wert''​. ​
 +
 +<code cpp>
 +In find_if (In first, In last, Pred pred) 
 +</​code>​
 +[[..:​lib:​find_if|Beschreibung]]:​
 + ​Liefert einen Iterator ''​i''​ auf das erste Element des Bereiches [first,​last), ​
 +auf den das Prädikat ''​pred(*i)''​ zutrifft.
 +
 +<code cpp>
 +In find_if_not (In first, In last, Pred pred) 
 +</​code>​
 +[[..:​lib:​find_if_not|Beschreibung]]:​
 + ​Liefert einen Iterator i auf das erste Element des Bereiches [first,​last), ​
 +auf den das Prädikat ''​pred(*i)''​ nicht zutrifft.
 +
 +<code cpp>
 +For find_first_of (For first, For last, For2 first2, For2 last2) ​
 +For find_first_of (For first, For last, For2 first2, For2 last2, Binary pred) 
 +</​code>​
 +[[..:​lib:​find_first_of|Beschreibung]]:​
 + ​Liefert einen Iterator auf das erste Element ''​x''​ des Bereiches [first,​last), ​
 + das mit einem Wert des Bereiches [first2,​last2) übereinstimmt bzw. 
 + für welches ''​pred(x,​ y)''​ mit einem Element ''​y''​ aus [first2,​last2) zutrifft.
 +
 +<code cpp>
 +For search (For first, For last, For2 first2, For2 last2) ​
 +For search (For first, For last, For2 first2, For2 last2, Binary pred) 
 +</​code>​
 +[[..:​lib:​search|Beschreibung]]:​
 + Sucht den Anfang eines Teilbereiches aus [first,​last), ​
 + der mit [first2,​last2) übereinstimmt bzw. das Prädikat ''​pred(x,​y)''​ erfüllt.
 +
 +<code cpp>
 +For search_n (For first, For last, Size n, T wert) 
 +For search_n (For first, For last, Size n, T wert, Binary pred) 
 +</​code>​
 +[[..:​lib:​search_n|Beschreibung]]:​
 + Sucht den Anfang eines Teilbereiches aus [first,​last), ​
 + der ''​n''​ gleiche Werte hat bzw. auf den ''​n''​ mal ''​pred(x,​wert)''​ zutrifft.
 +
 +<code cpp>
 +For find_end (For first, For last, For2 first2, For2 last2) ​
 +For find_end (For first, For last, For2 first2, For2 last2, Binary pred) 
 +</​code>​
 +[[..:​lib:​find_end|Beschreibung]]:​
 + Sucht den letzte Element eines Teilbereiches aus [first,​last), ​
 + der mit [first2,​last2) übereinstimmt bzw. 
 + für welches ''​pred(x,​ y)''​ mit einem Element ''​y''​ aus [first2,​last2) zutrifft.
 +
 +<code cpp>
 +For adjacent_find (For first, For last) 
 +For adjacent_find (For first, For last, Binary pred) 
 +</​code>​
 +[[..:​lib:​adjacent_find|Beschreibung]]:​
 + Sucht das erste Element des Bereiches [first,​last), ​
 + das mit seinem Nachfolger übereinstimmt bzw. 
 + mit seinem Nachfolger das Prädikat ''​pred(x,​nachfolger)''​ erfüllt.
 +
 +==== Binärsuche ====
 +<code cpp>
 +bool binary_search (For first, For last, T wert) 
 +bool binary_search (For first, For last, T wert, Comp comp) 
 +</​code>​
 +[[..:​lib:​binary_search|Beschreibung]]:​
 + Sucht ''​wert''​ in der aufsteigend geordneten Folge von Elementen [first,​last).
 +
 +<code cpp>
 +For lower_bound (For first, For last, T wert) 
 +For lower_bound (For first, For last, T wert, Comp comp) 
 +</​code>​
 +[[..:​lib:​lower_bound|Beschreibung]]:​
 + ​Bestimmt die erste Position, an der ''​wert''​ eingefügt werden kann, 
 + ohne die aufsteigende Ordnung der Folge [first,​last) zu zerstören.
 +
 +<code cpp>
 +For upper_bound (For first, For last, T wert) 
 +For upper_bound (For first, For last, T wert, Comp comp) 
 +</​code>​
 +[[..:​lib:​upper_bound|Beschreibung]]:​
 + ​Bestimmt die letzte Position, an der ''​wert''​ eingefügt werden kann, 
 + ohne die aufsteigende Ordnung der Folge [first,​last) zu zerstören.
 +
 +<code cpp>
 +std::​pair<​For,​ For> equal_range (For first, For last, T wert) 
 +std::​pair<​For,​ For> equal_range (For first, For last, T wert, Comp comp) 
 +</​code>​
 +[[..:​lib:​equal_range|Beschreibung]]:​
 + ​Bestimmt den Teilbereich der aufsteigend geordneten Folge [first,​last), ​
 + ​dessen Elemente mit ''​wert''​ übereinstimmen. ​
 +
 +==== Minimum und Maximum ====
 +<code cpp>
 +const T& min (const T& a, const T& b) 
 +const T& min (const T& a, const T& b, Comp comp)
 +T min(std::​initializer_list<​T>​ values)  ​
 +T min(std::​initializer_list<​T>​ values, Comp comp)  ​
 +</​code>​
 +[[..:​lib:​min|Beschreibung]]:​
 + ​Liefert den kleineren Wert.
 +
 +<code cpp>
 +const T& max (const T& a, const T& b) 
 +const T& max (const T& a, const T& b, Comp comp) 
 +T max(std::​initializer_list<​T>​ values)  ​
 +T max(std::​initializer_list<​T>​ values, Comp comp)  ​
 +</​code>​
 +[[..:​lib:​max|Beschreibung]]:​
 + ​Liefert den größeren Wert.
 +
 +<code cpp>
 +std::​pair<​T,​T>​ minmax (const T& a, const T& b) 
 +std::​pair<​T,​T>​ minmax (const T& a, const T& b, Comp comp)
 +std::​pair<​T,​T>​ minmax(std::​initializer_list<​T>​ values)  ​
 +std::​pair<​T,​T>​ minmax(std::​initializer_list<​T>​ values, Comp comp)  ​
 +</​code>​
 +[[..:​lib:​minmax|Beschreibung]]:​
 + ​Liefert kleinsten und größten Wert als geordnetes Paar (first %%<=%% second).
 +
 +<code cpp>
 +For min_element (For first, For last) 
 +For min_element (For first, For last, Comp comp) 
 +</​code>​
 +[[..:​lib:​min_element|Beschreibung]]:​
 + ​Liefert einen Iterator auf das kleinste Element des Bereiches [first,​last).
 +
 +<code cpp>
 +For max_element (For first, For last) 
 +For max_element (For first, For last, Comp comp) 
 +</​code>​
 +[[..:​lib:​max_element|Beschreibung]]:​
 + ​Liefert einen Iterator auf das größte Element des Bereiches [first,​last).
 +
 +<code cpp>
 +std::​pair<​For,​For>​ minmax_element (For first, For last) 
 +std::​pair<​For,​For>​ minmax_element (For first, For last, Comp comp) 
 +</​code>​
 +[[..:​lib:​minmax_element|Beschreibung]]:​
 + ​Liefert den weitesten Teilbereich [min,max).
 +
 +<code cpp>
 +const T& clamp (const T& value, const T& low, const T& high)              // C++17
 +const T& clamp (const T& value, const T& low, const T& high, Comp comp) 
 +</​code>​
 +[[..:​lib:​clamp|Beschreibung]]:​
 + ​Begrenzt Wert auf das Intervall [low,high].
 +
 +
 +
 +
 +==== Vergleichen ====
 +<code cpp>
 +bool equal (For first, For last, For2 first2) ​
 +bool equal (For first, For last, For2 first2, Binary pred) 
 +bool equal (For first, For last, For2 first2, For2 last2) ​
 +bool equal (For first, For last, For2 first2, For2 last2, Binary pred) 
 +</​code>​
 +[[..:​lib:​equal|Beschreibung]]:​
 + Ist wahr, wenn die Bereiche [first,​last) und [first2,​...) elementweise übereinstimmen bzw. 
 + ​paarweise das Prädikat ''​pred(x,​y)''​ erfüllen.
 +
 +<code cpp>
 +bool lexicographical_compare (In first, In last, In2 first2, In2 last2) ​
 +bool lexicographical_compare (In first, In last, In2 first2, In2 last2, ​
 +                              Comp comp) 
 +</​code>​
 +[[..:​lib:​lexicographical_compare|Beschreibung]]:​
 + Ist wahr, wenn der Bereich [first,​last) lexikographisch vor [first2,​last2) einzuordnen ist.
 +
 +<code cpp>
 +std::​pair<​In,​ In2> mismatch (In first, In last, In2 first2) ​
 +std::​pair<​In,​ In2> mismatch (In first, In last, In2 first2, Binary pred) 
 +std::​pair<​In,​ In2> mismatch (In first, In last, In2 first2, In2 last2) ​
 +std::​pair<​In,​ In2> mismatch (In first, In last, In2 first2, In2 last2, Binary pred) 
 +</​code>​
 +[[..:​lib:​mismatch|Beschreibung]]:​
 + ​Liefert ein Paar von Iteratoren, ​
 + ab denen die Bereiche [first,​last) und [first2,​...) nicht mehr übereinstimmen bzw. 
 + das Prädikat ''​pred(x,​y)''​ nicht mehr erfüllen.
 +
 +===== Modifizierende Algorithmen =====
 +==== Tauschen ====
 +<code cpp>
 +void swap (T& a, T& b) 
 +</​code>​
 +[[..:​lib:​swap|Beschreibung]]:​
 + ​Vertauscht die Werte von ''​a''​ und ''​b''​.
 +
 +<code cpp>
 +void iter_swap (Iter a, Iter b) 
 +</​code>​
 +[[..:​lib:​iter_swap|Beschreibung]]:​
 + ​Vertauscht die Werte der Objekte, auf die die Iteratoren von ''​a''​ und ''​b''​ verweisen.
 +
 +<code cpp>
 +For2 swap_ranges (For first, For last, For2 first) ​
 +</​code>​
 +[[..:​lib:​swap_ranges|Beschreibung]]:​
 + ​Tauscht die Werte in den Bereichen [first,​last) und [first2,​...) aus. 
 +
 +==== Kopieren ====
 +<code cpp>
 +Out copy (In first, In last, Out result) ​
 +</​code>​
 +[[..:​lib:​copy|Beschreibung]]:​
 + ​Kopiert die Werte des Bereiches [first,​last) nach [result,​...).
 +
 +<code cpp>
 +Out copy_if (In first, In last, Out result, Pred pred) 
 +</​code>​
 +[[..:​lib:​copy_if|Beschreibung]]:​
 + ​Kopiert die Werte ''​e''​ des Bereiches [first,​last) nach [result,​...),​ die das Prädikat ''​pred(e)''​ erfüllen.
 +
 +<code cpp>
 +Out copy_n (In first, Size n, Out result) ​
 +</​code>​
 +[[..:​lib:​copy_n|Beschreibung]]:​
 + ​Kopiert ''​n''​ Werte des Bereiches [first,​first+n) nach [result,​...).
 +
 +<code cpp>
 +Bi2 copy_backward (Bi first, Bi last, Bi2 result) ​
 +</​code>​
 +[[..:​lib:​copy_backward|Beschreibung]]:​
 + ​Kopiert die Werte des Bereiches [first,​last) am Ende beginnend nach [result - (last-first),​result).
 +
 +==== Verschieben ====
 +<code cpp>
 +Out move (In first, In last, Out result) ​
 +</​code>​
 +[[..:​lib:​move|Beschreibung]]:​
 + ​Verschiebt die Elemente des Bereiches [first,​last) nach [result,​...).
 +
 +<code cpp>
 +Bi2 move_backward (Bi first, Bi last, Bi2 result) ​
 +</​code>​
 +[[..:​lib:​move_backward|Beschreibung]]:​
 + ​Verschiebt die Elemente des Bereiches [first,​last) am Ende beginnend nach [result - (last-first),​result).
 +
 +
 +==== Füllen ====
 +<code cpp>
 +void fill (Out first, Out last, T wert) 
 +</​code>​
 +[[..:​lib:​fill|Beschreibung]]:​
 + ​Füllt den Bereich [first,​last) mit dem ''​wert''​.
 +
 +<code cpp>
 +void fill_n (Out first, Size n, T wert) 
 +</​code>​
 +[[..:​lib:​fill_n|Beschreibung]]:​
 + ​Füllt in den bei ''​first''​ beginnenden Bereich ''​n''​ mal den ''​wert''​.
 +
 +<code cpp>
 +void generate (Out first, Out last, Func generator_obj) ​
 +</​code>​
 +[[..:​lib:​generate|Beschreibung]]:​
 + ​Füllt den Bereich [first,​last) mit der durch ''​generator_obj''​ erzeugten Folge von Werten.
 +
 +<code cpp>
 +void generate_n (Out first, Size n, Func generator_obj) ​
 +</​code>​
 +[[..:​lib:​generate_n|Beschreibung]]:​
 + ​Füllt in den bei ''​first''​ beginnenden Bereich ''​n''​ durch ''​generator_obj''​ erzeugte Werte.
 +
 +==== Ersetzen ====
 +<code cpp>
 +void replace (For first, For last, T alterwert, T neuerwert) ​
 +</​code>​
 +[[..:​lib:​replace|Beschreibung]]:​
 + ​Ersetzt im Bereich [first,​last) ''​alterwert''​ durch ''​neuerwert''​.
 +
 +<code cpp>
 +void replace_if (For first, For last, Pred pred, T neuerwert) ​
 +</​code>​
 +[[..:​lib:​replace_if|Beschreibung]]:​
 + ​Ersetzt im Bereich [first,​last) all jene Elemente, auf die ''​pred(x)''​ zutrifft, durch ''​neuerwert''​.
 +
 +<code cpp>
 +Out replace_copy (In first, In last, Out result, T alterwert, T neuerwert) ​
 +</​code>​
 +[[..:​lib:​replace_copy|Beschreibung]]:​
 + ​Kopiert den Bereich [first,​last) nach [result,​...) und ersetzt dabei ''​alterwert''​ durch ''​neuerwert''​.
 +
 +<code cpp>
 +Out replace_copy_if (In first, In last, Out result, Pre pred, T neuerwert) ​
 +</​code>​
 +[[..:​lib:​replace_copy_if|Beschreibung]]:​
 + ​Kopiert den Bereich [first,​last) nach [result,​...) und ersetzt dabei all jene Elemente, ​
 + auf die ''​pred(x)''​ zutrifft, durch ''​neuerwert''​.
 +
 +==== Entfernen ====
 +<code cpp>
 +For remove (For first, For last, T wert) 
 +</​code>​
 +[[..:​lib:​remove|Beschreibung]]:​
 + ​Entfernt im Bereich [first,​last) alle Elemente mit dem angegebenen ''​wert''​.
 +
 +<code cpp>
 +For remove_if (For first, For last, Pred pred) 
 +</​code>​
 +[[..:​lib:​remove_if|Beschreibung]]:​
 + ​Entfernt im Bereich [first,​last) alle Elemente, auf die ''​pred(x)''​ zutrifft.
 +
 +<code cpp>
 +Out remove_copy (In first, In last, Out result, T wert) 
 +Out remove_copy_if (In first, In last, Out result, Pred pred) 
 +</​code>​
 +[[..:​lib:​remove_copy|Beschreibung]]:​
 + ​Kopiert den Bereich [first,​last) nach [result,​...) ​
 + und entfernt dabei alle Elemente mit dem angegebenen ''​wert''​ bzw. 
 + auf die ''​pred(x)''​ zutrifft.
 +
 +<code cpp>
 +For unique (For first, For last) 
 +For unique (For first, For last, Pred pred) 
 +</​code>​
 +[[..:​lib:​unique|Beschreibung]]:​
 + ​Entfernt alle Elemente aus dem Bereich [first,​last), ​
 + die mit ihren Vorgänger übereinstimmen bzw. auf die ''​pred(vorgaenger,​x)''​ zutrifft.
 +
 +<code cpp>
 +Out unique_copy (In first, In last, Out result) ​
 +Out unique_copy (In first, In last, Out result, Binary pred) 
 +</​code>​
 +[[..:​lib:​unique_copy|Beschreibung]]:​
 + ​Kopiert den Bereich [first,​last) nach [result,​...) ​
 + und entfernt alle Elemente aus dem Bereich [first,​last), ​
 + die mit ihren Vorgänger übereinstimmen bzw. auf die ''​pred(vorgaenger,​x)''​ zutrifft.
 +
 +==== Umwandeln ====
 +<code cpp>
 +Out transform (In first, In last, Out result, Func func) 
 +Out transform (In first, In last, In first2, Out result, Binary func) 
 +</​code>​
 +[[..:​lib:​transform|Beschreibung]]:​
 + ​Errechnet aus den Elementen des Bereiches [first,​last) ​
 + eine Folge von Werten ''​func(x)''​ bzw. 
 + ''​func(x,​ y)''​ und legt diese im Bereich [result,​...) ab. 
 +
 +===== Mutierende Algorithmen =====
 +==== Umkehren ====
 +<code cpp>
 +void reverse (Bi first, Bi last) 
 +</​code>​
 +[[..:​lib:​reverse|Beschreibung]]:​
 + Kehrt die Reihenfolge des Elemente im Bereich [first,​last) um.
 +
 +<code cpp>
 +Out reverse_copy (Bi first, Bi last, Out result) ​
 +</​code>​
 +[[..:​lib:​reverse_copy|Beschreibung]]:​
 + ​Kopiert den Bereich [first,​last) in umgekehrter Reihenfolge nach [result,​...).
 +
 +==== Rotieren ====
 +<code cpp>
 +For rotate (For first, For middle, For last) 
 +</​code>​
 +[[..:​lib:​rotate|Beschreibung]]:​
 + ​Vertauscht die Bereiche [first,​middle) und [middle,​last). ​
 +
 +<code cpp>
 +Out rotate_copy (For first, For middle, For last, Out result) ​
 +</​code>​
 +[[..:​lib:​rotate_copy|Beschreibung]]:​
 + ​Kopiert die Bereiche [middle,​last) und [first,​middle) in dieser Reihenfolge nach [result,​...).
 +
 +==== Durcheinanderbringen ====
 +<code cpp>
 +void shuffle (Ran first, Ran last, UniformRandomGenerator zufall) ​ // C++11
 +</​code>​
 +[[..:​lib:​shuffle|Beschreibung]]:​
 + ​Ordnet den Bereich [first,​last) zufällig um. 
 +
 +<code cpp>
 +Out sample (In first, In last, Out first2, N n, UniformRandomGenerator zufall) ​ // C++17
 +</​code>​
 +[[..:​lib:​sample|Beschreibung]]:​
 + ​Liefert n Werte aus dem Bereich [first,​last) in zufälliger Folge. ​
 +
 +Die folgenden Funktionen werden mit C++17 entfernt:
 +<code cpp>
 +void random_shuffle (Ran first, Ran last)              // bis C++14 
 +void random_shuffle (Ran first, Ran last, Func zufall) ​
 +</​code>​
 +[[..:​lib:​random_shuffle|Beschreibung]]:​
 + ​Ordnet den Bereich [first,​last) zufällig um. 
 + Der Aufruf zufall(n) sollte Zahlen im Bereich [0,n) liefern.
 +
 +
 +==== Systematisches Umordnen ====
 +<code cpp>
 +bool is_permutation (For first, For last, For2 first2) ​
 +bool is_permutation (For first, For last, For2 first2, Comp comp) 
 +bool is_permutation (For first, For last, For2 first2, For2 last2) ​
 +bool is_permutation (For first, For last, For2 first2, For2 last2, Comp comp) 
 +</​code>​
 +[[..:​lib:​is_permutation|Beschreibung]]:​
 + ​Prüft,​ ob [first2,​...) eine Permutation des Bereiches [first,​last) darstellt.
 +
 +<code cpp>
 +bool next_permutation (Bi first, Bi last) 
 +bool next_permutation (Bi first, Bi last, Comp comp) 
 +</​code>​
 +[[..:​lib:​next_permutation|Beschreibung]]:​
 + ​Erzeugt die nächste Permutation des Bereiches [first,​last).
 +
 +<code cpp>
 +bool prev_permutation (Bi first, Bi last) 
 +bool prev_permutation (Bi first, Bi last, Comp comp) 
 +</​code>​
 +[[..:​lib:​prev_permutation|Beschreibung]]:​
 + ​Erzeugt die vorhergehende Permutation des Bereiches [first,​last).
 +
 +===== Sortieren =====
 +==== Vollständiges Sortieren ====
 +<code cpp>
 +bool is_sorted (For first, For last) 
 +bool is_sorted (For first, For last, Comp comp) 
 +</​code>​
 +[[..:​lib:​is_sorted|Beschreibung]]:​
 + ​Prüft,​ ob der Bereich [first,​last) in aufsteigender Folge sortiert ist.
 +
 +<code cpp>
 +void sort (Ran first, Ran last) 
 +void sort (Ran first, Ran last, Comp comp) 
 +</​code>​
 +[[..:​lib:​sort|Beschreibung]]:​
 + ​Sortiert den Bereich [first,​last) in aufsteigender Folge.
 +
 +<code cpp>
 +void stable_sort (Ran first, Ran last) 
 +void stable_sort (Ran first, Ran last, Comp comp) 
 +</​code>​
 +[[..:​lib:​stable_sort|Beschreibung]]:​
 + ​Sortiert den Bereich [first,​last) in aufsteigender Folge.
 + Die relative Anordnung wertgleicher Elemente bleibt erhalten.
 +
 +
 +==== Teilweises Sortieren ====
 +<code cpp>
 +For is_sorted_until (For first, For last) 
 +For is_sorted_until (For first, For last, Comp comp) 
 +</​code>​
 +[[..:​lib:​is_sorted_until|Beschreibung]]:​
 + ​Liefert den Iterator ''​i''​ auf das Ende des aufsteigend sortierten Teilbereichs [first,i) von [first,​last).
 +
 +<code cpp>
 +void partial_sort (Ran first, Ran middle, Ran last) 
 +void partial_sort (Ran first, Ran middle, Ran last, Comp comp) 
 +</​code>​
 +[[..:​lib:​partial_sort|Beschreibung]]:​
 + ​Bringt die kleinsten Elemente des Bereiches [first,​last) ​
 + ​aufsteigend geordnet im Bereich [first,​middle) unter.
 +
 +<code cpp>
 +Ran partial_sort_copy (In first, In last, Ran result_first,​ Ran result_last) ​
 +Ran partial_sort_copy (In first, In last, Ran result_first,​ Ran result_last, ​
 +                       Comp comp) 
 +</​code>​
 +[[..:​lib:​partial_sort_copy|Beschreibung]]:​
 + ​Kopiert die kleinsten Elemente des Bereiches [first,​last)
 + ​aufsteigend geordnet in den Bereich [result_first,​result_last).
 +
 +<code cpp>
 +void nth_element (Ran first, Ran nth, Ran last) 
 +void nth_element (Ran first, Ran nth, Ran last, Comp comp) 
 +</​code>​
 +[[..:​lib:​nth_element|Beschreibung]]:​
 + ​Sortiert den Bereich [first,​last) soweit,
 + dass das nte Element an der richtigen Position steht 
 + und sich links davon nur kleinere, rechts davon nur größere Elementwerte befinden.
 +
 +==== Aufteilen ====
 +<code cpp>
 +bool is_partitioned (In first, In last, Pred pred) 
 +</​code>​
 +[[..:​lib:​is_partitioned|Beschreibung]]:​
 + ​Prüft,​ ob im Bereich [first,​last) alle Elemente ''​e'',​
 + auf die ''​pred(e)''​ zutrifft, links von denen stehen, auf die es nicht zutrifft.
 +
 +<code cpp>
 +For partition (For first, For last, Pred pred) 
 +</​code>​
 +[[..:​lib:​partition|Beschreibung]]:​
 + ​Bringt alle Elemente des Bereiches [first,​last), ​
 + auf die ''​pred(x)''​ zutrifft, nach links, alle anderen nach rechts.
 +
 +<code cpp>
 +Bi stable_partition (Bi first, Bi last, Pred pred) 
 +</​code>​
 +[[..:​lib:​stable_partition|Beschreibung]]:​
 + ​Bringt alle Elemente ''​e''​ des Bereiches [first,​last), ​
 + auf die ''​pred(e)''​ zutrifft, nach links, alle anderen nach rechts. ​
 + Die relative Ordnung der Elemente in beiden Gruppen bleibt erhalten.
 +
 +<code cpp>
 +std:​pair<​Out,​ Out2> partition_copy (In first, In last, Out good, Out2 bad, Pred pred) 
 +</​code>​
 +[[..:​lib:​partition_copy|Beschreibung]]:​
 + ​Kopiert alle Elemente ''​e''​ des Bereiches [first,​last), ​
 + auf die ''​pred(e)''​ zutrifft, in den durch ''​good''​ angegebenen Bereich, ​
 + alle anderen nach ''​bad''​.
 +
 +<code cpp>
 +For partition_point (For first, For last, Pred pred) 
 +</​code>​
 +[[..:​lib:​partition_point|Beschreibung]]:​
 + ​Liefert den Iterator hinter das letzte Element ''​x'' ​
 + im partitionierten Bereich [first,​last), ​
 + auf welches ''​pred(x)''​ zutrifft.
 +
 +==== Mischen ====
 +<code cpp>
 +Out merge (In first, In last, In2 first2, In2 last2, Out result) ​
 +Out merge (In first, In last, In2 first2, In2 last2, Out result, Comp comp) 
 +</​code>​
 +[[..:​lib:​merge|Beschreibung]]:​
 + ​Führt zwei aufsteigend sortierte Bereiche [first,​last) und [first2,​last2)
 + in [result,​...) aufsteigend sortiert zusammen. ​
 +
 +<code cpp>
 +void inplace_merge (Bi first, Bi middle, Bi last) 
 +void inplace_merge (Bi first, Bi middle, Bi last, Comp comp) 
 +</​code>​
 +[[..:​lib:​inplace_merge|Beschreibung]]:​
 + ​Ordnet die in sich aufsteigend sortierten Bereiche [first,​middle) und [middle,​last2) so um,
 + dass der gesamte Bereich aufsteigend sortiert ist.
 +
 +==== Mengenoperationen ====
 +<code cpp>
 +bool includes (In first1, In last1, In2 first2, In2 last2) ​
 +bool includes (In first1, In last1, In2 first2, In2 last2, Comp comp) 
 +</​code>​
 +[[..:​lib:​includes|Beschreibung]]:​
 + Ist ''​true'',​ wenn jedes Element des aufsteigend sortierten Bereiches [first2,​last2)
 + im aufsteigend sortierten Bereich [first,​last) enthalten ist.
 +
 +<code cpp>
 +Out set_union (In first1, In last1, In2 first2, In2 last2, Out result) ​
 +Out set_union (In first1, In last1, In2 first2, In2 last2, Out result, ​
 +               Comp comp) 
 +</​code>​
 +[[..:​lib:​set_union|Beschreibung]]:​
 + ​Schreibt die Vereinigung der beiden sortierten Mengen [first,​last) und [first2,​last2)
 + ​sortiert in den Bereich [result,​...).
 +
 +<code cpp>
 +Out set_intersection (In first, In last, In2 first2, In2 last2, Out result) ​
 +Out set_intersection (In first, In last, In2 first2, In2 last2, Out result, ​
 +                      Comp comp)  ​
 +</​code>​
 +[[..:​lib:​set_intersection|Beschreibung]]:​
 + ​Schreibt den Durchschnitt der beiden sortierten Mengen [first,​last) und [first2,​last2)
 + ​sortiert in den Bereich [result,​...).
 +
 +<code cpp>
 +Out set_difference (In first, In last, In2 first2, In2 last2, Out result) ​
 +Out set_difference (In first, In last, In2 first2, In2 last2, Out result, ​
 +                    Comp comp) 
 +</​code>​
 +[[..:​lib:​set_difference|Beschreibung]]:​
 + ​Kopiert jene Elemente des sortierten Bereichs [first,​last),​
 + die nicht in [first2,​last2) vorkommen, sortiert in den Bereich [result,​...).
 +
 +<code cpp>
 +Out set_symmetric_difference (In first, In last, In2 first2, In2 last2, ​
 +                              Out result) ​
 +Out set_symmetric_difference (In first, In last, In2 first2, In2 last2, ​
 +                              Out result, Comp comp) 
 +</​code>​
 +[[..:​lib:​set_symmetric_difference|Beschreibung]]:​
 + ​Kopiert jene Elemente,
 + die nur in einem der beiden sortierten Bereiche [first,​last) und [first2,​last2) vorkommen,
 + ​sortiert in den Bereich [result,​...).
 +
 +==== Heapoperationen ====
 +<code cpp>
 +bool is_heap (Ran first, Ran last) 
 +bool is_heap (Ran first, Ran last, Comp comp) 
 +</​code>​
 +[[..:​lib:​is_heap|Beschreibung]]:​
 + ​Prüft,​ ob der Bereich [first,​last) als [[..:​begriffe#​Heap]] geordnet ist.
 +
 +<code cpp>
 +Ran is_heap_until (Ran first, Ran last) 
 +Ran is_heap_until (Ran first, Ran last, Comp comp) 
 +</​code>​
 +[[..:​lib:​is_heap_until|Beschreibung]]:​
 + ​Liefert den Iterator auf das Ende des als [[..:​begriffe#​Heap]] geordneten Teilbereiches von [first,​last).
 +
 +<code cpp>
 +void push_heap (Ran first, Ran last) 
 +void push_heap (Ran first, Ran last, Comp comp) 
 +</​code>​
 +[[..:​lib:​push_heap|Beschreibung]]:​
 + Fügt das letzte Element des Bereiches [first,​last) in den davor liegenden, als [[..:​begriffe#​Heap]] geordneten Bereich ein.
 +
 +<code cpp>
 +void pop_heap (Ran first, Ran last) 
 +void pop_heap (Ran first, Ran last, Comp comp) 
 +</​code>​
 +[[..:​lib:​push_heap|Beschreibung]]:​
 + ​Vertauscht ''​*first''​ und ''​*(last-1)''​ des als [[..:​begriffe#​Heap]] geordneten Bereiches [first,​last) und ordnet den vor dem letzten Element liegenden Teilbereich wieder zu einem Heap um.
 +
 +<code cpp>
 +void make_heap (Ran first, Ran last) 
 +void make_heap (Ran first, Ran last, Comp comp) 
 +</​code>​
 +[[..:​lib:​make_heap|Beschreibung]]:​
 + ​Ordnet den Bereich [first,​last) zu einem [[..:​begriffe#​Heap]] um.
 +
 +<code cpp>
 +void sort_heap (Ran first, Ran last) 
 +void sort_heap (Ran first, Ran last, Comp comp) 
 +</​code>​
 +[[..:​lib:​sort_heap|Beschreibung]]:​
 + ​Sortiert den als [[..:​begriffe#​Heap]] vorgegebenen Bereich [first,​last) aufsteigend.
 +
 +==== Siehe auch ====
 +[[numeric]]
  
kennen/include/algorithm.txt · Zuletzt geändert: 2017-02-19 13:21 (Externe Bearbeitung)