実行できるC++ドキュメント: アルゴリズム

Q: C++ の ヘッダとは何ですか？

は、std::find、std::sort、std::count_if、std::transform のような汎用関数を収めた標準ライブラリのヘッダです。これらはイテレータのペア（通常は begin() と end()）で記述される範囲を対象に動作するため、同じアルゴリズムが vector、array、string、あるいはイテレータを公開する任意のコンテナで動作します。

Q: C++ で vector の中に値が存在するか確認するには？

std::find を使います: auto it = find(v.begin(), v.end(), target);。it == v.end() なら値は存在せず、そうでなければ it は最初の一致を指します。正確な値ではなく条件をテストしたい場合は、述語を伴う std::any_of を使います。

Q: なぜ std::remove はコンテナから要素を実際には削除しないのですか？

アルゴリズムはコンテナではなくイテレータしか見ないため、std::remove はコンテナを縮められません。残す要素を前方に詰め、新しい論理的な末尾を指すイテレータを返すだけです。余りを物理的に取り除くには、続けて v.erase(...)（erase-remove イディオム）を呼ぶ必要があります。

書かなくてよいループ

前のページで、すべてのコンテナがイテレータ - begin() と end() を備えた軽量なカーソル - を渡すことを見ました。この抽象化こそが、標準アルゴリズムが存在する理由のすべてです。データを検索・カウント・変換したいたびに生の for ループを書く代わりに、<algorithm> の名前付き関数を呼び出して範囲を渡します。

範囲とは単に 2 つのイテレータです。どこから始め、どこの 1 つ手前で止めるか、です。すべてのアルゴリズムがこの同じイテレータの言語を話すので、同じ find が vector、string、素の配列のいずれでも動作します。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {4, 8, 15, 16, 23, 42};

    // 16 は範囲 [begin, end) の中にあるか？
    auto it = find(v.begin(), v.end(), 16);

    if (it != v.end())
        cout << "found " << *it << " at index " << (it - v.begin()) << "\n";
    else
        cout << "not found\n";
    return 0;
}

身につけるべきパターン: 検索を行うアルゴリズムは「何も見つからなかった」という意味で end() イテレータを返します。結果を間接参照する前に必ず end() と比較しましょう。end() の間接参照は未定義動作です。

述語によるカウントとテスト

多くのアルゴリズムは述語 - 各要素に対して bool を返す関数（通常はラムダ）- を受け取ります。count_if は一致をカウントし、all_of、any_of、none_of は範囲全体についての yes/no の問いに答えます。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> scores = {42, 88, 17, 95, 63, 71};

    int passed = count_if(scores.begin(), scores.end(),
                          [](int s) { return s >= 60; });

    bool allPositive = all_of(scores.begin(), scores.end(),
                              [](int s) { return s > 0; });

    bool anyPerfect = any_of(scores.begin(), scores.end(),
                             [](int s) { return s == 100; });

    cout << passed << " passed\n";          // 4 件が合格
    cout << "all positive? " << allPositive << "\n";  // 1
    cout << "any perfect? " << anyPerfect << "\n";    // 0
    return 0;
}

std::count（_if なし）は、条件ではなく正確な値をカウントする、よりシンプルな親戚です。テストが「この特定の値」ではなく「ルールに一致するもの何でも」になった瞬間に、述語版に手を伸ばしましょう。

範囲の変換と畳み込み

2 つの働き者がデータ処理の大半をカバーします。std::transform は各要素を関数を通して写像し、std::accumulate（<algorithm> ではなく <numeric> から）は範囲を 1 つの値に畳み込みます。

transform は結果を出力イテレータを通して書き込みます。よくある危険な間違いは、出力を空の vector に向けることです。アルゴリズムはすでに空きがあると想定し、末尾を越えて書き込みます。出力先を先にサイズ設定するか、各結果が push_back されるように back_inserter を使いましょう。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4};
    vector<int> squares;   // 空 - まだ空きがない

    // back_inserter は結果が届くにつれて `squares` を成長させる
    transform(nums.begin(), nums.end(), back_inserter(squares),
              [](int n) { return n * n; });

    for (int s : squares) cout << s << " ";  // 1 4 9 16
    cout << "\n";
    return 0;
}

