kennen:include:algorithm
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Vorhergehende Überarbeitung | |||
— | kennen:include:algorithm [2023-10-14 12:24] (aktuell) – [<algorithm>] rrichter | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | ====== < | ||
+ | Typ-parametrisierte [[..: | ||
+ | | [[# | ||
+ | | [[# | ||
+ | | [[# | ||
+ | |||
+ | **Warnung**: | ||
+ | Die " | ||
+ | Für syntaktisch korrekte Dokumentation sei auf [[https:// | ||
+ | |||
+ | Die Einleitung '' | ||
+ | Die Iterator-[[..: | ||
+ | Mit '' | ||
+ | |||
+ | Erweiterungen in C++17: | ||
+ | [[..: | ||
+ | |||
+ | Erweiterungen in C++20: | ||
+ | Als '' | ||
+ | Projektionen '' | ||
+ | Steht an Stelle eines Ergebnistyps '' | ||
+ | |||
+ | <code cpp> | ||
+ | auto [x,y] = f(...); | ||
+ | |||
+ | auto result = f(...); | ||
+ | std::cout << result.name1 << ' ' << result.name2; | ||
+ | </ | ||
+ | Alternativ kann auf die Bestandteile der Rückgabestruktur per Namen zugegriffen werden. | ||
+ | Dazu muss man allerdings deren Namen kennen. | ||
+ | Diese werden in der Beschreibung der Algorithmen aufgeführt. | ||
+ | |||
+ | ===== Nichtmodifizierende Algorithmen ===== | ||
+ | ==== Ausführen und Zählen ==== | ||
+ | <code cpp> | ||
+ | Function for_each (In first, In last, Function f) | ||
+ | Function for_each (Exec pol, In first, In last, Function f) | ||
+ | |||
+ | [last, f] = ranges:: | ||
+ | [last, f] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | difference_type count (In first, In last, T wert) | ||
+ | difference_type count (Exec pol, In first, In last, T wert) | ||
+ | |||
+ | difference_type ranges:: | ||
+ | difference_type ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | difference_type count_if (In first, In last, Pred pred) | ||
+ | difference_type count_if (Exec pol, In first, In last, Pred pred) | ||
+ | |||
+ | difference_type ranges:: | ||
+ | difference_type ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | ==== Prädikatenlogik ==== | ||
+ | <code cpp> | ||
+ | bool all_of (In first, In last, Pred pred) | ||
+ | bool all_of (Exec pol, In first, In last, Pred pred) | ||
+ | |||
+ | bool ranges:: | ||
+ | bool ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | Bei leerem Bereich liefert die Funktion '' | ||
+ | |||
+ | <code cpp> | ||
+ | bool any_of (In first, In last, Pred pred) | ||
+ | bool any_of (Exec pol, In first, In last, Pred pred) | ||
+ | |||
+ | bool ranges:: | ||
+ | bool ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | Bei leerem Bereich liefert die Funktion '' | ||
+ | |||
+ | <code cpp> | ||
+ | bool none_of (In first, In last, Pred pred) | ||
+ | bool none_of (Exec pol, In first, In last, Pred pred) | ||
+ | |||
+ | bool ranges:: | ||
+ | bool ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | Bei leerem Bereich liefert die Funktion '' | ||
+ | |||
+ | ==== Suchen ==== | ||
+ | <code cpp> | ||
+ | In find (In first, In last, T wert) | ||
+ | In find (Exec pol, In first, In last, T wert) | ||
+ | |||
+ | In ranges:: | ||
+ | In ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | In find_if (In first, In last, Pred pred) | ||
+ | In find_if (Exec pol, In first, In last, Pred pred) | ||
+ | |||
+ | In ranges:: | ||
+ | In ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | auf den das Prädikat '' | ||
+ | |||
+ | <code cpp> | ||
+ | In find_if_not (In first, In last, Pred pred) | ||
+ | In find_if_not (Exec pol, In first, In last, Pred pred) | ||
+ | |||
+ | In ranges:: | ||
+ | In ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | auf den das Prädikat '' | ||
+ | |||
+ | <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) | ||
+ | For find_first_of (Exec pol, For first, For last, For2 first2, For2 last2) | ||
+ | For find_first_of (Exec pol, For first, For last, For2 first2, For2 last2, Binary pred) | ||
+ | |||
+ | For ranges:: | ||
+ | For ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | das mit einem Element '' | ||
+ | für welches '' | ||
+ | <code cpp> | ||
+ | For search (For first, For last, For2 first2, For2 last2) | ||
+ | For search (For first, For last, For2 first2, For2 last2, Binary pred) | ||
+ | For search (Exec pol, For first, For last, For2 first2, For2 last2) | ||
+ | For search (Exec pol, For first, For last, For2 first2, For2 last2, Binary pred) | ||
+ | |||
+ | Range ranges:: | ||
+ | Range ranges:: | ||
+ | |||
+ | For search (For first, For last, Searcher searcher) // C++17 | ||
+ | </ | ||
+ | [[..: | ||
+ | Sucht den Anfang eines Teilbereiches (den Teilbereich) aus [first, | ||
+ | der mit [first2, | ||
+ | dem Muster eines [[..: | ||
+ | <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) | ||
+ | For search_n (Exec pol, For first, For last, Size n, T wert) | ||
+ | For search_n (Exec pol, For first, For last, Size n, T wert, Binary pred) | ||
+ | |||
+ | Range ranges:: | ||
+ | Range ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | Sucht den Anfang eines Teilbereiches (den Teilbereich) aus [first, | ||
+ | der '' | ||
+ | |||
+ | <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) | ||
+ | For find_end (Exec pol, For first, For last, For2 first2, For2 last2) | ||
+ | For find_end (Exec pol, For first, For last, For2 first2, For2 last2, Binary pred) | ||
+ | |||
+ | Range ranges:: | ||
+ | Range ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | der mit [first2, | ||
+ | für dessen Elemente '' | ||
+ | |||
+ | <code cpp> | ||
+ | For adjacent_find (For first, For last) | ||
+ | For adjacent_find (For first, For last, Binary pred) | ||
+ | For adjacent_find (Exec pol, For first, For last) | ||
+ | For adjacent_find (Exec pol, For first, For last, Binary pred) | ||
+ | |||
+ | For ranges:: | ||
+ | For ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | das mit seinem Nachfolger übereinstimmt bzw. | ||
+ | mit seinem Nachfolger das Prädikat '' | ||
+ | |||
+ | ==== Binärsuche ==== | ||
+ | <code cpp> | ||
+ | bool binary_search (For first, For last, T wert) | ||
+ | bool binary_search (For first, For last, T wert, Binary comp) | ||
+ | |||
+ | bool ranges:: | ||
+ | bool ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | For lower_bound (For first, For last, T wert) | ||
+ | For lower_bound (For first, For last, T wert, Binary comp) | ||
+ | |||
+ | For ranges:: | ||
+ | For ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | ohne die aufsteigende Ordnung der Folge [first, | ||
+ | |||
+ | <code cpp> | ||
+ | For upper_bound (For first, For last, T wert) | ||
+ | For upper_bound (For first, For last, T wert, Binary comp) | ||
+ | |||
+ | For ranges:: | ||
+ | For ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | ohne die aufsteigende Ordnung der Folge [first, | ||
+ | |||
+ | <code cpp> | ||
+ | std:: | ||
+ | std:: | ||
+ | |||
+ | Range ranges:: | ||
+ | Range ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | der mit dem '' | ||
+ | |||
+ | ==== Minimum und Maximum ==== | ||
+ | <code cpp> | ||
+ | const T& min (const T& a, const T& b) | ||
+ | const T& min (const T& a, const T& b, Binary comp) | ||
+ | T min (std:: | ||
+ | T min (std:: | ||
+ | |||
+ | const T& ranges::min (const T& a, const T& b, Binary comp = {}, Proj proj = {}) | ||
+ | T ranges::min (std:: | ||
+ | T ranges::min (Range r, Binary comp = {}, Proj proj = {}) | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | const T& max (const T& a, const T& b) | ||
+ | const T& max (const T& a, const T& b, Binary comp) | ||
+ | T max (std:: | ||
+ | T max (std:: | ||
+ | |||
+ | const T& ranges::max (const T& a, const T& b, Binary comp = {}, Proj proj = {}) | ||
+ | T ranges::max (std:: | ||
+ | T ranges::max (Range r, Binary comp = {}, Proj proj = {}) | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | |||
+ | [min,max] = ranges:: | ||
+ | [min,max] = ranges:: | ||
+ | [min,max] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | For min_element (For first, For last) | ||
+ | For min_element (For first, For last, Binary comp) | ||
+ | For min_element (Exec pol, For first, For last) | ||
+ | For min_element (Exec pol, For first, For last, Binary comp) | ||
+ | |||
+ | For ranges:: | ||
+ | For ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | For max_element (For first, For last) | ||
+ | For max_element (For first, For last, Binary comp) | ||
+ | For max_element (Exec pol, For first, For last) | ||
+ | For max_element (Exec pol, For first, For last, Binary comp) | ||
+ | |||
+ | For ranges:: | ||
+ | For ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | |||
+ | Range ranges:: | ||
+ | Range ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <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, Binary comp) | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | ==== 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) | ||
+ | bool equal (Exec pol, For first, For last, For2 first2) | ||
+ | bool equal (Exec pol, For first, For last, For2 first2, Binary pred) | ||
+ | bool equal (Exec pol, For first, For last, For2 first2, For2 last2) | ||
+ | bool equal (Exec pol, For first, For last, For2 first2, For2 last2, Binary pred) | ||
+ | |||
+ | bool ranges:: | ||
+ | bool ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | Ist wahr, wenn die Bereiche [first, | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | bool lexicographical_compare (In first, In last, In2 first2, In2 last2) | ||
+ | bool lexicographical_compare (In first, In last, In2 first2, In2 last2, Binary comp) | ||
+ | bool lexicographical_compare (Exec pol, In first, In last, In2 first2, In2 last2) | ||
+ | bool lexicographical_compare (Exec pol, In first, In last, In2 first2, In2 last2, Binary comp) | ||
+ | |||
+ | bool ranges:: | ||
+ | bool ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | Ist wahr, wenn der Bereich [first, | ||
+ | |||
+ | <code cpp> | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | std:: | ||
+ | |||
+ | [pos1, pos2] = ranges:: | ||
+ | [pos1, pos2] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | ab denen die Bereiche [first, | ||
+ | das Prädikat '' | ||
+ | |||
+ | ===== Modifizierende Algorithmen ===== | ||
+ | |||
+ | ==== Tauschen ==== | ||
+ | <code cpp> | ||
+ | void iter_swap (Iter a, Iter b) | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | For2 swap_ranges (For first, For last, For2 first) | ||
+ | For2 swap_ranges (Exec pol, For first, For last, For2 first) | ||
+ | |||
+ | [pos, pos2] = ranges:: | ||
+ | [pos, pos2] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | ==== Kopieren ==== | ||
+ | <code cpp> | ||
+ | Out copy (In first, In last, Out result) | ||
+ | Out copy (Exec pol, In first, In last, Out result) | ||
+ | |||
+ | [last, res] = ranges:: | ||
+ | [last, res] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | Out copy_if (In first, In last, Out result, Pred pred) | ||
+ | Out copy_if (Exec pol, In first, In last, Out result, Pred pred) | ||
+ | |||
+ | [last, res] = ranges:: | ||
+ | [last, res] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | Out copy_n (In first, Size n, Out result) | ||
+ | Out copy_n (Exec pol, In first, Size n, Out result) | ||
+ | |||
+ | [last, res] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | Bi2 copy_backward (Bi first, Bi last, Bi2 result) | ||
+ | |||
+ | [last, res] = ranges:: | ||
+ | [last, res] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | ==== Verschieben ==== | ||
+ | <code cpp> | ||
+ | Out move (In first, In last, Out result) | ||
+ | Out move (Exec pol, In first, In last, Out result) | ||
+ | |||
+ | [last, res] = ranges:: | ||
+ | [last, res] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | [last, res] = ranges:: | ||
+ | [last, res] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | |||
+ | ==== Füllen ==== | ||
+ | <code cpp> | ||
+ | void fill (Out first, Out last, T wert) | ||
+ | void fill (Exec pol, Out first, Out last, T wert) | ||
+ | |||
+ | Out ranges:: | ||
+ | Out ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | void fill_n (Out first, Size n, T wert) | ||
+ | void fill_n (Exec pol, Out first, Size n, T wert) | ||
+ | |||
+ | Out ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | void generate (Out first, Out last, Func generator_obj) | ||
+ | void generate (Exec pol, Out first, Out last, Func generator_obj) | ||
+ | |||
+ | Out ranges:: | ||
+ | Out ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | void generate_n (Out first, Size n, Func generator_obj) | ||
+ | void generate_n (Exec pol, Out first, Size n, Func generator_obj) | ||
+ | |||
+ | Out ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | ==== Ersetzen ==== | ||
+ | <code cpp> | ||
+ | void replace (For first, For last, T alterwert, T neuerwert) | ||
+ | void replace (Exec pol, For first, For last, T alterwert, T neuerwert) | ||
+ | |||
+ | In ranges:: | ||
+ | In ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | void replace_if (For first, For last, Pred pred, T neuerwert) | ||
+ | void replace_if (Exec pol, For first, For last, Pred pred, T neuerwert) | ||
+ | |||
+ | In ranges:: | ||
+ | In ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | Out replace_copy (In first, In last, Out result, T alterwert, T neuerwert) | ||
+ | Out replace_copy (Exec pol, In first, In last, Out result, T alterwert, T neuerwert) | ||
+ | |||
+ | [last, out] = ranges:: | ||
+ | [last, out] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | Out replace_copy_if (In first, In last, Out result, Pre pred, T neuerwert) | ||
+ | Out replace_copy_if (Exec pol, In first, In last, Out result, Pre pred, T neuerwert) | ||
+ | |||
+ | [last, out] = ranges:: | ||
+ | [last, out] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | auf die '' | ||
+ | |||
+ | ==== Entfernen ==== | ||
+ | <code cpp> | ||
+ | For remove (For first, For last, T wert) | ||
+ | For remove (Exec pol, For first, For last, T wert) | ||
+ | |||
+ | Range ranges:: | ||
+ | Range ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | For remove_if (For first, For last, Pred pred) | ||
+ | For remove_if (Exec pol, For first, For last, Pred pred) | ||
+ | |||
+ | Range ranges:: | ||
+ | Range ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | Out remove_copy (In first, In last, Out result, T wert) | ||
+ | Out remove_copy (Exec pol, In first, In last, Out result, T wert) | ||
+ | |||
+ | [last, res] = ranges:: | ||
+ | [last, res] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | und entfernt dabei alle Elemente '' | ||
+ | auf die '' | ||
+ | |||
+ | <code cpp> | ||
+ | Out remove_copy_if (In first, In last, Out result, Pred pred) | ||
+ | Out remove_copy_if (Exec pol, In first, In last, Out result, Pred pred) | ||
+ | |||
+ | [last, res] = ranges:: | ||
+ | [last, res] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | und entfernt dabei alle Elemente '' | ||
+ | auf die '' | ||
+ | |||
+ | <code cpp> | ||
+ | For unique (For first, For last) | ||
+ | For unique (For first, For last, Binary pred) | ||
+ | For unique (Exec pol, first, For last) | ||
+ | For unique (Exec pol, For first, For last, Binary pred) | ||
+ | |||
+ | Range ranges:: | ||
+ | Range ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | die mit ihren Vorgänger übereinstimmen bzw. auf die '' | ||
+ | |||
+ | <code cpp> | ||
+ | Out unique_copy (In first, In last, Out result) | ||
+ | Out unique_copy (In first, In last, Out result, Binary pred) | ||
+ | Out unique_copy (Exec pol, In first, In last, Out result) | ||
+ | Out unique_copy (Exec pol, In first, In last, Out result, Binary pred) | ||
+ | |||
+ | [last,res] = ranges:: | ||
+ | [last,res] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | und übergeht dabei alle Elemente '' | ||
+ | die mit ihren Vorgänger übereinstimmen bzw. auf die '' | ||
+ | |||
+ | ==== 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) | ||
+ | Out transform (Exec pol, In first, In last, Out result, Func func) | ||
+ | Out transform (Exec pol, In first, In last, In first2, Out result, Binary func) | ||
+ | |||
+ | [end,res] = ranges:: | ||
+ | [end,res] = ranges:: | ||
+ | |||
+ | [end1, | ||
+ | [end1, | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | eine Folge von Werten '' | ||
+ | '' | ||
+ | |||
+ | ===== Mutierende Algorithmen ===== | ||
+ | |||
+ | ==== Umkehren ==== | ||
+ | <code cpp> | ||
+ | void reverse (Bi first, Bi last) | ||
+ | void reverse (Exec pol, Bi first, Bi last) | ||
+ | |||
+ | Bi ranges:: | ||
+ | Bi ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | Kehrt die Reihenfolge des Elemente im Bereich [first, | ||
+ | |||
+ | <code cpp> | ||
+ | Out reverse_copy (Bi first, Bi last, Out result) | ||
+ | Out reverse_copy (Exec pol, Bi first, Bi last, Out result) | ||
+ | |||
+ | [last,res] = ranges:: | ||
+ | [last,res] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | ==== Rotieren ==== | ||
+ | <code cpp> | ||
+ | For rotate (For first, For middle, For last) | ||
+ | For rotate (Exec pol, For first, For middle, For last) | ||
+ | |||
+ | Range ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | Out rotate_copy (For first, For middle, For last, Out result) | ||
+ | Out rotate_copy (Exec pol, For first, For middle, For last, Out result) | ||
+ | |||
+ | [last,res] = ranges:: | ||
+ | [last,res] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | ==== Durcheinanderbringen ==== | ||
+ | <code cpp> | ||
+ | void shuffle (Ran first, Ran last, UniformRandomBitGenerator zufall) | ||
+ | |||
+ | Ran ranges:: | ||
+ | Ran ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | Out sample (In first, In last, Out first2, N n, UniformRandomBitGenerator zufall) | ||
+ | |||
+ | Out ranges:: | ||
+ | Out ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | void random_shuffle (Ran first, Ran last) // bis C++14, entfernt in C++17 | ||
+ | void random_shuffle (Ran first, Ran last, Func zufall) | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | 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, Binary comp) | ||
+ | bool is_permutation (For first, For last, For2 first2, For2 last2) | ||
+ | bool is_permutation (For first, For last, For2 first2, For2 last2, Binary comp) | ||
+ | |||
+ | bool ranges:: | ||
+ | bool ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | bool next_permutation (Bi first, Bi last) | ||
+ | bool next_permutation (Bi first, Bi last, Binary comp) | ||
+ | |||
+ | [last,B] = ranges:: | ||
+ | [last,B] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | bool prev_permutation (Bi first, Bi last) | ||
+ | bool prev_permutation (Bi first, Bi last, binary comp) | ||
+ | |||
+ | [last,B] = ranges:: | ||
+ | [last,B] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | ==== Links/ | ||
+ | <code cpp> | ||
+ | For shift_left (For first, For last, difference_type n); // C++20 | ||
+ | For shift_left (Exec pol, For first, For last, difference_type n); | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | For shift_right (For first, For last, difference_type n); // C++20 | ||
+ | For shift_right (Exec pol, For first, For last, difference_type n); | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ===== Sortieren ===== | ||
+ | |||
+ | ==== Vollständiges Sortieren ==== | ||
+ | <code cpp> | ||
+ | bool is_sorted (For first, For last) | ||
+ | bool is_sorted (For first, For last, Binary comp) | ||
+ | bool is_sorted (Exec pol, For first, For last) | ||
+ | bool is_sorted (Exec pol, For first, For last, Binary comp) | ||
+ | |||
+ | bool ranges:: | ||
+ | bool ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | void sort (Ran first, Ran last) | ||
+ | void sort (Ran first, Ran last, Comp comp) | ||
+ | void sort (Exec pol, Ran first, Ran last) | ||
+ | void sort (Exec pol, Ran first, Ran last, Comp comp) | ||
+ | |||
+ | Ran ranges:: | ||
+ | Ran ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | void stable_sort (Ran first, Ran last) | ||
+ | void stable_sort (Ran first, Ran last, Comp comp) | ||
+ | void stable_sort (Exec pol, Ran first, Ran last) | ||
+ | void stable_sort (Exec pol, Ran first, Ran last, Comp comp) | ||
+ | |||
+ | Ran ranges:: | ||
+ | Ran ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | 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, Binary comp) | ||
+ | For is_sorted_until (Exec pol, For first, For last) | ||
+ | For is_sorted_until (Exec pol, For first, For last, Binary comp) | ||
+ | |||
+ | For ranges:: | ||
+ | For ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | void partial_sort (Ran first, Ran middle, Ran last) | ||
+ | void partial_sort (Ran first, Ran middle, Ran last, Binary comp) | ||
+ | void partial_sort (Exec pol, Ran first, Ran middle, Ran last) | ||
+ | void partial_sort (Exec pol, Ran first, Ran middle, Ran last, Binary comp) | ||
+ | |||
+ | Ran ranges:: | ||
+ | Ran ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | Ran partial_sort_copy (In first, In last, Ran result_first, | ||
+ | Ran partial_sort_copy (In first, In last, Ran result_first, | ||
+ | Ran partial_sort_copy (Exec pol, In first, In last, Ran result_first, | ||
+ | Ran partial_sort_copy (Exec pol, In first, In last, Ran result_first, | ||
+ | |||
+ | [last,res] = partial_sort_copy (Range1 r1, Range2 result, Binary comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) | ||
+ | [last,res] = partial_sort_copy (In first, In last, Ran result_first, | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | void nth_element (Ran first, Ran nth, Ran last) | ||
+ | void nth_element (Ran first, Ran nth, Ran last, Binary comp) | ||
+ | void nth_element (Exec pol, Ran first, Ran nth, Ran last) | ||
+ | void nth_element (Exec pol, Ran first, Ran nth, Ran last, Binary comp) | ||
+ | |||
+ | Ran ranges:: | ||
+ | Ran ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | 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) | ||
+ | bool is_partitioned (Exec pol, In first, In last, Pred pred) | ||
+ | |||
+ | bool ranges:: | ||
+ | bool ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | auf die '' | ||
+ | |||
+ | <code cpp> | ||
+ | For partition (For first, For last, Pred pred) | ||
+ | For partition (Exec pol, For first, For last, Pred pred) | ||
+ | |||
+ | Range range:: | ||
+ | Range range:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | auf die '' | ||
+ | |||
+ | <code cpp> | ||
+ | For stable_partition (For first, For last, Pred pred) | ||
+ | For stable_partition (Exec pol, For first, For last, Pred pred) | ||
+ | |||
+ | Range range:: | ||
+ | Range range:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | auf die '' | ||
+ | Die relative Ordnung der Elemente in beiden Gruppen bleibt erhalten. | ||
+ | |||
+ | <code cpp> | ||
+ | std: | ||
+ | std: | ||
+ | |||
+ | [last, endgood, endbad] = ranges:: | ||
+ | [last, endgood, endbad] = ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | auf die '' | ||
+ | alle anderen nach '' | ||
+ | |||
+ | <code cpp> | ||
+ | For partition_point (For first, For last, Pred pred) | ||
+ | |||
+ | For ranges:: | ||
+ | For ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | im partitionierten Bereich [first, | ||
+ | auf welches '' | ||
+ | |||
+ | ==== 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, Binary comp) | ||
+ | Out merge (Exec pol, In first, In last, In2 first2, In2 last2, Out result) | ||
+ | Out merge (Exec pol, In first, In last, In2 first2, In2 last2, Out result, binary comp) | ||
+ | |||
+ | [last1, | ||
+ | [last1, | ||
+ | | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | in [result, | ||
+ | |||
+ | <code cpp> | ||
+ | void inplace_merge (Bi first, Bi middle, Bi last) | ||
+ | void inplace_merge (Bi first, Bi middle, Bi last, Binary comp) | ||
+ | void inplace_merge (Exec pol, Bi first, Bi middle, Bi last) | ||
+ | void inplace_merge (Exec pol, Bi first, Bi middle, Bi last, Binary comp) | ||
+ | |||
+ | Bi ranges:: | ||
+ | Bi ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | 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, Binary comp) | ||
+ | bool includes (Exec pol, In first1, In last1, In2 first2, In2 last2) | ||
+ | bool includes (Exec pol, In first1, In last1, In2 first2, In2 last2, Binary comp) | ||
+ | |||
+ | bool ranges:: | ||
+ | bool ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | Ist '' | ||
+ | im aufsteigend sortierten Bereich [first, | ||
+ | |||
+ | <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, Binary comp) | ||
+ | Out set_union (Exec pol, In first1, In last1, In2 first2, In2 last2, Out result) | ||
+ | Out set_union (Exec pol, In first1, In last1, In2 first2, In2 last2, Out result, Binary comp) | ||
+ | |||
+ | [last1, | ||
+ | | ||
+ | [last1, | ||
+ | | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | Out set_intersection (In first1, In last1, In2 first2, In2 last2, Out result) | ||
+ | Out set_intersection (In first1, In last1, In2 first2, In2 last2, Out result, Binary comp) | ||
+ | Out set_intersection (Exec pol, In first1, In last1, In2 first2, In2 last2, Out result) | ||
+ | Out set_intersection (Exec pol, In first1, In last1, In2 first2, In2 last2, Out result, Binary comp) | ||
+ | |||
+ | [last1, | ||
+ | Binary comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) | ||
+ | [last1, | ||
+ | Binary comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | Out set_difference (In first1, In last1, In2 first2, In2 last2, Out result) | ||
+ | Out set_difference (In first1, In last1, In2 first2, In2 last2, Out result, Binary comp) | ||
+ | Out set_difference (Exec pol, In first1, In last1, In2 first2, In2 last2, Out result) | ||
+ | Out set_difference (Exec pol, In first1, In last1, In2 first2, In2 last2, Out result, Binary comp) | ||
+ | |||
+ | [last1,res] = ranges:: | ||
+ | Binary comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) | ||
+ | [last1,res] = ranges:: | ||
+ | Binary comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | die nicht in [first2, | ||
+ | |||
+ | <code cpp> | ||
+ | Out set_symmetric_difference (In first1, In last1, In2 first2, In2 last2, Out result) | ||
+ | Out set_symmetric_difference (In first1, In last1, In2 first2, In2 last2, Out result, Binary comp) | ||
+ | Out set_symmetric_difference (Exec pol, In first1, In last1, In2 first2, In2 last2, Out result) | ||
+ | Out set_symmetric_difference (Exec pol, In first1, In last1, In2 first2, In2 last2, Out result, Binary comp) | ||
+ | |||
+ | [last1,res] = ranges:: | ||
+ | Binary comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) | ||
+ | [last1,res] = ranges:: | ||
+ | Binary comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | die nur in einem der beiden sortierten Bereiche [first, | ||
+ | | ||
+ | |||
+ | ==== Heapoperationen ==== | ||
+ | <code cpp> | ||
+ | bool is_heap (Ran first, Ran last) | ||
+ | bool is_heap (Ran first, Ran last, Binary comp) | ||
+ | |||
+ | bool is_heap (Exec pol, Ran first, Ran last) | ||
+ | bool is_heap (Exec pol, Ran first, Ran last, Binary comp) | ||
+ | |||
+ | bool ranges:: | ||
+ | bool ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | Ran is_heap_until (Ran first, Ran last) | ||
+ | Ran is_heap_until (Ran first, Ran last, Binary comp) | ||
+ | Ran is_heap_until (Exec pol, Ran first, Ran last) | ||
+ | Ran is_heap_until (Exec pol, Ran first, Ran last, Binary comp) | ||
+ | |||
+ | Ran ranges:: | ||
+ | Ran ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | void push_heap (Ran first, Ran last) | ||
+ | void push_heap (Ran first, Ran last, Binary comp) | ||
+ | |||
+ | Ran ranges:: | ||
+ | Ran ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | Fügt das letzte Element des Bereiches [first, | ||
+ | |||
+ | <code cpp> | ||
+ | void pop_heap (Ran first, Ran last) | ||
+ | void pop_heap (Ran first, Ran last, Binary comp) | ||
+ | |||
+ | Ran ranges:: | ||
+ | Ran ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | void make_heap (Ran first, Ran last) | ||
+ | void make_heap (Ran first, Ran last, Binary comp) | ||
+ | |||
+ | Ran ranges:: | ||
+ | Ran ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | <code cpp> | ||
+ | void sort_heap (Ran first, Ran last) | ||
+ | void sort_heap (Ran first, Ran last, Binary comp) | ||
+ | |||
+ | Ran ranges:: | ||
+ | Ran ranges:: | ||
+ | </ | ||
+ | [[..: | ||
+ | | ||
+ | |||
+ | ==== Siehe auch ==== | ||
+ | [[numeric]] | ||