是否为包含相同值的范围定义了std :: nth_element？

Question

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

该算法不能使两个数字都middlePosition 小于 2,因为只有一个这样的数字.该算法尽力而为,输出符合要求:

1
2
2
3
2

我可以依靠这样好的行为吗？

我的实现(gcc 4.7)使用introselect算法.不幸的是我无法找到算法输入的要求.introselect是否需要所有值都不同？

Answer 1

我认为,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.

因此,范围中的元素[first,nth)将小于或等于范围中的元素[nth,last).

Answer 2

这是std :: nth_element的更好定义:

重新排列[first,last]范围内的元素,使得第n个位置的元素是在排序序列中处于该位置的元素.

除了nth之前的元素都不大于它之外,其他元素没有任何特定的顺序,并且其后面的元素都不会更少.