1. priority_queue（优先级队列）基本情况：priority_queue是一种容器适配器，它的逻辑结构跟堆差不多，默认是大堆；物理结构要看底层容器，默认是vector，也可以用deque。上面是大根堆与小根堆的逻辑结构。

默认底层容器是vector的原因：因为它的下标访问速率更快。不支持list作为底层容器，因为list仅提供双向迭代器，而priority_queue需要的是随机迭代器。

在这里插入图片描述

1. 以上是 priority_queue提供的一些接口，接下来我来简要的说明一些常用接口的作用：

1. (constructor)：构造函数，用于构造 priority_queue 类对象。其中系统自动生成的无参默认构造和范围(迭代器区间)构造用得比较多。
2. empty()：判断priority_queue对象是否为空。
3. size()：返回 priority_queue对象里元素的个数。
4. top()：返回优先级队列顶部的元素，即堆顶元素。
5. push()：压入一个元素。
6. pop()：移除优先级队列顶部元素，它没有返回值，不会返回被移除的元素值。

2. 使用

在这里插入图片描述

关于priority_queue对象的创建：能够看到，priority_queue这个容器适配器有三个模板参数，依次是：T: 接收存储元素的类型，Container：接收底层容器的类型，Compare：接收比较器（一般传递仿函数类类型，之后会讲到）的类型。其中后面两个模板参数都有默认值，在进行实例化对象时可以不用传递参数。

代码语言：javascript

AI代码解释

//使用priority_queue时要包含头文件queue priority_queue<int> pq1;

关于Container：vector是默认容器，我们也可以根据需求来改变底层容器，比如deque。

代码语言：javascript

AI代码解释

priority_queue<int, deque<int>> pq2;

关于Compare：默认值是less这个仿函数类型，因为它，priority_queue对象里大的数据的优先级更高，是大堆结构。我们可以传递另一个仿函数类型greater，这样是小堆结构，小的数据的优先级更高。比如下列代码：

代码语言：javascript

AI代码解释

priority_queue<int> pq1; priority_queue<int, deque<int>> pq2; //要传递第三个参数的话，第二个参数的值也不能漏掉 priority_queue<int, vector<int>, greater<int>> pq3; pq1.push(1); pq1.push(2); pq1.push(3); pq1.push(4); pq3.push(1); pq3.push(2); pq3.push(3); pq3.push(4); cout << "less: "; while (!pq1.empty()) { cout << pq1.top() << " "; pq1.pop(); } cout << endl; cout << "greater: "; while (!pq3.empty()) { cout << pq3.top() << " "; pq3.pop(); }

在这里插入图片描述

1. 由于priority_queue也是不支持迭代器（迭代器能提供随机访问）的，所以其对象的遍历需要用到top()与pop()接口来实现。

1. less -> " < " 大堆
2. greater -> " > " 小堆

它跟我们平常的思维习惯是反着来的，这一点要注意。其中的 < 与 > 是关于它的实现，可以参考下面的仿函数章节。

1. 不要搞混sort里面的Compare与priority_queue的Compare：sort是一个函数模板，而priority_queue是一个类模板。一个是函数模板类型参数，接收的是对象；一个是类模板参数，接收的是类型。

在这里插入图片描述

1. 一般比较器接收的是仿函数类类型的原因：比较器通常接收仿函数类类型而非函数指针或其他形式，一部分原因是因为类型的传递。就比如函数指针传递的是函数指针它的类型，而非传递函数指针所指向的函数，我们不知道实例化出来的对象里的函数指针指向哪里，可能是空指针，也可能是随机值，总之都是无效指针。当然，也不是不能传递函数指针，不过这个过程会非常麻烦。

二、仿函数

1. 仿函数，数如其名，它不是真函数，而是一个类。不过它的实例化对象可以像函数一样使用，这就得归功于仿函数内部对于()的重载。也可以这样说，重载了()的就是仿函数。
2. 我们来实现两个简单的less和greater仿函数以便更好的了解它：

代码语言：javascript

AI代码解释

namespace mosheng//防止与std里的冲突 { template<class T> class less { public: bool operator()(const T& a, const T& b) { return a < b; } }; template<class T> class greater { public: bool operator()(cosnt T& a, cosnt T& b) { return a > b; } }; }

1. 我们可以把它用在冒泡排序里来控制升序和降序：

代码语言：javascript

AI代码解释

template<class T, class Compare = mosheng::less<T>> void BubbleSort(T* a, int n, Compare com) { int exchange = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) { //等价于com.operator()(a[j + 1], a[j]) if (com(a[j + 1], a[j])) { exchange = 1; swap(a[j], a[j + 1]); } } if (exchange == 0) { break; } } } int main() { int arr[] = { 1, 5, 12, 2, 1, 3, 77 }; BubbleSort(arr, 7, mosheng::less<int>()); cout << "less: "; for (auto e : arr) { cout << e << " "; } cout << endl; cout << "greater: "; BubbleSort(arr, 7, mosheng::greater<int>()); for (auto e : arr) { cout << e << " "; } cout << endl; return 0; }

就有：

在这里插入图片描述

1. 我们将仿函数类类型less与greater传递给Campare，进而创造出Compare类型的实例化对象com，再通过com调用operator()函数，com(a[j + 1], a[j])，等价于com.operator()(a[j + 1], a[j])，进而达到目的。可以看到，虽然com不是函数，只是类的实例化对象，但它与函数的功能无二，所以是仿函数。
2. 有的时候，库里面提供的仿函数不能够达到我们的目的，比如为Date类的指针排序，它比较的是指针的大小，而不是指针所指向的数据。这个时候我们就得自己构建仿函数。如下：

代码语言：javascript

AI代码解释

class Date { public: Date(int year = 1900, int month = 1, int day = 1) : _year(year) , _month(month) , _day(day) {} bool operator<(const Date& d)const { return (_year < d._year) || (_year == d._year && _month < d._month) || (_year == d._year && _month == d._month && _day < d._day); } bool operator>(const Date& d)const { return (_year > d._year) || (_year == d._year && _month > d._month) || (_year == d._year && _month == d._month && _day > d._day); } friend ostream& operator<<(ostream& _cout, const Date& d); private: int _year; int _month; int _day; }; ostream& operator<<(ostream& _cout, const Date& d) { _cout << d._year << "-" << d._month << "-" << d._day; return _cout; } //构建仿函数 struct PDateLess { bool operator()(const Date* p1, const Date* p2) { return *p1 < *p2; } }; int main() { priority_queue<Date*, vector<Date*>> q1; q1.push(new Date(2025, 7, 20)); q1.push(new Date(2025, 7, 21)); q1.push(new Date(2025, 7, 22)); cout << "原始："; while (!q1.empty()) { cout << *q1.top() << " "; q1.pop(); } cout << endl; cout << "构建的PDteLess："; priority_queue<Date*, vector<Date*>, PDateLess> q2; q2.push(new Date(2025, 7, 20)); q2.push(new Date(2025, 7, 21)); q2.push(new Date(2025, 7, 22)); while (!q2.empty()) { cout << *q2.top() << " "; q2.pop(); } cout << endl; return 0; }

在这里插入图片描述

• 原始里面的顺序是随机的，不是我们预期的效果。