【c++】STL-容器适配器priority_queue与仿函数

priority_queue优先级队列基本情况priority_queue是一种容器适配器它的逻辑结构跟堆差不多默认是大堆物理结构要看底层容器默认是vector也可以用deque。上面是大根堆与小根堆的逻辑结构。默认底层容器是vector的原因因为它的下标访问速率更快。不支持list作为底层容器因为list仅提供双向迭代器而priority_queue需要的是随机迭代器。在这里插入图片描述以上是 priority_queue提供的一些接口接下来我来简要的说明一些常用接口的作用(constructor)构造函数用于构造 priority_queue 类对象。其中系统自动生成的无参默认构造和范围(迭代器区间)构造用得比较多。empty()判断priority_queue对象是否为空。size()返回 priority_queue对象里元素的个数。top()返回优先级队列顶部的元素即堆顶元素。push()压入一个元素。pop()移除优先级队列顶部元素它没有返回值不会返回被移除的元素值。2. 使用在这里插入图片描述关于priority_queue对象的创建能够看到priority_queue这个容器适配器有三个模板参数依次是T: 接收存储元素的类型Container接收底层容器的类型Compare接收比较器一般传递仿函数类类型之后会讲到的类型。其中后面两个模板参数都有默认值在进行实例化对象时可以不用传递参数。代码语言javascriptAI代码解释//使用priority_queue时要包含头文件queue priority_queueint pq1;关于Containervector是默认容器我们也可以根据需求来改变底层容器比如deque。代码语言javascriptAI代码解释priority_queueint, dequeint pq2;关于Compare默认值是less这个仿函数类型因为它priority_queue对象里大的数据的优先级更高是大堆结构。我们可以传递另一个仿函数类型greater这样是小堆结构小的数据的优先级更高。比如下列代码代码语言javascriptAI代码解释priority_queueint pq1; priority_queueint, dequeint pq2; //要传递第三个参数的话第二个参数的值也不能漏掉 priority_queueint, vectorint, greaterint 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(); }在这里插入图片描述由于priority_queue也是不支持迭代器迭代器能提供随机访问的所以其对象的遍历需要用到top()与pop()接口来实现。less - 大堆greater - 小堆它跟我们平常的思维习惯是反着来的这一点要注意。其中的 与 是关于它的实现可以参考下面的仿函数章节。不要搞混sort里面的Compare与priority_queue的Comparesort是一个函数模板而priority_queue是一个类模板。一个是函数模板类型参数接收的是对象一个是类模板参数接收的是类型。在这里插入图片描述一般比较器接收的是仿函数类类型的原因比较器通常接收仿函数类类型而非函数指针或其他形式一部分原因是因为类型的传递。就比如函数指针传递的是函数指针它的类型而非传递函数指针所指向的函数我们不知道实例化出来的对象里的函数指针指向哪里可能是空指针也可能是随机值总之都是无效指针。当然也不是不能传递函数指针不过这个过程会非常麻烦。二、仿函数仿函数数如其名它不是真函数而是一个类。不过它的实例化对象可以像函数一样使用这就得归功于仿函数内部对于()的重载。也可以这样说重载了()的就是仿函数。我们来实现两个简单的less和greater仿函数以便更好的了解它代码语言javascriptAI代码解释namespace mosheng//防止与std里的冲突 { templateclass T class less { public: bool operator()(const T a, const T b) { return a b; } }; templateclass T class greater { public: bool operator()(cosnt T a, cosnt T b) { return a b; } }; }我们可以把它用在冒泡排序里来控制升序和降序代码语言javascriptAI代码解释templateclass T, class Compare mosheng::lessT 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::lessint()); cout less: ; for (auto e : arr) { cout e ; } cout endl; cout greater: ; BubbleSort(arr, 7, mosheng::greaterint()); for (auto e : arr) { cout e ; } cout endl; return 0; }就有在这里插入图片描述我们将仿函数类类型less与greater传递给Campare进而创造出Compare类型的实例化对象com再通过com调用operator()函数com(a[j 1], a[j])等价于com.operator()(a[j 1], a[j])进而达到目的。可以看到虽然com不是函数只是类的实例化对象但它与函数的功能无二所以是仿函数。有的时候库里面提供的仿函数不能够达到我们的目的比如为Date类的指针排序它比较的是指针的大小而不是指针所指向的数据。这个时候我们就得自己构建仿函数。如下代码语言javascriptAI代码解释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_queueDate*, vectorDate* 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_queueDate*, vectorDate*, 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; }在这里插入图片描述原始里面的顺序是随机的不是我们预期的效果。