最終更新日時(UTC): 2024年12月05日 02時54分34秒
Akira Takahashi が更新

履歴 編集

<algorithm>

# algorithm

全てのアルゴリズムはデータ構造の実装の詳細から切り離されていて、イテレータによってパラメータ化されている。これはアルゴリズムの要件を満たすイテレータを提供しているなら、どのようなデータ構造であっても動作するということを示している。

このヘッダでは、以下の標準ヘッダをインクルードする：

- `<initializer_list>` (C++11)

### テンプレートパラメータ名とイテレータ要件

`<algorithm>`ヘッダでは、各アルゴリズムのテンプレートパラメータ名を、型の要件を表すために使っている。アルゴリズムを正しく利用するためには、テンプレートパラメータ名に応じたこれらの要件を満たしている必要がある。以下の通りである。

テンプレートパラメータ名 | 要件
--- | ---
InputIterator InputIterator1 InputIterator2 | input iterator
OutputIterator OutputIterator1 OutputIterator2 | output iterator
ForwardIterator ForwardIterator1 ForwardIterator2 | forward iterator
BidirectionalIterator BidirectionalIterator1 BidirectionalIterator2 | bidirectional iterator
RandomAccessIterator RandomAccessIterator1 RandomAccessIterator2 | random-access iterator

もし「効果」のセクションで、イテレータの値を書き換えるという旨の文章が書かれている場合、その引数の型は mutable iterator の要件を満たしていなければならないという追加の要件がある。 もちろん、output iterator は常に書き換え可能であるため、この追加の要件は無意味である。

テンプレートパラメータ名が `Predicate` となっている場合、`Predicate` の値 `pred` と、引数として渡すイテレータ `i` について以下の要件を満たす必要がある

- `pred(*i)` が `bool` として評価できなければならない。
- `pred(*i)` 内で `*i` を書き変えてはならない。

テンプレートパラメータ名が `BinaryPredicate` となっている場合、`BinaryPredicate` の値 `binary_pred` と、引数として渡すイテレータ `i1`, `i2` について以下の要件を満たす必要がある

- `binary_pred(*i1, *i2)` が `bool` として評価できなければならない。
- `binary_pred(*i1, *i2)` 内で `*i1` や `*i2` を書き変えてはならない。

### 要素の書き換え操作

関数オブジェクトを使用するアルゴリズムでは、`for_each`と`for_each_n`以外、プログラム定義の関数に引数として渡された要素を書き換えてはならない。

### 関数オブジェクトの取り扱い

関数オブジェクトを引数に取る `for_each`, `for_each_n` 以外のアルゴリズムは、内部処理においてその関数オブジェクトをコピーする可能性がある。

そのため、アルゴリズムの利用者はそのことに注意する必要がある。コピーされてしまうことが問題である場合、`reference_wrapper<T>` や同様の解決手段を使ってオブジェクトの中身をコピーしないようなラッパークラスを使うといった対策を行う必要がある。

### `_copy`サフィックス付きアルゴリズム

いくつかのアルゴリズムは `_copy` というサフィックスが付いている。これは `_copy` サフィックスの付いていないアルゴリズムと違い、処理の結果を別のイテレータへ出力するアルゴリズムである。

コピーバージョンを含めるかどうかの判断は、通常バージョンの計算量を考慮する。操作を行うコストがコピーのコストを大きく上回る場合、コピーバージョンは含めないようになっている。例えば `sort_copy` は存在しない。なぜなら、ソートのコストは大きいし、そのような場合、ユーザは `copy` してから `sort` するからだ。

### イテレータ操作に関する補足

アルゴリズムの説明で `+` や `-` を使っているが、random-access iterator 以外のイテレータはそれを定義していない。そういった場合、 `a+n` というのは

    X tmp = a;
    advance(tmp, n);
    return tmp;

を意味する。また、`b-a` は

    return distance(a, b);

を意味する。

### 射影とRangeサポート（C++20）

C++20ではアルゴリズム関数の新しいバージョンが`std::ranges`名前空間に追加された。従来の関数と比べて以下の点が異なる：

- テンプレート引数がコンセプトによって制約される
- イテレータの組に加えて、範囲(Range)も直接渡せる
- 射影(Projection)をサポートする
- ADLで発見されない

