C++学习笔记3：sort和priority_queue的比较器重载

1 sort

三种方法

1. 直接重载函数

#include <vector>
#include <memory>
#include <vector>
#include <queue>
#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;
}

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

#include <vector>
#include <memory>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>using namespace std;class Node{
public:int value;Node(){value = 0;};explicit Node(int value){this->value = value;}static bool cmp(const Node& n1, const Node& n2){return n1.value > n2.value;}static void fun(){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 << " ";}
};int main(){Node::fun();return 0;
}

3. 定义一个类，重载（）运算符

#include <vector>
#include <memory>
#include <vector>
#include <queue>
#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;
}

2 priority_queue

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

sort较为常用的参数表是：

first和last是迭代器，而comp是比较器，实现方式有上面的三种。

对于priority_queue，首先需要往确定模板的类型，然后给构造函数传递参数。

上面这段是用实际类型将类模板priority_queue实例化为模板类，还并没有到由模板类构造对象的那一步。此处compare需要传递的是比较器的类型，而不是比较器本身。

我们再看构造函数：

这个地方需要传递的才是比较器。所以当比较器为函数的时候，我们的写法是：

priority_queue<Node, vector<Node>, decltype(&cmp)> pq(cmp);

 前面的decltype(&cmp)是比较器的类型，后面的cmp给构造函数传递比较器。

那么问题来了，cmp的类型为什么不是decltype(cmp)而是decltype(&cmp)呢？

cmp是一个函数指针，代表着函数的首地址，类型是：bool (*)(::Node &,::Node &)，即decltype(&cmp)，而查文档可知，decltype(函数)返回的是这个函数的返回值类型，即decltype(cmp)为bool (::Node &,::Node &)。

接下来是三种写法具体实现

1. 直接用函数

#include <vector>
#include <memory>
#include <vector>
#include <queue>
#include <iostream>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]);cout << pq.top().value << endl;pq.push(a[1]);cout << pq.top().value << endl;pq.push(a[2]);cout << pq.top().value << endl;pq.push(a[3]);cout << pq.top().value << endl;pq.push(a[4]);cout << pq.top().value << endl;return 0;
}

2. 类中函数加static

#include <vector>
#include <memory>
#include <vector>
#include <queue>
#include <iostream>using namespace std;class Node{
public:int value;Node(){value = 0;};explicit Node(int value){this->value = value;}static bool cmp(const Node& n1, const Node& n2){return n1.value > n2.value;}static void fun(){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]);cout << pq.top().value << endl;pq.push(a[1]);cout << pq.top().value << endl;pq.push(a[2]);cout << pq.top().value << endl;pq.push(a[3]);cout << pq.top().value << endl;pq.push(a[4]);cout << pq.top().value << endl;}
};int main(){Node::fun();return 0;
}

3. 比较类，重载（）运算符

#include <vector>
#include <memory>
#include <vector>
#include <queue>
#include <iostream>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]);cout << pq.top().value << endl;pq.push(a[1]);cout << pq.top().value << endl;pq.push(a[2]);cout << pq.top().value << endl;pq.push(a[3]);cout << pq.top().value << endl;pq.push(a[4]);cout << pq.top().value << endl;return 0;
}