Algorithms
Algorithmen sind ein grundlegender Bestandteil der Standardvorlagenbibliothek.Algorithmen können nicht mit Containern selbst, sondern mit Iteratoren.Deshalb kann derselbe Algorithmus durch die meisten wenn nicht alle STL-Container verwendet werden.In diesem Abschnitt werden die Konventionen und die Terminologie der STL-Algorithmen.
Hinweise
Die Beschreibungen der Algorithmus von Funktionen stellen einige Ausdrücke Kurznotations ein:
Der Begriff „im Bereich [A, B)“ bedeutet die Reihenfolge der die keine oder diskreteren Werte, die mit A bis einschließlich Bjedoch nicht starten *.*Ein Bereich ist nur gültig, wenn B von A erreichbar ist . Sie können A in einem Objekt N speichern (N = A)das Objekt keine oder mehrere ++N (Mal inkrementiert) und das Objekt B nach einer begrenzten Anzahl der N-== Inkrementen (b) vergleichen können.
Der Begriff „jedes N im Bereich [A, B)“ bedeutet, dass N mit dem Wert Null beginnt und A oder mehrmals erhöht wird, bis er dem Wert *" b "*entspricht *.*Im Fall N-==B befindet sich nicht im Gültigkeitsbereich.
Der Begriff „der niedrigsten Wert von N im Bereich [A, *B)*so, dass X“ bedeutet, dass die Bedingung x für jedes N im Bereich festgelegte [A, *B),*bis die Bedingung X erfüllt ist.
Der Begriff „der höchsten Wert von N im Bereich [A, *B)*so, dass die X- bedeutet, dass die X- für jedes N im Bereich festgelegte [A, B).Die Funktion speichert in K eine Kopie von N, wenn die Bedingung erfüllt ist. XWenn irgend solcher Speicher auftritt, ersetzt die Funktion den endgültigen Wert N, Bentspricht, um den Wert von K.Bei einem das bidirektionale oder einen Iterator mit wahlfreier kann jedoch auch den Zugriff darauf hinweisen, dass N mit dem höchsten Wert im Bereich beginnt und über dem Bereich verringert wird, bis die Bedingung X erfüllt ist.
Ausdrücke wie X - Y, wobei X und Y Iteratoren Gegensatz zu Iteratoren mit wahlfreier Zugriff sein können, sind in mathematischen Sinn vorgesehen.Die Funktion wertet weder Operator- aus, wenn sie einen solchen Wert bestimmen müssen.Das gleiche Verfahren kann auch für Ausdrücke wie X + N und XTrue - n, wobei N ein Integer-Typ ist.
Einige Algorithmen verwenden ein Prädikat, das einen Vergleich wie mit paarweisen **operator==**ausführt, um ein bool Ergebnis zu erzielen.Die Prädikatfunktion **operator==**oder kein Ersatz für sie dürfen nicht aus seinen Operanden auch nicht ändern.Es muss das gleiche bool Ergebnis führen, wenn es jedes Mal ausgewertet werden, und er muss das gleiche Ergebnis führen, wenn eine Kopie jedes Operanden für den Operanden ersetzt wird.
Einige Algorithmen verwenden ein Prädikat, das eine strikte schwache Sortierung Paare von Elementen aus einer Sequenz auferlegen 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( X,Y)(x-==Y muss nicht definiert werden soll).
Die Einrichtung bedeutet dies pr(X, Y) && pr(Y, Z) bedeutet pr(X, Z).
Einige dieser Algorithmen verwenden implizit das Prädikat XY< *.*Andere Prädikate, die in der Regel der strengen Anforderung der schwachen Sortierung erfüllen, werden > XY, kleiner(X, *Y)*und greater(X, Y).Beachten Sie jedoch, wie Prädikate dem XY >= X und Y <= dieser Anforderung nicht erfüllen.
Eine Sequenz von Elementen, die von Iteratoren im Bereich [First, Last) festgelegt wird, ist eine Sequenz von**<**-Operator, wenn für jedes N im Bereich [0, wird Last - First) und für jedes im Bereich ( nLast, N - First) das Prädikat! (* (First + M)* (<zuerst + N)) ist true.(Beachten Sie, dass die Elemente in aufsteigender Reihenfolge sortiert ist). Die Prädikatfunktion **operator<**oder kein Ersatz für sie dürfen sich nicht auf seinen Operanden auch nicht ändern.Es muss das gleiche bool Ergebnis führen, wenn es jedes Mal ausgewertet werden, und er muss das gleiche Ergebnis führen, wenn eine Kopie jedes Operanden für den Operanden ersetzt wird.Darüber hinaus muss sie eine strikte schwache Sortierung der Operand auferlegen, die verglichen werden.
Eine Sequenz von Elementen, die von Iteratoren im Bereich [First, Lastist ein Heap) festgelegt wird, der von operator< , wenn für jedes N im Bereich [1, wird Last - First) das Prädikat! (*First < + *N)*First (*) ist true.(Das erste Element ist der größte). Die interne Struktur ist nur für andernfalls make_heap, Funktionen und Vorlagen pop_heappush_heap.Wie eine geordnete Sequenz, dürfen sich der Prädikatfunktion **operator<**oder kein Ersatz für sie auch nicht von seinen Operanden nicht geändert werden, und sie muss eine strikte schwache Sortierung der Operand auferlegen, die verglichen werden.Sie müssen das gleiche bool Ergebnis führen, wenn er ausgewertet wird. Sie muss das gleiche Ergebnis führen, wenn eine Kopie jedes Operanden für den Operanden ersetzt wird.
Die STL-Algorithmen sind in den <algorithm> und <numeric> Headerdateien.