algorithm

全てのアルゴリズムはデータ構造の実装の詳細から切り離されていて、イテレータによってパラメータ化されている。これはアルゴリズムの要件を満たすイテレータを提供しているなら、どのようなデータ構造であっても動作するということを示している。

このヘッダでは、以下の標準ヘッダをインクルードする：

• <initializer_list> (C++11)

テンプレートパラメータ名とイテレータ要件

<algorithm>ヘッダでは、各アルゴリズムのテンプレートパラメータ名を、型の要件を表すために使っている。アルゴリズムを正しく利用するためには、テンプレートパラメータ名に応じたこれらの要件を満たしている必要がある。以下の通りである。

もし「効果」のセクションで、イテレータの値を書き換えるという旨の文章が書かれている場合、その引数の型は mutable iterator の要件を満たしていなければならないという追加の要件がある。 もちろん、output iterator は常に書き換え可能であるため、この追加の要件は無意味である。

テンプレートパラメータ名が Predicate となっている場合、Predicate の値 pred と、引数として渡すイテレータ i について以下の要件を満たす必要がある

• pred(*i) が bool として評価できなければならない。
• pred(*i) 内で *i を書き変えてはならない。

テンプレートパラメータ名が BinaryPredicate となっている場合、BinaryPredicate の値 binary_pred と、引数として渡すイテレータ i1, i2 について以下の要件を満たす必要がある

• binary_pred(*i1, *i2) が bool として評価できなければならない。
• binary_pred(*i1, *i2) 内で *i1 や *i2 を書き変えてはならない。

要素の書き換え操作

関数オブジェクトを使用するアルゴリズムでは、for_eachとfor_each_n以外、プログラム定義の関数に引数として渡された要素を書き換えてはならない。

関数オブジェクトの取り扱い

関数オブジェクトを引数に取る for_each, for_each_n 以外のアルゴリズムは、内部処理においてその関数オブジェクトをコピーする可能性がある。

そのため、アルゴリズムの利用者はそのことに注意する必要がある。コピーされてしまうことが問題である場合、reference_wrapper<T> や同様の解決手段を使ってオブジェクトの中身をコピーしないようなラッパークラスを使うといった対策を行う必要がある。

_copyサフィックス付きアルゴリズム

いくつかのアルゴリズムは _copy というサフィックスが付いている。これは _copy サフィックスの付いていないアルゴリズムと違い、処理の結果を別のイテレータへ出力するアルゴリズムである。

コピーバージョンを含めるかどうかの判断は、通常バージョンの計算量を考慮する。操作を行うコストがコピーのコストを大きく上回る場合、コピーバージョンは含めないようになっている。例えば sort_copy は存在しない。なぜなら、ソートのコストは大きいし、そのような場合、ユーザは copy してから sort するからだ。

イテレータ操作に関する補足

アルゴリズムの説明で + や - を使っているが、random-access iterator 以外のイテレータはそれを定義していない。そういった場合、 a+n というのは

X tmp = a;
advance(tmp, n);
return tmp;

を意味する。また、b-a は

return distance(a, b);

を意味する。

射影とRangeサポート（C++20）

C++20ではアルゴリズム関数の新しいバージョンがstd::ranges名前空間に追加された。従来の関数と比べて以下の点が異なる：

• テンプレート引数がコンセプトによって制約される
• イテレータの組に加えて、範囲(Range)も直接渡せる
• 射影(Projection)をサポートする
• ADLで発見されない

新しいアルゴリズム関数には範囲(Range)を直接渡すことができる。

// 従来のアルゴリズム関数
sort(v.begin(), v.end());
// C++20以降の新しいアルゴリズム関数: Rangeを直接渡せる
ranges::sort(v);
// イテレータ対も渡せる
ranges::sort(v.begin(), v.end());

射影は、述語とは別に渡すことができる関数オブジェクトで、特定のメンバだけを対象にアルゴリズムを実行するために用いる。

