比较规则与函数对象

读完能做什么

• 能用一句话说清自己的排序需求：“谁应该排在前面”，并把它写成一个比较规则。
• 能读懂 bool operator()(const Score& a, const Score& b) const { ... } 这种写法的每个部分，知道结构体和 operator() 在这里做什么。
• 能把写好的规则交给 sort 使用，得到唯一的排序结果。
• 能直接使用 less<int>、greater<int> 这类现成的函数对象，并说出它们各自表达了什么规则。

为什么需要它

前面几页排数据用的都是默认规则：sort(v.begin(), v.end()) 从小到大；后面要学的 set 也会给元素一个默认顺序。可是现实中的“顺序”常常更复杂：

• 成绩表要按成绩从高到低排，成绩相同的人按编号从小到大排。
• 待办任务要先做要紧的，优先级相同的任务按编号先做。

这两条需求都能用一句话说清楚：“谁应该排在前面”。默认的 < 只会比大小，没法表达“先看成绩、再看编号”这样的复合要求。我们需要一种办法，把“谁排在前面”这件事写成一个能交给算法调用的规则。

它是什么

一句话：比较规则是一个“接收两个元素、回答一个真假问题”的东西——“第一个元素应该排在第二个元素前面吗？”回答“是”就返回 true，回答“不”就返回 false。

把这条规则写成能交给 sort 调用的形式，最常用的做法是函数对象：重载了 operator() 的结构体，它的对象可以像函数一样被调用。

本页要处理的是一份成绩记录表，每条记录由编号和成绩两部分组成：

规则是：成绩从高到低；成绩相同时，编号小的排在前面。 按这条规则排完之后的顺序是 1 号、3 号、2 号。

下面把这几个新概念就地解释清楚。

结构体。 struct Score { int id; int score; }; 定义了一个新类型 Score，把相关的数据打包在一起——这里是一个编号 id 和一个成绩 score。花括号里的每一项叫成员，用 对象.成员 的形式读写，比如 s1.id、s1.score。Score s1 = {1, 90}; 按成员的声明顺序给出初值，于是 s1.id 是 1，s1.score 是 90。有了它，“一条成绩记录”就是一个可以整体传递、整体比较的东西。

函数对象（仿函数）。 如果结构体里写了名为 operator() 的成员函数，那么这个结构体的对象就可以用 对象(参数) 这种“像函数一样”的形式调用。这样的对象叫函数对象，也叫仿函数。std::less<int>、std::greater<int> 就是标准库已经写好的函数对象。

运算符重载。 operator() 这个名字是在给这个类型定义“小括号运算符”的行为：C++ 允许把 ()、== 这样的运算符定义成成员函数，写法是 operator 紧跟运算符本身。所以写 cmp(a, b) 时，真正执行的是 cmp.operator()(a, b)。这里给结构体定义 ()，就是为了让它能“像函数一样”接收两个元素并回答真假。

const Score& 参数与结尾的 const。 参数写成 const Score& a：& 表示引用，直接用原来的那个对象，不复制一份；前面的 const 表示函数里不会改动它——比较规则只应该读数据，不应该改数据。函数名后面那个 const 表示“这个成员函数不会改动对象自己的数据”。比较规则统一写成这样，才能被 set、map 这类把规则存起来、并以常量方式调用的容器使用。

严格弱序。 比较规则必须满足的一组性质叫严格弱序（strict weak ordering）。入门阶段只要记住其中最关键的一条：同一条规则比较同一个对象时，必须返回假，也就是 cmp(x, x) 为 false。换句话说，规则只负责回答“a 在 b 前面吗”，当 a 和 b 其实是同一个（或按规则等价）时，两个方向都应该回答“不”。这一条正是“必须用 < 而不能用 <=”的原因，后面会具体讲。

适用场景：任何需要“按自己的规则定顺序、定优先级”的地方。本页先和 sort 搭配使用；下一篇 priority_queue 优先队列 会用它决定“谁是排在最上面的那一个”，set 有序集合 也会用它维护元素顺序。排序本身的操作见 sort 排序。

最小可运行示例

