C++如何使用std::ranges::sort对自定义类/结构体容器进行高性能排序

std::ranges::sort要求自定义类型必须满足std::totally_ordered约束，即必须支持operator<（或通过三路比较operator<=>导出），且该比较需构成严格弱序；它不接受仅定义operator==或operator>的类型，也不允许仅靠函数指针或带捕获lambda绕过此约束。

std::ranges::sort要求自定义类型必须满足什么约束？

它不接受任意可比较类型，而是严格要求类型支持 operator 或提供显式比较器，且该比较必须是 <strong>strict weak ordering</strong>（严格弱序）。常见错误是重载了 <code>operator== 却忘了 operator，或者用 <code>memcmp 或字段直连比较（如 a.x ）导致违反传递性。

例如以下写法会编译失败或行为未定义：

struct Point { int x, y; };
// ❌ 缺少 operator<，std::ranges::sort 无法推导比较逻辑

正确做法是显式定义：

bool operator<(const Point& a, const Point& b) {
    return a.x != b.x ? a.x < b.x : a.y < b.y;
}

• 必须为 const& 参数，避免拷贝开销
• 返回 bool，不能返回 int 或其他类型
• 若用 lambda 作比较器，需确保捕获为空（[ ]），否则无法满足 std::invocable 约束

如何用 lambda 比较器避免污染全局命名空间？

直接在 std::ranges::sort 调用中传 lambda 最安全，尤其当比较逻辑只用一次、或依赖局部变量时。但注意：lambda 类型不可名，不能用于模板参数推导以外的场景；且必须是可复制、无状态的（即不能捕获非 const 变量）。

立即学习“C++免费学习笔记（深入）”；

例如按字符串长度降序排序：

std::vector<std::string> v = {"hello", "hi", "world"};
std::ranges::sort(v, [] (const auto& a, const auto& b) {
    return a.size() > b.size(); // 注意是 >，实现降序
});

• 捕获列表必须为空（[ ]），否则 std::ranges::sort 无法满足 std::indirect_strict_weak_order 概念
• 参数用 const auto& 避免字符串等类型的不必要拷贝
• 不要写成 [&] —— 即使没实际捕获，语法上已违反约束

std::ranges::sort 和 std::sort 在性能上有本质区别吗？

没有。两者底层都调用相同优化过的 introsort（混合堆排/快排/插入排序），时间复杂度都是 O(n log n)，最坏情况 O(n log n)。差异仅在于接口设计：std::ranges::sort 接受范围（range）而非迭代器对，自动推导 begin/end，并支持投影（projection）——这才是真正影响实操效率的关键点。

投影（proj）允许你“提取字段再比较”，避免重复计算或冗余访问。比如按结构体某个成员的绝对值排序：

struct Data { int val; };
std::vector<Data> v = {{-5}, {3}, {-1}};
std::ranges::sort(v, std::less<>{}, &Data::val); // 投影到 .val，再用 std::less 比较
// 等价于：sort by abs(x.val)，但这里需额外包装；更常见的是配合自定义投影
std::ranges::sort(v, {}, [] (const Data& d) { return std::abs(d.val); });

• 第三个参数是投影，类型必须满足 std::regular_invocable<Proj, T>
• 使用投影比在 lambda 中重复取字段（如 a.val < b.val）更清晰，也便于复用
• 对于 std::vector<std::string> 按长度排序，std::ranges::sort(v, {}, &std::string::size) 比 lambda 稍快（省去函数对象构造）

为什么 vector<unique_ptr<T>> 用 std::ranges::sort 会编译失败？

因为 std::unique_ptr 不可复制，而 std::ranges::sort 内部可能需要移动或交换元素——这本身没问题，但如果你的自定义类型重载了 operator< 却用了 const T& 参数但内部尝试解引用空指针，或比较逻辑依赖被移动后的状态，就会出问题。

典型错误写法：

struct Node { std::unique_ptr<int> ptr; };
bool operator<(const Node& a, const Node& b) {
    return *a.ptr < *b.ptr; // ❌ 若 ptr 为空，解引用 UB
}

正确方式是先判空：

bool operator<(const Node& a, const Node& b) {
    if (!a.ptr && !b.ptr) return false;
    if (!a.ptr) return true;
    if (!b.ptr) return false;
    return *a.ptr < *b.ptr;
}

• std::ranges::sort 对 move-only 类型完全友好，前提是比较器和类型自身满足概念约束
• 切忌在比较逻辑里做非常规操作（如 IO、抛异常、修改对象状态）
• 如果比较开销大（如涉及字符串处理），考虑提前缓存键值，再用投影排序

投影不是银弹，但它是 std::ranges::sort 相比老式 std::sort 最实用的差异化能力；用错投影比写错比较器更容易引发静默错误。