C++/標準ライブラリ/algorithm

はじめに

アルゴリズムとは

アルゴリズムとは、特定の問題を解決するための一連の手順や計算方法のことを指します。コンピュータプログラミングにおいては、与えられた入力に対して望ましい出力を得るための具体的な手順を定義したものがアルゴリズムと呼ばれます。

効率的なアルゴリズムは、プログラムの実行速度や消費するメモリ量を大幅に改善することができます。一方で、非効率的なアルゴリズムを使用すると、処理時間が指数関数的に増大したり、メモリ不足に陥ったりする可能性があります。したがって、適切なアルゴリズムを選択することは、プログラミングにおいて非常に重要です。

C++標準ライブラリにおけるアルゴリズムの役割

C++標準ライブラリには、さまざまな一般的なアルゴリズムが実装されており、<algorithm> ヘッダーからアクセスできます。これらのアルゴリズムは、コンテナやイテレータと連携して使用でき、効率的で再利用可能なコードを書くことができます。

標準アルゴリズムを利用することで、以下のようなメリットがあります。

• 既にテストされた信頼性の高い実装を使用できる
• 自作するよりも効率的なアルゴリズムが利用できる
• コードの可読性が向上し、保守性が高まる
• 一般化されたアルゴリズムなので、様々な状況で再利用できる

C++標準ライブラリのアルゴリズムを理解し、効果的に活用することは、モダンなC++プログラミングにおいて非常に重要です。

アルゴリズムヘッダーの概要

<algorithm> ヘッダーには、以下のようなさまざまなアルゴリズムが含まれています。

非変更序列操作

探索

find、count、equal など

変換

for_each、transform など

合計・積

accumulate、inner_product など

変更序列操作

コピー・入れ替え

copy、swap など)

初期化

fill、generate など)

除去

remove、unique など)

並べ替え

reverse、rotate など)

分割

partition、stable_partition など)

ソート

sort、stable_sort、nth_element、partial_sort など

ヒープ操作

make_heap、push_heap、pop_heap など

集合操作

set_union、set_intersection、set_difference など

バイナリ検索

lower_bound、upper_bound、equal_range など

その他

next_permutation、prev_permutation、random_shuffle など

これらのアルゴリズムは、コンテナの値を直接変更したり、新しいコンテナを生成したりするなど、様々な機能を提供しています。アルゴリズムの選択と適切な使い方を学ぶことで、C++プログラミングを効率的に行うことができるようになります。

非変更序列操作

非変更序列操作は、与えられた入力範囲の要素を変更せずに処理を行うアルゴリズムのグループです。この種のアルゴリズムは、主に探索、変換、合計・積の計算に使用されます。

find、count、equalなどの探索アルゴリズム

探索アルゴリズムは、指定された条件を満たす要素を入力範囲から見つける際に使用します。

• find(first, last, value) は、範囲 [first, last) から value と等しい最初の要素を見つけます。
• count(first, last, value) は、範囲 [first, last) に value が何回出現するかをカウントします。
• equal(first1, last1, first2) は、2つの範囲 [first1, last1) と [first2, ...) が等しいかどうかを判定します。

これらの探索アルゴリズムは、コンテナ内の特定の値を見つけたり、値の出現回数を数えたりする場合に便利です。

for_each、transformなどの変換アルゴリズム

変換アルゴリズムは、入力範囲の各要素に対して何らかの操作を行い、その結果を別の範囲に書き込みます。

• for_each(first, last, op) は、範囲 [first, last) の各要素に対して op の操作を適用します。
• transform(first, last, result, op) は、範囲 [first, last) の各要素に op を適用し、その結果を result から始まる範囲に書き込みます。

これらの変換アルゴリズムは、コンテナの各要素に対して同じ操作を行う場合に便利です。例えば、すべての要素を2倍にしたり、大文字に変換したりするような処理に使えます。

accumulate、inner_productなどの合計・積アルゴリズム