先不排序，直接把写好的规则调用起来，看它到底回答了什么问题：

#include <bits/stdc++.h>
using namespace std;

struct Score {
    int id;        // 编号
    int score;     // 成绩
};

struct ByScoreDescIdAsc {
    bool operator()(const Score& a, const Score& b) const {
        if (a.score != b.score) return a.score > b.score;
        return a.id < b.id;
    }
};

int main() {
    Score s1 = {1, 90};
    Score s2 = {2, 80};
    Score s3 = {3, 90};

    ByScoreDescIdAsc cmp;
    cout << boolalpha;
    cout << "cmp(1/90, 2/80) = " << cmp(s1, s2) << '\n';
    cout << "cmp(2/80, 1/90) = " << cmp(s2, s1) << '\n';
    cout << "cmp(1/90, 3/90) = " << cmp(s1, s3) << '\n';
    cout << "cmp(3/90, 1/90) = " << cmp(s3, s1) << '\n';
    cout << "cmp(1/90, 1/90) = " << cmp(s1, s1) << '\n';
    return 0;
}

输出：

cmp(1/90, 2/80) = true
cmp(2/80, 1/90) = false
cmp(1/90, 3/90) = true
cmp(3/90, 1/90) = false
cmp(1/90, 1/90) = false

逐行看：

• struct Score { ... }; 定义记录类型：一条记录有编号和成绩两个成员。注意结尾的分号，结构体定义也是一条语句。
• struct ByScoreDescIdAsc { ... }; 定义规则类型。它的名字就是在念这条规则：按成绩降序（Desc）、同分按编号升序（Asc）。
• ByScoreDescIdAsc cmp; 创建一个规则对象。创建时它什么都不比较，比较发生在调用的时候。
• cmp(s1, s2) 问的是“1 号（90 分）应该排在 2 号（80 分）前面吗？”，规则先看到成绩不同，再判断 90 > 80 成立，返回 true。
• cout << boolalpha; 让 bool 打印成 true / false（默认会打印 1 / 0）。本页要反复看布尔结果，所以统一打开它；如果代码里没有 boolalpha，true 就会显示成 1。
• 最后一行是同一个对象和自己比较，规则返回 false，这正是严格弱序要求的结果。

一步步看变化

把五次调用逐个拆开，看规则内部的判断走到哪个分支：

规则的两个分支正好对应两种情形：成绩不同时由第一条 if 决定；成绩相同时由最后的 return a.id < b.id; 决定。所以可以把 cmp(a, b) 读成两个问题：“a 的成绩比 b 高吗？如果成绩一样，a 的编号比 b 小吗？”

注意第 3 行和第 4 行：同一次比较换成相反的顺序，答案就从 true 变成 false。规则不回答“谁大”，只回答“谁在前面”。

逐项扩展核心操作

把规则交给 sort

sort 的作用是把一个区间里的元素重新排列：前两个参数是要处理的位置区间，第三个参数就是比较规则。不写第三个参数时，它默认按 < 从小到大排。用本页的规则给三条记录排序：

#include <bits/stdc++.h>
using namespace std;

struct Score {
    int id;
    int score;
};

struct ByScoreDescIdAsc {
    bool operator()(const Score& a, const Score& b) const {
        if (a.score != b.score) return a.score > b.score;
        return a.id < b.id;
    }
};

int main() {
    vector<Score> v = {{1, 90}, {2, 80}, {3, 90}};

    sort(v.begin(), v.end(), ByScoreDescIdAsc());

    cout << "排序后的编号：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i].id << ' ';
    cout << '\n';
    cout << "对应的成绩：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i].score << ' ';
    cout << '\n';
    return 0;
}

输出：

排序后的编号：1 3 2 
对应的成绩：90 90 80 

• vector<Score> v = {{1, 90}, {2, 80}, {3, 90}}; 创建三条记录，v[0] 是 1 号 90 分，依此类推。
• sort(v.begin(), v.end(), ByScoreDescIdAsc()); 把整个 vector 按规则重排。第三个参数是“临时创建一个规则对象”：ByScoreDescIdAsc() 后面这对小括号是在构造对象。
• 编号输出是 1 3 2：两个 90 分里编号小的 1 号在前，所以 1 号、3 号排在前面；80 分的 2 号在最后。
• 成绩输出是 90 90 80，和编号一一对应——同分的两条记录由规则的第二个分支决定了先后，所以这个结果不是“碰巧”，而是规则规定的。

