C++怎么自定义std::sort的比较函数_C++算法排序与自定义比较函数应用

尼克 2025-11-10 00:00:00 次阅读

std::sort支持自定义比较函数实现排序，需满足严格弱序规则。可通过函数指针、Lambda表达式（推荐）、函数对象或重载operator

在C++中使用std::sort时，如果需要对自定义类型排序或改变默认的排序规则，可以通过自定义比较函数实现。标准库的std::sort支持多种方式传入比较逻辑，包括函数指针、函数对象（仿函数）、Lambda表达式等。

1. 比较函数的基本要求

比较函数必须满足“严格弱序”（Strict Weak Ordering），即：

对于任意元素 a，compare(a, a) 必须为 false（不能小于自己）
如果 compare(a, b) 为 true，则 compare(b, a) 应为 false
若 compare(a, b) 和 compare(b, c) 都为 true，则 compare(a, c) 也应为 true（可传递性）

违反这些规则可能导致程序崩溃或未定义行为。

2. 使用函数指针自定义比较

适用于简单场景，例如按整数降序排列：

bool cmp(int a, int b) {
    return a > b; // 降序
}
std::vector nums = {3, 1, 4, 1, 5};
std::sort(nums.begin(), nums.end(), cmp);

3. 使用Lambda表达式（推荐）

Lambda写法简洁，适合局部逻辑。例如对二维点按横坐标升序、纵坐标降序：

std::vector> points = {{1,2}, {3,4}, {1,5}};
std::sort(points.begin(), points.end(), [](const auto& a, const auto& b) {
    if (a.first != b.first)
        return a.first < b.first;
    return a.second > b.second;
});

4. 自定义结构体的排序

假设有一个学生结构体，按成绩降序、姓名升序排列：

struct Student {
    std::string name;
    int score;
};

std::vector students = {{"Alice", 85}, {"Bob", 90}, {"Charlie", 85}};

std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    if (a.score != b.score)
        return a.score > b.score;     // 成绩高者在前
    return a.name < b.name;           // 成绩相同时按名字字典序
});

5. 重载 operator

如果希望类型有自然顺序，可在类内或类外重载 operator：

bool operator<(const Student& a, const Student& b) {
    return a.score < b.score;
}
// 此时可以直接调用 std::sort(students.begin(), students.end());

6. 使用函数对象（Functor）提高性能

对于复杂逻辑或需捕获状态的情况，定义函数对象更高效（避免Lambda重复生成）：

struct CompareByScore {
    bool operator()(const Student& a, const Student& b) const {
        return a.score < b.score;
    }
};
std::sort(students.begin(), students.end(), CompareByScore{});