c++如何使用std::sort自定义排序规则_c++ Lambda表达式与cmp函数编写【技巧】

std::sort传lambda时仅当引用外部变量才需捕获，如[threshold]或[&threshold]；cmp函数必须返回严格弱序，即a应排在b前时返回true；vector按长度排序用lambda更安全因其自动推导const引用；std::sort不稳定，需稳定排序应改用std::stable_sort。

std::sort 传 lambda 表达式时必须捕获什么？

直接传 lambda 给 std::sort 通常不需要捕获任何变量，只要排序逻辑只依赖于元素本身。一旦你在 lambda 中用了外部变量（比如按某个阈值过滤、按动态权重排序），就必须显式捕获——否则编译报错 error: variable 'xxx' cannot be implicitly captured in a lambda with no capture clause。

常见做法是值捕获或引用捕获：

• 值捕获：[threshold] —— 安全，但注意大对象拷贝开销
• 引用捕获：[&threshold] —— 高效，但确保 threshold 生命周期长于 std::sort 调用
• 万能捕获：[&] 或 [=] 少用，容易隐含依赖、难以调试

int threshold = 5;
std::vector v = {1, 8, 3, 9, 2};
std::sort(v.begin(), v.end(), [threshold](int a, int b) {
    // 按与 threshold 的距离升序
    return std::abs(a - threshold) < std::abs(b - threshold);
});

写 cmp 函数时 bool 返回值到底要怎么定义？

std::sort 要求比较函数返回 true 当且仅当前者“应排在后者前面”——即严格弱序（strict weak ordering）。这不是“谁大谁小”，而是“是否应该前置”。写反了会导致未定义行为（崩溃、乱序、甚至 infinite loop）。

典型错误包括：

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

• 用 >= 或 —— 违反“严格”要求，a == a 时必须返回 false
• 对浮点数直接用 做比较却不处理 NaN —— 导致排序中断
• 结构体多字段排序时漏掉后续字段的相等情况判断

struct Point { int x, y; };
// ✅ 正确：先比 x，x 相等再比 y
bool cmp(const Point& a, const Point& b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
// ❌ 错误：x 相等时没定义顺序，行为未定义
bool bad_cmp(const Point& a, const Point& b) {
    return a.x < b.x;
}

vector 按长度排序，为什么用 lambda 比写函数更安全？

对 std::vector<:string> 按长度排序，lambda 可直接用 .size()，无需担心参数类型或 const 正确性；而手写 cmp 函数容易忽略 const& 引用，导致临时对象绑定失败或编译不过。

尤其当容器元素是自定义类型且 size() 非 const 成员时，函数声明稍有不慎就报错 passing 'const XXX' as 'this' argument discards qualifiers。

• lambda 自动推导参数类型，且默认以 const& 接收（除非加 mutable）
• 函数需手动写 const std::string& a, const std::string& b，漏一个 const 就可能出问题
• lambda 在调用点内联定义，作用域干净；函数名可能污染命名空间

std::vector words = {"hi", "hello", "a"};
std::sort(words.begin(), words.end(), [](const auto& a, const auto& b) {
    return a.size() < b.size();
});

std::sort 稳定吗？需要稳定排序时该换什么？

std::sort 不保证稳定 —— 相等元素的相对顺序可能改变。如果你依赖原始顺序（比如先按分数排、分数相同再按输入顺序排），不能靠两次 std::sort 实现，必须用 std::stable_sort。

性能差异明显：std::stable_sort 通常多耗约 1.5× 时间和 O(n) 额外内存；std::sort 平均 O(n log n)，原地完成。别为了“看起来稳定”盲目替换。

• 真需要稳定：直接换 std::stable_sort，接口完全一致
• 想模拟稳定效果但坚持用 std::sort：在比较逻辑里加入原始索引字段（如用 std::vector<:pair size_t>>）
• 结构体排序中混用多个条件时，“相等则按原序”逻辑必须显式编码，不能假设编译器会保留

最容易被忽略的是：即使你写的 cmp 逻辑“看起来”能保序，std::sort 内部实现（如 introsort）仍可能打乱相等块 —— 这不是 bug，是标准允许的行为。