新しいアルゴリズム関数には範囲(Range)を直接渡すことができる。

    // 従来のアルゴリズム関数
    sort(v.begin(), v.end());
    // C++20以降の新しいアルゴリズム関数: Rangeを直接渡せる
    ranges::sort(v);
    // イテレータ対も渡せる
    ranges::sort(v.begin(), v.end());

射影は、述語とは別に渡すことができる関数オブジェクトで、特定のメンバだけを対象にアルゴリズムを実行するために用いる。

例えば、クラス型の配列のソートでは、特定のメンバによってソートしたいことはよくある。しかし、従来のアルゴリズム関数では特定のメンバで比較を行う述語を用意しなければならなかった。

    struct Person {
      string name;
      int age = 0;
    };

    vector<Person> pv = { … };

    sort(pv.begin(), pv.end(), [](auto&& a, auto&& b){ return a.name < b.name; });

これは、述語がメンバの選択と比較という2つの仕事をしてしまっている点でよくない。この責務を分割し、メンバの選択だけを行うようにしたものが射影である。

    // デフォルトの述語(ranges::less{})で、nameでソート
    ranges::sort(pv, {}, [](auto&& a){ return a.name; });
    // std::invokeで呼び出されるため、メンバ変数ポインタでもよい
    ranges::sort(pv, {}, &Person::name);

なお、各関数の説明においては、射影の影響は無視していることがある。

## シーケンスを変更しない操作

名前 | 説明 | 対応バージョン
--- | --- | ---
`all_of` | 全ての要素が条件を満たしているかを調べる | C++11
`any_of` | どれかの要素が条件を満たしているかを調べる | C++11
`none_of` | 全ての要素が条件を満たしていないかを調べる | C++11
`for_each` | 全ての要素に対して処理を行う |
`for_each_n` | 範囲の先頭N個の要素に対して処理を行う | C++17
`find` | 指定された値を検索する |
`find_if` | 条件を満たす最初の要素を検索する |
`find_if_not` | 条件を満たしていない最初の要素を検索する | C++11
`find_end` | 指定された最後のサブシーケンスを検索する |
`find_first_of` | ある集合の1つとマッチする最初の要素を検索する |
`adjacent_find` | 隣接する要素で条件を満たしている最初の要素を検索する |
`count` | 指定された値である要素の数を数える |
`count_if` | 条件を満たしている要素の数を数える |
`mismatch` | 2つの範囲が一致していない場所を検索する |
`equal` | 2つの範囲を等値比較する |
`search` | 指定された最初のサブシーケンスを検索する |
`search_n` | 指定された最初のサブシーケンスを検索する |
`ranges::all_of` | 全ての要素が条件を満たしているかを調べる | C++20
`ranges::any_of` | どれかの要素が条件を満たしているかを調べる | C++20
`ranges::none_of` | 全ての要素が条件を満たしていないかを調べる | C++20
`ranges::contains` | シーケンスの中に指定された要素があるか調べる | C++23
`ranges::contains_subrange` | シーケンスの中に指定されたシーケンスがあるか調べる | C++23
`ranges::for_each` | 全ての要素に対して処理を行う | C++20
`ranges::for_each_n` | 範囲の先頭N個の要素に対して処理を行う | C++20
`ranges::find` | 指定された値を検索する | C++20
`ranges::find_if` | 条件を満たす最初の要素を検索する | C++20
`ranges::find_if_not` | 条件を満たしていない最初の要素を検索する | C++20
`ranges::find_last` | 指定された値を末尾から検索する | C++23
`ranges::find_last_if` | 条件を満たす最後の要素を検索する | C++23
`ranges::find_last_if_not` | 条件を満たしていない最後の要素を検索する | C++23
`ranges::find_end` | 指定された最後のサブシーケンスを検索する | C++20
`ranges::find_first_of` | ある集合の1つとマッチする最初の要素を検索する | C++20
`ranges::adjacent_find` | 隣接する要素で条件を満たしている最初の要素を検索する | C++20
`ranges::count` | 指定された値である要素の数を数える | C++20
`ranges::count_if` | 条件を満たしている要素の数を数える | C++20
`ranges::mismatch` | 2つの範囲が一致していない場所を検索する | C++20
`ranges::equal` | 2つの範囲を等値比較する | C++20
`ranges::search` | 指定された最初のサブシーケンスを検索する | C++20
`ranges::search_n` | 指定された最初のサブシーケンスを検索する | C++20
`ranges::starts_with` | 先頭が指定されたシーケンスと一致するかを調べる | C++23
`ranges::ends_with` | 末尾が指定されたシーケンスと一致するかを調べる | C++23

