namespace cpp

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


kennen:include:algorithm

<algorithm>

Typ-parametrisierte Algorithmen:

Die Iterator-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.

Nichtmodifizierende Algorithmen

Ausführen und Zählen

Function for_each (In first, In last, Function f) 

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.

difference_type count (In first, In last, T wert) 

Beschreibung: Liefert die Anzahl der Elemente des Bereiches [first,last) mit dem wert.

difference_type count_if (In first, In last, Pred pred) 

Beschreibung: Liefert die Anzahl der Elemente e des Bereiches [first,last), auf die das Prädikat pred(e) zutrifft.

Prädikatenlogik

bool all_of (In first, In last, Pred pred) 

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.

bool any_of (In first, In last, Pred pred) 

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.

bool none_of (In first, In last, Pred pred) 

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

In find (In first, In last, T wert) 

Beschreibung: Liefert einen Iterator auf das erste Element des Bereiches [first,last) mit dem wert.

In find_if (In first, In last, Pred pred) 

Beschreibung: Liefert einen Iterator i auf das erste Element des Bereiches [first,last), auf den das Prädikat pred(*i) zutrifft.

In find_if_not (In first, In last, Pred pred) 

Beschreibung: Liefert einen Iterator i auf das erste Element des Bereiches [first,last), auf den das Prädikat pred(*i) nicht zutrifft.

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) 

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.

For search (For first, For last, For2 first2, For2 last2) 
For search (For first, For last, For2 first2, For2 last2, Binary pred) 

Beschreibung: Sucht den Anfang eines Teilbereiches aus [first,last), der mit [first2,last2) übereinstimmt bzw. das Prädikat pred(x,y) erfüllt.

For search_n (For first, For last, Size n, T wert) 
For search_n (For first, For last, Size n, T wert, Binary pred) 

Beschreibung: Sucht den Anfang eines Teilbereiches aus [first,last), der n gleiche Werte hat bzw. auf den n mal pred(x,wert) zutrifft.

For find_end (For first, For last, For2 first2, For2 last2) 
For find_end (For first, For last, For2 first2, For2 last2, Binary pred) 

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.

For adjacent_find (For first, For last) 
For adjacent_find (For first, For last, Binary pred) 

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

bool binary_search (For first, For last, T wert) 
bool binary_search (For first, For last, T wert, Comp comp) 

Beschreibung: Sucht wert in der aufsteigend geordneten Folge von Elementen [first,last).

For lower_bound (For first, For last, T wert) 
For lower_bound (For first, For last, T wert, Comp comp) 

Beschreibung: Bestimmt die erste Position, an der wert eingefügt werden kann, ohne die aufsteigende Ordnung der Folge [first,last) zu zerstören.

For upper_bound (For first, For last, T wert) 
For upper_bound (For first, For last, T wert, Comp comp) 

Beschreibung: Bestimmt die letzte Position, an der wert eingefügt werden kann, ohne die aufsteigende Ordnung der Folge [first,last) zu zerstören.

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) 

Beschreibung: Bestimmt den Teilbereich der aufsteigend geordneten Folge [first,last), dessen Elemente mit wert übereinstimmen.

Minimum und Maximum

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)  

Beschreibung: Liefert den kleineren Wert.

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)  

Beschreibung: Liefert den größeren Wert.

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)  

Beschreibung: Liefert kleinsten und größten Wert als geordnetes Paar (first <= second).

For min_element (For first, For last) 
For min_element (For first, For last, Comp comp) 

Beschreibung: Liefert einen Iterator auf das kleinste Element des Bereiches [first,last).

For max_element (For first, For last) 
For max_element (For first, For last, Comp comp) 

Beschreibung: Liefert einen Iterator auf das größte Element des Bereiches [first,last).

std::pair<For,For> minmax_element (For first, For last) 
std::pair<For,For> minmax_element (For first, For last, Comp comp) 

Beschreibung: Liefert den weitesten Teilbereich [min,max).

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) 

