Являются ли дубликаты n-го элемента всегда смежными при использовании 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()); 

Будет ли это всегда приводит к:

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

Или будет другой возможный результат:

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

Я пробовал несколько раз на моей машине Wich привели к п-го значений всегда будучи смежным. Но это не доказательство;).

Что это за:

Я хочу строить уникальный Kdtree, но у меня есть дубликаты в моем векторе. В настоящее время я использую nth_element, чтобы найти медианное значение. Проблема заключается в том, чтобы выбрать уникальную/восстановимую медианную, без необходимости повторять вектор. Если медианные значения были смежными, я мог бы выбрать уникальную медианную, без особых перемещений.

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 

Если обмануты были смежными, что выход был бы 2.

Answer 2

Я только что попробовал несколько не очень простых примеров, а на третьем получил несмежный вывод.

Программа

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

с GCC 4.8.1 под Linux, с std=c++11, дает мне выход

3 1 1 2 3 3 5 5 5 5 

, а п-й элемент 3.

Так нет, элементы не всегда смежны.

Я также считаю, что даже более простой способ, не думая о хорошем тестовом случае, состоял в том, чтобы генерировать длинные случайные массивы со множеством повторяющихся элементов и проверять, поддерживает ли он. Я думаю, что это сломается на первой или второй попытке.