Algorithmen

  • Artikel

Algorithmen sind grundlegender Bestandteil der C++-Standardbibliothek. Algorithmen funktionieren nicht mit Containern selbst, sondern mit Iteratoren. Daher kann der gleiche Algorithmus von den meisten, wenn nicht gar allen, C++-Standardbibliothekcontainern verwendet werden. Dieser Abschnitt beschreibt die Konventionen und die Terminologie von C++-Standardbibliothekalgorithmen.

Hinweise

Die Beschreibungen der Algorithmusfunktionsvorlagen verwenden mehrere Kurzformulierungen:

  • Der Ausdruck "im Bereich [A, B)" bedeutet die Abfolge von null oder mehr diskreten Werten, die mit A bis A beginnen, aber nicht einschließlich B. Ein Bereich ist nur gültig, wenn B von A aus erreichbar ist, Sie können A in einem Objekt N (N = A) speichern, sie können das Objekt null oder mehr Mal (++N) erhöhen und das Objekt nach einer begrenzten Anzahl von Schritten (N == B) gleich B vergleichen lassen.

  • Der Ausdruck "jeder N im Bereich [A, B)" bedeutet, dass N mit dem Wert A beginnt und null oder mehr Mal erhöht wird, bis er dem Wert B entspricht. Der Fall N == B befindet sich nicht im Bereich.

  • Der Ausdruck „der niedrigste Wert von N im Bereich (A, B), sodass X“ bedeutet, dass die Bedingung X für jedes N im Bereich (A, B) bestimmt wird, bis die Bedingung X erfüllt ist.

  • Der Ausdruck "der höchste Wert von N im Bereich [A, B) so, dass X" bedeutet, dass X für jeden N im Bereich [A, B) bestimmt wird. Die Funktion speichert in K eine Kopie von N jedes Mal, wenn die Bedingung X erfüllt ist. Wenn ein solcher Speicher auftritt, ersetzt die Funktion den Endwert von N, der gleich B ist, durch den Wert von K. Bei einem bidirektionalen oder random-access-Iterator kann es jedoch auch bedeuten, dass N mit dem höchsten Wert im Bereich beginnt und über den Bereich dekrementiert wird, bis die Bedingung X erfüllt ist.

  • Ausdrücke wie Y - Y, wobei X und Y andere Iteratoren als solche mit wahlfreiem Zugriff sein können, sind im mathematischen Sinn vorgesehen. Die Funktion wertet den Operator - nicht unbedingt aus, wenn er einen solchen Wert bestimmen muss. Gleiches gilt für Ausdrücke wie X + N und X - N, wobei N ein Ganzzahltyp ist.

Mehrere Algorithmen verwenden ein Prädikat, das einen paarweisen Vergleich vornimmt, wie z. B. mit operator==, um ein bool-Ergebnis auszugeben. Die Prädikatfunktion operator==, oder jeder Ersatz hierfür, darf keinen der beiden Operanden ändern. Es muss jedes Mal, wenn es ausgewertet wird, dasselbe bool Ergebnis liefern, und es muss dasselbe Ergebnis liefern, wenn eine Kopie eines beiden Operanden durch den Operanden ersetzt wird.

Mehrere Algorithmen verwenden ein Prädikat, das eine strikte schwache Sortierung für Elementpaare aus einer Sequenz anwendet. Für das Prädikat Prädikat (X, Y):

  • "Strict" bedeutet, dass "pred(X, X)" falsch ist.

  • Schwach bedeutet, dass X und Y eine entsprechende Sortierung haben, wenn !pred(X, Y) && !pred(Y, X) (X == Y muss nicht definiert werden).

  • Die Sortierung bedeutet, dass pred(X, Y) && pred(Y, Z) pred(X, Z) impliziert.

Einige dieser Algorithmen verwenden implizit das Prädikat X<Y. Andere Prädikate, die in der Regel die strenge schwache Sortieranforderung erfüllen, sind X>Y, less(X, Y) und greater(X, Y). Beachten Sie jedoch, dass Prädikate wie X<= Y und X>= Y diese Anforderung nicht erfüllen.

Eine Sequenz von Elementen, die von Iteratoren im BereichFirst [, ) bezeichnet werden, Lastist eine Sequenz nach Operator < sortiert, wenn, für jeden N im Bereich [0, LastFirst - ) und für jeden M im Bereich (N, Last - First) das Prädikat !( *(M) < *(First + First + N)) ist wahr. (Beachten Sie, dass die Elemente in aufsteigender Reihenfolge sortiert sind.) Die Prädikatfunktion operator<oder eine Ersatzfunktion darf keines seiner Operanden ändern. Es muss jedes Mal, wenn es ausgewertet wird, dasselbe bool Ergebnis liefern, und es muss dasselbe Ergebnis liefern, wenn eine Kopie eines beiden Operanden durch den Operanden ersetzt wird. Darüber hinaus muss sie eine strikte schwache Sortierung für die verglichenen Operanden anwenden.

Eine Abfolge von Elementen, die von Iteratoren im BereichFirst [, ) bezeichnet werden, Lastist ein Heap, nach operator< dem, wenn, für jeden N im Bereich [1, Last - First) das Prädikat !( *First< *(First + N)) ist wahr. (Das erste Element ist die größte.) Seine interne Struktur ist ansonsten nur für die Vorlagenfunktionen make_heapbekannt, pop_heapund push_heap. Wie bei einer geordneten Sequenz darf die Prädikatfunktion operator<oder ein Ersatz dafür keines ihrer Operanden ändern, und sie muss eine strenge schwache Reihenfolge für die zu vergleichenden Operanden auferlegen. Es muss jedes Mal, wenn es ausgewertet wird, dasselbe bool Ergebnis liefern, und es muss dasselbe Ergebnis liefern, wenn eine Kopie eines beiden Operanden durch den Operanden ersetzt wird.

Die C++-Standardbibliotheksalgorithmen befinden sich in den <algorithm> Dateien und <numeric> Headerdateien.

Siehe auch

C++-Standardbibliotheksreferenz
Threadsicherheit in der C++-Standardbibliothek