Beschreibung: Begrenzt Wert auf das Intervall [low,high].

Vergleichen

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) 

Beschreibung: Ist wahr, wenn die Bereiche [first,last) und [first2,…) elementweise übereinstimmen bzw. paarweise das Prädikat pred(x,y) erfüllen.

bool lexicographical_compare (In first, In last, In2 first2, In2 last2) 
bool lexicographical_compare (In first, In last, In2 first2, In2 last2, 
                              Comp comp) 

Beschreibung: Ist wahr, wenn der Bereich [first,last) lexikographisch vor [first2,last2) einzuordnen ist.

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) 

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

void iter_swap (Iter a, Iter b) 

Beschreibung: Vertauscht die Werte der Objekte, auf die die Iteratoren von a und b verweisen.

For2 swap_ranges (For first, For last, For2 first) 

Beschreibung: Tauscht die Werte in den Bereichen [first,last) und [first2,…) aus.

Kopieren

Out copy (In first, In last, Out result) 

Beschreibung: Kopiert die Werte des Bereiches [first,last) nach [result,…).

Out copy_if (In first, In last, Out result, Pred pred) 

Beschreibung: Kopiert die Werte e des Bereiches [first,last) nach [result,…), die das Prädikat pred(e) erfüllen.

Out copy_n (In first, Size n, Out result) 

Beschreibung: Kopiert n Werte des Bereiches [first,first+n) nach [result,…).

Bi2 copy_backward (Bi first, Bi last, Bi2 result) 

Beschreibung: Kopiert die Werte des Bereiches [first,last) am Ende beginnend nach [result - (last-first),result).

Verschieben

Out move (In first, In last, Out result) 

Beschreibung: Verschiebt die Elemente des Bereiches [first,last) nach [result,…).

Bi2 move_backward (Bi first, Bi last, Bi2 result) 

Beschreibung: Verschiebt die Elemente des Bereiches [first,last) am Ende beginnend nach [result - (last-first),result).

Füllen

void fill (Out first, Out last, T wert) 

Beschreibung: Füllt den Bereich [first,last) mit dem wert.

void fill_n (Out first, Size n, T wert) 

Beschreibung: Füllt in den bei first beginnenden Bereich n mal den wert.

void generate (Out first, Out last, Func generator_obj) 

Beschreibung: Füllt den Bereich [first,last) mit der durch generator_obj erzeugten Folge von Werten.

void generate_n (Out first, Size n, Func generator_obj) 

Beschreibung: Füllt in den bei first beginnenden Bereich n durch generator_obj erzeugte Werte.

Ersetzen

void replace (For first, For last, T alterwert, T neuerwert) 

Beschreibung: Ersetzt im Bereich [first,last) alterwert durch neuerwert.

void replace_if (For first, For last, Pred pred, T neuerwert) 

Beschreibung: Ersetzt im Bereich [first,last) all jene Elemente, auf die pred(x) zutrifft, durch neuerwert.

Out replace_copy (In first, In last, Out result, T alterwert, T neuerwert) 

Beschreibung: Kopiert den Bereich [first,last) nach [result,…) und ersetzt dabei alterwert durch neuerwert.

Out replace_copy_if (In first, In last, Out result, Pre pred, T neuerwert) 

Beschreibung: Kopiert den Bereich [first,last) nach [result,…) und ersetzt dabei all jene Elemente, auf die pred(x) zutrifft, durch neuerwert.

Entfernen

For remove (For first, For last, T wert) 

Beschreibung: Entfernt im Bereich [first,last) alle Elemente mit dem angegebenen wert.

For remove_if (For first, For last, Pred pred) 

Beschreibung: Entfernt im Bereich [first,last) alle Elemente, auf die pred(x) zutrifft.

Out remove_copy (In first, In last, Out result, T wert) 
Out remove_copy_if (In first, In last, Out result, Pred pred) 

Beschreibung: Kopiert den Bereich [first,last) nach [result,…) und entfernt dabei alle Elemente mit dem angegebenen wert bzw. auf die pred(x) zutrifft.

