C++の標準ライブラリは、効率的なデータ操作を支援する多くのアルゴリズムを提供しています。これらのアルゴリズムは、コンテナ内の要素を検索、変更、並べ替え、統計情報の取得など、さまざまな目的で使用されます。

1. 非変更アルゴリズム

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

1.1 find と find_if

• find(first, last, value): 指定した値と一致する最初の要素を検索します。
• find_if(first, last, pred): 条件を満たす最初の要素を検索します。
• find_end(first, last, s_first, s_last): サブシーケンスが最後に現れる位置を検索します。

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

auto itr = std::find(numbers.begin(), numbers.end(), 5);
if (itr != numbers.end()) {
    std::cout << "見つかった: " << *itr << std::endl;  // 出力: 5
}

auto itr2 = std::find_if(numbers.begin(), numbers.end(), [](int x) {
    return x > 6;
});
std::cout << "最初の6より大きい数: " << *itr2 << std::endl;  // 出力: 7

std::vector<int> subseq = {3, 5};
auto itr3 = std::find_end(numbers.begin(), numbers.end(), subseq.begin(), subseq.end());
if (itr3 != numbers.end()) {
    std::cout << "サブシーケンスの開始位置: " << std::distance(numbers.begin(), itr3) << std::endl;  // 出力: 1
}

1.2 count と count_if

• count(first, last, value): 指定した値と一致する要素の数をカウントします。
• count_if(first, last, pred): 条件を満たす要素の数をカウントします。

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

1.3 for_each

範囲内の各要素に対して関数を適用します。

std::vector<int> values = {1, 2, 3, 4, 5};
std::for_each(values.begin(), values.end(), [](int& x) {
    x *= 2; // 各要素を2倍にする
});
// 現在valuesは{2, 4, 6, 8, 10}

1.4 equal と mismatch

• equal(first1, last1, first2): 2つの範囲が等しいかどうかをチェックします。
• mismatch(first1, last1, first2): 2つの範囲内で初めて異なる要素のイテレータペアを返します。

std::vector<int> vec_a = {1, 2, 3};
std::vector<int> vec_b = {1, 2, 4};
std::vector<int> vec_c = {1, 2, 3, 4};

bool are_equal = std::equal(vec_a.begin(), vec_a.end(), vec_b.begin());
std::cout << "vec_a == vec_b? " << std::boolalpha << are_equal << std::endl;  // 出力: false

auto miss = std::mismatch(vec_a.begin(), vec_a.end(), vec_c.begin());
if (miss.first != vec_a.end()) {
    std::cout << "不一致: " << *miss.first << " vs " << *miss.second << std::endl;  // 出力なし（最初の3要素が一致）
}

1.5 all_of, any_of, none_of

範囲内の要素がすべて、いずれか、または一つも条件を満たさないかをチェックします。

std::vector<int> values = {2, 4, 6, 8};
bool all_even = std::all_of(values.begin(), values.end(), [](int x) {
    return x % 2 == 0;
}); // true
bool any_odd = std::any_of(values.begin(), values.end(), [](int x) {
    return x % 2 != 0;
}); // false
bool none_negative = std::none_of(values.begin(), values.end(), [](int x) {
    return x < 0;
}); // true

2. 変更アルゴリズム

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

2.1 copy と copy_if

• copy(first, last, dest): 要素をコピーします。
• copy_if(first, last, dest, pred): 条件を満たす要素のみをコピーします。

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(source.size());

std::copy(source.begin(), source.end(), destination.begin());  // destination: [1,2,3,4,5]

std::vector<int> evens;
std::copy_if(source.begin(), source.end(), std::back_inserter(evens), [](int x) {
    return x % 2 == 0;
});  // evens: [2,4]

2.2 transform

範囲内の各要素に対して関数を適用し、結果を別の範囲に格納します。

std::vector<int> numbers = {1, 2, 3};
std::vector<int> squares(numbers.size());

std::transform(numbers.begin(), numbers.end(), squares.begin(), [](int x) {
    return x * x;
});  // squares: [1,4,9]

