アルゴリズム

  • [アーティクル]

アルゴリズムは、C++ 標準ライブラリの基本的な部分です。 アルゴリズムはコンテナー自体ではなく反復子で動作します。 そのため、C++ 標準ライブラリ コンテナーのすべてではありませんが、そのほとんどで同じアルゴリズムを使用できます。 このセクションでは、C++ 標準ライブラリ アルゴリズムの規則と用語について説明します。

解説

アルゴリズム関数テンプレートの説明には、いくつかの短縮句が使用されています。

  • "範囲 [A, B)" の語句は、A から始まる 0 個以上の不連続値のシーケンスを意味しますが、B は含まれません。範囲は、B が A から到達可能で、A をオブジェクト N (N = A) に格納でき、オブジェクトを 0 回以上インクリメントでき (++N)、オブジェクトを有限の増分数 (N == B) の後に B と等しく比較する場合にのみ有効です。

  • "範囲 [A, B) の各 N" という語句は、N が値 A で始まり、値 B に等しくなるまで 0 回以上インクリメントされることを意味します。ケース N == B が範囲内にありません。

  • "X のような範囲 [A, B の最小値 N)" という語句は、条件 X が満たされるまで、範囲 [A, B) 内の各 N に対して、条件 X が判断されるという意味です。

  • 「範囲[A,B)においてNの最大値がXになるように」という語句は、範囲[A,B]のNごとにXが決定されることを意味する。 関数は、条件 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> ヘッダー ファイルにあります。

関連項目

C++ 標準ライブラリ リファレンス
C++ 標準ライブラリ内のスレッド セーフ