# 自定义比较器
使用自定义比较器来排序。
本文部分参考[usaco.guide](https://usaco.guide/gold/custom-cpp-stl)。以下方法均适用于 `set`、`map`、`priority_queue` 容器，以及对 `vector` 进行 `sort` 排序。
## 方法 1：重载 `<` 运算符（operator overloading）
```cpp
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int a, b, w;
// 第二个 const 意味着你不能在该成员函数内修改类 Edge 的成员变量
bool operator<(const Edge &y) const { return w < y.w; }
};
vector<Edge> edge;
/*
priority_queue<Edge> pq;
set<Edge> s;
map<Edge, int> m;
*/
int main() {
int M = 4;
for (int i = 0; i < M; ++i) {
int a, b, w;
cin >> a >> b >> w;
edge.push_back({a, b, w});
}
sort(edge.begin(), edge.end());
for (Edge e : edge) cout << e.a << " " << e.b << " " << e.w << "\n";
}
```
### 方法 2：函数
直接使用函数定义比较器。
```cpp
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int a, b, w;
};
bool cmp(const Edge &x, const Edge &y) { return x.w < y.w; }
vector<Edge> edge;
/*
priority_queue<Edge, vector<Edge>, decltype(&cmp)> pq(cmp);
set<Edge, bool (*)(const Edge &, const Edge &)> v(cmp);
set<Edge, decltype(&cmp)> s(cmp);
map<Edge, int, decltype(&cmp)> m(cmp);
*/
int main() {
int M = 4;
for (int i = 0; i < M; ++i) {
int a, b, w;
cin >> a >> b >> w;
edge.push_back({a, b, w});
}
sort(edge.begin(), edge.end(), cmp);
for (Edge e : edge) cout << e.a << " " << e.b << " " << e.w << "\n";
}
```
使用 lambda 表达式定义比较器。
```cpp
vector<Edge> edge;
/*
priority_queue<Edge, vector<Edge>, decltype(cmp)> pq(cmp);
set<Edge, bool (*)(const Edge &, const Edge &)> v(cmp);
set<Edge, decltype(cmp)> s(cmp);
map<Edge, int, decltype(cmp)> m(cmp);
*/
auto cmp = [](const Edge &x, const Edge &y) { return x.w < y.w; };
int main() {
int M = 4;
for (int i = 0; i < M; ++i) {
int a, b, w;
cin >> a >> b >> w;
edge.push_back({a, b, w});
}
sort(edge.begin(), edge.end(), cmp);
for (Edge e : edge) cout << e.a << " " << e.b << " " << e.w << "\n";
}
```
## 方法 3：函数对象（functor，function object）
functor 是 C++ 中行为类似函数的对象，它是通过在类或结构体里重载运算符 `()` 来实现的。一个例子如下：
```cpp
// 定义一个简单的 Functor
class Add {
public:
int operator()(int a, int b) const {
return a + b;
}
};
// 使用 Functor
Add add;
int result = add(3, 5); // 调用 operator()，返回 8
```
使用 functor 来进行排序的例子如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int a, b, w;
};
struct cmp {
// 第二个 const 意味着你不能在该成员函数内修改类 cmp 的成员变量
bool operator()(const Edge &x, const Edge &y) const {
return x.w < y.w;
}
};
vector<Edge> edge;
/*
priority_queue<Edge, vector<Edge>, cmp> pq;
set<Edge, cmp> s;
map<Edge, int, cmp> m;
*/
int main() {
int M = 4;
for (int i = 0; i < M; ++i) {
int a, b, w;
cin >> a >> b >> w;
edge.push_back({a, b, w});
}
sort(edge.begin(), edge.end(), cmp());
for (Edge e : edge) cout << e.a << " " << e.b << " " << e.w << "\n";
}
```
当你需要对元素进行多种比较规则的排序时，优先使用该方法而不是重载 `<` 运算符。
一个有趣的用法是，重载 `<` 运算符会自动生成 functor `less<Edge>`，重载 `>` 运算符会自动生成 functor `greater<Edge>`。
```cpp
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int a, b, w;
bool operator>(const Edge &y) const { return w > y.w; }
};
vector<Edge> v;
int main() {
int M = 4;
for (int i = 0; i < M; ++i) {
int a, b, w;
cin >> a >> b >> w;
v.push_back({a, b, w});
}
sort(v.begin(), v.end(), greater<Edge>());
for (Edge e : v) cout << e.a << " " << e.b << " " << e.w << "\n";
}