C++-Programmierung/ Die STL/ Algorithmen

Algorithmen

Zielsetzung

Die Algorithmen der C++ Standardbibliothek sind mächtige Werkzeuge, die aus Funktionen aufgebaut sind und numerische oder generelle Verarbeitung von Sequenzen ermöglichen. Diese Sequenzen sind durch einen Start/End-Iterator oder selten einen Start-Iterator und eine Anzahl definiert.

Die Algorithmen sind für den Einsatz mit den Standardcontainern der Standardbibliothek konzipiert, müssen aber nicht so verwendet werden, da sie ausschließlich Sequenzen verarbeiten, die durch Iteratoren dargestellt werden.

Einfach ausgedrückt: Standardcontainer, Funktionsobjekte, Prädikatoren, Iteratoren (...) sind für sich alleine wunderbare Konzepte, aber nur mit den richtigen Algorithmen ergeben sie überhaupt einen Sinn. Wenn Daten gesammelt und gespeichert werden, soll höchstwahrscheinlich auch irgendwann etwas damit gemacht werden. Um diese Verwendung zu vereinfachen und nach Möglichkeit fehleranfällige selbstgebaute Schleifen zu vermeiden, bietet die Standardbibliothek vorgefertigte Algorithmen an.

Intervalle, Sequenzen und Bereiche

Im folgenden werden Intervalle, bzw. Bereiche zwischen Iteratoren Sequenzen genannt und in Textschreibweise dargestellt. Eckige Klammern bezeichnen dabei Bereiche einschließlich der Grenzwerte, runde Klammern Intervalle ausschließlich der Grenzwerte. [a, b) ist also ein Intervall, das a enthält und b nicht. Diese Schreibweise ist in der Mathematik und in Referenzwerken zu C++ üblich, daher wird sie auch hier verwendet. In der Standardbibliothek ist eine Sequenz ein Abschnitt, der durch einen Startiterator und Enditerator begrenzt wird, der Enditerator ist jedoch meistens das erste Element hinter dem letzten Wert der Sequenz!

Referenz

Function for_each(InputIterator first, InputIterator last, Function f);

Die Funktion f wird auf alle Elemente in [first,last) angewandt. Der allgemeinste Algorithmus.

Zählen/Finden/Vergleichen

void count(InputIterator first, InputIterator last, const T& value, Size& n);

Zählt akkumulierend die Vorkommen eines Werts. Addiert auf n die Anzahl der Elemente in [first,last), die den Wert value haben.

void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n);

Zählt akkumulierend das Erfülltsein eines Prädikats. Addiert auf n die Anzahl der Elemente in [first,last), für die pred den Wert true hat.

ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);

Findet Paare gleicher aufeinanderfolgender Elemente. Liefert den ersten Iterator i in [first,last-1), so dass *i==*(i+1).

ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate bpred);

Wie die erste Instanz, nur dass die Paare nicht durch ==, sondern über das Prädikat bestimmt werden, also über bpred(*i,*(i+1))==true.

InputIterator find(InputIterator first, InputIterator last, const T &value);

Liefert einen Iterator auf das erste Element in [first,last), das den Wert value hat.

InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

Liefert einen Iterator auf das erste Element in [first,last), für das pred den Wert true hat.

InputIterator search_n*(InputIterator first, InputIterator last, Size n, const T &value);

Sucht nach einer Untersequenz aus n Vorkommen des Werts value und liefert einen Iterator auf das erste der n Elemente.

pair<InputIterator1,InputIterator2> mismatch(InputIterator first1, InputIterator1 last1, InputIterator first2);

Vergleicht paarweise die Sequenzen [first1,last1) und [first2,first2+(last1-first1)). Gibt ein Paar von Iteratoren für das erste ungleiche Elementpaar zurück. Sind die beiden Sequenzen komplett gleich, zeigen die zurückgegebenen Iteratoren hinter die Sequenzen.