std::vector<int> vec_a = {1, 2, 3};
std::vector<int> vec_b = {4, 5, 6};
std::vector<int> sums(vec_a.size());
std::transform(vec_a.begin(), vec_a.end(), vec_b.begin(), sums.begin(), [](int x, int y) {
    return x + y;
});  // sums: [5,7,9]

2.3 replace, replace_if, replace_copy

• replace(first, last, old_val, new_val): 指定した値を別の値に置き換えます。
• replace_if(first, last, pred, new_val): 条件を満たす要素を別の値に置き換えます。
• replace_copy(first, last, dest, old_val, new_val): コピー時に置き換えます。

std::vector<int> numbers = {1, 2, 3, 2, 5};

std::replace(numbers.begin(), numbers.end(), 2, 20);  // numbers: [1,20,3,20,5]

std::replace_if(numbers.begin(), numbers.end(), [](int x) {
    return x > 10;
}, 0);  // numbers: [1,0,3,0,5]

std::vector<int> results;
std::replace_copy(numbers.begin(), numbers.end(), std::back_inserter(results), 3, 300);  // results: [1,0,300,0,5]

2.4 remove, remove_if, erase

• remove(first, last, val): 指定した値を末尾に移動します。
• remove_if(first, last, pred): 条件を満たす要素を末尾に移動します。
• erase(first, last): 実際に要素を削除します。

std::vector<int> numbers = {1, 2, 3, 2, 4};

auto new_end = std::remove(numbers.begin(), numbers.end(), 2);  // numbers: [1,3,4,2,2]
numbers.erase(new_end, numbers.end());  // numbers: [1,3,4]

numbers = {1, 2, 3, 4, 5};
numbers.erase(std::remove_if(numbers.begin(), numbers.end(), [](int x) {
    return x % 2 == 0;
}), numbers.end());  // numbers: [1,3,5]

2.5 unique

連続する重複要素を削除し、新しい論理的終端イテレータを返します。

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()); // vecは{3, 4, 5, 1, 2}になる

2.8 shuffle

範囲内の要素をランダムにシャッフルします。

#include <random>
#include <algorithm>

std::vector<int> vec = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(vec.begin(), vec.end(), gen); // vecの要素がランダムに並び替わる

3. ソートと関連アルゴリズム

3.1 sort, stable_sort, partial_sort

• sort(first, last): 要素をソートします。
• stable_sort(first, last): 相等な要素の相対的な順序を保ちながらソートします。
• partial_sort(first, middle, last): 最初のmiddle個の要素をソートします。

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::vector<std::pair<int, int>> pairs = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
    return a.first < b.first;
});

std::vector<int> vec2 = {5, 3, 1, 4, 2, 6};
std::partial_sort(vec2.begin(), vec2.begin() + 3, vec2.end());
// vec2の最初の3要素は{1, 2, 3}になり、残りはソートされていない

3.2 nth_element

指定された位置の要素をソートされた位置に移動します。

std::vector<int> vec = {5, 3, 1, 4, 2, 6};
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(first, last, value): 指定した値が存在するかをチェックします。
• lower_bound(first, last, value): 指定した値以上の最初の要素のイテレータを返します。
• upper_bound(first, last, value): 指定した値を超える最初の要素のイテレータを返します。

std::vector<int> sorted = {1, 3, 3, 5, 7};

bool exists = std::binary_search(sorted.begin(), sorted.end(), 3);  // true

auto lb = std::lower_bound(sorted.begin(), sorted.end(), 3);
std::cout << "lower_boundのインデックス: " << std::distance(sorted.begin(), lb) << std::endl;  // 出力: 1

auto ub = std::upper_bound(sorted.begin(), sorted.end(), 3);
std::cout << "upper_boundのインデックス: " << std::distance(sorted.begin(), ub) << std::endl;  // 出力: 3

3.4 merge

2つのソート済みの範囲をマージして新しいコンテナに格納します。

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

std::merge(a.begin(), a.end(), b.begin(), b.end(), merged.begin());  // merged: [1,2,3,4,5,6]

4. ヒープアルゴリズム

STLは範囲をヒープとして操作するためのアルゴリズムを提供しています。

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_value = 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. 数値アルゴリズム（<numeric>ヘッダ）

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

1つのソート済み範囲が別のソート済み範囲を含むかどうかをチェックします。

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}