1、非破壊シーケンスアルゴリズム

これらのアルゴリズムは操作対象のコンテナ内の要素を変更しません。

1.1 find と find_if

• find(begin, end, value)：value に等しい最初の要素を検索し、イテレータを返す（見つからない場合は end を返す）。
• find_if(begin, end, predicate)：述語を満たす最初の要素を検索する。
• find_end(begin, end, sub_begin, sub_end)：サブシーケンスが最後に出現する位置を検索する。

std::vector<int> 数列 = {1, 3, 5, 7, 9};

// 値が7の要素を検索
auto 位置 = find(数列.begin(), 数列.end(), 7);
if (位置 != 数列.end()) {
    std::cout << "見つかりました: " << *位置 << std::endl;  // 出力：7
}

// 6より大きい最初の要素を検索
auto 位置2 = find_if(数列.begin(), 数列.end(), [](int x) {
    return x > 6;
});
std::cout << "最初の6より大きい値: " << *位置2 << std::endl;  // 出力：7

// サブシーケンスを検索
std::vector<int> 部分 = {3, 5};
auto 位置3 = find_end(数列.begin(), 数列.end(), 部分.begin(), 部分.end());
if (位置3 != 数列.end()) {
    std::cout << "サブシーケンスの開始インデックス: " << 位置3 - 数列.begin() << std::endl;  // 出力：1
}

1.2 count と count_if

• count(begin, end, value)：value に等しい要素の数をカウントする。
• count_if(begin, end, predicate)：述語を満たす要素の数をカウントする。

std::vector<int> ベクター = {1, 2, 3, 2, 4, 2};
int 数 = std::count(ベクター.begin(), ベクター.end(), 2); // 2の個数、結果は3
int 偶数数 = std::count_if(ベクター.begin(), ベクター.end(), [](int x) { 
    return x % 2 == 0; 
}); // 偶数の個数、結果は4

1.3 for_each

範囲内の各要素に関数を適用する

std::vector<int> ベクター = {1, 2, 3, 4, 5};
std::for_each(ベクター.begin(), ベクター.end(), [](int& x) { 
    x *= 3; // 各要素を3倍する
});
// 現在ベクターは{3, 6, 9, 12, 15}になる

1.4 equal と mismatch

• equal(b1, e1, b2)：[b1,e1) と [b2, b2+(e1-b1)) の範囲が等しいかを判定。
• mismatch(b1, e1, b2)：2つの範囲で最初に一致しない要素のイテレータペアを返す。

vector<int> a = {1, 2, 3};
vector<int> b = {1, 2, 4};
vector<int> c = {1, 2, 3, 4};

// aとbの最初の3要素を比較
bool 等しい = equal(a.begin(), a.end(), b.begin());
std::cout << "a == b? " << std::boolalpha << 等しい << std::endl;  // 出力：false

// aとcの最初に不一致する要素を検索
auto 不一致 = mismatch(a.begin(), a.end(), c.begin());
if (不一致.first != a.end()) {
    std::cout << "不一致: " << *不一致.first << " vs " << *不一致.second << std::endl;  // 出力なし（aとcの最初の3要素は等しい）
}

1.5 all_of, any_of, none_of

範囲内の要素がすべて、存在、または存在しない条件をチェックする

std::vector<int> ベクター = {2, 4, 6, 8};
bool 全て偶数 = std::all_of(ベクター.begin(), ベクター.end(), [](int x) { 
    return x % 2 == 0; 
}); // true
bool 奇数存在 = std::any_of(ベクター.begin(), ベクター.end(), [](int x) { 
    return x % 2 != 0; 
}); // false
bool 負数なし = std::none_of(ベクター.begin(), ベクター.end(), [](int x) { 
    return x < 0; 
}); // true

2、破壊的シーケンスアルゴリズム

これらのアルゴリズムは操作対象のコンテナ内の要素を変更します。

2.1 copy と copy_if

• copy(begin, end, dest)：[begin, end) の要素を dest の開始位置にコピーする。
• copy_if(begin, end, dest, predicate)：述語を満たす要素を dest にコピーする。

vector<int> 元 = {1, 2, 3, 4, 5};
vector<int> 宛先(5);  // 事前に十分なスペースを確保する必要がある

// 全ての要素をコピー
copy(元.begin(), 元.end(), 宛先.begin());  // 宛先: [1,2,3,4,5]

