algorithm.md

algorithm

• algorithm[meta header]

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

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

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

テンプレートパラメータ名	要件
InputIterator InputIterator1 InputIterator2	input iterator
OutputIterator OutputIterator1 OutputIterator2	output iterator
ForwardIterator ForwardIterator1 ForwardIterator2	forward iterator
BidirectionalIterator BidirectionalIterator1 BidirectionalIterator2	bidirectional iterator
RandomAccessIterator RandomAccessIterator1 RandomAccessIterator2	random-access iterator

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

いくつかのアルゴリズムは _copy というサフィックスが付いている。これは _copy サフィックスの付いていないアルゴリズムと違い、処理の結果を別のイテレータへ出力するアルゴリズムである。コピーバージョンを含めるかどうかの判断は、通常バージョンの計算量を考慮する。操作を行うコストがコピーのコストを大きく上回る場合、コピーバージョンは含めないようになっている。例えば sort_copy は存在しない。なぜなら、ソートのコストは大きいし、そのような場合、ユーザは copy してから sort するからだ。

テンプレートパラメータ名が 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 以外のアルゴリズムは、その関数オブジェクトを自由にコピーしても構わない。そのため、アルゴリズムの利用者はそのことに注意する必要がある。コピーされてしまうことが問題である場合、reference_wrapper<T> や同様の解決手段を使ってオブジェクトの中身をコピーしないようなラッパークラスを使うといった対策を行う必要がある。

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

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

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

return distance(a, b);

を意味する。

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

• <initializer_list> (C++11)

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

名前	説明	対応バージョン
all_of	全ての要素が条件を満たしているかを調べる	C++11
any_of	どれかの要素が条件を満たしているかを調べる	C++11
none_of	全ての要素が条件を満たしていないかを調べる	C++11
for_each	全ての要素に対して処理を行う
for_each_n	範囲の先頭N個の要素に対して処理を行う	C++17
find	指定された値を検索する
find_if	条件を満たす最初の要素を検索する
find_if_not	条件を満たしていない最初の要素を検索する	C++11
find_end	指定された最後のサブシーケンスを検索する
find_first_of	ある集合の1つとマッチする最初の要素を検索する
adjacent_find	隣接する要素で条件を満たしている最初の要素を検索する
count	指定された値である要素の数を数える
count_if	条件を満たしている要素の数を数える
mismatch	2つの範囲が一致していない場所を検索する
equal	2つの範囲を等値比較する
search	指定された最初のサブシーケンスを検索する
search_n	指定された最初のサブシーケンスを検索する

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

名前	説明	対応バージョン
copy	指定された範囲の要素をコピーする
copy_n	指定された数の要素をコピーする	C++11
copy_if	条件を満たす要素のみをコピーする	C++11
copy_backward	指定された範囲の要素を後ろからコピーする
move	指定された範囲の要素をムーブする	C++11
move_backward	指定された範囲の要素を後ろからムーブする	C++11
swap_ranges	指定された2つの範囲同士を swap する
iter_swap	2つのイテレータの要素を swap する
transform	全ての要素に関数を適用する
replace	指定された値と一致する要素を指定された値に置き換える
replace_if	条件を満たす要素を指定された値に置き換える
replace_copy	指定された値を一致する要素を指定された値に置き換え、その結果を出力の範囲へコピーする
replace_copy_if	条件を満たす要素を指定された値に置き換え、その結果を出力の範囲へコピーする
fill	指定された値で出力の範囲に書き込む
fill_n	指定された値で出力の範囲に n 個書き込む
generate	出力の範囲へ関数の結果を書き込む
generate_n	出力の範囲へ関数の結果を n 個書き込む
remove	指定された要素を除ける
remove_if	条件を満たす要素を除ける
remove_copy	指定された要素を除け、その結果を出力の範囲へコピーする
remove_copy_if	条件を満たす要素を除け、その結果を出力の範囲へコピーする
unique	重複した要素を除ける
unique_copy	重複した要素を除け、その結果を出力の範囲へコピーする
reverse	要素の並びを逆にする
reverse_copy	要素の並びを逆にし、その結果を出力の範囲へコピーする
rotate	要素の並びを回転させる
rotate_copy	要素の並びを回転させ、その結果を出力の範囲へコピーする
shift_left	要素を左にシフトさせる	C++20
shift_right	要素を右にシフトさせる	C++20
sample	範囲から指定された個数の要素をランダムに抽出する	C++17
random_shuffle	それぞれの要素をランダムな位置に移動させる	C++14から非推奨 C++17で削除
shuffle	それぞれの要素をランダムな位置に移動させる	C++11
is_partitioned	与えられた範囲が条件によって区分化されているか判定する	C++11
partition	与えられた範囲を条件によって区分化する
stable_partition	与えられた範囲を相対順序を保ちながら条件によって区分化する
partition_copy	与えられた範囲を条件によって 2 つの出力の範囲へ分けてコピーする	C++11
partition_point	与えられた範囲から条件によって区分化されている位置を得る	C++11

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