For unique (For first, For last) 
For unique (For first, For last, Pred pred) 

Beschreibung: Entfernt alle Elemente aus dem Bereich [first,last), die mit ihren Vorgänger übereinstimmen bzw. auf die pred(vorgaenger,x) zutrifft.

Out unique_copy (In first, In last, Out result) 
Out unique_copy (In first, In last, Out result, Binary pred) 

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

Out transform (In first, In last, Out result, Func func) 
Out transform (In first, In last, In first2, Out result, Binary func) 

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

void reverse (Bi first, Bi last) 

Beschreibung: Kehrt die Reihenfolge des Elemente im Bereich [first,last) um.

Out reverse_copy (Bi first, Bi last, Out result) 

Beschreibung: Kopiert den Bereich [first,last) in umgekehrter Reihenfolge nach [result,…).

Rotieren

For rotate (For first, For middle, For last) 

Beschreibung: Vertauscht die Bereiche [first,middle) und [middle,last).

Out rotate_copy (For first, For middle, For last, Out result) 

Beschreibung: Kopiert die Bereiche [middle,last) und [first,middle) in dieser Reihenfolge nach [result,…).

Durcheinanderbringen

void shuffle (Ran first, Ran last, UniformRandomGenerator zufall)  // C++11

Beschreibung: Ordnet den Bereich [first,last) zufällig um.

Out sample (In first, In last, Out first2, N n, UniformRandomGenerator zufall)  // C++17

Beschreibung: Liefert n Werte aus dem Bereich [first,last) in zufälliger Folge.

void random_shuffle (Ran first, Ran last)              // bis C++14, entfernt in C++17 
void random_shuffle (Ran first, Ran last, Func zufall) 

Beschreibung: Ordnet den Bereich [first,last) zufällig um. Der Aufruf zufall(n) sollte Zahlen im Bereich [0,n) liefern.

Systematisches Umordnen

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) 

Beschreibung: Prüft, ob [first2,…) eine Permutation des Bereiches [first,last) darstellt.

bool next_permutation (Bi first, Bi last) 
bool next_permutation (Bi first, Bi last, Comp comp) 

Beschreibung: Erzeugt die nächste Permutation des Bereiches [first,last).

bool prev_permutation (Bi first, Bi last) 
bool prev_permutation (Bi first, Bi last, Comp comp) 

Beschreibung: Erzeugt die vorhergehende Permutation des Bereiches [first,last).

Sortieren

Vollständiges Sortieren

bool is_sorted (For first, For last) 
bool is_sorted (For first, For last, Comp comp) 

Beschreibung: Prüft, ob der Bereich [first,last) in aufsteigender Folge sortiert ist.

void sort (Ran first, Ran last) 
void sort (Ran first, Ran last, Comp comp) 

Beschreibung: Sortiert den Bereich [first,last) in aufsteigender Folge.

void stable_sort (Ran first, Ran last) 
void stable_sort (Ran first, Ran last, Comp comp) 

Beschreibung: Sortiert den Bereich [first,last) in aufsteigender Folge. Die relative Anordnung wertgleicher Elemente bleibt erhalten.

Teilweises Sortieren

For is_sorted_until (For first, For last) 
For is_sorted_until (For first, For last, Comp comp) 

Beschreibung: Liefert den Iterator i auf das Ende des aufsteigend sortierten Teilbereichs [first,i) von [first,last).

void partial_sort (Ran first, Ran middle, Ran last) 
void partial_sort (Ran first, Ran middle, Ran last, Comp comp) 

Beschreibung: Bringt die kleinsten Elemente des Bereiches [first,last) aufsteigend geordnet im Bereich [first,middle) unter.

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) 

Beschreibung: Kopiert die kleinsten Elemente des Bereiches [first,last) aufsteigend geordnet in den Bereich [result_first,result_last).

void nth_element (Ran first, Ran nth, Ran last) 
void nth_element (Ran first, Ran nth, Ran last, Comp comp) 

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