pair<InputIterator1,InputIterator2> mismatch(InputIterator first1, InputIterator1 last1, InputIterator first2, BinaryPredicate bpred);

Wie die erste Instanz, nur dass gleiche Paare nicht durch == bestimmt werden, sondern über bpred(*i,*(i+1))==true.

bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator first2);

Liefert true genau dann, wenn die Sequenzen [first1,last1) und [first2,first2+(last1-first1)) elementweise gleich sind.

bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator first2, BinaryPredicate bpred);

Wie die erste Instanz, nur dass statt == das binäre Prädikat bpred benutzt wird.

ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2);

Sucht die erste Stelle in [first1,last1), ab der [first2,first2+(last1-first1)) als Untersequenz in [first1,last1) vorkommt. Gibt es keine solche Stelle, wird last1 zurückgegeben.

ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate bpred);

Wie die erste Instanz, nur dass für eine Untersequenz nicht elementweise ==, sondern das binäre Prädikat bpred erfüllt sein muss.

ForwardIterator1 find_end*(ForwardIterator1 first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2);

Wie search, liefert aber das letzte Vorkommen der zweiten Sequenz als Untersequenz in der ersten.

ForwardIterator1 find_end*(ForwardIterator1 first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate bpred);

Wie die erste Instanz, nur dass für eine Untersequenz nicht elementweise ==, sondern das binäre Prädikat bpred erfüllt sein mu&szlig.

ForwardIterator1 find_first_of*(ForwardIterator1 first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2);

Liefert einen Iterator auf das erste Element in [first1,last1), das auch in [first2,first2+(last1-first1)) vorkommt.

ForwardIterator1 find_first_of*(ForwardIterator1 first1, ForwardIterator last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate bpred);

Wie die erste Instanz, nur dass das Erfülltsein von bpred für ein Elementpaar ausschlaggebend ist.

Kopieren

OutputIterator copy(InputIterator first1, InputIterator last1, OutputIterator first2);

Kopiert die Sequenz [first1,last1) auf die Sequenz [first2,first2+(last1-first1)). Die Sequenzen werden dabei von links nach rechts durchlaufen. Es wird first2+(last1-first1) zurückgeliefert. Vorsicht: wenn first2 ein Element von [first1,last1) ist, sollte man die Funktion copy_backward benutzen, wenn die Zielsequenz in [first1,last1) liegt muss man es.

BidirectionalIterator2 copy_backward(BidirectionalIterator1 first1, BidirectionalIterator1 last1, BidirectionalIterator2 last2);

Kopiert die Sequenz [first1,last1) auf die Sequenz [last2-(last1-first1),last2). Die Sequenzen werden dabei von rechts nach links durchlaufen. Es wird last2-(last1-first1) zurückgeliefert.

Transformieren

OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unop);

Transformiert die Elemente aus [first,last) durch Anwendung von unop und schreibt sie nach [result,result+(last-first)). Liefert result+(last-first) zurück.

OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binop);

Kombiniert je ein Element aus [first1,last1) und [first2,first2+(last1-first1)) über binop und schreibt das Ergebnis nach [result,result+(last-first)). Liefert result+(last-first) zurück.

Ersetzen

void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);

Ersetzt in [first,last) jedes Vorkommen von old_value durch new_value.

void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);

Ersetzt in [first,last) jedes Element, das pred erfüllt, durch den Wert new_value.

OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value);

Kopiert die Sequenz [first,last) nach [result,result+(last-first)), wobei aber alle Vorkommen des Werts old_value durch den Wert new_value ersetzt werden. Gibt result+(last-first) zurück.

OutputIterator replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);

Kopiert die Sequenz [first,last) nach [result,result+(last-first)), wobei alle Elemente, die das Prädikat pred erfüllen, durch den Wert new_value ersetzt werden.

Füllen

void fill(ForwardIterator first, ForwadIterator last, const T& value);

Überschreibt alle Elemente in [first,last) mit dem Wert value.