// 偶数要素を新規コンテナにコピー
vector<int> 偶数;
copy_if(元.begin(), 元.end(), back_inserter(偶数), [](int x) {
    return x % 2 == 0;
});  // 偶数: [2,4]

注意：back_inserter(dest) は自動的に push_back を呼び出し、事前にスペースを確保する必要がない。

2.2 transform

範囲内の各要素に関数を適用し、結果を別の範囲に保存する

vector<int> 数 = {1, 2, 3};
vector<int> 平方(3);

// 平方計算（単一パラメータ変換）
transform(数.begin(), 数.end(), 平方.begin(), [](int x) {
    return x * x;
});  // 平方: [1,4,9]

// 2つのコンテナの要素を加算（双パラメータ変換）
vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
vector<int> 総和(3);
transform(a.begin(), a.end(), b.begin(), 総和.begin(), [](int x, int y) {
    return x + y;
});  // 総和: [5,7,9]

2.3 replace、replace_if と replace_copy

• replace(begin, end, old_val, new_val)：old_val をすべて new_val に置き換える。
• replace_if(begin, end, predicate, new_val)：述語を満たす要素を置き換える。
• replace_copy(begin, end, dest, old_val, new_val)：コピー時に要素を置き換える（元のコンテナは変更されない）。

vector<int> 数 = {1, 2, 3, 2, 5};

// 全ての2を20に置き換える
replace(数.begin(), 数.end(), 2, 20);  // 数: [1,20,3,20,5]

// 10より大きい要素を0に置き換える
replace_if(数.begin(), 数.end(), [](int x) {
    return x > 10;
}, 0);  // 数: [1,0,3,0,5]

// コピー時に3を300に置き換える（元コンテナは変更されない）
vector<int> 結果;
replace_copy(数.begin(), 数.end(), back_inserter(結果), 3, 300);  // 結果: [1,0,300,0,5]

2.4 remove、remove_if と erase

• remove(begin, end, value)：value に等しい要素を「末尾に移動」し、論理的な末尾のイテレータを返す（実際には要素は削除されない。erase と併用する必要がある）。
• remove_if(begin, end, predicate)：述語を満たす要素を末尾に移動する。

vector<int> 数 = {1, 2, 3, 2, 4};

// 論理的に2を削除（末尾に移動）
auto 新しい末尾 = remove(数.begin(), 数.end(), 2);  // 数: [1,3,4,2,2]

// 実際に削除（要素を本当に削除）
数.erase(新しい末尾, 数.end());  // 数: [1,3,4]

// lambda式で偶数を削除
数 = {1, 2, 3, 4, 5};
数.erase(remove_if(数.begin(), 数.end(), [](int x) {
    return x % 2 == 0;
}), 数.end());  // 数: [1,3,5]

2.5 unique

連続した重複要素を削除し、新しい論理的な末尾のイテレータを返す。通常 erase と併用する。

std::vector<int> ベクター = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto 最終 = std::unique(ベクター.begin(), ベクター.end());
ベクター.erase(最終, ベクター.end()); // ベクターは{1, 2, 3, 4, 5}になる

2.6 reverse

範囲内の要素の順序を逆転させる

std::vector<int> ベクター = {1, 2, 3, 4, 5};
std::reverse(ベクター.begin(), ベクター.end()); // ベクターは{5, 4, 3, 2, 1}になる

2.7 rotate

範囲内の要素を回転させ、中間要素を新しい最初の要素にする

std::vector<int> ベクター = {1, 2, 3, 4, 5};
std::rotate(ベクター.begin(), ベクター.begin() + 2, ベクター.end()); // 3を起点に回転、ベクターは{3, 4, 5, 1, 2}になる

2.8 shuffle

範囲内の要素をランダムに並び替える（C++11以降が必要）

#include <random>
#include <algorithm>

std::vector<int> ベクター = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(ベクター.begin(), ベクター.end(), g); // ベクター内の要素をランダムに並び替える

3、ソートおよび関連アルゴリズム

3.1 sort、stable_sort と partial_sort

• sort(begin, end)：要素をクイックソート（不安定、平均時間計算量 O(n log n)）で並べ替える。
• stable_sort(begin, end)：安定ソート（等しい要素の相対順序は保持される）。
• partial_sort(begin, mid, end)：[begin, mid) を全体の中で最小の要素にソートする。

