Daily bit(e) C++. std::partial_sort_copy
Добавлено 25 августа 2026 в 22:51
Daily bit(e) C++ 87, алгоритм частичной сортировки, не требующий, чтобы исходный диапазон предоставлял произвольный доступ к элементам: std::partial_sort_copy.
std::partial_sort_copy – необычный алгоритм сортировки. Он не требует произвольного доступа к элементам в исходном диапазоне, обеспечивая при этом сложность выполнения O(n*logk).
Алгоритм «копирует» верхние k элементов в выходной диапазон (который должен быть с произвольным доступом) в отсортированном порядке.
Сортировка нестабильна, т.е. не сохраняет порядок равных элементов.
Доступны как параллельная версия из C++17, так и версия для диапазонов из C++20.
#include <forward_list>
#include <string>
#include <string_view>
#include <vector>
#include <algorithm>
std::forward_list<std::string> names{
"Emma", "Liam", "Zara", "Ethan", "Aria", "Mateo", "Ivy", "Finn",
"Luna", "Kai", "Mila", "Oscar", "Ruby", "Levi", "Nora"};
// Размер выходного диапазона определяет количество
// копируемых/сортируемых элементов
std::vector<std::string> out1(3);
std::partial_sort_copy(
names.begin(), names.end(), // исходный диапазон
out1.begin(), out1.end()); // целевой диапазон
// out1 == {"Aria", "Emma", "Ethan"}
std::vector<std::string> out2(5);
std::partial_sort_copy(
names.begin(), names.end(), // исходный диапазон
out2.begin(), out2.end(), // целевой диапазон
std::greater<>{}); // пользовательский компаратор
// out2 == {"Zara", "Ruby", "Oscar", "Nora", "Mila"}
std::vector<std::string> out3(4);
// версия для диапазонов
auto length = [](const std::string& s) { return s.length(); };
std::ranges::partial_sort_copy(names, out3, // диапазоны
std::greater<>{}, // пользовательский компаратор
length, // проекция для исходного диапазона
length); // проекция для диапазона назначения
// out3 ~= {"Oscar", "Mateo", "Ethan", "Zara"}
// Из-за раздельных проекций в целевом диапазоне могут
// использоваться элементы другого типа.
std::vector<std::string_view> out4(4);
auto view_len = [](const std::string_view& s) { return s.length(); };
std::ranges::partial_sort_copy(names, out4, // диапазоны
std::greater<>{}, // greater поддерживает сравнение std::string/std::string_view
// без преобразований
length, // проекция для std::string
view_len); // проекция для std::string_view
// out4 ~= {"Oscar", "Mateo", "Ethan", "Zara"}