使用 std::nth_element 时，第 n 个元素的副本是否总是连续的？

Question

vector<int> data = {3, 1, 5, 3, 3, 8, 7, 3, 2}; 
std::nth_element(data.begin(), data.begin() + median, data.end());

这是否总是会导致：

data = {less, less, 3, 3, 3, 3, larger, larger, larger} ?

或者其他可能的结果是：

data = {3, less, less, 3, 3, 3, larger, larger, larger} ?

我已经在我的机器上尝试了多次，结果第 n 个值总是连续的。但这不是证据 ;).

用途：

我想构建一个独特的 Kdtree，但我的向量中有重复项。目前我正在使用 nth_element 来查找中值。问题是 select 一个 unique/reconstructible 中位数，而不必再次遍历向量。如果中值是连续的，我可以选择一个唯一的中值，而无需太多遍历。

Answer 1

我刚刚尝试了几个不太简单的例子，第三个得到了不连续的输出。

计划

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

int main() {
   std::vector<int> a = {1, 3, 3, 2, 1, 3, 5, 5, 5, 5};
   std::nth_element(a.begin(), a.begin() + 5, a.end());
   for(auto v: a) std::cout << v << " ";
   std::cout << std::endl;
}

在 Linux 下使用 gcc 4.8.1，在 std=c++11 下输出

3 1 1 2 3 3 5 5 5 5

而第n个元素是3.

所以不，元素并不总是连续的。

我还认为更简单的方法，没有考虑好的测试用例，只是生成包含许多重复元素的长随机数组并检查它是否成立。我认为它会在第一次或第二次尝试时崩溃。

Answer 2

没有。 documentation does not specify such behavior, and with a few minutes of experimentation, it was pretty easy to find a test case where the dupes weren't contiguous on ideone:

#include <iostream>
#include <algorithm>

int main() {
    int a[] = {2, 1, 2, 3, 4};
    std::nth_element(a, a+2, a+5);
    std::cout << a[1];
    return 0;
}

输出：

如果 dupes 是连续的，则输出将是 2。

使用 std::nth_element 时，第 n 个元素的副本是否总是连续的？

Are duplicates of the nth element always contiguous when using std::nth_element?

c++

sorting

nth-element

contiguous

quickselect