C++ 自定义排序与优先队列运算符重载
一、优先队列的底层逻辑 (Worldview)
1. 核心矛盾:为什么用 < 却是'大根堆'?
std::priority_queue 的行为逻辑与其命名看似矛盾,实则遵循了 STL 的一致性设计。
- 默认属性:
priority_queue= Max Heap (大根堆)。 - 默认判据: (即调用 )。
C++ 优先队列底层逻辑与自定义排序实现。重点解析默认大根堆机制下 operator< 的重载规则,对比友元函数写法与 std::greater 配合的优劣。涵盖单关键字与小根堆实现技巧,以及多条件排序(如分数优先、ID 兜底)的结构体重载与外部仿函数方案。提供避坑指南,包括模板类型与对象实例的区别、const 引用规范及常见编译错误排查。
< 却是'大根堆'?std::priority_queue 的行为逻辑与其命名看似矛盾,实则遵循了 STL 的一致性设计。
priority_queue = Max Heap (大根堆)。std::lessoperator<a 和 b。a < b。b 比 a 强 (在默认的大根堆语境下,数值大的被视为'强')。b) 上浮至堆顶。// 代码逻辑 friend bool operator<(node a,node b){ return a.z<b.z; }
解析:遵循默认逻辑。z 越大,< 比较时在右侧越显'强',因此 z 最大的在堆顶。
统一使用 Friend (友元) 写法,该写法无 this 指针干扰,逻辑对称,不易出错。
struct node{
int z;
// 逻辑:a.z < b.z 为真 -> b 强 -> b 在顶
friend bool operator<(node a,node b){ return a.z<b.z; }
};
// 声明:使用默认的大根堆机制
priority_queue<node> q;
struct node{
int z;
// 逻辑反转:若 a.z > b.z,返回 true (告诉队列 b 比 a "强")
// 结果:z 值小的会被判定为"强",放在堆顶
friend bool operator<(node a,node b){ return a.z>b.z; // <--- 重点:小于号里写大于逻辑 }
};
// 声明:无需修改队列定义,直接用
priority_queue<node> q;
greater)less 替换为 greater。operator>。struct node{
int z;
// 逻辑:诚实重载大于号,不欺骗
friend bool operator>(node a,node b){ return a.z>b.z; }
};
// 声明:显式指定 greater,并填补 vector 占位符
priority_queue<node,vector<node>,greater<node>> q;
在重载 friend bool operator<(Type a, Type b) 时,你给参数起名 x 还是 y 无所谓,但参数的位置决定了谁是比较符号 < 左边的数,谁是右边的数。这是一个极易混淆的基础概念。
当你写 friend bool operator < (Node a, Node b) 时,C++ 编译器遵循以下铁律:
a):代表 小于号左边 的那个对象 (LHS, Left Hand Side)。b):代表 小于号右边 的那个对象 (RHS, Right Hand Side)。当我们执行逻辑 x < y 时,编译器实际调用的是 operator<(x, y)。
假设我们有两个病人,按等级 (level) 排序:
level = 10level = 20张三 < 李四friend bool operator < (people a, people b){ // a 是张三 (10),b 是李四 (20)
return a.level < b.level; // 逻辑:10 < 20 -> 返回 true
}
true (张三比李四'小')。priority_queue 判定 B (李四) 比 A (张三) 强。如果你搞混了顺序,或者故意写反:
friend bool operator < (people a, people b){ // a 依然是张三 (10),b 依然是李四 (20)
return a.level > b.level; // <--- 逻辑反转!
// 逻辑:10 > 20 -> 返回 false
}
false (张三不比李四'小',在队列眼里张三比李四'强')。std::priority_queue 的底层逻辑非常简单粗暴:
operator<(A, B)。true:它认为 B 的优先级比 A 高 (B is strict weak ordering greater than A)。结论推导:
return a.val < b.val; -> 数值大的优先级高 -> 大数在顶。return a.val > b.val; -> 数值小的优先级高 -> 小数在顶。为了符合直觉,永远建议按标准写法来,需要小根堆时再去配合 greater 或修改逻辑,不要乱换参数位置:
// 标准模版
friend bool operator < (const Node& a, const Node& b) {
return a.属性 < b.属性; // 正常的升序逻辑 -> 对应大根堆
}
greater 与 std::sort 的深度用法std::greater 是一个模板结构体(仿函数),其本质是调用类型的 operator>。
std::sort 的默认行为默认使用 <,执行升序排列。
vector<int> v={1,5,3};
sort(v.begin(),v.end()); // 结果:1, 3, 5
greater 改为降序传入 greater 实例,执行降序排列。
// 语法:greater<int>() 是构造一个临时对象
sort(v.begin(),v.end(),greater<int>()); // 结果:5, 3, 1
>)若对自定义结构体使用 greater 排序,结构体内部必须重载 >。
struct node{
int z;
// sort 降序需要 > 运算符支持
friend bool operator>(node a,node b){ return a.z>b.z; }
};
vector<node> arr={{1},{5},{3}};
// 自动调用 operator>,实现 z 从大到小
sort(arr.begin(),arr.end(),greater<node>()); // 结果:5, 3, 1
对比记忆表:
| 容器/算法 | 使用 greater 的效果 | 记忆口诀 |
|---|---|---|
std::sort | 降序 (Desc) | 大的排前面 |
std::priority_queue | 小根堆 (Min Heap) | 小的(被视为强)在堆顶 |
处理复杂逻辑(如:分数优先,ID 兜底)的两种核心范式。
struct Student{
int score,id;
};
目标:分数 (score) 高的优先;分数相同,学号 (id) 小的优先。
在一个 operator< 中处理所有层级逻辑。
struct Student{
int score,id;
friend bool operator<(Student a,Student b){
// 第一关键字:分数。分数高的在顶 (大根堆逻辑)
// 若分数不相等,直接按分数定胜负
if(a.score!=b.score) return a.score<b.score;
// 第二关键字:学号 (仅当分数相等时执行)
// 想要 id 小的在顶,需反转逻辑 (小根堆逻辑)
return a.id>b.id;
}
};
priority_queue<Student> q;
不修改结构体源码,通过定义外部'裁判类'控制排序。此方法可实现一套数据结构多种排序方式。
// 纯净数据结构
struct Student{
int score,id;
};
// 裁判 A:按分数优先
struct CmpScore{
bool operator()(Student a,Student b){
if(a.score!=b.score) return a.score<b.score;
return a.id>b.id;
}
};
// 裁判 B:纯按 ID 小的优先
struct CmpID{
bool operator()(Student a,Student b){
return a.id>b.id; // 小根堆逻辑
}
};
// 声明时传入具体裁判类型
priority_queue<Student,vector<Student>,CmpScore> q1;
priority_queue<Student,vector<Student>,CmpID> q2;
假设 Key1 为主键,Key2 为次键。基于默认 priority_queue (大根堆)。
| 需求模式 | 逻辑方向 | 代码写法 (friend operator <) |
|---|---|---|
| 全大优先 | 大顶 + 大顶 | if(a.k1!=b.k1)return a.k1<b.k1; return a.k2<b.k2; |
| 全小优先 | 小顶 + 小顶 | if(a.k1!=b.k1)return a.k1>b.k1; return a.k2>b.k2; |
| 混合模式 | 大顶 + 小顶 | if(a.k1!=b.k1)return a.k1<b.k1; return a.k2>b.k2; |
心法:
< (顺应默认)。> (逻辑反转)。priority_queue 需要的是类型 (Type):priority_queue<..., Cmp> (无括号)。sort 需要的是对象实例 (Instance):sort(..., Cmp()) (有括号)。greater 的依赖性
greater<T> 时,T 必须重载 operator>。no match for operator> 通常是因为只写了 < 却用了 greater。friend bool operator<(node a,node b) (值传递,简单)。bool operator<(const node& a) const (必须加 const,否则 STL 报错)。
微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online