C++ アルゴリズムライブラリ<algorithm>

C++ 標準ライブラリの<algorithm>ヘッダーファイルは、コンテナ（配列、ベクター、リストなど）を操作するための一連のアルゴリズムを提供します。これらのアルゴリズムには、ソート、探索、コピー、比較などが含まれ、効率的で再利用可能なコードを記述するための重要なツールです。

<algorithm>ヘッダーファイルは、コンテナがイテレータをサポートしている限り、あらゆるタイプのコンテナに適用できるテンプレート関数のセットを定義しています。これらのアルゴリズムは通常、操作の開始位置と終了位置を示す2つ以上のイテレータを引数として受け取ります。

構文

ほとんどの<algorithm>内の関数は以下の基本構文に従います：

algorithm_name(container.begin(), container.end(), ...);

ここでのcontainerはコンテナオブジェクトです。begin()とend()はコンテナのメンバ関数で、コンテナの先頭と末尾を指すイテレータを返します。

実例

1. ソートアルゴリズム

関数：sort

定義：コンテナ内の要素をソートします。

構文：

sort(container.begin(), container.end(), compare_function);

ここで compare_function はソート方法をカスタマイズするためのオプションの比較関数です。

実例

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6};
    std::sort(numbers.begin(), numbers.end());

    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

出力結果：

1 2 5 5 6 9

std::partial_sort部分的な区間をソートし、先頭の n 個の要素を整列させます。

std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());

std::stable_sort: 安定ソートで、等しい要素の相対的な順序を保持します。

std::stable_sort(vec.begin(), vec.end());

2. 探索アルゴリズム

関数：find

定義：コンテナ内で指定された値に一致する最初の要素を検索します。

構文：

auto it = find(container.begin(), container.end(), value);

見つかった場合、it は一致する要素を指します。見つからなかった場合、it は container.end() と等しくなります。

実例

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    auto it = std::find(numbers.begin(), numbers.end(), 3);

    if (it != numbers.end()) {
        std::cout << "Found: " << *it << std::endl;
    } else {
        std::cout << "Value not found." << std::endl;
    }

    return 0;
}

出力結果：

Found: 3

std::binary_search: ソート済みの区間に対して二分探索を行います。

std::sort(vec.begin(), vec.end());  // 先排序
bool found = std::binary_search(vec.begin(), vec.end(), 4);

std::find_if: 特定の条件を満たす最初の要素を検索します。

auto it = std::find_if(vec.begin(), vec.end(), [](int x) { return x > 3; });

3. コピーアルゴリズム

関数：copy

定義：ある範囲内の要素を別のコンテナまたは配列にコピーします。

構文：

copy(source_begin, source_end, destination_begin);

実例：

実例

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> source = {1, 2, 3, 4, 5};
    int destination[5];
    std::copy(source.begin(), source.end(), destination);

    for (int i = 0; i < 5; ++i) {
        std::cout << destination[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

出力結果：

1 2 3 4 5

4. 比較アルゴリズム

関数：equal

定義：2つのコンテナまたは2つの範囲内の要素が等しいかどうかを比較します。

構文：

bool result = equal(first1, last1, first2);

或

bool result = equal(first1, last1, first2, compare_function);

実例

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {1, 2, 3, 4, 5};

    bool are_equal = std::equal(v1.begin(), v1.end(), v2.begin());
    std::cout << (are_equal ? "Vectors are equal." : "Vectors are not equal.") << std::endl;

    return 0;
}

出力結果：

Vectors are equal.

5. 変更アルゴリズム

std::reverse: 区間内の要素の順序を反転させます。

std::reverse(vec.begin(), vec.end());

std::fill: 指定された区間内のすべての要素に特定の値を代入します。

std::fill(vec.begin(), vec.end(), 0);  // 所有元素设为 0

std::replace: 区間内の特定の値を別の値に置き換えます。

std::replace(vec.begin(), vec.end(), 1, 99);  // 将所有 1 替换为 99

std::copy: 区間内の要素を別の区間にコピーします。

std::vector<int> vec2(6);
std::copy(vec.begin(), vec.end(), vec2.begin());

6. 順列アルゴリズム

std::next_permutation: 辞書順で次の順列を生成し、次の順列がない場合は false を返します。

std::vector<int> vec = {1, 2, 3};
do {
    for (int n : vec) std::cout << n << " ";
    std::cout << std::endl;
} while (std::next_permutation(vec.begin(), vec.end()));

std::prev_permutation: 辞書順で前の順列を生成します。

std::prev_permutation(vec.begin(), vec.end());

7. マージアルゴリズム

std::merge: 2つのソート済みの区間を1つのソート済みの区間にマージします。

std::vector<int> vec1 = {1, 3, 5};
std::vector<int> vec2 = {2, 4, 6};
std::vector<int> result(6);
std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

std::inplace_merge: 単一の区間内で2つのソート済みの部分区間をマージします。

std::inplace_merge(vec.begin(), middle, vec.end());

8. 集合アルゴリズム

std::set_union: 2つのソート済み集合の和集合を計算します。

std::vector<int> result(10);
auto it = std::set_union(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
result.resize(it - result.begin());

std::set_intersection: 2つのソート済み集合の積集合を計算します。

auto it = std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
result.resize(it - result.begin());

std::set_difference: 集合の差集合を計算します。

auto it = std::set_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
result.resize(it - result.begin());

9. その他の便利なアルゴリズム

std::accumulate（<numeric> ライブラリが必要です）: 範囲内の要素の累積和を計算します。

#include <numeric>
int sum = std::accumulate(vec.begin(), vec.end(), 0);

std::for_each: 区間内の各要素に対して操作を実行します。

std::for_each(vec.begin(), vec.end(), [](int& x) { x += 1; });

std::min_elementとstd::max_element: 区間内の最小値と最大値を検索します。

auto min_it = std::min_element(vec.begin(), vec.end());
auto max_it = std::max_element(vec.begin(), vec.end());

<algorithm>は C++ 標準ライブラリの中でも非常に強力なツールであり、大量の汎用アルゴリズムを提供して、プログラミングを大幅に簡素化することができます。

その他の拡張