アルゴリズム
アルゴリズムは、C++ 標準ライブラリの基本的な部分です。 アルゴリズムはコンテナー自体ではなく反復子で動作します。 そのため、C++ 標準ライブラリ コンテナーのすべてではありませんが、そのほとんどで同じアルゴリズムを使用できます。 このセクションでは、C++ 標準ライブラリ アルゴリズムの規則と用語について説明します。
解説
アルゴリズム関数テンプレートの説明には、いくつかの短縮句が使用されています。
"[A, B)" という語句は、A で始まる 0 個以上の不連続値のシーケンスを意味最大B。範囲は、B が A から到達可能な場合にのみ有効です Aをオブジェクト N (N = A) に格納し、オブジェクトを 0 回以上インクリメントし (++N)、有限のインクリメント (N == B 後にオブジェクトを B と等しく比較できます。
"各 N 範囲 [A, B)" という語句は、 N が値 A で始まり、値が B になるまで 0 回以上インクリメントされることを意味。ケース N == B が範囲内にありません。
"X のような範囲 [A, B の最小値 N)" という語句は、条件 X が満たされるまで、範囲 [A, B) 内の各 N に対して、条件 X が判断されるという意味です。
"N の最大値範囲 [A, B) の中で、X" という語句は、範囲 [A, B) のXがNごとに決定されることを意味します。 関数は、条件 X が満たされるたびに K に N のコピーを格納します。 このように格納されると、関数は B に等しい N の最終的な値を K の値に置き換えます。ただし、双方向アクセス反復子またはランダム アクセス反復子の場合は、N が範囲内の最大値から始まり、条件 X が満たされるまでその範囲でデクリメントされることを意味する場合もあります。
X - Y のような式 (ここで X と Y はランダム アクセス反復子以外の反復子にすることができます) は、数学的な意味で使用されます。 このような値を決定する必要がある場合、関数は必ずしも演算子 - を評価するとは限りません。 X + N および X - N (ここで、Nは整数型) などの式にも同じことが当てはまります。
いくつかのアルゴリズムでは、bool の結果が得られるように operator== を使用するようなペアの比較を実行する述語を使用します。 述語関数 operator==、または、それに変わる関数では、どちらのオペランドも変更されません。 評価されるたびに同じ bool 結果が得られ、いずれかのオペランドのコピーがオペランドに置き換わる場合は、同じ結果が得られる必要があります。
いくつかのアルゴリズムでは、厳密弱順序をシーケンスの要素のペアに強制する述語を使用します。 述語 pred(X, Y) の意味は、次のとおりです。
厳密とは、pred(X, Y) が false であることを意味します。
弱い X と Y !pred(X, Y) &pred(Y, X) (X == Y を定義する必要はありません)。
順序付けとは、 pred(X, Y) & pred(Y, Z) は、 pred(X, Z) を意味します。
これらのアルゴリズムの一部は、暗黙的に述語 X<Y を使用します。通常、厳密弱順序要件に適合するその他の述語は X>Y、less(X, Y)、および greater(X, Y) です。 ただし、 X<= Y や X>= Y などの述語は この要件を満たしていません。
範囲 [0, Last - First) 内の各 N および範囲 (N, Last - First) の各 M に対し、述語 !(*(First + M) < *(First + N)) が true の場合、範囲 [First, Last) 内で反復子によって指定された要素のシーケンスは、演算子 < で順序付けられたシーケンスです。 (要素は昇順で並べ替えられていることに注意してください)。述語関数 operator<、またはその代わりの関数は、どちらのオペランドも変更しないでください。 評価されるたびに同じ bool 結果が得られ、いずれかのオペランドのコピーがオペランドに置き換わる場合は、同じ結果が得られる必要があります。 さらに、比較するオペランドに対して厳密弱順序を適用する必要があります。
範囲 [1, Last - First) の各 N に対し、述語 !(*First< *(First + N)) が true の場合、範囲 [First, Last) 内の反復子で指定された要素のシーケンスは、operator< によって順序付けられたヒープです。 (最初の要素は最大です)。それ以外の場合、その内部構造は、テンプレート関数 make_heap、 pop_heap、および push_heapにのみ認識されます。 順序付けられたシーケンスと同様、述語関数 operator<、または、それに代わる関数では、そのどちらのオペランドも変更できません。さらに、比較するオペランドに対して厳密弱順序を強制します。 評価されるたびに同じ bool 結果が得られ、いずれかのオペランドのコピーがオペランドに置き換わる場合は、同じ結果が得られる必要があります。
C++ 標準ライブラリ アルゴリズムは、<algorithm> および <numeric> ヘッダー ファイルにあります。