自定义比较规则
在算法竞赛中，当处理自定义结构体时，必须明确定义数据的比较规则：比如按年龄、成绩、姓名等进行升降序排序。
此时，我们需要自定义比较规则，以便对数据进行排序。
数组排序
如果是简单的对于数组进行排序，可通过传递比较函数实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Point {
int 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;
}
int main(){
Point p[3] = { {1,2}, {3,4}, {5,6} };
sort(p, p + 3, cmp);
// 输出结果将按x升序排列，x相同时按y升序：
for(int i = 0; i < 3; i++){
cout << p[i].x << " " << p[i].y << endl;
}
}
容器排序
与数组排序不同，STL容器需要将比较逻辑编译到类型信息中。因此我们需要通过模板参数指定比较规则。
STL容器通过模板参数静态绑定比较规则，这与sort()函数的动态绑定有本质区别。
需要使用set，map等容器时，需要提供函数对象（Function Object） 作为模板参数。
容器排序实现步骤
-
定义比较器类型
创建包含operator()的结构体/类 -
指定模板参数
在容器声明时传入比较器类型：1
set<Point, PointCmp> s; // PointCmp作为第二个模板参数
完整实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Point{
int x, y;
};
struct PointCmp{ // 自定义比较规则
bool operator()(const Point& a, const Point& b) const{ // 必须声明为const成员函数
if(a.x != b.x){
return a.x < b.x;
}
return a.y < b.y;
}
};
int main(){
set<Point, PointCmp> s = { {1,2}, {3,4}, {5,6} };
// 输出结果将按x升序排列，x相同时按y升序：
for(auto p : s){
cout << p.x << " " << p.y << endl;
}
}
优先队列比较规则
优先队列的堆类型由比较规则决定：
- 当
comp(a, b) == true时，a的优先级 低于 b - 最小堆要求数值小的元素优先级更高，因此当a > b时返回true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct MinHeapCmp{
bool operator()(const int& a, const int& b) const {
return a > b;
}
};
priority_queue<int> maxHeap; // 默认最大堆，无需显式说明
priority_queue<int, vector<int>, MinHeapCmp> minHeap; // 最小堆
priority_queue<int, vector<int>, greater<int>> minHeapStd; // 最小堆，使用标准库中的比较规则
/*
* 模板参数详解：
* 1. int: 元素类型
* 2. vector<int>: 底层容器类型
* 3. MinHeapCmp: 比较器类型
*/
priority_queue<int, vector<int>, MinHeapCmp> minHeap;
总结
自定义比较器
- 核心目的：明确定义元素的排序逻辑
- 应用场景：
- 数组排序 → 使用比较函数
- 容器排序 → 模板参数指定函数对象类型
