c++ - 使用 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，但我的 vector 中有重复项。目前我正在使用 nth_element 来查找中值。问题是选择一个独特的/可重构的中位数，而不必再次遍历 vector 。如果中值是连续的，我可以选择一个唯一的中值，而无需太多遍历。

Answer 1

没有。 documentation没有指定这种行为，经过几分钟的实验，很容易找到一个测试用例，其中受骗者在 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;
}

输出:

1

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