std::vector<int> ベクター = {5, 3, 1, 4, 2};
std::sort(ベクター.begin(), ベクター.end()); // 通常昇順、ベクターは{1, 2, 3, 4, 5}になる
std::sort(ベクター.begin(), ベクター.end(), std::greater<int>()); // 降順、ベクターは{5, 4, 3, 2, 1}になる
std::sort(ベクター.begin(), ベクター.end(), [](int a, int b) { 
    return a < b; 
}); // 昇順、カスタム比較

std::vector<std::pair<int, int>> ベクター = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(ベクター.begin(), ベクター.end(), [](const auto& a, const auto& b) {
    return a.first < b.first; // firstでソート、等しい要素の順序は保持
});

std::vector<int> ベクター = {5, 3, 1, 4, 2, 6};
// 最小の3つの要素を先頭に並べる
std::partial_sort(ベクター.begin(), ベクター.begin() + 3, ベクター.end());
// 現在ベクターの先頭3要素は1, 2, 3、後は未ソートの4, 5, 6

3.2 nth_element

範囲を再構成し、指定位置の要素がソート後の要素と等しくなるようにする。左の要素はすべてそれ以下、右の要素はすべてそれ以上になる。

std::vector<int> ベクター = {5, 3, 1, 4, 2, 6};
// 3番目に小さい要素（インデックス2）を探す
std::nth_element(ベクター.begin(), ベクター.begin() + 2, ベクター.end());
// 現在ベクター[2]は3、左の要素は<=3、右の要素は>=3

3.3 binary_search、lower_bound、upper_bound

ソート済みコンテナでのみ使用可能

• binary_search(begin, end, value)：value が存在するかを判定（bool を返す）。
• lower_bound(begin, end, value)：最初に等しくない value より大きい要素のイテレータを返す。
• upper_bound(begin, end, value)：最初に等しくない value より大きい要素のイテレータを返す。

vector<int> ソート済み = {1, 3, 3, 5, 7};  // 事前にソートが必要

// 3が存在するかを判定
bool 存在 = binary_search(ソート済み.begin(), ソート済み.end(), 3);  // true

// 最初に>=3の要素を検索
auto 下限 = lower_bound(ソート済み.begin(), ソート済み.end(), 3);
std::cout << "lower_bound インデックス: " << 下限 - ソート済み.begin() << std::endl;  // 出力：1

// 最初に>3の要素を検索
auto 上限 = upper_bound(ソート済み.begin(), ソート済み.end(), 3);
std::cout << "upper_bound インデックス: " << 上限 - ソート済み.begin() << std::endl;  // 出力：3

3.4 merge

2つのソート済み範囲を新しいコンテナにマージ（ソート済みを保持）

vector<int> a = {1, 3, 5};
vector<int> b = {2, 4, 6};
vector<int> 合併(a.size() + b.size());

// aとbをマージ（どちらもソート済み）
merge(a.begin(), a.end(), b.begin(), b.end(), 合併.begin());  // 合併: [1,2,3,4,5,6]

4、ヒープアルゴリズム

STLは範囲をヒープとして操作するアルゴリズムを提供しています。make_heap, push_heap, pop_heap, sort_heap などが含まれます。

std::vector<int> ベクター = {4, 1, 3, 2, 5};
std::make_heap(ベクター.begin(), ベクター.end()); // 最大ヒープを構築、ベクターは{5, 4, 3, 2, 1}になる

ベクター.push_back(6);
std::push_heap(ベクター.begin(), ベクター.end()); // 新しい要素をヒープに追加、ベクターは{6, 4, 5, 2, 1, 3}になる

std::pop_heap(ベクター.begin(), ベクター.end()); // 最大要素を末尾に移動、ベクターは{5, 4, 3, 2, 1, 6}になる
int 最大値 = ベクター.back(); // 最大値6を取得
ベクター.pop_back(); // 最大値を削除

std::sort_heap(ベクター.begin(), ベクター.end()); // ヒープを昇順にソート、ベクターは{1, 2, 3, 4, 5}になる

5、最小/最大値アルゴリズム

5.1 min と max

2つの値または初期化リストから最小/最大値を返す

int a = 5, b = 3;
int 最小 = std::min(a, b); // 3
int 最大 = std::max(a, b); // 5

auto 最小リスト = std::min({4, 2, 8, 5, 1}); // 1
auto 最大リスト = std::max({4, 2, 8, 5, 1}); // 8

5.2 min_element と max_element

範囲内での最小/最大要素のイテレータを返す