### `fold`アルゴリズム

`fold`操作は、初期値及び累積値とともに範囲の各要素について与えられた関数を適用していき、その結果を返すものである。これは、数値集計処理に特化した`accumulate`を改善しより汎用的にしたものである。処理を範囲のどちら側から始めるかによって、`foldl`（`fold_left`）と`foldr`（`fold_right`）の2種類がある。

名前 | 説明 | 対応バージョン
--- | --- | ---
`ranges::fold_left` | 範囲の左（先頭）からの`fold` | C++23
`ranges::fold_right` | 範囲の右（終端）からの`fold` | C++23
`ranges::fold_left_first` | 範囲の左（先頭）からの`fold`、初期値を省略する | C++23
`ranges::fold_right_last` | 範囲の右（終端）からの`fold`、初期値を省略する | C++23
`ranges::fold_left_with_iter` | 範囲の左（先頭）からの`fold`、終端イテレータを返す | C++23
`ranges::fold_left_first_with_iter` | 範囲の左（先頭）からの`fold`、初期値を省略し終端イテレータを返す | C++23

## シーケンスを変更する操作

名前 | 説明 | 対応バージョン
--- | --- | ---
`copy` | 指定された範囲の要素をコピーする |
`copy_n` | 指定された数の要素をコピーする | C++11
`copy_if` | 条件を満たす要素のみをコピーする | C++11
`copy_backward` | 指定された範囲の要素を後ろからコピーする |
`move` | 指定された範囲の要素をムーブする | C++11
`move_backward` | 指定された範囲の要素を後ろからムーブする | C++11
`swap_ranges` | 指定された2つの範囲同士を swap する |
`iter_swap` | 2つのイテレータの要素を swap する |
`transform` | 全ての要素に関数を適用する |
`replace` | 指定された値と一致する要素を指定された値に置き換える |
`replace_if` | 条件を満たす要素を指定された値に置き換える |
`replace_copy` | 指定された値を一致する要素を指定された値に置き換え、その結果を出力の範囲へコピーする |
`replace_copy_if` | 条件を満たす要素を指定された値に置き換え、その結果を出力の範囲へコピーする |
`fill` | 指定された値で出力の範囲に書き込む |
`fill_n` | 指定された値で出力の範囲に n 個書き込む |
`generate` | 出力の範囲へ関数の結果を書き込む |
`generate_n` | 出力の範囲へ関数の結果を n 個書き込む |
`remove` | 指定された要素を除ける |
`remove_if` | 条件を満たす要素を除ける |
`remove_copy` | 指定された要素を除け、その結果を出力の範囲へコピーする |
`remove_copy_if` | 条件を満たす要素を除け、その結果を出力の範囲へコピーする |
`unique` | 重複した要素を除ける |
`unique_copy` | 重複した要素を除け、その結果を出力の範囲へコピーする |
`reverse` | 要素の並びを逆にする |
`reverse_copy` | 要素の並びを逆にし、その結果を出力の範囲へコピーする |
`rotate` | 要素の並びを回転させる |
`rotate_copy` | 要素の並びを回転させ、その結果を出力の範囲へコピーする |
`shift_left` | 要素を左にシフトさせる | C++20
`shift_right` | 要素を右にシフトさせる | C++20
`sample` | 範囲から指定された個数の要素をランダムに抽出する | C++17
`random_shuffle` | それぞれの要素をランダムな位置に移動させる | C++14から非推奨 C++17で削除
`shuffle` | それぞれの要素をランダムな位置に移動させる | C++11
`is_partitioned` | 与えられた範囲が条件によって区分化されているか判定する | C++11
`partition` | 与えられた範囲を条件によって区分化する |
`stable_partition` | 与えられた範囲を相対順序を保ちながら条件によって区分化する |
`partition_copy` | 与えられた範囲を条件によって 2 つの出力の範囲へ分けてコピーする | C++11
`partition_point` | 与えられた範囲から条件によって区分化されている位置を得る | C++11
`ranges::copy` | 指定された範囲の要素をコピーする | C++20
`ranges::copy_n` | 指定された数の要素をコピーする | C++20
`ranges::copy_if` | 条件を満たす要素のみをコピーする | C++20
`ranges::copy_backward` | 指定された範囲の要素を後ろからコピーする | C++20
`ranges::move` | 指定された範囲の要素をムーブする | C++20
`ranges::move_backward` | 指定された範囲の要素を後ろからムーブする | C++20
`ranges::swap_ranges` | 指定された2つの範囲同士を swap する | C++20
`ranges::transform` | 全ての要素に関数を適用する | C++20
`ranges::replace` | 指定された値と一致する要素を指定された値に置き換える | C++20
`ranges::replace_if` | 条件を満たす要素を指定された値に置き換える | C++20
`ranges::replace_copy` | 指定された値を一致する要素を指定された値に置き換え、その結果を出力の範囲へコピーする | C++20
`ranges::replace_copy_if` | 条件を満たす要素を指定された値に置き換え、その結果を出力の範囲へコピーする | C++20
`ranges::fill` | 指定された値で出力の範囲に書き込む | C++20
`ranges::fill_n` | 指定された値で出力の範囲に n 個書き込む | C++20
`ranges::generate` | 出力の範囲へ関数の結果を書き込む | C++20
`ranges::generate_n` | 出力の範囲へ関数の結果を n 個書き込む | C++20
`ranges::remove` | 指定された要素を除ける | C++20
`ranges::remove_if` | 条件を満たす要素を除ける | C++20
`ranges::remove_copy` | 指定された要素を除け、その結果を出力の範囲へコピーする | C++20
`ranges::remove_copy_if` | 条件を満たす要素を除け、その結果を出力の範囲へコピーする | C++20
`ranges::unique` | 重複した要素を除ける | C++20
`ranges::unique_copy` | 重複した要素を除け、その結果を出力の範囲へコピーする | C++20
`ranges::reverse` | 要素の並びを逆にする | C++20
`ranges::reverse_copy` | 要素の並びを逆にし、その結果を出力の範囲へコピーする | C++20
`ranges::rotate` | 要素の並びを回転させる | C++20
`ranges::rotate_copy` | 要素の並びを回転させ、その結果を出力の範囲へコピーする | C++20
`ranges::shift_left` | 要素を左にシフトさせる | C++23
`ranges::shift_right` | 要素を右にシフトさせる | C++23
`ranges::sample` | 範囲から指定された個数の要素をランダムに抽出する | C++20
`ranges::shuffle` | それぞれの要素をランダムな位置に移動させる | C++20
`ranges::is_partitioned` | 与えられた範囲が条件によって区分化されているか判定する | C++20
`ranges::partition` | 与えられた範囲を条件によって区分化する | C++20
`ranges::stable_partition` | 与えられた範囲を相対順序を保ちながら条件によって区分化する | C++20
`ranges::partition_copy` | 与えられた範囲を条件によって 2 つの出力の範囲へ分けてコピーする | C++20
`ranges::partition_point` | 与えられた範囲から条件によって区分化されている位置を得る | C++20

