シーケンス 2 5 3 4 7 があり、その中間または中央値要素を検出するとします。関数 nth_element() を使用してこの検出を行うと、その結果は次のようなシーケンスになります。
3 2 | 4 | 7 5
垂直バーは、要求された値の前の要素、要求された値、要求された値の後の要素の 3 つの部分に結果が区切られることを説明するために使用されています。最初と最後のシーケンス内の値は、順序付けられていないことに注意してください。実際は、これらの値は任意の順序で結果に表示することができます。唯一の条件は、最初の部分の値が検索する値よりも大きくなく、第 3 の部分の要素が検索値より小さくないことです。
引数としてアルゴリズム nth_element() に渡される 3 つの反復子は、このように引数シーケンスを 3 つのセクションに分割します。すなわち、中間反復子の前のセクション、中間反復子によって表記される単一値、中間反復子とシーケンスの終わりの間の領域です。
アルゴリズムの引数は、次のように定義されます。
void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last [, Compare ] );
nth_element() を呼び出すと、n 番目に大きな値が中間反復子によって表示される位置にコピーされます。 最初の反復子と中間反復子の間の領域には n 番目の要素より小さい値が表示され、中間反復子とシーケンスの終わりの間の領域には n 番目の要素より大きい値が表示されます。
以下のプログラム例は、乱数 vector 内の 5 番目に大きい値の検索を説明しています。
void nth_element_example () // nth_element アルゴリズムの使用方法を説明する // 完全なソースコードについては alg7.cpp を参照 { // 乱数ベクトルを作成する vector<int> aVec(10); generate (aVec.begin(), aVec.end(), randomValue); // 5 番目に大きい値を検索する vector<int>::iterator nth = aVec.begin() + 4; nth_element (aVec.begin(), nth, aVec.end()); cout << "fifth largest is " << *nth << endl; }