14.1 概要

この節では、順序付きコレクションに特有の、標準 C++ ライブラリにある汎用アルゴリズムについて説明します。これらのアルゴリズムを表 19 に示します。

表 19 -- 順序付きコレクションに特有の汎用アルゴリズム

アルゴリズム	目的
*ソートアルゴリズム*
`sort`	シーケンスを再配列して順次並べる
`stable_sort`	等価要素の元の順序を保持したままソートする
`partial_sort`	シーケンスの一部だけをソートする
`partial_sort_copy`	一部をソートしてコピーする
*N 番目に大きな要素を検索するアルゴリズム*
`nth_element`	n 番目に大きな要素を検索する
*2 等分探索アルゴリズム*
`binary_search`	検索してブール型を返す
`lower_bound`	検索して最初の位置を返す
`upper_bound`	検索して最後の位置を返す
`equal_range`	検索して最初と最後の位置を返す
*順序付きシーケンスマージアルゴリズム*
`merge`	2 つの順序付きシーケンスを組み合わせる
*集合演算アルゴリズム*
`set_union`	2 つの集合の和集合を生成する
`set_intersection`	2 つの集合の積集合を生成する。
`set_difference`	2 つの集合の差を生成する
`set_symmetric_difference`	2 つの集合の対称差を生成する
`includes`	ある集合が別の集合の部分集合かどうかを調べる
*ヒープ操作アルゴリズム*
`make_heap`	シーケンスをヒープに変換する
`push_heap`	新しい値をヒープに追加する
`pop_heap`	ヒープから最大値を削除する
`sort_heap`	ヒープをソートされた集合に変換する

順序付きコレクションは、標準 C++ ライブラリを使用してさまざまな方法で作成することができます。以下はその例です。

コンテナ set、multiset、map、multimap は、定義による順序付きコレクションです。
list は、sort() メンバー関数を呼び出して順序付けることができます。
vector、deque、または通常の C++ 配列は、14.2 節で説明するソートアルゴリズムのいずれかを使用して順序付けることができます。

13 章で説明した汎用アルゴリズムと同様に、ここで説明するアルゴリズムは特定のコンテナクラスに特有のアルゴリズムではありません。つまり、これらのアルゴリズムはさまざまな型に使用することができます。ただし、その多くはランダムアクセス反復子の使用を必要とします。このため、vector、deque、または通常の配列で最も容易に使用することができます。

この節で説明するアルゴリズムのほとんどが、2 つのバージョンを持ちます。最初のバージョンは、コンテナ要素型特有の比較に小なり演算子 < を使用します。第 2 バージョンはより一般的で、明示的な比較関数オブジェクトを使用します。ここではそれを Compare と記述します。この関数オブジェクトは、2 項述語 (3.2 節を参照) である必要があります。この引数は省略可能なので、引数型の説明ではこれを角括弧で囲んでいます。

すべての有効または表示可能な反復子 i と表示可能な後続の反復子 j について、比較 Compare(*j, *i) が false の場合、シーケンスは順序付きとみなされます。これは必ずしも Compare(*i, *j) が true であることを意味しないので注意してください。Compare によって発生する関係は推移的であり、値の全体の順序を誘導するものと想定されています。

以降の説明では、2 つの値 x と y は、Compare(x, y) と Compare(y, x) がいずれも false である場合は等価とされます。これは必ずしも x == y であることを意味しませんので注意してください。

14.1.1 インクルードファイル

第 13 章で説明したアルゴリズムと同様に、これらのアルゴリズムをプログラムに使用する前に、algorithm ヘッダーファイルをインクルードする必要があります。

# include <algorithm>