## ソートや、それに関連した操作

ここで挙げる操作には全て２つのバージョンがある。一つは `Compare` 型の関数オブジェクトを取る関数、もう一つは `operator<` を使用する関数である。

`Compare` は関数オブジェクト型である。
`Compare` 型のオブジェクトに適用した関数呼び出しの戻り値は、 `bool` へ文脈依存の変換をされたとき、第一引数が第二引数より小さい場合は `true` を、そうでない場合は `false` を返す。
何らかの順序関係 (ordering relation) を前提とするアルゴリズム全般に対して `Compare` 型の `comp` を使用する。
`comp` は間接参照したイテレータを通して非 `const` な関数を適用しないものとする。

`Compare` を取るアルゴリズムには全て、代わりに `operator<` を使うバージョンもある。
つまり、`comp(*i, *j) != false` はデフォルトで `*i < *j != false` である。
二分探索以外のアルゴリズムでは、`comp` は「狭義の弱順序 (strict weak ordering) 」を示さなければならない。

ここでの用語「狭義 (strict) 」 は非反射関係 (irreflexive relation) (全ての `x` について `!comp(x,x)` である）の要求を示し、用語「弱 (weak) 」は全順序 (total ordering) ほど強くはないが半順序 (partial ordering) よりは強い要求を示す。`!comp(a, b) && !comp(b, a)` として `equiv(a, b)` を定義する場合、用語「弱」の要求は `comp` と `equiv` の両方が以下のように推移的関係 (transitive relations) となることである。

- `comp(a, b) && comp(b, c)` は `comp(a, c)` を意味する
- `equiv(a, b) && equiv(b, c)` は `equiv(a, c)` を意味する

これらの前提のもと、以下を示すことができる。

- `equiv` は同値関係 (equivalence relation) である
- `comp` は `equiv` によって決まる同値類 (equivalence class) の間での明確な関係を示す
- その示される関係は狭義の全順序 (strict total ordering) である

数学用語の日本語訳として "equivalence relation" には「同値関係」 "equivalence class" には「同値類」が定着しており、同じく数学的な文脈では上記 `equiv` を満たす２つの値を「同値」 (equivalent) であると言う。しかし特に数学的でない文脈で「同値」と言った場合は `operator==` による "equal" の関係と誤解される可能性が高いと考えられるため、本サイトでは上記 `equiv` による "equivalent" の関係を「等価」 `operator==` による "equal" の関係を「等値」として区別する。

あるシーケンスを指す任意のイテレータ `i` と、`i + n` がそのシーケンス上の要素を指す有効なイテレータであるような任意の非負整数 `n` について、`comp(*(i + n), *i) == false` であれば、そのシーケンスは比較関数 (comparator) `comp` によってソートされているという。

あるシーケンス `[start,finish)` があり、`0 <= i < (finish - start)` 内の全ての整数 `i` について、`i < n` の時かつその時に限り `f(*(start + i))` が `true` となるような整数 `n` が存在するなら、そのシーケンス `[start,finish)` は式 `f(e)` によって区分化されているという。

- 「区分化されている」と「ソートされている」との関係
  あるシーケンスが比較関数 `comp` でソートされている場合、そのシーケンスは `comp` に任意の検索キー `k` を部分適用した式 `comp(e, k)` や `!comp(k, e)` などにより区分化されているともいえる。
  例えば、ソートされた整数列 `[1, 5, 13, 17, 25]` は「 `10` より小さい」によって区分化されている。さらに、そのほかの任意の数値についても「～より小さい」あるいは「～より小さくない（～以上）」などによって区分化されているといえる。
  C++03 までの二分探索アルゴリズムは比較関数が狭義の弱順序となることおよび対象シーケンスがその比較関数でソートされていることを要求していた。しかしその後、 C++11 で異なる型のキーによる検索を明示的に許すために制限が見直された結果、比較関数そのものに対する要求はなくなり、比較関数に検索キーを部分適用した式による区分化のみに要求が緩められた。（参照: LWG issue 270 "Binary search requirements overly strict" ）
  これにより、例えばソートされていない整数列 `[5, 1, 25, 13, 17]` に対しても `10` をキーとして `lower_bound()` を用いることにより `10` より小さい範囲の境界を取り出すことが可能になっている。しかし `15` をキーとすることは不正である。
  ただ、 C++03 の要件に合わない（特にソートされていない範囲に対する）二分探索を行いたい場合は、同じく C++11 で追加された `partition_point()` の使用も検討したほうがよい。

順序関係を扱う関数の説明において、この節では安定性 (stability) のような考え方を説明するために同値性 (equivalence) の概念を頻繁に使う。 この節で参照する同値性は必ずしも `operator==` ではなく、狭義の弱順序によって示される同値関係である。つまりそれは、２つの要素 `a` と `b` は `!(a < b) && !(b < a)` の時かつその時に限り同値とみなされるということである。

### ソート

名前 | 説明 | 対応バージョン
--- | --- | ---
`sort` | 範囲を並べ替える |
`stable_sort` | 範囲を安定ソートで並べ替える |
`partial_sort` | 範囲を部分的にソートし、先頭N個を並んだ状態にする |
`partial_sort_copy` | 範囲を部分的にソートした結果を他の範囲にコピーする |
`is_sorted` | ソート済みか判定する | C++11
`is_sorted_until` | ソート済みか判定し、ソートされていない位置のイテレータを取得する | C++11
`ranges::sort` | 範囲を並べ替える | C++20
`ranges::stable_sort` | 範囲を安定ソートで並べ替える | C++20
`ranges::partial_sort` | 範囲を部分的にソートし、先頭N個を並んだ状態にする | C++20
`ranges::partial_sort_copy` | 範囲を部分的にソートした結果を他の範囲にコピーする | C++20
`ranges::is_sorted` | ソート済みか判定する | C++20
`ranges::is_sorted_until` | ソート済みか判定し、ソートされていない位置のイテレータを取得する | C++20

### N 番目の要素

名前 | 説明 | 対応バージョン
--- | --- | ---
`nth_element` | 基準となる要素よりも小さい要素が、前に来るよう並べ替える |
`ranges::nth_element` | 基準となる要素よりも小さい要素が、前に来るよう並べ替える | C++20

### 二分探索

これらのアルゴリズムは全て二分探索を行う。これらは探索されるシーケンスが検索キーを比較関数（暗黙の `operator <` 、または明示的に渡された `Compare comp` ）の引数として部分適用することで得られる式によって区分化されていると仮定している。
これらはランダムアクセスイテレータでない場合でも最小の比較回数で動作する。
これらのアルゴリズムに渡されたイテレータがランダムアクセスイテレータである場合、データ構造を渡るときに対数のステップ数で済むため、このイテレータが適している。ランダムアクセスイテレータでない場合は線形のステップ数になる。

名前 | 説明 | 対応バージョン
--- | --- | ---
`lower_bound` | 指定された要素以上の値が現れる最初の位置のイテレータを取得する |
`upper_bound` | 指定された要素より大きい値が現れる最初の位置のイテレータを取得する |
`equal_range` | `lower_bound`と`upper_bound`の結果を組で取得する |
`binary_search` | 二分探索法による検索を行う |
`ranges::lower_bound` | 指定された要素以上の値が現れる最初の位置のイテレータを取得する | C++20
`ranges::upper_bound` | 指定された要素より大きい値が現れる最初の位置のイテレータを取得する | C++20
`ranges::equal_range` | 指定した値と等しい範囲を取得する | C++20
`ranges::binary_search` | 二分探索法による検索を行う | C++20

### マージ

名前 | 説明 | 対応バージョン
--- | --- | ---
`merge` | 2つのソート済み範囲をマージする |
`inplace_merge` | 2つの連続したソート済み範囲をマージする |
`ranges::merge` | 2つのソート済み範囲をマージする | C++20
`ranges::inplace_merge` | 2つの連続したソート済み範囲をマージする | C++20

### ソート済み構造に対する集合演算

このセクションでは基本的なソート済み構造に対する集合演算を定義する。
これらの演算は、等価なキーの要素を複数格納できる `multiset` であっても動作する。集合演算のセマンティクスは、等価なキーの要素が複数あっても、一般化された標準的な方法で演算できるようになっている。
例えば `set_union()` ならそれぞれの要素の最大数を格納する、`set_intersection()` なら最小数を格納するといったようになる。

名前 | 説明 | 対応バージョン
--- | --- | ---
`set_union` | 2つのソート済み範囲の和集合を得る |
`set_intersection` | 2つのソート済み範囲の積集合を得る |
`set_difference` | 2つのソート済み範囲の差集合を得る |
`set_symmetric_difference` | 2つのソート済み範囲の対称差集合を得る |
`includes` | 2つのソート済み範囲において、一方の範囲の要素がもう一方の範囲に全て含まれているかを判定する |
`ranges::set_union` | 2つのソート済み範囲の和集合を得る | C++20
`ranges::set_intersection` | 2つのソート済み範囲の積集合を得る | C++20
`ranges::set_difference` | 2つのソート済み範囲の差集合を得る | C++20
`ranges::set_symmetric_difference` | 2つのソート済み範囲の対称差集合を得る | C++20
`ranges::includes` | 2つのソート済み範囲において、一方の範囲の要素がもう一方の範囲に全て含まれているかを判定する | C++20

### ヒープ

２つのランダムアクセスイテレータ `[a,b)` の範囲を特定の構造で構築したものをヒープ(heap)と呼ぶ。ヒープには２つの特性がある。

- `*a` より大きい要素は無い
- `*a` は、`pop_heap()` で削除したり、`push_heap()` で要素を追加する操作が O(log(N)) でできる

これらの特性はプライオリティキューで有用である。
`make_heap()` は heap の中の範囲を変換し、`sort_heap()` はソート済みシーケンスの中にあるヒープを turn する。

名前 | 説明 | 対応バージョン
--- | --- | ---
`push_heap` | ヒープ化された範囲に要素を追加する |
`pop_heap` | ヒープ化された範囲の先頭と末尾を入れ替え、ヒープ範囲を作り直す |
`make_heap` | 範囲をヒープ化する |
`sort_heap` | ヒープ化された範囲を並べ替える |
`is_heap_until` | 範囲がヒープ化されているか判定し、ヒープ化されていない最初の要素を指すイテレータを取得する | C++11
`is_heap` | 範囲がヒープ化されているか判定する | C++11
`ranges::push_heap` | ヒープ化された範囲に要素を追加する | C++20
`ranges::pop_heap` | ヒープ化された範囲の先頭と末尾を入れ替え、ヒープ範囲を作り直す | C++20
`ranges::make_heap` | 範囲をヒープ化する | C++20
`ranges::sort_heap` | ヒープ化された範囲を並べ替える | C++20
`ranges::is_heap_until` | 範囲がヒープ化されているか判定し、ヒープ化されていない最初の要素を指すイテレータを取得する | C++20
`ranges::is_heap` | 範囲がヒープ化されているか判定する | C++20

### 最小と最大

名前 | 説明 | 対応バージョン
--- | --- | ---
`min` | 最小値を取得する |
`max` | 最大値を取得する |
`minmax` | 最小値と最大値を取得する | C++11
`min_element` | 範囲内の最小要素へのイテレータを取得する |
`max_element` | 範囲内の最大要素へのイテレータを取得する |
`minmax_element` | 範囲内の最小要素と最大要素へのイテレータを取得する | C++11
`clamp` | 値を範囲内に収める | C++17
`ranges::min` | 最小値を取得する | C++20
`ranges::max` | 最大値を取得する | C++20
`ranges::minmax` | 最小値と最大値を取得する | C++20
`ranges::min_element` | 範囲内の最小要素へのイテレータを取得する | C++20
`ranges::max_element` | 範囲内の最大要素へのイテレータを取得する | C++20
`ranges::minmax_element` | 範囲内の最小要素と最大要素へのイテレータを取得する | C++20
`ranges::clamp` | 値を範囲内に収める | C++20

### 辞書式比較

名前 | 説明 | 対応バージョン
--- | --- | ---
`lexicographical_compare` | 2つの範囲を辞書式順序で比較する |
`ranges::lexicographical_compare` | 2つの範囲を辞書式順序で比較する | C++20

### 三方比較アルゴリズム

名前 | 説明 | 対応バージョン
--- | --- | ---
`lexicographical_compare_three_way` | 2つの範囲を辞書式順序で比較する | C++20

### 順列

名前 | 説明 | 対応バージョン
--- | --- | ---
`next_permutation` | 次の順列を生成する |
`prev_permutation` | 前の順列を生成する |
`is_permutation` | 範囲が順列かを判定する | C++11
`ranges::next_permutation` | 次の順列を生成する | C++20
`ranges::prev_permutation` | 前の順列を生成する | C++20
`ranges::is_permutation` | 範囲が順列かを判定する | C++20

## アルゴリズムの戻り値型

これらの型は、複数の値を1つの戻り値として返すために使われる汎用的な型である。構造化束縛で受け取ることが想定されている。

名前 | 説明 | 対応バージョン
--- | --- | ---
`ranges::in_fun_result` | イテレータと関数オブジェクトを格納する型 | C++20
`ranges::in_in_result` | 2つのイテレータを格納する型 | C++20
`ranges::in_out_result` | 2つのイテレータを格納する型 | C++20
`ranges::in_in_out_result` | 3つのイテレータを格納する型 | C++20
`ranges::in_out_out_result` | 3つのイテレータを格納する型 | C++20
`ranges::min_max_result` | 2つの値または参照を格納する型 | C++20
`ranges::in_found_result` | イテレータとbool値を格納する型 | C++20
`ranges::in_value_result` | イテレータと値を格納する型 | C++23
`ranges::out_value_result` | イテレータと値を格納する型 | C++23

## 関連項目

- `<numeric>`
  - 数値計算のアルゴリズム

## 参照

- N2930 Range-Based For Loop Wording (Without Concepts)
- N4821 25 Algorithms library