c++sortingcontiguousquickselectnth-element

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


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.


Solution

  • 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.