同じ値を含む範囲に対してstd :: nth_elementが定義されていますか？我々が持っている<a href="http://en.cppreference.com/w/cpp/algorithm/nth_element" rel="noreferrer">std::nth_element</a>のドキュメントから

Question

：昇順で

template< class RandomIt > 
void nth_element(RandomIt first, RandomIt nth, RandomIt last); 

が部分的に最後の、最初の[範囲をソート）の範囲内のすべての の要素となるよう[最初の、n番目のは）それよりも少ないです [n番目、最後の）の範囲です。

私を悩ますものは、より小さく、という単語です。 以下でなければなりません？範囲は、例えば、ある場合のみ：そのような数があるため

#include <algorithm> 
#include <vector> 
#include <iostream> 

int main() 
{ 
    std::vector<int> numbers = {3, 2, 2, 2, 1}; 
    auto middlePosition = numbers.begin() + 2; 
    std::nth_element(numbers.begin(), middlePosition, numbers.end()); 

    for (int x : numbers) 
     std::cout << x << std::endl; 
    return 0; 
} 

アルゴリズムはは、2よりmiddlePosition以下前両方数字を作ることができません。アルゴリズムは最適ですし、出力は必要に応じてあります：

1 
2 
2 
3 
2 

私はこのような素晴らしい動作に頼ることができますか？

私の実装（gcc 4.7）はintroselectアルゴリズムを使用しています。残念ながら、私はアルゴリズムの入力に関する要件を見つけることができませんでした。 introselectはすべての値が異なる必要がありますか？

Answer 1

ここでは、cppの参照が正しくありません。標準（N3337 25.4.2）で戦利品を取る：

template<class RandomAccessIterator> 
void nth_element 
(
    RandomAccessIterator first, 
    RandomAccessIterator nth, 
    RandomAccessIterator last 
); 

---

...任意のイテレータiの場合、範囲[first,nth)し、任意のイテレータjに 範囲[nth,last)を、それが保持していること：!(*j < *i)をまたはcomp(*j, *i) == false。

したがって、範囲[first,nth)の要素は、範囲[nth,last)以下の要素になります。

Answer 2

HereはSTDのより良い定義され:: nth_element：

は、n番目の位置にある要素は、そのなる要素である ように、）最初、最後の範囲内の要素を並べ替え並べ替えられた順序で の位置にあること。

nthに先行する要素はどれもそれより大きく、それに続く要素はそれ以下ではありません。

Answer 3

いいえ、それ以下はソートされません！ nth_elementはソートされた配列のn番目の位置にある値の1つをランダムに選択します。これはn番目の位置であるため、方法はありません。左辺にすべて等しいものを置くことができます。それ以来、それはもうn番目の要素ではありません。試して！等しい値は、n番目の位置の両側に表示されます。