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

从std::nth_element的文件有：std :: nth_element是否为包含相同值的范围定义？

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

部分按升序排序范围[第一，最后），以便在区间[first，第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少不能使既号，因为只有一个这样数。该算法尽力而为，输出如所需：

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

我的实现（gcc 4.7）使用introselect算法。不幸的是我找不到对算法输入的要求。 introselect需要所有的值是不同的？

来源

2013-08-22 Martin Drozdik

我想，cppreference在这里是不正确的。拿战利品的标准（N3337 25.4.2）：

template<class RandomAccessIterator> 
void nth_element 
(
    RandomAccessIterator first, 
    RandomAccessIterator nth, 
    RandomAccessIterator last 
); 
...对于范围[first,nth)任何迭代器i和范围[nth,last)其持有的任何迭代j说：!(*j < *i)或comp(*j, *i) == false。

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

来源

2013-08-22 15:20:49 soon

当然，'！（* i> * j）'意味着'[nth，last]'中的元素不会少于'[first，nnth]中的元素吗？ – Useless

@无用，谢谢，修正。 – soon

感谢您的大胆和编辑cppreference：我对它进行了更多编辑以应用[LWG问题2162]（http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#2163 ） – Cubbi

Here是标准:: nth_element的一个更好的定义：

重新排列在范围[第一元素，最后一个），在这样一种方式，在第n个位置的元素是元素，将在排序序列中位于该位置。

其他元素没有任何特定顺序，除了之前没有第n个元素大于它，并且它后面的元素都不是更少。

来源

2013-08-22 15:24:20 cpp

@NicolBolas，thanx，修正。 – cpp

+1用于查找cplusplus.com比cppreference.com更正确的实例！ – Yakk

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

来源

2015-05-21 08:03:00 aces

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

回答

相关问题