合計・積アルゴリズムは、入力範囲の要素を特定の方法で累積させる際に使用します。

• accumulate(first, last, init) は、範囲 [first, last) の要素の総和を init に加算した結果を返します。
• inner_product(first1, last1, first2, init) は、2つの範囲 [first1, last1) と [first2, ...) の要素の内積を init に加算した結果を返します。

これらのアルゴリズムは、コンテナの要素を合計したり、ベクトルの内積を計算したりする場合に役立ちます。accumulate は一般的な総和の計算に使えますが、inner_product はベクトル演算などの特殊な用途で利用されます。

総じて、非変更序列操作のアルゴリズムは、コンテナの要素を変更することなく、探索、変換、合計・積の計算を効率的に行うことができます。適切なアルゴリズムを選択することで、コードの可読性と保守性が向上します。

変更序列操作

変更序列操作は、与えられた入力範囲の要素を直接変更するアルゴリズムのグループです。このカテゴリには、コピー・入れ替え、初期化、除去、並べ替え、分割などのさまざまなアルゴリズムが含まれています。

copy、swapなどのコピー・入れ替えアルゴリズム

• copy(first, last, result) は、範囲 [first, last) の要素をコピーして result から始まる範囲に書き込みます。
• swap(a, b) は、2つの値 a と b を入れ替えます。
• swap_ranges(first1, last1, first2) は、2つの範囲 [first1, last1) と [first2, ...) の対応する要素を交換します。

これらのアルゴリズムは、配列やコンテナの要素をコピーしたり入れ替えたりする場合に使用します。copy は新しい範囲にデータをコピーし、swap と swap_ranges は既存のデータを入れ替えます。

fill、generateなどの初期化アルゴリズム

• fill(first, last, value) は、範囲 [first, last) の要素を value で初期化します。
• fill_n(first, n, value) は、範囲の先頭から n 個の要素を value で初期化します。
• generate(first, last, gen) は、範囲 [first, last) の各要素に gen 関数を適用した結果で初期化します。

これらのアルゴリズムは、配列やコンテナの要素を特定の値や関数で初期化する場合に使用します。fill と fill_n は固定値で初期化し、generate は関数で動的に値を生成します。

remove、uniqueなどの除去アルゴリズム

• remove(first, last, value) は、範囲 [first, last) から value に等しい要素を論理的に除去します。
• unique(first, last) は、範囲 [first, last) から連続する重複要素を論理的に除去します。

これらのアルゴリズムは、コンテナから特定の値や重複した値を除去する場合に使用します。ただし、物理的には要素を削除せず、有効な要素の範囲を返すだけです。実際の削除には、別の処理が必要になります。

reverse、rotateなどの並べ替えアルゴリズム

• reverse(first, last) は、範囲 [first, last) の要素の順序を逆転させます。
• rotate(first, middle, last) は、範囲 [first, last) の要素を回転させ、middle を先頭に移動させます。

これらのアルゴリズムは、コンテナの要素の順序を逆転したり回転させたりする場合に使用します。reverse は要素の順序を反転し、rotate は指定した位置を先頭に移動させます。

partition、stable_partitionなどの分割アルゴリズム

• partition(first, last, pred) は、範囲 [first, last) の要素を pred で分割し、pred を満たさない要素を前に、満たす要素を後ろに並べ替えます。
• stable_partition(first, last, pred) は、partition と同様の動作をしますが、相対的な要素の順序を保証します。

これらのアルゴリズムは、コンテナの要素を特定の条件で分割する場合に使用します。partition は効率的ですが要素の相対的な順序は保証されません。一方、stable_partition は若干効率が悪くなりますが、要素の順序を維持します。

変更序列操作のアルゴリズムは、コンテナの要素を直接変更する強力な機能を提供します。適切なアルゴリズムを選択し、効果的に利用することで、データの処理を効率化できます。ただし、副作用に注意する必要があります。

