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

Question

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

Will this always result in:

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

Or would a other possible outcome be:

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

I've tried it multiple times on my machine wich resulted in the nth values always being contiguous. But that's not proof ;).

What it's for:

I want to building a unique Kdtree but I have duplicates in my vector. Currently I'm using nth_element to find the median value. The issue is to select a unique/reconstructible median, without having to traverse the vector again. If the median values were contiguous I could choose a unique median, without much traversing.

Answer 1

No. The 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;
}

Output:

1

If the dupes were contiguous, that output would have been 2.