13

std::nth_elementのドキュメントから、次のものがあります。

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

範囲 [first, last) を部分的に昇順に並べ替え、範囲 [first, nth) 内のすべての要素が範囲 [nth, last) 内の要素より小さくなるようにします。

私を悩ませているのは、言葉が少ないことです。それ以下であるべきではありませんか？たとえば、範囲が次の場合:

#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;
}

このような数は1 つしかないため、アルゴリズムは 2未満の数の前に両方の数を作成することはできません。アルゴリズムは最善を尽くし、出力は希望どおりです。middlePosition 

1
2
2
3
2

このような素敵な振る舞いに頼ることができますか?

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

4

3 に答える 3

14

ここでは cppreference が間違っていると思います。スタンダードで略奪する(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

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

于 2013-08-22T15:20:49.053 に答える
0

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

于 2015-05-21T08:03:00.273 に答える