Всегда ли дубликаты 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, чтобы найти среднее значение. Задача состоит в том, чтобы выбрать уникальную / восстанавливаемую медиану без повторного прохождения вектора. Если бы медианные значения были смежными, я мог бы выбрать уникальную медиану без особого обхода.
Решение
№ документация не описывает такое поведение, и после нескольких минут экспериментов было довольно легко найти тестовый пример, в котором обманщики не были смежными 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,
Другие решения
Я только что попробовал несколько не очень простых примеров, и на третьем получил несмежные результаты.
программа
#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.
Так что нет, элементы не всегда смежные.
Я также думаю, что даже более простым способом, не думая о хорошем тестовом примере, было просто генерировать длинные случайные массивы со многими дублирующимися элементами и проверять, сохраняется ли оно. Я думаю, что это сломается с первой или второй попытки.