CODEWITHSUNDEEP
c++sortingcontiguousquickselectnth-element
aces
aces

Reputation: 305

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.

Upvotes: 1

Views: 315

Answers (2)

Petr
Petr

Reputation: 9997

I have just tried several not-so-simple examples, and on the third got non-contiguous output.

Program

#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;
}

with gcc 4.8.1 under Linux, with std=c++11, gives me output

3 1 1 2 3 3 5 5 5 5

while the n-th element is 3.

So no, the elements are not always contiguous.

I also think that even a simpler way, with no thinking of a good test case, was just generating long random arrays with many duplicate elements and checking whether it holds. I think it will break on the first or second attempt.

Upvotes: 1

user2357112
user2357112

Reputation: 280301

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.

Upvotes: 1

Related Questions