Algorithmen
Algorithmen sind grundlegender Bestandteil der Standardvorlagenbibliothek. Algorithmen können nicht mit Containern selbst sondern mit Iteratoren. Daher kann der gleiche Algorithmus von den meisten verwendet werden wenn nicht alle STL-Container. In diesem Abschnitt werden die Konventionen erläutert und die Terminologie der STL-Algorithmen.
Hinweise
Die Beschreibungen der Algorithmusvorlagenfunktionen stellen einige Kurznotationsausdrücke ein:
Der Ausdruck "im Bereich [A, B)" bedeutet die Sequenz der null oder diskreteren Werte beginnend mit A bis, jedoch nicht einschließlich B. Ein Bereich ist nur gültig, wenn B von A erreichbar ist; Sie können A in einem Objekt N (N = A) speichern, das Objekt null oder mehrmals erhöhen (++N) und das Objekt nach einer endlichen Anzahl von Erhöhungsschritten (N == B*)* gleich B entsprechen lassen.
Der Ausdruck "jedes N im Bereich [A, B)" bedeutet, dass N mit dem Wert A beginnt und null oder mehrmals erhöht wird, bis es gleich dem Wert B ist. Der Fall N == B ist nicht im Bereich.
Der Ausdruck "der niedrigsten Wert von n im Bereich [A, B), sodass X" bedeutet, dass die Bedingung X für jedes N im Bereich bestimmt wird [A, B), bis die X- Bedingung erfüllt ist.
Der Ausdruck "der höchsten Wert von n im Bereich [A, B), sodass X bedeutet, dass jedes X für N im Bereich bestimmt wird [A, B). Die Funktion wird in K eine Kopie von n, wenn die Bedingung erfüllt ist. X Wenn irgend solche Speicher vorkommt, ersetzt die Funktion den endgültigen Wert von n, der B entspricht, durch den Wert von K. Ein oder bidirektional ein Iterator mit wahlfreier Zugriff jedoch kann er auch bedeuten, dass mit N dem Höchstwert im Bereich beginnt und über dem Bereich dekrementiert wird, bis die X- Bedingung erfüllt ist.
Ausdrücke wie X - Y, wobei X und Y Iteratoren anders Iteratoren mit wahlfreier Zugriff sein können, werden im Sinne mathematischen vorgesehen. Die Funktion nicht unbedingt wertet Operator -, wenn sie einen solchen Wert bestimmen muss. Das gilt auch für Ausdrücke wie x + N und X erfüllt - N, wobei n einen ganzzahligen Typ ist.
Einige Algorithmen nutzen ein Prädikat aus, das einen paarweisen Vergleich, wie mit operator== ausführen, um ein Ergebnis auszugeben. bool Die Prädikatfunktion operator== oder kein Ersatz vorhanden, dürfen sich nicht von den Operanden auch nicht ändern. Es muss das gleiche bool Ergebnis führen, wenn es ausgewertet wird, und es muss zum gleichen Ergebnis führen, wenn eine Kopie jedes Operanden für den Operanden ersetzt wird.
Einige Algorithmen nutzen ein Prädikat aus, das eine strenge schwache Sortierung Paare von Elementen aus einer Folge haben muss. Für das Prädikat pr(x, y):
Streng bedeutet dies pr(x, X) ist falsch.
Schwach bedeutet, dass X und Y eine entsprechende Reihenfolge wenn haben!pr(x, y) &&!pr(y, X)(x-== Y muss nicht definiert werden).
Die Festlegung bedeutet dies pr(x, *y) &&*pr(y, Z) bedeutet pr(x, Z).
Einige dieser Algorithmen verwenden implizit das X-Y Prädikat <. Andere Prädikate, die in der Regel der strengen Anforderung von schwacher Sortierung erfüllen, sind, wenigerX-Y > (X, Y) und greater(x, y). Beachten Sie jedoch der Prädikate wie X < = Y X > und Y = dieser Anforderung nicht erfüllen.
Eine Sequenz von Elementen, die von Iteratoren im Bereich [First, Last) festgelegt ist eine Sequenz, die aus dem Operator <, wenn für jedes N im Bereich sortiert wird [0, Last - First) und für jedes M im Bereich (n, Last - First) das Prädikat! (* (First + M < )* (zuerst + N)) gilt. (Beachten Sie, dass die Elemente in aufsteigender Reihenfolge sortiert werden.) Die Prädikatfunktion Operator < oder kein Ersatz für sie, dürfen sich nicht von den Operanden auch nicht ändern. Es muss das gleiche bool Ergebnis führen, wenn es ausgewertet wird, und es muss zum gleichen Ergebnis führen, wenn eine Kopie jedes Operanden für den Operanden ersetzt wird. Darüber hinaus muss sie eine strenge schwache Sortierung den Operanden festlegen, die diese vergleichen.
Eine Sequenz von Elementen, die von Iteratoren im Bereich [First, Last) festgelegt ist ein Heap, der von Operator <, wenn für jedes N im Bereich sortiert wird [1, Last - First) das Prädikat! (* *First < (First + N)) gilt. (Das erste Element ist das Element). Die interne Struktur bezeichnet sonst nur an Vorlagenfunktionen make_heap, pop_heap und push_heap. Wie eine geordnete Sequenz, dürfen sich die Prädikatfunktion Operator < oder kein Ersatz für sie, nicht von den Operanden auch nicht ändern, und sie muss eine genaue schwache Sortierung den Operanden festlegen, die diese vergleichen. Es muss das gleiche bool Ergebnis führen, wenn es ausgewertet wird, und es muss zum gleichen Ergebnis führen, wenn eine Kopie jedes Operanden für den Operanden ersetzt wird.
Die STL-Algorithmen sind in den Headerdateien <algorithm> und <numeric>.