accumulate は初期値から始まり、要素を左から右へ結合します。初期値の型が重要です。0（int）を渡すと合計は int で計算され、オーバーフローや切り捨てが起こり得ます。

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    vector<double> prices = {9.99, 4.50, 19.95};

    // 累計が double のままになるよう 0.0（double）から始める。
    double total = accumulate(prices.begin(), prices.end(), 0.0);

    cout << "total: " << total << "\n";  // total: 34.44
    return 0;
}

もし accumulate(prices.begin(), prices.end(), 0) と int の初期値で書いていたら、各加算は int で行われ、セント単位が消えてしまいます。初期値の型が、結果の型を静かに決定するのです。

erase-remove イディオム

ここが誰もが驚く落とし穴です。std::remove はコンテナから何も削除しません。アルゴリズムはイテレータしか持たないので、コンテナのサイズを変えられません。そもそもコンテナの存在すら知らないのです。remove が実際に行うのは、残すすべての要素を前方へ移動し、末尾を未規定の状態にして、新しい論理的な末尾を指すイテレータを返すことです。

// remove 単独ではサイズは変わらない - これがバグ:
remove(v.begin(), v.end(), 0);  // 無視した戻り値のイテレータを返す
// v は依然として元のサイズ。末尾はゴミ

要素を本当に削除するには、remove をコンテナの erase と組み合わせます。だからこそ erase-remove イディオムと呼ばれます。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 0, 7, 0, 1, 0, 9};

    // 1. remove は非ゼロを前方へ詰め、新しい末尾を返す
    // 2. erase はそこから本当の末尾までをすべて切り落とす
    v.erase(remove(v.begin(), v.end(), 0), v.end());

    for (int n : v) cout << n << " ";  // 3 7 1 9
    cout << "\n";
    return 0;
}

正確な値ではなく述語を使う場合は remove_if を使います。C++20 では、両方のステップを代わりにこなしてくれる自由関数 std::erase / std::erase_if で、この一連の手順をまるごと省けます: erase(v, 0);。

イテレータは有効期間を越えると自己責任

アルゴリズムはイテレータを返すため、それらのイテレータは前のページで出会ったのと同じ無効化規則の対象になります。イテレータを保存してからコンテナを変更すること - 再確保を引き起こす push_back や erase - は、保存したイテレータをダングリング状態にし、それを使うのは未定義動作です。

auto it = find(v.begin(), v.end(), 16);
v.push_back(99);   // v のストレージを再確保するかもしれない
cout << *it;       // BUG: `it` は今や解放済みメモリを指しているかもしれない

安全な習慣: アルゴリズムが返すイテレータは、コンテナをリサイズしたり再確保したりし得るあらゆる操作の前にすぐに使いましょう。結果に基づいてコンテナを変更する必要がある場合は、代わりにインデックス（it - v.begin()）を取得します。インデックスは再確保を生き延びるからです。

次へ: ソート

これで検索・カウント・変換・畳み込みを見てきましたが、独立したページに値するほど重要なアルゴリズムが 1 つあります。std::sort は範囲をその場で並べ替え、データがいったんソートされると、より高速でソート済みデータ専用の一群のアルゴリズム（binary_search、lower_bound、equal_range）が使えるようになります。次はソートを掘り下げます。カスタム比較子の与え方、sort と stable_sort の違い、そして未定義動作を避けるために比較関数が守らねばならない規則についてです。

よくある質問

C++ の <algorithm> ヘッダとは何ですか？

<algorithm> は、std::find、std::sort、std::count_if、std::transform のような汎用関数を収めた標準ライブラリのヘッダです。これらはイテレータのペア（通常は begin() と end()）で記述される範囲を対象に動作するため、同じアルゴリズムが vector、array、string、あるいはイテレータを公開する任意のコンテナで動作します。

C++ で vector の中に値が存在するか確認するには？

std::find を使います: auto it = find(v.begin(), v.end(), target);。it == v.end() なら値は存在せず、そうでなければ it は最初の一致を指します。正確な値ではなく条件をテストしたい場合は、述語を伴う std::any_of を使います。

なぜ std::remove はコンテナから要素を実際には削除しないのですか？

アルゴリズムはコンテナではなくイテレータしか見ないため、std::remove はコンテナを縮められません。残す要素を前方に詰め、新しい論理的な末尾を指すイテレータを返すだけです。余りを物理的に取り除くには、続けて v.erase(...)（erase-remove イディオム）を呼ぶ必要があります。