Daily bit(e) C++. std::nth_element
Daily bit(e) C++ 40: алгоритм с линейной сложностью, который разбивает диапазон вокруг опорной позиции, содержащей элемент, «как если бы он был отсортирован»: std::nth_element.
std::nth_element – это алгоритм разбиения с линейной сложностью, который переупорядочивает элементы заданного диапазона таким образом, чтобы элемент под опорным итератором был тем элементом, который был бы там, если бы диапазон был отсортирован.
Это может быть полезно для выбора различных процентилей вне диапазона (например, медианы) без явной сортировки (которая была бы операцией O(n*logn)).
Линейная сложность алгоритма сопровождается нетривиальной постоянной стоимостью, что означает, что если вы ищете крайний процентиль, алгоритм std::partial_sort может быть быстрее.
Алгоритм предоставляет как параллельную версию в C++17, так и версию для диапазонов в C++20.
#include <algorithm>
#include <vector>
#include <string>
std::vector<int> data{8, 6, 2, 4, 3, 5, 9, 1};
std::nth_element(data.begin(), data.begin()+3, data.end());
// *(data.begin()+3) == 4
// потому что отсортированный диапазон будет {1, 2, 3, 4...}
// В версии для диапазонов опорный элемент указывается во втором аргументе
std::ranges::nth_element(data, data.begin()+3); // то же, что и выше
// Потому что алгоритм также разделяет диапазон на части.
// - 1,2,3 гарантировано будут упорядочены перед 4
// - 5,6,8,9 гарантировано будут упорядочены после 4
std::vector<std::string> labels{"dd", "bbbb", "aaaaa", "e", "xxx"};
// Обе версии поддерживают пользовательский компаратор,
// а версия для диапазонов поддерживает проекцию
std::ranges::nth_element(labels, // входной диапазон
labels.begin()+2, // опорный элемент
std::less<>{}, // компаратор
[](const std::string& s) { // проекция
return s.length();
});
// *(labels.begin()+2) == "xxx" (строка с медианной длиной)