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

该算法不能使两个数字都在middlePosition 小于2 之前，因为只有一个这样的数字。该算法尽力而为，并且输出符合要求：

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 中的元素[first,nth)将小于或等于 range 中的元素[nth,last)。

于 2013-08-22T15:20:49.053 回答
6

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

重新排列范围 [first,last) 中的元素，使得第 n 个位置的元素是排序序列中该位置的元素。

剩下的其他元素没有任何特定的顺序，除了 nth 前面的元素都没有大于它，并且它后面的元素都没有小于它。

于 2013-08-22T15:24:20.910 回答
0

不，它的排序不等于或小于！nth_element 随机选择一个值，该值可能位于已排序数组中的第 n 个位置。因为这将是第 n 个位置，所以没有办法，它可以将所有相等放在左侧，因为那样它就不再是第 n 个元素了。测试它！相等的值出现在第 n 个位置的两侧。

于 2015-05-21T08:03:00.273 回答