ここで挙げる操作には全て２つのバージョンがある。一つは 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) の時かつその時に限り同値とみなされるということである。

ソート

名前	説明	対応バージョン
sort	範囲を並べ替える
stable_sort	範囲を安定ソートで並べ替える
partial_sort	範囲を部分的にソートし、先頭N個を並んだ状態にする
partial_sort_copy	範囲を部分的にソートした結果を他の範囲にコピーする
is_sorted	ソート済みか判定する	C++11
is_sorted_until	ソート済みか判定し、ソートされていない位置のイテレータを取得する	C++11

N 番目の要素

名前	説明	対応バージョン
nth_element	基準となる要素よりも小さい要素が、前に来るよう並べ替える

二分探索

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

名前	説明	対応バージョン
lower_bound	指定された要素以上の値が現れる最初の位置のイテレータを取得する
upper_bound	指定された要素より大きい値が現れる最も後ろの位置のイテレータを取得する
equal_range	lower_boundとupper_boundの結果を組で取得する
binary_search	二分探索法による検索を行う

マージ

名前	説明	対応バージョン
merge	2つのソート済み範囲をマージする
inplace_merge	2つの連続したソート済み範囲をマージする

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

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

名前	説明	対応バージョン
set_union	2つのソート済み範囲の和集合を得る
set_intersection	2つのソート済み範囲の積集合を得る
set_difference	2つのソート済み範囲の差集合を得る
set_symmetric_difference	2つのソート済み範囲の互いに素な集合を得る
includes	2つのソート済み範囲において、一方の範囲の要素がもう一方の範囲に全て含まれているかを判定する

ヒープ

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

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

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

名前	説明	対応バージョン
push_heap	ヒープ化された範囲に要素を追加したヒープ範囲を得る
pop_heap	ヒープ化された範囲の先頭と末尾を入れ替え、ヒープ範囲を作り直す
make_heap	範囲をヒープ化する
sort_heap	ヒープ化された範囲を並べ替える
is_heap_until	範囲がヒープ化されているか判定し、ヒープ化されていない最初の要素を指すイテレータを取得する	C++11
is_heap	範囲がヒープ化されているか判定する	C++11

最小と最大

名前	説明	対応バージョン
min	最小値を取得する
max	最大値を取得する
minmax	最小値と最大値を取得する	C++11
min_element	範囲内の最小要素へのイテレータを取得する
max_element	範囲内の最大要素へのイテレータを取得する
minmax_element	範囲内の最小要素と最大要素へのイテレータを取得する	C++11
clamp	値を範囲内に収める	C++17

辞書式比較

名前	説明	対応バージョン
lexicographical_compare	2つの範囲を辞書式順序で比較する

順列

名前	説明	対応バージョン
next_permutation	次の順列を生成する
prev_permutation	前の順列を生成する
is_permutation	範囲が順列かを判定する	C++11

関連項目

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

参照

• N2930 Range-Based For Loop Wording (Without Concepts)