现成的函数对象：greater<int> 与 less<int>

标准库在 <functional> 里提供了一组常用的比较规则（#include <bits/stdc++.h> 已经把它们包含进来）：

• less<int>()(a, b) 返回 a < b；
• greater<int>()(a, b) 返回 a > b。

它们本身就是函数对象，所以可以像本页的 cmp 一样直接调用，也可以直接传给 sort：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {3, 1, 4, 2};

    sort(a.begin(), a.end(), greater<int>());
    cout << "greater<int>() 排序：";
    for (int x : a) cout << x << ' ';
    cout << '\n';

    sort(a.begin(), a.end(), less<int>());
    cout << "less<int>() 排序：";
    for (int x : a) cout << x << ' ';
    cout << '\n';

    cout << boolalpha;
    cout << "greater<int>()(1, 2) = " << greater<int>()(1, 2) << '\n';
    cout << "less<int>()(1, 2) = " << less<int>()(1, 2) << '\n';
    return 0;
}

输出：

greater<int>() 排序：4 3 2 1 
less<int>() 排序：1 2 3 4 
greater<int>()(1, 2) = false
less<int>()(1, 2) = true

• greater<int>() 里的 <int> 表示“比较哪种类型”，这里是比较 int。
• 用 greater<int>() 排序得到 4 3 2 1：规则说“a 比 b 大就该排在前面”，所以从大到小。
• 用 less<int>() 排序得到 1 2 3 4：正好是 sort 不写第三个参数时的默认行为，因为 sort 默认用的就是 less<T>。
• 最后两行是直接调用这两个函数对象：greater<int>()(1, 2) 问的是“1 排在 2 前面吗”，因为 1 不比 2 大，返回 false；less<int>()(1, 2) 返回 true。

普通函数也能当规则

规则不一定非得是函数对象，普通函数（传函数名）也可以：

#include <bits/stdc++.h>
using namespace std;

// 普通函数也能当比较规则：返回 true 表示 a 排在 b 前面
bool byAbsDesc(int a, int b) {
    return abs(a) > abs(b);
}

int main() {
    vector<int> a = {1, -3, 2, -4};

    sort(a.begin(), a.end(), byAbsDesc);

    cout << "按绝对值从大到小：";
    for (int x : a) cout << x << ' ';
    cout << '\n';
    return 0;
}

输出：

按绝对值从大到小：-4 -3 2 1 

这里把函数名 byAbsDesc 交给 sort，sort 每需要比较两个元素时就调用它一次。结果按绝对值从大到小排：4、3、2、1，对应的元素是 -4、-3、2、1。

选读：函数对象和普通函数有什么不一样。 从写法上看两者几乎等价，都能表达“谁在前面”。差别在于函数对象是一个类型，编译器能直接看出要调用哪个函数，往往把它内联展开；函数指针则需要多一次间接调用。入门阶段不用为此纠结，写哪种都可以，需要给规则配数据（比如后面按等级排序）时，函数对象更方便。

什么时候选它、哪里容易错

规则说的是“谁排在前面”，不是“谁更大”。 这是最容易搞反的地方。写规则之前先用一句话把它读出来：cmp(a, b) 为 true 表示 a 在前。本页规则读作“成绩高的在前，同分时编号小的在前”；如果读成“谁的分数小谁在前”，写出来的程序正好会反过来。

不能把 < 写成 <=。

// 错误示例：相等时返回 true，破坏了严格弱序
struct BadCmp {
    bool operator()(const Score& a, const Score& b) const {
        return a.score <= b.score;      // 相等时也是 true
    }
};

