13.1 概要

この章と第 14 章は、標準 C++ ライブラリが提供する各汎用アルゴリズムについて説明します。この章で説明する各アルゴリズムの名称と概略を表 18 に示します。アルゴリズムは、その代表的な使用方法に基づいていくつかのカテゴリに分類されています。この分類は、アルゴリズムがその引数を変更するかどうかに基づき、標準 C++ ライブラリ定義で使用されているカテゴリとは異なります。

表 18 -- 標準 C++ ライブラリの汎用アルゴリズム

アルゴリズム	目的
*シーケンス初期化アルゴリズム*
`fill`	シーケンスに初期値を入力する
`fill_n`	n 位置に初期値を入力する
`copy`	シーケンスを別のシーケンスにコピーする
`copy_backward`	シーケンスを別のシーケンスにコピーする
`generate`	ジェネレータを使用してシーケンスを初期化する
`generate_n`	ジェネレータを使用して n 位置を初期化する
`swap_ranges`	2 つの並列シーケンスの値を交換する
*検索アルゴリズム*
`find`	引数に一致する要素を検索する
`find_if`	条件を満たす要素を検出する
`adjacent_find`	連続重複要素を検索する
`find_first_of`	別のシーケンス内でシーケンスメンバーの最初の発生を検出する
`find_end`	シーケンス内でサブシーケンスの最後の発生を検出する
`search`	シーケンス内のサブシーケンスを検索する
`max_element`	シーケンス内の最大値を検索する
`min_element`	シーケンス内の最小値を検索する
`mismatch`	並列シーケンス内の最初の不一致を検出する
*インプレース変換アルゴリズム*
`reverse`	シーケンス内の要素を反転する
`replace`	特定の値を新しい値に置換する
`replace_if`	述語に一致する要素を置換する
`rotate`	シーケンス内の要素を点を軸に回転する
`partition`	要素を 2 つのグループに区分する
`stable_partition`	元の順序を維持して区分する
`next_permutation`	シーケンスに順列を生成する
`prev_permutation`	順列を逆順に生成する
`inplace_merge`	隣接する 2 つのシーケンスを 1 つにマージする
`random_shuffle`	シーケンス内の要素をランダムに再配列する
*削除アルゴリズム*
`remove`	条件に一致する要素を削除する
`unique`	シーケンス内の最初の重複値を除くすべての重複値を削除する
*スカラー生成アルゴリズム*
`count`	値の一致する要素数をカウントする
`count_if`	述語の一致する要素をカウントする
`accumulate`	シーケンスをスカラー値に還元する
`inner_product`	2 つの並列シーケンスの内積を算出する
`equal`	2 つのシーケンスの等価性を検査する
`lexicographical_compare`	2 つのシーケンスを比較する
シーケンス生成アルゴリズム
`transform`	各要素を変換する
`partial_sum`	部分和のシーケンスを生成する
`adjacent_difference`	隣接差のシーケンスを生成する
*その他の操作*
`for_each`	コレクションの各要素に関数を適用する

この章では、各アルゴリズムの使用方法を簡単な例を挙げて説明します。アルゴリズムの多くは、さまざまなコンテナクラスに関する章のプログラム例にも使用されています。これらの相互参照については、適宜注釈を付けてあります。

この章で説明するプログラム例はすべて、alg1.cpp から alg6.cpp までの一連のファイルに含まれています。これらのファイルでは、プログラム例は、テストプログラムとアルゴリズム実行結果を説明する出力文によって増大します。不要な詳細情報に煩わされないように、この節の説明からこうした出力文は省略してあります。出力文付きの完全なテキストプログラムを参照する場合は、テストファイルをコンパイルして実行してください。これらのプログラムの実行結果も含まれています。

13.1.1 インクルードファイル

汎用アルゴリズムを使用するには、まず適切なヘッダーファイルをインクルードする必要があります。関数の大部分は、ヘッダーファイル algorithm で定義されます。関数 accumulate()、inner_product()、partial_sum()、adjacent_difference() は、ヘッダーファイル numeric に定義されます。

# include <algorithm>
# include <numeric>