ソート

ソートは、コンピュータプログラミングにおける基本的で重要な操作の1つです。C++の <algorithm> ヘッダーには、さまざまなソートアルゴリズムが実装されています。

sort、stable_sortなどの並べ替えアルゴリズム

• sort(first, last) は、範囲 [first, last) の要素を昇順に並べ替えます。
• sort(first, last, comp) は、範囲 [first, last) の要素をユーザー定義の比較関数 comp に基づいて並べ替えます。
• stable_sort(first, last) は、範囲 [first, last) の要素を昇順に安定ソートします。

sort は、高速な一般的なソートアルゴリズム(イントロソート)を実装しています。stable_sort は、安定性を保証する分、若干遅くなります。比較関数を渡すことで、カスタマイズしたソート順序を実現できます。

nth_element、partial_sortなどの部分的ソート

• nth_element(first, nth, last) は、範囲 [first, last) の要素を部分的に並べ替え、nth 番目の要素が適切な位置に来るようにします。
• partial_sort(first, middle, last) は、範囲 [first, last) の前半部分 [first, middle) を昇順に並べ替えます。
• partial_sort_copy(first, last, result_first, result_last) は、範囲 [first, last) をソートし、その結果を [result_first, result_last) にコピーします。

nth_element は、n番目の要素の位置を特定する際に使用します。partial_sort は、配列の一部分のみをソートする場合に便利です。partial_sort_copy は、ソート結果を別の範囲にコピーします。

ソートの安定性と複雑度

安定性

ソートアルゴリズムが安定かどうかは、等しいキーを持つ要素の相対的な順序が保たれるかどうかで判断されます。stable_sort は安定ですが、sort は不安定です。

計算量の複雑度

ソートアルゴリズムの性能は、計算量の観点から評価されます。sort と stable_sort は、平均的に$O(n\log n)$の時間計算量を持ちます。一方、nth_element は$O(n)$の平均時間計算量を持ちますが、ワーストケースでは$O(n^{2})$となる可能性があります。

一般に、安定性を保証するソートは若干遅くなる傾向があります。また、ソートの種類によっては、ベストケース、平均、ワーストケースで計算量が大きく異なることがあります。

ソートアルゴリズムを選択する際は、安定性の要否、計算量、メモリ使用量などを考慮する必要があります。また、ソート対象のデータ量や分布によっても、適切なアルゴリズムは変わってくるでしょう。

ヒープ操作

ヒープ(Heap)は、優先度付きキューの実装などに使われるデータ構造です。C++の <algorithm> ヘッダーには、ヒープを操作するためのアルゴリズムが含まれています。

make_heap、push_heap、pop_heapなどのヒープ操作

• make_heap(first, last) は、範囲 [first, last) の要素からヒープを構築します。
• push_heap(first, last) は、範囲 [first, last) の最後の要素をヒープに追加し、ヒープ性質を維持します。
• pop_heap(first, last) は、範囲 [first, last) の先頭の要素(最大値または最小値)をヒープから取り除き、ヒープ性質を維持します。
• sort_heap(first, last) は、範囲 [first, last) のヒープを昇順に並べ替えます。

これらのアルゴリズムを使うことで、ランダムアクセスイテレータで表される範囲上にヒープを構築し、要素の追加・削除・ソートを効率的に行うことができます。

ヒープの性質とヒープソート

ヒープには以下の2つの性質があります。

ヒープ性質

ノードの値は、その子ノードの値以上(最大ヒープの場合)または以下(最小ヒープの場合)です。

完全二分木

最後のノードを除く全てのノードが、2つの子ノードを持っています。最後のノードは、左から右に並んでいます。

ヒープの利点は、最大値または最小値へのアクセスが高速($O(1)$)で、要素の追加や削除も$O(\log n)$の計算量で行えることです。

ヒープソートは、ヒープの性質を利用したソートアルゴリズムです。手順は以下の通りです。

