sort（函数模板）和priority_queue（类模板）的比较器重载

一、sort的比较器重载

sort是一个函数模板，定义如下

它的比较器重载的两种方法：

1. 传函数指针

#include <iostream>
#include <algorithm>using namespace std;class Node
{
public:int value;Node() { value = 0; };explicit Node(int value){this->value = value;}
};bool cmp(const Node& n1, const Node& n2)
{return n1.value > n2.value;
}int main()
{Node* a = new Node[5];a[0].value = 2;a[1].value = 5;a[2].value = 2;a[3].value = 9;a[4].value = 0;sort(a, a + 5, cmp);for (int i = 0; i < 5; i++) {cout << a[i].value << " ";}return 0;
}

注意：在类中时，需要注意加上static，因为非静态函数不加static指针的时候，会隐藏地传一个this指针，导致参数表不符

2. 使用仿函数

#include <iostream>
#include <algorithm>using namespace std;class Node
{
public:int value;Node() { value = 0; };explicit Node(int value){this->value = value;}
};class CMP
{
public:bool operator()(const Node& n1, const Node& n2){return n1.value > n2.value;}
};int main()
{Node* a = new Node[5];a[0].value = 2;a[1].value = 5;a[2].value = 2;a[3].value = 9;a[4].value = 0;sort(a, a + 5, CMP());for (int i = 0; i < 5; i++) {cout << a[i].value << " ";}return 0;
}

二、priority_queue的比较器重载

priority_queue是一个类模板，定义如下

它的构造函数如下：

需要注意的是，priority_queue是一个类模板，而sort是一个函数模板，因此在重载的时候有些区别

它的比较器重载的两种方法：

1. 传函数指针

#include <iostream>
#include <queue>using namespace std;class Node
{
public:int value;Node() { value = 0; };explicit Node(int value){this->value = value;}
};bool cmp(const Node& n1, const Node& n2)
{return n1.value > n2.value;
}int main()
{Node* a = new Node[5];a[0].value = 2;a[1].value = 5;a[2].value = 2;a[3].value = 9;a[4].value = 0;priority_queue<Node, vector<Node>, decltype(&cmp)> pq(cmp);pq.push(a[0]);pq.push(a[1]);pq.push(a[2]);pq.push(a[3]);pq.push(a[4]);while (!pq.empty()){cout << pq.top().value << " ";pq.pop();}return 0;
}

注意：在类中时，也需要注意加上static

2. 使用仿函数

#include <iostream>
#include <queue>using namespace std;class Node
{
public:int value;Node() { value = 0; };explicit Node(int value){this->value = value;}
};class CMP
{
public:bool operator()(const Node& n1, const Node& n2){return n1.value > n2.value;}
};int main()
{Node* a = new Node[5];a[0].value = 2;a[1].value = 5;a[2].value = 2;a[3].value = 9;a[4].value = 0;//CMP cmp;//priority_queue<Node, vector<Node>, CMP> pq(cmp); // 也可以传，但完全没必要priority_queue<Node, vector<Node>, CMP> pq;pq.push(a[0]);pq.push(a[1]);pq.push(a[2]);pq.push(a[3]);pq.push(a[4]);while (!pq.empty()){cout << pq.top().value << " ";pq.pop();}return 0;
}

三、常见疑问

priority_queue比较器重载传函数指针时是priority_queue<Node, vector<Node>, decltype(&cmp)> pq(cmp);，那么decltype(&cmp)可不可以换成decltype(cmp)呢？

答：不可以，虽然函数名很多时候和函数名取地址使用起来一样，但这里确实是不一样的，decltype(&cmp)是bool (*)(const Node& n1, const Node& n2)，而decltype(&cmp)却是bool (const Node& n1, const Node& n2)，不仅仅是decltype，当使用typeid查看类型时它们也不一样，它们的typeid如下图所示。可能原因是函数名是表明这种函数类型的类型，只是在大多数场景下我们使用它时它隐式类型转换变成了函数指针。

priority_queue比较器重载使用仿函数时可以不用给构造函数传参，而为什么使用用函数指针时一定要给构造函数传递函数指针呢，它不是也像使用仿函数时一样传递了类型吗？

答：priority_queue的构造函数中对应比较器的参数是const Compare& comp = Compare()，而它有缺省参数，并且是一个匿名对象，其中Compare就是给模板传递的类型，使用仿函数本质是定义了一个类，并使用运算符重载重载了()，当使用仿函数时向模板传递的是一个类类型，而类类型是对应唯一的一个类的，用类类型定义匿名对象可以用来调用该类的函数成员，所以当使用仿函数时构造函数可以直接用缺省参数给比较器初始化，而传递函数指针时给模板传递的是函数指针类型，而函数指针类型的匿名对象跟类的匿名对象完全不一样，一个函数指针类型可以对应无数个拥有相同返回值和相同参数的函数的指针，所以它的匿名对象规定为是0，而值为0的函数指针并不能用来调用函数，所以必须传递需要调用的函数的函数指针。