bool is_partitioned (In first, In last, Pred pred) 

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.

For partition (For first, For last, Pred pred) 

Beschreibung: Bringt alle Elemente des Bereiches [first,last), auf die pred(x) zutrifft, nach links, alle anderen nach rechts.

Bi stable_partition (Bi first, Bi last, Pred pred) 

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.

std:pair<Out, Out2> partition_copy (In first, In last, Out good, Out2 bad, Pred pred) 

Beschreibung: Kopiert alle Elemente e des Bereiches [first,last), auf die pred(e) zutrifft, in den durch good angegebenen Bereich, alle anderen nach bad.

For partition_point (For first, For last, Pred pred) 

Beschreibung: Liefert den Iterator hinter das letzte Element x im partitionierten Bereich [first,last), auf welches pred(x) zutrifft.

Mischen

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) 

Beschreibung: Führt zwei aufsteigend sortierte Bereiche [first,last) und [first2,last2) in [result,…) aufsteigend sortiert zusammen.

void inplace_merge (Bi first, Bi middle, Bi last) 
void inplace_merge (Bi first, Bi middle, Bi last, Comp comp) 

Beschreibung: Ordnet die in sich aufsteigend sortierten Bereiche [first,middle) und [middle,last2) so um, dass der gesamte Bereich aufsteigend sortiert ist.

Mengenoperationen

bool includes (In first1, In last1, In2 first2, In2 last2) 
bool includes (In first1, In last1, In2 first2, In2 last2, Comp comp) 

Beschreibung: Ist true, wenn jedes Element des aufsteigend sortierten Bereiches [first2,last2) im aufsteigend sortierten Bereich [first,last) enthalten ist.

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) 

Beschreibung: Schreibt die Vereinigung der beiden sortierten Mengen [first,last) und [first2,last2) sortiert in den Bereich [result,…).

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)  

Beschreibung: Schreibt den Durchschnitt der beiden sortierten Mengen [first,last) und [first2,last2) sortiert in den Bereich [result,…).

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) 

Beschreibung: Kopiert jene Elemente des sortierten Bereichs [first,last), die nicht in [first2,last2) vorkommen, sortiert in den Bereich [result,…).

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) 

Beschreibung: Kopiert jene Elemente, die nur in einem der beiden sortierten Bereiche [first,last) und [first2,last2) vorkommen, sortiert in den Bereich [result,…).

Heapoperationen

bool is_heap (Ran first, Ran last) 
bool is_heap (Ran first, Ran last, Comp comp) 

Beschreibung: Prüft, ob der Bereich [first,last) als Heap geordnet ist.

Ran is_heap_until (Ran first, Ran last) 
Ran is_heap_until (Ran first, Ran last, Comp comp) 

Beschreibung: Liefert den Iterator auf das Ende des als Heap geordneten Teilbereiches von [first,last).

void push_heap (Ran first, Ran last) 
void push_heap (Ran first, Ran last, Comp comp) 

Beschreibung: Fügt das letzte Element des Bereiches [first,last) in den davor liegenden, als Heap geordneten Bereich ein.

void pop_heap (Ran first, Ran last) 
void pop_heap (Ran first, Ran last, Comp comp) 

Beschreibung: Vertauscht *first und *(last-1) des als Heap geordneten Bereiches [first,last) und ordnet den vor dem letzten Element liegenden Teilbereich wieder zu einem Heap um.

void make_heap (Ran first, Ran last) 
void make_heap (Ran first, Ran last, Comp comp) 

Beschreibung: Ordnet den Bereich [first,last) zu einem Heap um.

void sort_heap (Ran first, Ran last) 
void sort_heap (Ran first, Ran last, Comp comp) 

Beschreibung: Sortiert den als Heap vorgegebenen Bereich [first,last) aufsteigend.

Siehe auch

kennen/include/algorithm.txt · Zuletzt geändert: 2019-11-20 14:53 von rrichter