这段不能这么做：用同一条规则比较同一个对象时，a.score <= a.score 是 true，违反了“cmp(x, x) 必须为假”。把这样的规则交给 sort 属于未定义行为——结果不确定，可能崩溃，也可能排出错误内容，所以本页不给它编造一个运行结果。正确做法是写 a.score < b.score，或者像本页示例那样分成“先比成绩、再比编号”两个分支。

结尾的 const 不要漏。

// 片段：比较规则的两种写法
bool operator()(const Score& a, const Score& b) const { /* ... */ }   // 推荐
bool operator()(const Score& a, const Score& b) { /* 漏了 const */ } // 有的容器不接受

在本机的实现里，漏掉 const 的规则交给 sort 还能编过，但交给 set、map 会直接编译失败：这些容器把比较器存起来，并以常量的方式调用它。为了写出一条到处都能用的规则，统一在 operator() 末尾写 const。

同分记录的顺序要靠规则自己说清楚。 如果规则只写一句 return a.score > b.score;，那么两条 90 分的记录谁在前就没有任何保证（sort 允许任意顺序，见 sort 排序 里的稳定排序）。想要唯一结果，就像本页这样把第二关键字补上。

priority_queue 里同一个规则的含义是反过来的。 在 sort 里 cmp(a, b) == true 表示“a 排在 b 前面”；在优先队列里，规则为 true 表示“a 排在 b 后面”，也就是 b 的优先级更高。这个差别在 priority_queue 优先队列 里用同一条规则在两处对比讲解。

复杂度。 规则本身通常只做几次判断，是 O(1)；sort 会调用它 O(n log n) 次。所以规则写得越简单，排序越快。

接下来读什么。 本页写出的规则是后面两页的前置知识：priority_queue 优先队列 用规则决定“谁留在堆顶”，那里规则的方向是反的；sort 排序 会把第三个参数的用法、同分记录的处理和稳定排序讲全。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main，假设 ByScoreDescIdAsc 就是本页定义的那条规则），请先手推出输出，再运行核对：

ByScoreDescIdAsc cmp;
cout << boolalpha;
cout << cmp(Score{3, 90}, Score{1, 90}) << ' '
     << cmp(Score{2, 80}, Score{2, 80}) << ' '
     << cmp(Score{1, 90}, Score{2, 80}) << '\n';

第 2 题：修改代码

把本页的规则改成：成绩仍然从高到低，但成绩相同时编号大的排在前面。数据还是 (1, 90)、(2, 80)、(3, 90)。

验证条件：先说出排序后的编号顺序，再运行核对。

#include <bits/stdc++.h>
using namespace std;

struct Score {
    int id;
    int score;
};

struct ByScoreDescIdAsc {
    bool operator()(const Score& a, const Score& b) const {
        if (a.score != b.score) return a.score > b.score;
        return a.id < b.id;
    }
};

int main() {
    ByScoreDescIdAsc cmp;
    cout << boolalpha;
    cout << cmp(Score{3, 90}, Score{1, 90}) << ' '
         << cmp(Score{2, 80}, Score{2, 80}) << ' '
         << cmp(Score{1, 90}, Score{2, 80}) << '\n';
    return 0;
}

false false true

struct ByScoreDescIdDesc {
    bool operator()(const Score& a, const Score& b) const {
        if (a.score != b.score) return a.score > b.score;
        return a.id > b.id;                 // 同分时编号大的排在前面
    }
};

#include <bits/stdc++.h>
using namespace std;

struct Score {
    int id;
    int score;
};

struct ByScoreDescIdDesc {
    bool operator()(const Score& a, const Score& b) const {
        if (a.score != b.score) return a.score > b.score;
        return a.id > b.id;                 // 同分时编号大的排在前面
    }
};

int main() {
    vector<Score> v = {{1, 90}, {2, 80}, {3, 90}};

    sort(v.begin(), v.end(), ByScoreDescIdDesc());

    cout << "排序后的编号：";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i].id << ' ';
    cout << '\n';
    return 0;
}

排序后的编号：3 1 2 

立即练习

两道题都只用数组、循环、字符串和本页的比较规则。做完后请说明：你写的规则里，cmp(a, b) 返回 true 时到底表示 a 排在哪里？如果把它交给优先队列，取出的第一个元素会是谁？