如何基于std::range在sort和equal_range中处理数组元素序列？

问题分析 #

核心需求是对indexes数组排序时，依据每个索引在values中对应的从该位置到末尾的子序列的字典序；同时希望该逻辑能兼容std::ranges::equal_range，用于搜索匹配的子序列。

原代码的问题在于：

• ChainComparator依赖元素的内存地址反推子序列起始位置，这是未定义行为（UB）——当比较的元素不是values数组的成员时（比如equal_range中的values_to_search），地址计算完全失效。
• 投影函数将索引映射为单个元素，迫使比较器不得不通过地址“绕路”获取子序列，违背了range的抽象设计。

解决方案 #

我们需要让比较逻辑直接基于子序列本身而非元素地址，同时兼容排序和搜索场景。以下提供两种符合std::range规范的实现：

方案1：投影为子视图（更符合range抽象） #

将索引投影为values中对应的子范围（std::ranges::subrange），然后用通用字典序比较器处理任意范围的比较。

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

// 生成投影函数：将索引映射为values中从该索引开始的子视图
auto make_subrange_projection = []<std::ranges::random_access_range R>(R& range) {
    return [&range](std::ranges::range_difference_t<R> i) {
        return std::ranges::subrange(std::ranges::begin(range) + i, std::ranges::end(range));
    };
};

// 通用字典序比较器：支持任意两个输入范围的比较
struct SubrangeLexicographicalLess {
    template<std::ranges::input_range R1, std::ranges::input_range R2>
    bool operator()(const R1& lhs, const R2& rhs) const {
        return std::ranges::lexicographical_compare(lhs, rhs);
    }
};

int main()
{
    std::vector<int> values = { 0,30,20,40,10 };
    std::vector<int> indexes = { 3,4,2,1,0 };

    // 按子序列字典序排序索引
    auto subrange_proj = make_subrange_projection(values);
    std::ranges::sort(indexes, SubrangeLexicographicalLess{}, subrange_proj);

    // 创建索引对应的子视图
    auto indexing_view = indexes | std::views::transform(subrange_proj);

    std::vector<int> values_to_search = { 20, 40 };
    // 搜索匹配的子序列
    auto range_pred_seq = std::ranges::equal_range(indexing_view, values_to_search, SubrangeLexicographicalLess{});
}

方案2：直接基于索引比较（性能更优） #

让比较器持有values的引用，直接接收索引参数进行子序列比较，避免创建子视图对象（开销极小，但逻辑更直接）。

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

// 基于索引的字典序比较器，支持三种比较场景：索引-索引、索引-目标序列、目标序列-索引
struct IndexBasedLexicographicalLess {
    const std::vector<int>& values;
    explicit IndexBasedLexicographicalLess(const std::vector<int>& v) : values(v) {}

    // 排序时：比较两个索引对应的子序列
    bool operator()(int lhs_idx, int rhs_idx) const {
        auto lhs_begin = values.begin() + lhs_idx;
        auto rhs_begin = values.begin() + rhs_idx;
        return std::ranges::lexicographical_compare(lhs_begin, values.end(), rhs_begin, values.end());
    }

    // 搜索时：索引子序列 < 目标序列
    bool operator()(int lhs_idx, const std::vector<int>& target) const {
        auto lhs_begin = values.begin() + lhs_idx;
        return std::ranges::lexicographical_compare(lhs_begin, values.end(), target.begin(), target.end());
    }

    // 搜索时：目标序列 < 索引子序列
    bool operator()(const std::vector<int>& target, int lhs_idx) const {
        auto lhs_begin = values.begin() + lhs_idx;
        return std::ranges::lexicographical_compare(target.begin(), target.end(), lhs_begin, values.end());
    }
};

int main()
{
    std::vector<int> values = { 0,30,20,40,10 };
    std::vector<int> indexes = { 3,4,2,1,0 };

    // 按子序列字典序排序索引
    std::ranges::sort(indexes, IndexBasedLexicographicalLess(values));

    std::vector<int> values_to_search = { 20, 40 };
    // 直接对索引数组搜索匹配的子序列
    auto range_pred_seq = std::ranges::equal_range(indexes, values_to_search, IndexBasedLexicographicalLess(values));
}

原代码的关键问题 #

• 未定义行为：&lhs - std::data(vec)仅当lhs是vec的成员时才合法，equal_range中传入的values_to_search元素不在values数组中，此计算会导致UB。
• 耦合性高：比较器与元素的内存布局强绑定，无法处理外部序列的比较需求。

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