运算符重载 排序
在算法中，重载排序是解决问题的常见手段，尤其是需要根据自定义逻辑对数据进行排序时
重载の语法
有时在重载 < 操作符的实现中却使用了 > 排序逻辑，就很懵
所以有必要深入了解一下基本的语法和逻辑
基本语法
在C++中，可以为自定义类型重载运算符，以支持该类型的对象之间进行比较。对于 < 操作符，基本语法如下：
class MyClass {
public:
int key;
// 其他成员和方法...
bool operator<(const MyClass& rhs) const {
// 比较逻辑
}
};
这里，operator< 是一个成员函数，它接受一个类型为 MyClass 的常量引用参数 rhs（表示右手边的对象），并返回一个布尔值。如果当前对象（即左手边的对象，或 *this）应当在 rhs 之前，则返回 true；否则，返回 false。
使用 > 实现逆序排序
假设我们有一个 Product 类，我们想要按照产品价格进行降序排序。一种直观的方式是重载 < 操作符，但在函数体内部使用 > 来比较价格：
class Product {
public:
string name;
double price;
Product(string n, double p) : name(n), price(p) {}
bool operator<(const Product& rhs) const {
return price > rhs.price; // 使用 > 实现降序排序逻辑
}
};
在这个例子中，如果我 们想要 std::sort 默认实现升序排序，但因为我们使用 > 操作符，实际上它执行的是降序排序。这种方法虽然在逻辑上似乎颠倒了，但它允许我们利用C++标准库算法（如 std::sort）的默认行为来达到我们想要的排序效果。
理解背后的逻辑
重载 < 操作符并使用 > 比较逻辑，其核心理念是定义对象间的“小于”关系，以支持排序算法。当你希望以非升序（如降序）排序时，可以通过这种
seemingly contradictory 实现来达成目的。实质上，你告诉排序算法，一个对象“小于”另一个对象意味着它实际上在排序中应该排在后面。
为什么不能写成bool operator>(const Product& rhs) const呢
原因在于 std::sort 和大多数标准库容器的默认比较机制使用的是 operator<。这意味着，如果你只重载 operator> 而不重载 operator<，当你尝试使用 std::sort（不带自定义比较函数）对 Product 对象进行排序时，编译器会报错，因为它找不到用于比较两个 Product 对象的 < 操作符。
std::sort 的默认行为是基于元素之间的“小于”关系进行排序，即它期望存在一个能够判断一个元素是否“小于”另一个元素的比较函数。这就是为什么通常会重载 operator< 而不是 operator>。
如果想要通过重载 operator> 来实现降序排序，可以这样做，但需要明确地告诉 std::sort 使用这个操作符进行比较。这通常通过传递一个自定义比较函数或使用 std::greater<> 完成，如下所示：
class Product {
public:
string name;
double price;
Product(string n, double p) : name(n), price(p) {}
// 使用 > 操作符实现降序排序逻辑
bool operator>(const Product& rhs) const {
return price > rhs.price;
}
};
int main() {
vector<Product> products = {
Product("Laptop", 1200.99),
Product("Smartphone", 699.99),
Product("Tablet", 499.99)
};
// 使用 greater<> 明确指定使用 operator> 进行排序
sort(products.begin(), products.end(), greater<Product>());
结论
说人话就是sort默认使用<排序 所以改一下<的排序规则即可 用法就是那样 先重载bool operator<(const myclass &rhs)const运算符
再在里面写真正的排序逻辑 如果非要写>的话 就要让sort不默认用<排序 而是用我们新写的排序规则进行排序 用法：sort(products.begin(), products.end(), greater<Product>());
使用 > 在 < 操作符重载实现中来达到降序排序的效果是一种有效的技巧。它允许开发者利用标准库算法的默认行为来实现自定义的排序需求。理解这一点，可以帮助开发者更灵活地控制数据结构中元素的排序逻辑。
单关键字排序
1. 贪心算法
场景描述：在进行区间覆盖、会议室预定、或是工作调度问题中，经常需要根据结束时间或开始时间对区间进行排序。通过排序，贪心选择策略（如选择最早结束的任务）可以更容易地应用。
排序需求：重载 < 操作符以按结束时间（或开始时间）升序排序。
struct Interval {
int start, end;
// 重载 < 操作符以按结束时间升序排序
bool operator<(const Interval& rhs) const {
return end < rhs.end;
}
};
vector<Interval> intervals = {{1, 3}, {2, 4}, {5, 7}};
sort(intervals.begin(), intervals.end());
2. 合并区间
场景描述：给定多个区间，合并所有重叠的区间。首先需要按照区间的开始时间对所有区间进行排序，然后遍历排序后的区间列表以合并重叠部分。
排序需求：重载 < 操作符以按开始时间升序排序。
struct Interval {
int start, end;
// 重载 < 操作符以按开始时间升序排序
bool operator<(const Interval& rhs) const {
return start < rhs.start;
}
};
vector<Interval> intervals = {{1, 4}, {2, 3}, {8, 10}};
sort(intervals.begin(), intervals.end());
3. 最近点对问题
场景描述：给定平面上的点集，找出距离最近的一对点。解决此问题的一种方法是分而治之，其中一个步骤涉及将点按照X轴（或Y轴）坐标排序。
排序需求：重载 < 操作符以按X轴（或Y轴）坐标升序排序。
struct Point {
int x, y;
// 重载 < 操作符以按X轴坐标升序排序
bool operator<(const Point& rhs) const {
return x < rhs.x;
}
};
vector<Point> points = {{1, 2}, {3, 4}, {5, 1}};
sort(points.begin(), points.end());
4. Dijkstra算法 优先队列
场景描述：在实现Dijkstra算法寻找最短路径时，通常使用优先队列（最小堆）来存储并快速检索当前节点到源点的最短距离。
排序需求：重载 < 操作符以按照从源点到当前节点的距离进行排序，确保优先队列能够根据最短距离提取节点。
struct Node {
int id;
int distance;
bool operator>(const Node& rhs) const {
return distance > rhs.distance;
}
};
priority_queue<Node, vector<Node>, greater<Node>> pq;
struct Node {
int id;
int distance;
bool operator<(const Node& rhs) const {
return distance > rhs.distance;
}
};
priority_queue<Node> pq;
拓展一下 优先队列priority_queue<Type, Container, Functional>
大根堆：priority_queue<int> maxHeap
小根堆：priority_queue<int, vector<int>, greater<int>> minHeap;
它也是默认用 operator< 表示大根堆的 要改成小根堆也是一样的原理 要么把<重载成> 要么就直接重写一个比较规则
传入参数里告诉它让它使用
int类型的话 可以不需要进行重载 直接传入vetcor,greater即可 可能是它已经写好的默认构造参数
但是复合类型就得像前面所说一样了
struct Person {
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
//基于年龄构建最小堆
bool operator<(const Person& rhs) const {
return age > rhs.age;
}
};
priority_queue<Person> people;
struct Person {
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
};
//基于年龄构建最大堆
struct CompareAge {
bool operator()(const Person& a, const Person& b) {
return a.age < b.age; // 较大的年龄优先
}
};
priority_queue<Person, vector<Person>, CompareAge> people;
大根堆用<，小根堆用> 怎么理解
感觉抽象成堆顶在线性的右边就好了 要深入理解更绕
理解优先队列（priority_queue）中大根堆和小根堆的比较函数的关键在于弄清楚优先队列的底层是如何工作的，以及这些比较函数是如何决定元素排列顺序的。
优先队列的底层工作原理
std::priority_queue 在 C++ 中默认是使用一个最大堆（大根堆）实现的，这意味着堆顶（即优先队列的 top() 方法返回的元素）是所有元素中最大的。在最大堆中，父节点的值总是大于或等于其子节点的值。因此，当你想要实现一个最大堆并且使用默认的比较方法时（即不提供自定义比较函数），你实际上是在使用 operator< 来确保堆顶元素是最大的。
自定义比较函数的逻辑
- 大根堆（最大堆）：在自定义比较函数中使用
<操作符意味着“如果a < b返回true，则a应该在b之后”。这样的逻辑实际上是在构建一个最大堆，因为这确保了较大的元素（即b）会被放置在较高的位置（接近堆顶），从而a（较小的元素）被视为优先级较低。 - 小根堆（最小堆）：相反地，如果你想要构建一个小根堆（最小堆），你会希望最小的元素位于堆顶。为了实现这一点，你需要让比较函数在“较小的元素优先”的逻辑下返回
true。因此，你会使用>操作符——“如果a > b返回true，则a应该在b之后”。这表示a（较大的元素）优先级较低，从而确保了较小的元素（即b）会被放在更高的位置。
堆顶的位置
在 std::priority_queue 中，无论是大根堆还是小根堆，堆顶始终是“优先级最高”的元素，而不是物理上的“末尾”。在最大堆中，优先级最高意味着数值最大的元素，而在最小堆中，则意味着数值最小的元素。priority_queue 抽象了底层的数据结构细节，所以你不需要担心元素是如何物理存储的，只需要知道通过 top() 方法可以获取到优先级最高的元素。
5. 排序字符串或元组
场景描述：在处理字符串数组或元组数组时，可能需要根据字符串长度或元组中的某个特定元素进行排序。
排序需求：重载 < 操作符或提供自定义比较函数，以根据字符串长度或元组中的特定元素排序。
struct StringByLength {
string str;
// 重载 < 操作符以按字符串长度升序排序
bool operator<(const StringByLength& rhs) const {
return str.length() < rhs.str.length();
}
};
vector<StringByLength> strings = {{"apple"}, {"banana"}, {"pear"}};
sort(strings.begin(), strings.end());
6. 统计和排名
场景描述：在竞赛编程或数据分析中，经常需要根据成绩、分数或其他指标对参赛者或数据点进行排序以确定排名。
排序需求：重载 < 操作符以按成绩或分数等指标降序或升序排序。
struct Participant {
string name;
int score;
// 重载 < 操作符以按成绩降序排序
bool operator<(const Participant& rhs) const {
return score > rhs.score; // 注意：为了降序，这里使用 >
}
};
vector<Participant> participants = {{"Alice", 90}, {"Bob", 95}, {"Charlie", 85}};
sort(participants.begin(), participants.end());
多关键字排序
对于更复杂的排序需求，比如需要先根据一个关键字进行排序，然后在此基础上根据第二个关键字排序，这种需求在处理多维数据或者需要多级排序的场景中非常常见。
1. 人员信息排序
场景描述：假设你有一个人员信息列表，需要先按年龄排序，然后在年龄相同的情况下按姓名字典序排序。
struct Person {
string name;
int age;
// 重载 < 操作符以先按年龄升序排序，再按姓名字典序排序
bool operator<(const Person& rhs) const {
if (age != rhs.age)
return age < rhs.age;
return name < rhs.name;
}
};
vector<Person> people = {{"John", 30}, {"Jane", 25}, {"John", 25}};
sort(people.begin(), people.end());
2. 多条件学生成绩排序
场景描述：在学生成绩管理系统中，需要先根据数学成绩进行降序排序，若数学成绩相同，则根据英语成绩升序排序。
struct Student {
string name;
int mathScore, englishScore;
// 重载 < 操作符以先按数学成绩降序，再按英语成绩升序排序
bool operator<(const Student& rhs) const {
if (mathScore != rhs.mathScore) return mathScore > rhs.mathScore;
return englishScore < rhs.englishScore;
}
};
vector<Student> students = {{"Alice", 90, 80}, {"Bob", 90, 85}, {"Charlie", 85, 90}};
sort(students.begin(), students.end());
3. 商品排序
场景描述：电商平台上的商品需要根据销量进行降序排序，销量相同的商品按照评分进行降序排序。
struct Product {
string name;
int sales; // 销量
double rating; // 评分
// 重载 < 操作符以先按销量降序，再按评分降序排序
bool operator<(const Product& rhs) const {
if (sales != rhs.sales)
return sales > rhs.sales;
return rating > rhs.rating;
}
};
vector<Product> products = {{"ProductA", 100, 4.5}, {"ProductB", 100, 4.7}, {"ProductC", 90, 4.8}};
sort(products.begin(), products.end());
多关键字排序的一般方法
在C++中，除了通过重载 < 运算符以实现复杂的排序逻辑，std::sort 函数还可以接受第三个参数——一个比较函数或者函数对象，这在处理多关键字排序时尤其有用。
例如，对于上面的商品排序问题，我们也可以使用自定义比较函数来完成：
bool compareProduct(const Product& a, const Product& b) {
if (a.sales != b.sales)
return a.sales > b.sales;
return a.rating > b.rating;
}
sort(products.begin(), products.end(), compareProduct);
⬅️ 贪心相关模型 🏠 00-刷题理模型 ➡️ priority_queue
💬 评论