1. make_heapで与えられた配列からヒープを構築する
2. pop_heapで最大値または最小値を取り出し、適切な位置に移動する
3. 2を残りの要素に対して繰り返す
4. sort_heapで並び替えを完了する

ヒープソートは、$O(n\log n)$の計算量を持ち、汎用的で安定したソートアルゴリズムです。ただし、メモリ使用量が多く、ランダムアクセスが必要なため、リンクリストには適していません。

ヒープ操作は、優先度付きキューの実装や、ヒープソートの基盤として役立ちます。また、ヒープの操作と性質を理解することは、効率的なアルゴリズムを設計する上で重要です。

集合操作

集合操作は、2つの集合に対して和集合、共通部分集合、差集合などの標準的な集合演算を行うアルゴリズムです。C++の <algorithm> ヘッダーには、効率的な集合操作が実装されています。

set_union、set_intersection、set_differenceなどの集合操作

• set_union(first1, last1, first2, last2, result) は、2つの範囲 [first1, last1) と [first2, last2) の和集合を result から始まる範囲に書き込みます。
• set_intersection(first1, last1, first2, last2, result) は、2つの範囲の共通部分集合を result から始まる範囲に書き込みます。
• set_difference(first1, last1, first2, last2, result) は、範囲 [first1, last1) から [first2, last2) の要素を除いた差集合を result から始まる範囲に書き込みます。
• set_symmetric_difference(first1, last1, first2, last2, result) は、2つの範囲の排他的論理和集合を result から始まる範囲に書き込みます。

これらのアルゴリズムは、ソートされた範囲に対してのみ適用可能です。入力範囲がソートされていない場合は、事前に sort アルゴリズムを使ってソートする必要があります。

集合の性質と利用例

集合操作は、以下のような集合の基本的な性質に基づいています。

同値関係

集合の要素は同値関係を満たします。つまり、反射律、対称律、推移律が成り立ちます。

重複の排除

集合には重複する要素は含まれません。

順序関係なし

集合では要素の順序は無視されます。

集合操作は、様々な分野で利用されています。例えば:

データベース

2つのテーブルの和集合、共通部分集合、差集合を求めるクエリの処理

コンパイラ

複数のヘッダファイルから必要なシンボルの集合を導出する

ネットワーク

ルーティングテーブルの更新や、アクセス制御リストの管理

自然言語処理

文書からキーワードの集合を抽出する

また、数学的な集合論における一般化された概念として、集合操作を利用することもできます。

適切な集合操作アルゴリズムを選択し、効果的に利用することで、プログラムの可読性と効率が向上します。ただし、入力データがソートされている必要があることに留意してください。

バイナリ検索

バイナリ検索は、ソートされた範囲内で特定の値を探す際に使用される高速な検索アルゴリズムです。C++の <algorithm> ヘッダーには、バイナリ検索を行うためのさまざまなアルゴリズムが実装されています。

lower_bound、upper_bound、equal_rangeなどのバイナリ検索

• lower_bound(first, last, value) は、範囲 [first, last) 内で value 以上の最初の要素を指すイテレータを返します。
• upper_bound(first, last, value) は、範囲 [first, last) 内で value より大きい最初の要素を指すイテレータを返します。
• equal_range(first, last, value) は、lower_bound と upper_bound の結果をペアで返します。

これらのアルゴリズムは、対数時間 $O(\log n)$ で検索を行うことができます。見つからない場合は、範囲の終端を指すイテレータが返されます。

• binary_search(first, last, value) は、範囲 [first, last) 内に value が存在するかどうかを判定します。

binary_search は、単に値の有無を確認するだけの目的で使用します。

前提条件と利用例

バイナリ検索アルゴリズムを使用する際の前提条件は、検索対象の範囲がソート済みであることです。範囲がソートされていない場合、結果は不確定となります。

バイナリ検索は、以下のような場面で利用できます。