OutputIterator fill_n(OutputIterator first, Size n, const T& value);

Überschreibt die n Elemente in [first,first+n) mit dem Wert value. Gibt first+n zurück.

void generate(ForwardIterator first, ForwardIterator last, Generator gen);

Ruft das parameterlose Funktions-Objekt gen auf und überschreibt alle Elemente in [first,last) mit dem zurückgegebenen Wert.

OutputIterator generate_n(OutputIterator first, Size n, Generator gen);

Überschreibt die n Elemente in [first,first+n) mit dem von gen zurückgegebenen Wert. Gibt first+n zurück.

Entfernen

ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);

Entfernt aus [first,last) alle Elemente mit dem Wert value. Gibt einen Iterator hinter die gekürzte Sequenz zurück.

ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);

Entfernt aus [first,last) alle Elemente, die das Prädikat pred erfüllen. Gibt einen Iterator hinter die gekürzte Sequenz zurück.

OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);

Entfernt durch Kopieren, d.h. ohne die Quellsequenz zu verändern. Kopiert die Elemente aus [first,last), die nicht den Wert value haben, in eine zusammenhängende Sequenz ab result. Gibt einen Iterator hinter die resultierende Sequenz zurück.

OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);

Wie remove_copy, kopiert aber die Elemente, die das Prädikat pred nicht erfüllen.

ForwardIterator unique(ForwardIterator first, ForwardIterator last);

Entfernt aus allen Untersequenzen von [first,last), die aus gleichen Elementen bestehen, jeweils alle Elemente bis auf das erste.

ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate bpred);

Entfernt aus allen Untersequenzen von [first,last), für die für aufeinanderfolgende Elemente bpred erfüllt ist, alle Elemente außer dem ersten.

OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result);

Entfernt doppelte durch Kopieren. Kopiert von [first,last) in eine Sequenz ab result, wobei von mehreren aufeinanderfolgenden gleichen Elementen nur das erste übernommen wird.

OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate bpred);

Kopiert von [first,last) in eine Sequenz ab result, wobei von Untersequenzen, in denen aufeinanderfolgende Elemente bpred erfüllen, nur jeweils das erste Element übernommen wird.

Reihenfolge ändern

void swap(T& a, T& b);

Vertauscht zwei Elemente.

void iter_swap(ForwardIterator1 a, ForwardIterator2 b);

Vertauscht zwei Elemente über Iteratoren auf sie.

ForwardIterator2 swap_ranges(ForwardIterator first1, ForwardIterator last1, ForwardIterator2 first2);

Vertauscht die Elemente der Sequenzen [first1,last1) und [first2,first2+(last1-first1)). Es wird first2+(last1-first1) zurückgeliefert. Das Ergebnis ist nicht definiert, wenn sich die beiden Sequenzen überlappen.

void reverse(BidirectionalIterator first, BidirectionalIterator last);

Kehrt die Reihenfolge in der Sequenz [first,last) durch Vertauschungen um.

OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);

Kopiert [first,last) nach [result,result+(last-first)) in umgekehrter Reihenfolge.

void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);

Voraussetzung: first<=middle<=last. Rotiert die Elemente in [first,last) um last-middle Positionen nach rechts. Die Sequenzen [first,middle) und [middle,last) tauschen dabei also die Plätze.

OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);

Rotiert durch Kopieren. Kopiert [middle,last) nach [result,result+(last-middle)) und [first,middle) nach [result+(last-middle),result+(last-first)).

void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);

Permutiert die Elemente in [first,last) pseudo-zufällig durch last-first-1 Vertauschungen.

void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand);

Wie die erste Instanz, wobei die Vertauschungen durch das Funktions-Objekt rand bestimmt werden. Es erhält RandomAccessGenerator::distance_type n als Parameter und muss einen pseudo-zufälligen Wert in [0,n-1] liefern.

BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

Partitioniert [first,last) so, dass hinterher alle Elemente, die pred erfüllen, vor all denen stehen, die pred nicht erfüllen.

BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

Wie partition, aber die relative Ordnung innerhalb der beiden Teile bleibt erhalten.

Sortieren

Es gibt fast alle Operationen in Paaren, von denen die erste für die Ordnung auf dem Grundtyp T mit dem Operator < arbeitet, die zweite mit einem zweistelligen Prädikat Compare. Compare repräsentiert eine vollständige Ordnung in Form von <, nicht <=. Mit not(a<b) and not(b<a) kann auf Gleichheit getestet werden.

void sort(RandomAccessIterator first, RandomAccessIterator last);

Sortiert [first,last) mit etwa der Ordnung O(n·log n) unter Verwendung von T<T für die Vergleiche.

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Sortiert [first,last) mit etwa der Ordnung O(n·log n) unter Verwendung von comp für die Vergleiche.

void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

Sortiert [first,last) mit < und erhält die relative Reihenfolge gleicher Elemente. Es wird ca. O(n·log n) oder bei Speichermangel O(n·log2 n) Zeit benötigt.

void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);

Die ersten middle-first Elemente aus [first,last) werden nach [first,middle) sortiert. Die restlichen Elemente landen in unbestimmter Reihenfolge in [middle,last).

void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);

Sortiert die ersten m:=min(last-first,result_last-result_first) Elemente und schreibt sie nach [result_first,result_first+m). Es wird result_first+m zurückgegeben. Benötigt ca. (last-first)·log m Vergleiche.

RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

Tauscht das Element nach *nth, das nach vollständiger Sortierung von [first,last) dort stehen würde. Außerdem sind nachher alle Elemente in [first,nth) kleiner als alle Elemente in [nth,last).

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

Suchen

Alle Algorithmen arbeiten zwar auch mit Vorwärts-Iteratoren, benötigen dazu aber O(n), da sie ggf. wieder links neu aufsetzen müssen. Mit Random-Access-Iteratoren wird nur O(log n) benötigt.

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

Liefert einen Iterator auf die erste Position in [first,last), in die der Wert value eingefügt werden könnte, ohne die Ordnung zu verletzen.

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);

Liefert einen Iterator auf die letzte Position in [first,last), in die der Wert value eingefügt werden könnte, ohne die Ordnung zu verletzen.

ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

pair<ForwardIterator,ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value);

Liefert begrenzende Iteratoren für die größte Untersequenz von [first,last), in die value an jede Stelle eingefügt werden könnte, ohne die Ordnung zu verletzen.

pair<ForwardIterator,ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);

Liefert true genau dann, wenn es in [first,last) ein Element mit dem Wert value gibt. (Gleichheit wird wie üblich über not(a<b) and not(b<a) bestimmt.)

bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

Verschmelzen

OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator last);

Verschmilzt zwei sortierte Sequenzen [first1,last1) und [first2,last2) in eine Sequenz ab last. Elemente aus der ersten Sequenz erscheinen dabei immer vor gleichen Elementen aus der zweiten Sequenz. Die Quellsequenzen dürfen sich nicht überlappen.

OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);

Verschmilzt die aufeinanderfolgenden sortierten Sequenzen [first,middle) und [middle,last) zu einer sortierten Sequenz [first,last). Elemente aus der ersten Sequenz erscheinen dabei vor gleichen Elementen aus der zweiten Sequenz. Es wird normalerweise O(n), bei Speichermangel O(n·log n) Zeit benötigt.

void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

Mengen-Operationen auf sortierten Sequenzen

bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

Test: [first2,last2) Teilmenge von [first1,last1) unter Verwendung von operator <.

bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);

Test: [first2,last2) Teilmenge von [first1,last1) unter Verwendung von comp.

OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

Bildet die sortierte Vereinigung von [first1,last1) und [first2,last2) und schreibt sie in eine Sequenz ab result. Bei mehrfach vorkommenden Elementen wird das erste aus der ersten Sequenz übernommen.

OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

Bildet die sortierte Schnittmenge von [first1,last1) und [first2,last2) und schreibt sie in eine Sequenz ab result. Es wird immer das jeweilige Element aus der ersten Sequenz übernommen.

OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

Bildet die sortierte Mengendifferenz [first1,last1) \ [first2,last2) und schreibt sie in eine Sequenz ab result.

OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

Bildet die sortierte symmetrische Mengendifferenz ([first1,last1) vereinigt [first2,last2)) \ ([first1,last1) geschnitten first2,last2)) und schreibt sie in eine Sequenz ab result.

OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

Heap-Operationen

Ein Heap ist eine speziell organisierte Sequenz. Das vorderste Element ist immer das größte. Es kann mit pop_heap so entfernt werden, dass die resultierende Sequenz wieder ein Heap ist. Mit push_heap kann ein beliebiges Element so eingefügt werden, dass wieder ein Heap entsteht. Beide Operationen benötigen nur O(log n) Zeit. Eine normale Sequenz muss zunächst mit make_heap umgewandelt werden.

void make_heap(RandomAccessIterator first, RandomAccessIterator last);

Wandelt die Sequenz [first,last) in einen Heap um.

void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

void push_heap(RandomAccessIterator first, RandomAccessIterator last);

Fügt das Element *(last-1) in den Heap [first,last-1) ein. Der resultierende Heap ist [first,last).

void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

void pop_heap(RandomAccessIterator first, RandomAccessIterator last);

Vertauscht *first und *(last-1), so dass [first,last-1) wieder ein Heap wird.

void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

Sortiert den Heap [first,last). Die relative Reihenfolge gleicher Elemente bleibt nicht erhalten.

void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

Weitere Operationen

ForwardIterator min_element(ForwardIterator first, ForwardIterator last);

Liefert einen Iterator auf das erste Element in [first,last), für das es kein kleineres gibt.

ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

ForwardIterator max_element(ForwardIterator first, ForwardIterator last);

Liefert einen Iterator auf das erste Element in [first,last), für das es kein größeres gibt.

ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

Liefert true genau dann, wenn die Sequenz [first1,last1) bezüglich < lexikographisch kleiner ist als die Sequenz [first2,last2).

bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

Erzeugt die nächste Permutation der Sequenz [first,last) in der lexikographischen Ordnung auf den Permutationen, die durch < auf den Elementen induziert wird. Gibt genau dann false zurück, wenn die letzte Permutation erreicht war, und transformiert die Sequenz in die erste Permutation.

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

Wie next_permutation, erzeugt aber die vorherige Permutation.

bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

Wie die erste Instanz, unter Benutzung von comp statt operator <.

Numerische Operationen

T accumulate(InputIterator first, InputIterator last, T init);

Summiert init und die Elemente in [first,last) mit +.

T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binop);

Wie die erste Instanz, nur dass binop statt + verwendet wird.

T inner_product(InputIterator first1, InputIterator last1, InputIterator first2, T init);

Berechnet ein Skalarprodukt. Liefert init plus die Summe der Produkte gleichpositionierter Elemente in [first1,last1) und [first2,last2).

T inner_product(InputIterator first1, InputIterator last1, InputIterator first2, T init, BinaryOperation1 plus, BinaryOperation times);

Wie die erste Instanz, nur dass plus statt + und times statt * verwendet wird.

OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result);

Füllt [result,result+(last-first)) mit den Partialsummen der Elemente aus [first,last), d.h. *result=*first, *(result+1)=*first+*(first+1), etc. Die beiden Sequenzen dürfen gleich sein.

OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binop);

Wie die erste Instanz, nur dass binop statt + verwendet wird. OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);

Füllt [result+1,result+(last-first) mit den Differenzen aufeinanderfolgender Elemente aus [first,last), also *(result+1)=*(first+1)-*first, etc.

OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binop);

Wie die erste Instanz, nur dass binop statt - verwendet wird.