如何通过Views实现基于数据的索引排序？

核心思路 #

利用C++20的std::ranges::sort结合**投影（projection）**特性，直接通过索引映射到对应的值完成排序，完全无需自定义谓词。投影函数会把索引数组中的每个元素（索引值）映射到values向量的对应元素，排序逻辑自动基于映射后的值执行，等价于原IndexedValuesComparator的功能，但代码更简洁安全。

基础实现：对现有索引数组排序 #

假设我们有基础数据结构：

#include <vector>
#include <ranges>
#include <algorithm>

std::vector<int> values = {5, 2, 8, 1, 9};
std::vector<size_t> indexes = {0, 1, 2, 3, 4}; // 初始索引

直接通过投影实现排序：

// 基于values的值对indexes排序，无需自定义谓词
std::ranges::sort(indexes, std::less<>{}, [&values](size_t idx) { return values[idx]; });

第三个参数即为投影逻辑，明确将索引映射为对应值，排序时自动比较这些值。

动态生成排序后的索引 #

如果不需要保留原索引数组，直接生成排序后的索引序列：

// 生成0到values.size()-1的索引并排序
auto sorted_indexes = std::views::iota(0uz, values.size())
                      | std::ranges::to<std::vector<size_t>>();
std::ranges::sort(sorted_indexes, std::less<>{}, [&values](size_t idx) { return values[idx]; });

C++23支持更简洁的链式写法：

auto sorted_indexes = std::views::iota(0uz, values.size())
                      | std::ranges::sort(std::less<>{}, [&values](size_t idx) { return values[idx]; })
                      | std::ranges::to<std::vector<size_t>>();

多数组多索引绑定与多层间接引用 #

1. 多数组绑定排序 #

若需同时基于多个数组的值排序，投影返回包含多值的tuple即可，排序会遵循tuple的默认比较规则（先比较第一个元素，再比较第二个）：

std::vector<int> values1 = {5, 2, 8, 1, 9};
std::vector<std::string> values2 = {"e", "b", "h", "a", "i"};
std::vector<size_t> indexes = {0, 1, 2, 3, 4};

std::ranges::sort(indexes, std::less<>{}, [&](size_t idx) {
    return std::make_tuple(values1[idx], values2[idx]);
});

2. 多层间接引用 #

针对嵌套索引（如索引指向另一索引数组），仅需在投影中完成多层映射：

std::vector<int> values = {5, 2, 8, 1, 9};
std::vector<size_t> secondary_indexes = {3, 1, 0, 4, 2};
std::vector<size_t> indexes = {0, 1, 2, 3, 4};

std::ranges::sort(indexes, std::less<>{}, [&](size_t idx) {
    return values[secondary_indexes[idx]]; // 两层索引映射
});

预留复杂自定义比较逻辑的位置 #

后续若需复杂比较逻辑，直接替换std::less<>为自定义比较函子即可，投影部分保持独立，完全不影响映射逻辑：

// 自定义比较：先按值的绝对值，再按原值
struct CustomComparator {
    bool operator()(int a, int b) const {
        if (std::abs(a) != std::abs(b)) {
            return std::abs(a) < std::abs(b);
        }
        return a < b;
    }
};

std::ranges::sort(indexes, CustomComparator{}, [&values](size_t idx) { return values[idx]; });

这种方式既移除了老式的IndexedValuesComparator谓词，又能灵活扩展比较逻辑，同时清晰表达索引到值的映射关系，避免了谓词中可能出现的错误。

内容的提问来源于stack exchange，提问作者Damir Tenishev