• 辞書やデータベースから特定のキーを検索する
• ソートされた大規模データから特定の値を探す
• プログラムの初期設定値を二分探索で決定する
• ゲームのスコアボードから特定のランクを探す

また、lower_bound と upper_bound は、ソートされた範囲に新しい値を挿入する適切な位置を見つけるのにも役立ちます。

バイナリ検索アルゴリズムを適切に使用すれば、線形探索と比べて大幅な高速化が図れます。ただし、事前にデータをソートする必要があり、ソート自体のコストも考慮する必要があります。全体としてのパフォーマンスを考えた上で、バイナリ検索の利用を検討することが重要です。

その他のアルゴリズム

<algorithm> ヘッダーには、上記のカテゴリに分類されない有用なアルゴリズムがいくつか実装されています。

next_permutation、prev_permutationなどの順列生成

• next_permutation(first, last) は、範囲 [first, last) を次の辞書順の並び替えに変更します。
• prev_permutation(first, last) は、範囲 [first, last) を前の辞書順の並び替えに変更します。

これらのアルゴリズムは、与えられた範囲の要素の全ての順列を生成する場合に使用できます。next_permutation は辞書順で次の順列を、prev_permutation は前の順列を返します。

random_shuffleなどのシャッフル

• random_shuffle(first, last) は、範囲 [first, last) の要素を無作為に並び替えます。
• shuffle(first, last, rand) は、範囲 [first, last) の要素を指定された乱数生成器 rand を使って無作為に並び替えます。

これらのアルゴリズムは、コンテナの要素をランダムにシャッフルしたい場合に使用します。random_shuffle は標準の乱数生成器を使用しますが、shuffle ではカスタムの乱数生成器を指定できます。

その他の有用なアルゴリズム

• min_element(first, last) は、範囲 [first, last) の最小要素を指すイテレータを返します。
• max_element(first, last) は、範囲 [first, last) の最大要素を指すイテレータを返します。
• minmax_element(first, last) は、範囲 [first, last) の最小要素と最大要素をペアで返します。
• is_sorted(first, last) は、範囲 [first, last) がソート済みかどうかを判定します。
• is_partitioned(first, last, pred) は、範囲 [first, last) が pred で分割されているかどうかを判定します。

これらのアルゴリズムは、様々な目的で使用できます。最小値・最大値の取得、範囲のソート状態の確認、条件による分割の確認など、汎用的な機能を提供しています。

<algorithm> ヘッダーには、さまざまな用途に役立つアルゴリズムが実装されています。状況に応じて適切なアルゴリズムを選択し、効率的にプログラミングを行うことが重要です。

カスタムアルゴリズム

標準ライブラリに実装されているアルゴリズムだけでは、あらゆるニーズを満たすことはできません。C++ではカスタムアルゴリズムを作成することができ、これによりプログラムに合わせて特化したアルゴリズムを実装することが可能です。カスタムアルゴリズムを作成する際には、関数オブジェクトやラムダ式を活用することができます。

関数オブジェクトの利用

関数オブジェクトは、operator() をオーバーロードした関数呼び出し可能なクラスのことです。標準アルゴリズムの多くは、関数オブジェクトを受け取ることができます。これにより、アルゴリズムの動作をカスタマイズすることが可能になります。

struct AbsValue {
    int operator()(int x) const { 
        return x >= 0 ? x : -x;
    }
};

auto main() -> int {
    std::vector<int> v = {-3, -1, 0, 2, 5};
    std::transform(v.begin(), v.end(), v.begin(), AbsValue());

    // v = {3, 1, 0, 2, 5}
}

上記の例では、AbsValue という関数オブジェクトを定義し、std::transform に渡すことで、ベクトルの各要素の絶対値を計算しています。

ラムダ式の利用

C++11から導入されたラムダ式は、簡潔に無名関数を記述できる機能です。ラムダ式は関数オブジェクトと同様の役割を果たし、アルゴリズムをカスタマイズする際に非常に便利です。

