14.3 部分ソート

汎用アルゴリズム partial_sort() は、シーケンスの一部だけをソートします。このアルゴリズムの最初のバージョンには、シーケンスの始まり、中間、終わりを定義する 3 つの反復子が使用されています。n が開始と中間点の間の要素数を表す場合、最小 n 要素が順番にこの範囲に移動されます。残りの要素は第 2 の領域に移動されます。この第 2 の領域内の要素の順序は定義されていません。

void partial_sort (RandomAccessIterator first, 
   RandomAccessIterator middle, 
   RandomAccessIterator last [ , Compare ]);

アルゴリズムの第 2 のバージョンは、入力を変更しません。出力領域はランダムアクセス反復子の対によって定義されます。n がこの領域のサイズを表す場合、入力の最小 n 要素が順番に出力領域に移動されます。n が入力より大きい場合、入力全体がソートされ、最初の n 位置が出力領域に出力されます。いずれの場合も、出力シーケンスの終わりが操作の結果として返されます。

RandomAccessIterator partial_sort_copy 
   (InputIterator first, InputIterator last, 
   RandomAccessIterator result_first, 
   RandomAccessIterator result_last [, Compare ] );

このアルゴリズムバージョンへの入力は、入力反復子の対としてのみ指定されるため、partial_sort_copy() アルゴリズムは標準 C++ ライブラリのコンテナにのみ使用することができます。プログラム例では、このバージョンは list に使用されています。

void partial_sort_example () 
      // 部分ソートアルゴリズムの使用方法を説明する
      // 完全なソースコードについては alg7.cpp を参照
{
      // 15 の乱数を含む vector を作成する
   vector<int> aVec(15);
   generate (aVec.begin(), aVec.end(), randomValue);

      // 最初の 7 つの位置を部分ソートする
   partial_sort (aVec.begin(), aVec.begin() + 7, aVec.end());

      // 乱数のリストを作成する
   list<int> aList(15, 0);
   generate (aList.begin(), aList.end(), randomValue);
   
      // 最初の 7 つの要素のみをソートする
   vector<int> start(7);
   partial_sort_copy (aList.begin(), aList.end(),
      start.begin(), start.end(), greater<int>());
}