例えば、クラス型の配列のソートでは、特定のメンバによってソートしたいことはよくある。しかし、従来のアルゴリズム関数では特定のメンバで比較を行う述語を用意しなければならなかった。

struct Person {
  string name;
  int age = 0;
};

vector<Person> pv = { … };

sort(pv.begin(), pv.end(), [](auto&& a, auto&& b){ return a.name < b.name; });

これは、述語がメンバの選択と比較という2つの仕事をしてしまっている点でよくない。この責務を分割し、メンバの選択だけを行うようにしたものが射影である。

// デフォルトの述語(ranges::less{})で、nameでソート
ranges::sort(pv, {}, [](auto&& a){ return a.name; });
// std::invokeで呼び出されるため、メンバ変数ポインタでもよい
ranges::sort(pv, {}, &Person::name);

なお、各関数の説明においては、射影の影響は無視していることがある。

シーケンスを変更しない操作

foldアルゴリズム

fold操作は、初期値及び累積値とともに範囲の各要素について与えられた関数を適用していき、その結果を返すものである。これは、数値集計処理に特化したaccumulateを改善しより汎用的にしたものである。処理を範囲のどちら側から始めるかによって、foldl（fold_left）とfoldr（fold_right）の2種類がある。

シーケンスを変更する操作

ソートや、それに関連した操作

ここで挙げる操作には全て２つのバージョンがある。一つは Compare 型の関数オブジェクトを取る関数、もう一つは operator< を使用する関数である。

Compare は関数オブジェクト型である。
Compare 型のオブジェクトに適用した関数呼び出しの戻り値は、 bool へ文脈依存の変換をされたとき、第一引数が第二引数より小さい場合は true を、そうでない場合は false を返す。
何らかの順序関係 (ordering relation) を前提とするアルゴリズム全般に対して Compare 型の comp を使用する。
comp は間接参照したイテレータを通して非 const な関数を適用しないものとする。

Compare を取るアルゴリズムには全て、代わりに operator< を使うバージョンもある。
つまり、comp(*i, *j) != false はデフォルトで *i < *j != false である。
二分探索以外のアルゴリズムでは、comp は「狭義の弱順序 (strict weak ordering) 」を示さなければならない。

