Выбор элемента по порядку
Если нужен один элемент на позиции k в отсортированной последовательности, полная сортировка делает лишнюю работу. std::nth_element переставляет диапазон так, чтобы элемент на позиции nth оказался там же, где при полной сортировке; элементы слева не больше него, а справа не меньше.
#include <algorithm>
#include <vector>
std::vector<int> values{8, 1, 5, 2, 9, 3};
const auto middle = values.begin() + values.size() / 2;
std::nth_element(values.begin(), middle, values.end());
const int medianCandidate = *middle;После вызова диапазоны слева и справа не отсортированы. Если нужны первые N элементов в отсортированном порядке, примените std::sort к левой части после выбора.
Компаратор и крайние случаи
Пользовательский компаратор должен задавать строгий слабый порядок, как и для сортировки. Проверьте, что рассчитанный итератор nth лежит внутри диапазона, прежде чем разыменовывать его; пустой вектор не имеет медианного элемента. Алгоритм обычно полезен для медианы, процентиля и выбора top-N по ключу, но не заменяет полную сортировку, когда нужен упорядоченный вывод.