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

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

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

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

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

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

Для чего это:

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


c++ sorting nth-element contiguous quickselect
person aces    schedule 21.05.2015    source источник
comment
Какая часть документации неясна?   -  person Kerrek SB    schedule 21.05.2015

Ответы (2)


arrow_upward
1
arrow_downward

Нет. В документации такое поведение не указано, и после нескольких минут экспериментов , было довольно легко найти тестовый пример, в котором дубликаты не были смежными на 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.

person user2357112 supports Monica    schedule 21.05.2015

arrow_upward
1
arrow_downward

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

Программа

#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

в то время как n-й элемент равен 3.

Так что нет, элементы не всегда являются смежными.

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

person Petr    schedule 21.05.2015
comment
Благодарность! Мне придется придумать другое решение. - person aces; 22.05.2015