ここでの用語「狭義 (strict) 」 は非反射関係 (irreflexive relation) (全ての x について !comp(x,x) である）の要求を示し、用語「弱 (weak) 」は全順序 (total ordering) ほど強くはないが半順序 (partial ordering) よりは強い要求を示す。!comp(a, b) && !comp(b, a) として equiv(a, b) を定義する場合、用語「弱」の要求は comp と equiv の両方が以下のように推移的関係 (transitive relations) となることである。

• comp(a, b) && comp(b, c) は comp(a, c) を意味する
• equiv(a, b) && equiv(b, c) は equiv(a, c) を意味する

これらの前提のもと、以下を示すことができる。

• equiv は同値関係 (equivalence relation) である
• comp は equiv によって決まる同値類 (equivalence class) の間での明確な関係を示す
• その示される関係は狭義の全順序 (strict total ordering) である

数学用語の日本語訳として "equivalence relation" には「同値関係」 "equivalence class" には「同値類」が定着しており、同じく数学的な文脈では上記 equiv を満たす２つの値を「同値」 (equivalent) であると言う。しかし特に数学的でない文脈で「同値」と言った場合は operator== による "equal" の関係と誤解される可能性が高いと考えられるため、本サイトでは上記 equiv による "equivalent" の関係を「等価」 operator== による "equal" の関係を「等値」として区別する。

あるシーケンスを指す任意のイテレータ i と、i + n がそのシーケンス上の要素を指す有効なイテレータであるような任意の非負整数 n について、comp(*(i + n), *i) == false であれば、そのシーケンスは比較関数 (comparator) comp によってソートされているという。

あるシーケンス [start,finish) があり、0 <= i < (finish - start) 内の全ての整数 i について、i < n の時かつその時に限り f(*(start + i)) が true となるような整数 n が存在するなら、そのシーケンス [start,finish) は式 f(e) によって区分化されているという。

• 「区分化されている」と「ソートされている」との関係
  あるシーケンスが比較関数 comp でソートされている場合、そのシーケンスは comp に任意の検索キー k を部分適用した式 comp(e, k) や !comp(k, e) などにより区分化されているともいえる。
  例えば、ソートされた整数列 [1, 5, 13, 17, 25] は「 10 より小さい」によって区分化されている。さらに、そのほかの任意の数値についても「～より小さい」あるいは「～より小さくない（～以上）」などによって区分化されているといえる。
  C++03 までの二分探索アルゴリズムは比較関数が狭義の弱順序となることおよび対象シーケンスがその比較関数でソートされていることを要求していた。しかしその後、 C++11 で異なる型のキーによる検索を明示的に許すために制限が見直された結果、比較関数そのものに対する要求はなくなり、比較関数に検索キーを部分適用した式による区分化のみに要求が緩められた。（参照: LWG issue 270 "Binary search requirements overly strict" ）
  これにより、例えばソートされていない整数列 [5, 1, 25, 13, 17] に対しても 10 をキーとして lower_bound() を用いることにより 10 より小さい範囲の境界を取り出すことが可能になっている。しかし 15 をキーとすることは不正である。
  ただ、 C++03 の要件に合わない（特にソートされていない範囲に対する）二分探索を行いたい場合は、同じく C++11 で追加された partition_point() の使用も検討したほうがよい。

順序関係を扱う関数の説明において、この節では安定性 (stability) のような考え方を説明するために同値性 (equivalence) の概念を頻繁に使う。 この節で参照する同値性は必ずしも operator== ではなく、狭義の弱順序によって示される同値関係である。つまりそれは、２つの要素 a と b は !(a < b) && !(b < a) の時かつその時に限り同値とみなされるということである。

ソート

N 番目の要素

二分探索

これらのアルゴリズムは全て二分探索を行う。これらは探索されるシーケンスが検索キーを比較関数（暗黙の operator < 、または明示的に渡された Compare comp ）の引数として部分適用することで得られる式によって区分化されていると仮定している。
これらはランダムアクセスイテレータでない場合でも最小の比較回数で動作する。
これらのアルゴリズムに渡されたイテレータがランダムアクセスイテレータである場合、データ構造を渡るときに対数のステップ数で済むため、このイテレータが適している。ランダムアクセスイテレータでない場合は線形のステップ数になる。

マージ

ソート済み構造に対する集合演算

このセクションでは基本的なソート済み構造に対する集合演算を定義する。
これらの演算は、等価なキーの要素を複数格納できる multiset であっても動作する。集合演算のセマンティクスは、等価なキーの要素が複数あっても、一般化された標準的な方法で演算できるようになっている。
例えば set_union() ならそれぞれの要素の最大数を格納する、set_intersection() なら最小数を格納するといったようになる。

ヒープ

２つのランダムアクセスイテレータ [a,b) の範囲を特定の構造で構築したものをヒープ(heap)と呼ぶ。ヒープには２つの特性がある。

• *a より大きい要素は無い
• *a は、pop_heap() で削除したり、push_heap() で要素を追加する操作が O(log(N)) でできる

これらの特性はプライオリティキューで有用である。
make_heap() は heap の中の範囲を変換し、sort_heap() はソート済みシーケンスの中にあるヒープを turn する。

最小と最大

辞書式比較

三方比較アルゴリズム

順列

アルゴリズムの戻り値型

これらの型は、複数の値を1つの戻り値として返すために使われる汎用的な型である。構造化束縛で受け取ることが想定されている。

関連項目

• <numeric>
  • 数値計算のアルゴリズム

参照

• N2930 Range-Based For Loop Wording (Without Concepts)
• N4821 25 Algorithms library