std::vector<int> ベクター = {3, 1, 4, 2, 5};
auto 最小イテ = std::min_element(ベクター.begin(), ベクター.end()); // 1を指す
auto 最大イテ = std::max_element(ベクター.begin(), ベクター.end()); // 5を指す

5.3 minmax_element (C++11)

範囲内での最小と最大要素のイテレータを同時に返す

std::vector<int> ベクター = {3, 1, 4, 2, 5};
auto 最小最大 = std::minmax_element(ベクター.begin(), ベクター.end());
// 最小最大.firstは1を指し、最小最大.secondは5を指す

6、数値アルゴリズム（に含まれる）

6.1 accumulate

範囲内の要素の累積和（またはカスタム操作）を計算する

#include <numeric>

std::vector<int> ベクター = {1, 2, 3, 4, 5};
int 総和 = std::accumulate(ベクター.begin(), ベクター.end(), 0); // 総和、初期値0、結果は15
int 積 = std::accumulate(ベクター.begin(), ベクター.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 内積 = std::inner_product(a.begin(), a.end(), b.begin(), 0); // 1*4 + 2*5 + 3*6 = 32

6.3 iota

連続した増分値で範囲を埋める

std::vector<int> ベクター(5);
std::iota(ベクター.begin(), ベクター.end(), 10); // 填充: 10, 11, 12, 13, 14

6.4 partial_sum

部分和を計算し、結果をターゲット範囲に保存する

std::vector<int> 元 = {1, 2, 3, 4, 5};
std::vector<int> 宛先(元.size());
std::partial_sum(元.begin(), 元.end(), 宛先.begin()); // 宛先は{1, 3, 6, 10, 15}になる

6.5 adjacent_difference

隣接要素の差を計算し、結果をターゲット範囲に保存する

std::vector<int> 元 = {1, 2, 3, 4, 5};
std::vector<int> 宛先(元.size());
std::adjacent_difference(元.begin(), 元.end(), 宛先.begin()); // 宛先は{1, 1, 1, 1, 1}になる

7、その他

7.1 generate

生成関数で範囲を埋める

std::vector<int> ベクター(5);
int n = 0;
std::generate(ベクター.begin(), ベクター.end(), [&n]() { 
    return n++; 
}); // 填充: 0, 1, 2, 3, 4

7.2 generate_n

生成関数で範囲の最初のn個の要素を埋める

std::vector<int> ベクター(5);
int n = 10;
std::generate_n(ベクター.begin(), 3, [&n]() { 
    return n++; 
}); // 最初の3要素は10, 11, 12、残りは変更されない

7.3 includes

1つのソート範囲がもう1つのソート範囲のすべての要素を含むかを確認する

std::vector<int> ベクター1 = {1, 2, 3, 4, 5};
std::vector<int> ベクター2 = {2, 4};
bool 包含 = std::includes(ベクター1.begin(), ベクター1.end(), ベクター2.begin(), ベクター2.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> 結果;

// 合併
std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(結果));
// 結果: {1, 2, 3, 4, 5, 6, 7}

// 交差
結果.clear();
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(結果));
// 結果: {3, 4, 5}

// 差 (v1 - v2)
結果.clear();
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(結果));
// 結果: {1, 2}

// 対称差 (v1 ∪ v2 - v1 ∩ v2)
結果.clear();
std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(結果));
// 結果: {1, 2, 6, 7}

8、よくある質問

1. sort と stable_sort の違いは？

• sort はクイックソート（実際には introsort アルゴリズム）を使用し、不安定（等しい要素の相対順序が変化する可能性あり）、平均時間計算量 O(n log n)。
• stable_sort はマージソートを使用し、安定（等しい要素の相対順序は保持される）、時間計算量 O(n log n) だが、空間コストがやや高い。

2. なぜ remove アルゴリズムは erase と併用する必要があるのか？ remove アルゴリズムは「上書き」によって削除する要素を末尾に移動し、新しい論理的な末尾のイテレータを返すが、コンテナの実際のサイズは変更されない。erase はイテレータ範囲で要素を実際に削除し、コンテナのサイズを変更する。そのため、container.erase(remove(...), container.end()) と併用する必要がある。
3. どのアルゴリズムがソート済みコンテナが必要か？ 二分検索系列（binary_search、lower_bound、upper_bound）、集合アルゴリズム（set_intersection、set_union など）、merge など。これらのアルゴリズムは順序性に依存して効率的な操作（例：二分検索 O(log n)）を実現している。