演算法
演算法是 C++ 標準程式庫的基礎部分。 演算法本身不適用於容器,而是與反覆運算器搭配使用。 因此,相同的演算法可供大部分甚至所有的 C++ 標準程式庫容器使用。 本節討論 C++ 標準程式庫演算法的慣例和術語。
備註
演算法函式範本的描述採用數個速記片語:
「在範圍 [A, B)] 中的片語表示零個或多個離散值的序列,開頭為 A,但不包含 B。範圍只有在從 A 可連線到 B 時有效,您可以將 A 儲存在物件 N (N = A),您可以遞增物件零或多次 (++N),而且物件在有限增量數之後與 B 相等(N == B)。
「範圍 [A, B) 中的每個 N] 片語表示 N 以 A 值開頭,而且會遞增零或多次,直到它等於 B 值為止。案例 N == B 不在範圍內。
片語「在 X 條件下,範圍 [A, B) 中的最小 N 值」表示會為範圍 [A, B) 中的每個 N 指定條件 X,直到符合條件 X 為止。
「範圍 [A, B) 中 N 的最高值,如此 X」表示 X 是針對範圍 [A, B] 中的每個 N 所決定。 函式會在每次符合條件 X 時,將 N 複本儲存在 K 中。 如果發生這類存放區,函式會以 K 的值取代 N 的最終值,其等於 B。不過,如果是雙向或隨機存取反覆運算器,也可能表示 N 以範圍中最高的值開始,而且會遞減到範圍,直到符合條件 X 為止。
X - Y 這類運算式,其中 X 和 Y 可以是隨機存取迭代器以外的迭代器,用於數學領域。 如果函式必須判斷這類值,則函式不一定評估運算符 - 。 這同樣也適用於 X + N 和 X - N,其中 N 是整數類型。
有數種演算法使用會執行 pairwise 比較 (例如與 operator==
) 的述詞來產生 bool
結果。 述詞函式 operator==
(或任何替代項目) 不可變更其任一運算元。 每次評估時,它都必須產生相同的 bool
結果,而且如果任一操作數的複本取代操作數,就必須產生相同的結果。
有數個演算法使用必須對序列中的元素配對強制執行嚴格弱式順序的述詞。 針對述詞述詞(X,Y):
Strict 表示 pred(X, X) 為 false。
弱式表示如果 !pred(X, Y) & & !pred(Y, X) (X == Y 不需要定義)。
訂購表示 pred(X, Y) & pred(Y, Z) 暗示 pred(X, Z)。
其中有些演算法會隱含地使用述詞 X<Y。通常滿足嚴格弱式排序需求的其他述詞為 X>Y、(X、less
Y)和 greater
(X、Y)。 不過請注意,例如 X<= Y 和 X>= Y 等述詞不符合這項需求。
範圍 [First
, ] 中迭代器所指定的元素序列是依運算符<
排序的序列,如果範圍 [0,Last
First
- ] 中的每個 N,以及範圍中每個 M 的序列 (N,First
Last
- ) 述詞 !( Last
*(M) < *(First
+ + First
N)) 是真的。 (請注意,元素會以遞增順序排序。述詞函 operator<
式或其任何取代專案不得改變其任一操作數。 每次評估時,它都必須產生相同的 bool
結果,而且如果任一操作數的複本取代操作數,就必須產生相同的結果。 此外,它必須對它所比較的運算元強制執行嚴格弱式排序。
範圍 [, Last
] 中迭代器所指定的元素序列是依operator<
範圍 [First
1,First
- Last
] 述詞中每個 N 排序的堆積。*First< *(First
+ N)) 為 true。 (第一個專案是最大的。其內部結構只有在樣板函 make_heap
式、 pop_heap
和 push_heap
中才知道。 如同已排序的序列,述詞函 operator<
式或其任何取代,不得改變其操作數之一,而且必須對其比較的操作數施加嚴格的弱式順序。 每次評估時,它都必須產生相同的 bool
結果,而且如果任一操作數的複本取代操作數,就必須產生相同的結果。
C++標準連結庫演演算法位於 <algorithm>
和 <numeric>
頭檔中。