auto main() -> int {
    std::vector<int> v = {1, 2, 3, 4, 5};
    int sum = std::accumulate(v.begin(), v.end(), 0, [](int x, int y) { return x + y; });

    // sum = 15
}

この例では、std::accumulate の第4引数にラムダ式を渡すことで、ベクトルの要素の合計を計算しています。ラムダ式は関数オブジェクトよりも簡潔に記述できるため、可読性が向上します。

カスタムアルゴリズムの実装例

カスタムアルゴリズムを実装する際は、イテレータやコンテナの仕組みを理解する必要があります。以下は、2つのソート済み範囲をマージする merge アルゴリズムの実装例です。

template <typename InputIt1, typename InputIt2, typename OutputIt>
OutputIt merge(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt result) {
    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2) {
            *result++ = *first1++;
        } else {
            *result++ = *first2++;
        }
    }

    return std::copy(first1, last1, std::copy(first2, last2, result));
}

この関数は、2つのソート済み範囲 [first1, last1) と [first2, last2) をマージし、結果を result から始まる範囲に書き込みます。このように、イテレータと汎用性の高いテンプレートを活用することで、再利用可能なカスタムアルゴリズムを実装することができます。

カスタムアルゴリズムを作成することで、標準ライブラリでは提供されていない機能を補完したり、特定のニーズに特化したアルゴリズムを実装したりすることが可能になります。関数オブジェクトやラムダ式を組み合わせることで、アルゴリズムの挙動をさらに詳細にカスタマイズすることもできます。

まとめ

C++の <algorithm> ヘッダーには、さまざまな高度なアルゴリズムが実装されています。これらのアルゴリズムを適切に選択し、効率的に利用することは、モダンなC++プログラミングにおいて非常に重要です。

アルゴリズムの選択と利用のポイント

アルゴリズムの機能

必要とする処理内容に適したアルゴリズムを選択します。

入出力要件

アルゴリズムが要求する入力範囲とイテレータの条件を満たしているか確認します。

計算量の複雑度

効率的な実行を行うため、アルゴリズムの計算量を考慮します。

安定性

データの順序を維持する必要があれば、安定したアルゴリズムを選びます。

メモリ使用量

使用可能なメモリ量に応じて、適切なアルゴリズムを選びます。

制約条件

ソート済みデータ、一意キーなどの制約条件を満たしているか確認します。

適切なアルゴリズムを選ぶには、アルゴリズムの機能、要件、特性を理解する必要があります。状況に応じて、複数の候補からトレードオフを検討し、最適なアルゴリズムを選択することが重要です。

アルゴリズムの効率的な利用

一時コンテナの最小化

アルゴリズムが一時コンテナを使用する場合、メモリ使用量に注意します。

範囲の最小化

アルゴリズムに渡す範囲を必要最小限に絞り込むことで、計算量を削減できます。

適切な関数オブジェクト

カスタム関数オブジェクトを使用することで、アルゴリズムの動作をカスタマイズできます。

ラムダ式の活用

ラムダ式は簡潔でわかりやすいコードを記述できます。

カスタムアルゴリズムの作成

標準ライブラリでは対応できない処理には、カスタムアルゴリズムを実装します。

プロファイリングとチューニング

プログラムの実行プロファイルを測定し、ボトルネックとなる部分を最適化します。

アルゴリズムを効率的に利用するためには、メモリ使用量、計算量、カスタマイズ性などを考慮する必要があります。また、プロファイリングによってボトルネックを発見し、チューニングすることも重要です。

C++の <algorithm> ヘッダーには多くの高機能なアルゴリズムが実装されていますが、それらを適切に選択し効率的に利用することが、パフォーマンスの良いプログラムを作成する上で不可欠です。アルゴリズムの特性を理解し、状況に応じて最適なアプローチを取ることが大切です。