1、変更しないシーケンスアルゴリズム
これらのアルゴリズムは、操作対象のコンテナ内の要素を変更しません。
1.1 find と find_if
find(開始イテレータ, 終了イテレータ, 値)：指定された値に一致する最初の要素を検索し、イテレータを返します（見つからない場合は終了イテレータを返します）。find_if(開始イテレータ, 終了イテレータ, 条件関数)：条件関数を満たす最初の要素を検索します。find_end(開始イテレータ, 終了イテレータ, サブ範囲の開始, サブ範囲の終了)：サブシーケンスが最後に現れる位置を検索します。
vector<int> numbers = {1, 3, 5, 7, 9};
// 値5を持つ要素を探す
auto iter = find(numbers.begin(), numbers.end(), 5);
if (iter != numbers.end()) {
cout << "発見: " << *iter << endl; // 出力: 5
}
// 6より大きい最初の要素を探す
auto iter2 = find_if(numbers.begin(), numbers.end(), [](int x) {
return x > 6;
});
cout << "最初の6より大きい要素: " << *iter2 << endl; // 出力: 7
// サブシーケンスを検索
vector<int> subseq = {3, 5};
auto iter3 = find_end(numbers.begin(), numbers.end(), subseq.begin(), subseq.end());
if (iter3 != numbers.end()) {
cout << "サブシーケンスの開始インデックス: " << iter3 - numbers.begin() << endl; // 出力: 1
}
1.2 count と count_if
count(開始イテレータ, 終了イテレータ, 値)：指定された値に一致する要素の数をカウントします。count_if(開始イテレータ, 終了イテレータ, 条件関数)：条件関数を満たす要素の数をカウントします。
std::vector<int> data = {1, 2, 3, 2, 4, 2};
int count = std::count(data.begin(), data.end(), 2); // 値2の個数をカウント、結果は3
int even_count = std::count_if(data.begin(), data.end(), [](int x) {
return x % 2 == 0;
}); // 偶数の個数、結果は4
1.3 for_each
範囲内の各要素に対して関数を適用します。
std::vector<int> data = {1, 2, 3, 4, 5};
std::for_each(data.begin(), data.end(), [](int& x) {
x *= 2; // 各要素を2倍にする
});
// dataは{2, 4, 6, 8, 10}に変化
1.4 equal と mismatch
equal(範囲1の開始, 範囲1の終了, 範囲2の開始)：2つの範囲が等しいかどうかを判定します。mismatch(範囲1の開始, 範囲1の終了, 範囲2の開始)：2つの範囲で最初に一致しない要素のイテレータペアを返します。
vector<int> first = {1, 2, 3};
vector<int> second = {1, 2, 4};
vector<int> third = {1, 2, 3, 4};
// firstとsecondの最初の3要素を比較
bool is_equal = equal(first.begin(), first.end(), second.begin());
cout << "first == second? " << boolalpha << is_equal << endl; // 出力: false
// firstとthirdの最初の不一致要素を検索
auto diff = mismatch(first.begin(), first.end(), third.begin());
if (diff.first != first.end()) {
cout << "不一致: " << *diff.first << " vs " << *diff.second << endl; // 出力なし（最初の3要素は一致）
}
1.5 all_of, any_of, none_of
範囲内の要素がすべて、いずれか、またはどれも条件を満たすかをチェックします。
std::vector<int> data = {2, 4, 6, 8};
bool all_even = std::all_of(data.begin(), data.end(), [](int x) {
return x % 2 == 0;
}); // true
bool any_odd = std::any_of(data.begin(), data.end(), [](int x) {
return x % 2 != 0;
}); // false
bool none_negative = std::none_of(data.begin(), data.end(), [](int x) {
return x < 0;
}); // true
2、シーケンスを変更するアルゴリズム
これらのアルゴリズムは、操作対象のコンテナ内の要素を変更します。
2.1 copy と copy_if
copy(開始イテレータ, 終了イテレータ, コピー先)：範囲内の要素をコピー先に移動します。copy_if(開始イテレータ, 終了イテレータ, コピー先, 条件関数)：条件関数を満たす要素のみをコピーします。
vector<int> source = {1, 2, 3, 4, 5};
vector<int> destination(5); // 事前に十分な領域を確保する必要があります
// 全ての要素をコピー
copy(source.begin(), source.end(), destination.begin()); // destination: [1,2,3,4,5]
// 偶数要素を新しいコンテナにコピー
vector<int> even_nums;
copy_if(source.begin(), source.end(), back_inserter(even_nums), [](int x) {
return x % 2 == 0;
}); // even_nums: [2,4]
注意：back_inserter(コンテナ) は自動的に push_back を呼び出すため、事前の領域確保は必要ありません。
2.2 transform
範囲内の各要素に関数を適用し、結果を別の範囲に格納します。
vector<int> nums = {1, 2, 3};
vector<int> squares(3);
// 平方を計算（単一引数変換）
transform(nums.begin(), nums.end(), squares.begin(), [](int x) {
return x * x;
}); // squares: [1,4,9]
// 2つのコンテナの要素を加算（二重引数変換）
vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
vector<int> sum(3);
transform(a.begin(), a.end(), b.begin(), sum.begin(), [](int x, int y) {
return x + y;
}); // sum: [5,7,9]
2.3 replace、replace_if と replace_copy
replace(開始イテレータ, 終了イテレータ, 古い値, 新しい値)：すべての古い値を新しい値に置き換えます。replace_if(開始イテレータ, 終了イテレータ, 条件関数, 新しい値)：条件関数を満たす要素を置き換えます。replace_copy(開始イテレータ, 終了イテレータ, コピー先, 古い値, 新しい値)：コピー時に要素を置き換えます（元のコンテナは変更されません）。
vector<int> nums = {1, 2, 3, 2, 5};
// すべての2を20に置き換え
replace(nums.begin(), nums.end(), 2, 20); // nums: [1,20,3,20,5]
// 10より大きい要素を0に置き換え
replace_if(nums.begin(), nums.end(), [](int x) {
return x > 10;
}, 0); // nums: [1,0,3,0,5]
// 3を300に置き換えながらコピー（元のコンテナは変更されない）
vector<int> result;
replace_copy(nums.begin(), nums.end(), back_inserter(result), 3, 300); // result: [1,0,300,0,5]
2.4 remove、remove_if と erase
remove(開始イテレータ, 終了イテレータ, 値)：指定された値を持つ要素をコンテナの末尾に「移動」し、新しい論理終端イテレータを返します（実際には要素を削除しません。eraseと組み合わせる必要があります）。remove_if(開始イテレータ, 終了イテレータ, 条件関数)：条件関数を満たす要素を末尾に移動します。
vector<int> nums = {1, 2, 3, 2, 4};
// すべての2を論理的に削除（末尾に移動）
auto new_end = remove(nums.begin(), nums.end(), 2); // nums: [1,3,4,2,2]
// 実際に要素を削除（物理的に削除）
nums.erase(new_end, nums.end()); // nums: [1,3,4]
// ラムダ式を使って偶数を削除
nums = {1, 2, 3, 4, 5};
nums.erase(remove_if(nums.begin(), nums.end(), [](int x) {
return x % 2 == 0;
}), nums.end()); // nums: [1,3,5]
2.5 unique
連続した重複要素を削除し、新しい論理終端イテレータを返します。通常 erase と組み合わせて使用されます。
std::vector<int> vec = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto last = std::unique(vec.begin(), vec.end());
vec.erase(last, vec.end()); // vecは{1, 2, 3, 4, 5}に変化
2.6 reverse
範囲内の要素の順序を逆転させます。
std::vector<int> vec = {1, 2, 3, 4, 5};
std::reverse(vec.begin(), vec.end()); // vecは{5, 4, 3, 2, 1}に変化
2.7 rotate
範囲内の要素を回転し、中央の要素を新しい最初の要素にします。
std::vector<int> vec = {1, 2, 3, 4, 5};
std::rotate(vec.begin(), vec.begin() + 2, vec.end()); // 3を基準に回転、vecは{3, 4, 5, 1, 2}に変化
2.8 shuffle
範囲内の要素をランダムに再配置します（C++11以降が必要）。
#include <random>
#include <algorithm>
std::vector<int> vec = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(vec.begin(), vec.end(), g); // vec内の要素をランダムに並び替え
3、ソートと関連アルゴリズム
3.1 sort、stable_sort と partial_sort
sort(開始イテレータ, 終了イテレータ)：クイックソートを使用して要素を並べ替えます（不安定、平均時間計算量 O(n log n)）。stable_sort(開始イテレータ, 終了イテレータ)：安定ソート（等価な要素の相対位置が保たれます）。partial_sort(開始イテレータ, 中間イテレータ, 終了イテレータ)：範囲内の最小要素を先頭に並べ替えます。
std::vector<int> vec = {5, 3, 1, 4, 2};
std::sort(vec.begin(), vec.end()); // 昇順、vecは{1, 2, 3, 4, 5}に変化
std::sort(vec.begin(), vec.end(), std::greater<int>()); // 降順、vecは{5, 4, 3, 2, 1}に変化
std::sort(vec.begin(), vec.end(), [](int a, int b) {
return a < b;
}); // 昇順、カスタム比較
std::vector<std::pair<int, int>> vec = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) {
return a.first < b.first; // firstでソートし、等価要素の相対順序を保持
});
std::vector<int> vec = {5, 3, 1, 4, 2, 6};
// 最小の3要素を先頭に並べ替え
std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
// 今後vecの最初の3要素は1, 2, 3、残りは未ソートの4, 5, 6
3.2 nth_element
範囲を再配置し、指定された位置の要素をソート後の要素にし、左側の要素はそれ以下、右側の要素はそれ以上になるようにします。
std::vector<int> vec = {5, 3, 1, 4, 2, 6};
// 3番目に小さい要素を見つける（インデックス2）
std::nth_element(vec.begin(), vec.begin() + 2, vec.end());
// 今後vec[2]は3になり、その左は3以下、右は3以上
3.3 binary_search、lower_bound、upper_bound
ソート済みコンテナでのみ使用できます。
binary_search(開始イテレータ, 終了イテレータ, 値)：値が存在するかどうかを判定します（boolを返します）。lower_bound(開始イテレータ, 終了イテレータ, 値)：値以上の最初の要素のイテレータを返します。upper_bound(開始イテレータ, 終了イテレータ, 値)：値より大きい最初の要素のイテレータを返します。
vector<int> sorted = {1, 3, 3, 5, 7}; // 事前にソートされている必要があります
// 3が存在するか確認
bool exists = binary_search(sorted.begin(), sorted.end(), 3); // true
// 3以上となる最初の要素を検索
auto lb = lower_bound(sorted.begin(), sorted.end(), 3);
cout << "lower_boundのインデックス: " << lb - sorted.begin() << endl; // 出力: 1
// 3より大きい最初の要素を検索
auto ub = upper_bound(sorted.begin(), sorted.end(), 3);
cout << "upper_boundのインデックス: " << ub - sorted.begin() << endl; // 出力: 3
3.4 merge
2つのソート済み範囲を新しいコンテナにマージし、ソート状態を維持します。
vector<int> a = {1, 3, 5};
vector<int> b = {2, 4, 6};
vector<int> merged(a.size() + b.size());
// aとbをマージ（どちらも事前にソートされている必要があります）
merge(a.begin(), a.end(), b.begin(), b.end(), merged.begin()); // merged: [1,2,3,4,5,6]
4、ヒープアルゴリズム
STLは範囲をヒープとして扱うアルゴリズムを提供します。make_heap, push_heap, pop_heap, sort_heapなどが含まれます。
std::vector<int> vec = {4, 1, 3, 2, 5};
std::make_heap(vec.begin(), vec.end()); // 最大ヒープを作成、vecは{5, 4, 3, 2, 1}に変化
vec.push_back(6);
std::push_heap(vec.begin(), vec.end()); // 新しい要素をヒープに追加、vecは{6, 4, 5, 2, 1, 3}に変化
std::pop_heap(vec.begin(), vec.end()); // 最大要素を末尾に移動、vecは{5, 4, 3, 2, 1, 6}に変化
int max_val = vec.back(); // 最大要素6を取得
vec.pop_back(); // 最大要素を削除
std::sort_heap(vec.begin(), vec.end()); // ヒープを昇順にソート、vecは{1, 2, 3, 4, 5}に変化
5、最小/最大値アルゴリズム
5.1 min と max
2つの値または初期化リストから最小/最大値を返します。
int a = 5, b = 3;
int min_val = std::min(a, b); // 3
int max_val = std::max(a, b); // 5
auto min_of_list = std::min({4, 2, 8, 5, 1}); // 1
auto max_of_list = std::max({4, 2, 8, 5, 1}); // 8
5.2 min_element と max_element
範囲内の最小/最大要素のイテレータを返します。
std::vector<int> vec = {3, 1, 4, 2, 5};
auto min_it = std::min_element(vec.begin(), vec.end()); // 1を指す
auto max_it = std::max_element(vec.begin(), vec.end()); // 5を指す
5.3 minmax_element (C++11)
範囲内の最小と最大要素のイテレータを同時に返します。
std::vector<int> vec = {3, 1, 4, 2, 5};
auto minmax = std::minmax_element(vec.begin(), vec.end());
// minmax.firstは1を指し、minmax.secondは5を指す
6、数値アルゴリズム（で定義）
6.1 accumulate
範囲内の要素の総和（またはカスタム操作）を計算します。
#include <numeric>
std::vector<int> vec = {1, 2, 3, 4, 5};
int sum = std::accumulate(vec.begin(), vec.end(), 0); // 合計、初期値0、結果15
int product = std::accumulate(vec.begin(), vec.end(), 1, std::multiplies<int>()); // 積、初期値1、結果120
6.2 inner_product
2つの範囲の内積（またはカスタム操作）を計算します。
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {4, 5, 6};
int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0); // 1*4 + 2*5 + 3*6 = 32
6.3 iota
連続した増加値で範囲を埋めます。
std::vector<int> vec(5);
std::iota(vec.begin(), vec.end(), 10); // 10, 11, 12, 13, 14で埋める
6.4 partial_sum
部分和を計算し、結果を目的の範囲に格納します。
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(src.size());
std::partial_sum(src.begin(), src.end(), dst.begin()); // dstは{1, 3, 6, 10, 15}に変化
6.5 adjacent_difference
隣接する要素の差を計算し、結果を目的の範囲に格納します。
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(src.size());
std::adjacent_difference(src.begin(), src.end(), dst.begin()); // dstは{1, 1, 1, 1, 1}に変化
7、その他
7.1 generate
生成関数を使用して範囲を埋めます。
std::vector<int> vec(5);
int n = 0;
std::generate(vec.begin(), vec.end(), [&n]() {
return n++;
}); // 0, 1, 2, 3, 4で埋める
7.2 generate_n
生成関数を使用して範囲の最初のn要素を埋めます。
std::vector<int> vec(5);
int n = 10;
std::generate_n(vec.begin(), 3, [&n]() {
return n++;
}); // 最初の3要素は10, 11, 12、残りは変更されない
7.3 includes
ソートされた範囲が別のソートされた範囲のすべての要素を含むかを確認します。
std::vector<int> vec1 = {1, 2, 3, 4, 5};
std::vector<int> vec2 = {2, 4};
bool includes = std::includes(vec1.begin(), vec1.end(), vec2.begin(), vec2.end()); // true
7.4 set_union, set_intersection, set_difference, set_symmetric_difference
集合演算：和、積、差、対称差を実行します。
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {3, 4, 5, 6, 7};
std::vector<int> result;
// 和集合
std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
// resultは{1, 2, 3, 4, 5, 6, 7}
// 積集合
result.clear();
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
// resultは{3, 4, 5}
// 差集合 (v1 - v2)
result.clear();
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
// resultは{1, 2}
// 対称差集合 (v1 ∪ v2 - v1 ∩ v2)
result.clear();
std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
// resultは{1, 2, 6, 7}
8、よくある質問
sortとstable_sortの違いは？
sortはクイックソート（正確にはintrosort）を使用し、不安定（等価要素の相対位置が変わる可能性あり）、平均時間計算量 O(n log n)。stable_sortはマージソートを使用し、安定（等価要素の相対位置が保たれる）、時間計算量 O(n log n)、ただし空間コストが若干高い。
- なぜ
removeアルゴリズムはeraseと組み合わせる必要があるのですか？removeアルゴリズムの仕組みは、削除する要素を「上書き」し、残す要素を前方に移動することです。そして新しい論理終端イテレータを返しますが、コンテナの実際のサイズは変更されません。eraseはイテレータ範囲を使って実際に要素を削除し、コンテナのサイズを変更します。したがって、組み合わせて使用する必要があります：container.erase(remove(...), container.end())。 - どのアルゴリズムはコンテナがソート済みであることを前提としますか？
二分探索系列（
binary_search、lower_bound、upper_bound）、集合アルゴリズム（set_intersection、set_unionなど）、mergeなどは、効率的な操作（例えば二分探索のO(log n)）のためにソート状態に依存します。