c++初阶-----适配器---priority_queue

作者前言

🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂
​🎂 作者介绍： 🎂🎂
🎂 🎉🎉🎉🎉🎉🎉🎉 🎂
🎂作者id：老秦包你会， 🎂
简单介绍：🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂
喜欢学习C语言、C++和python等编程语言，是一位爱分享的博主，有兴趣的小可爱可以来互讨 🎂🎂🎂🎂🎂🎂🎂🎂
🎂个人主页::小小页面🎂
🎂gitee页面:秦大大🎂
🎂🎂🎂🎂🎂🎂🎂🎂
🎂 一个爱分享的小博主 欢迎小可爱们前来借鉴🎂

---

介绍

翻译：

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元
   素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特
   定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭
   代器访问，并支持以下操作：
   empty()：检测容器是否为空
   size()：返回容器中有效元素个数
   front()：返回容器中第一个元素的引用
   push_back()：在容器尾部插入元素
   函数声明 接口说明
   priority_queue()/priority_queue(first,0last) 构造一个空的优先级队列
   empty( )
   检测优先级队列是否为空，是返回true，否则返回
   false
   top( ) 返回优先级队列中最大(最小元素)，即堆顶元素
   push(x) 在优先级队列中插入元素x
   pop() 删除优先级队列中最大(最小)元素，即堆顶元素
   pop_back()：删除容器尾部元素
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指
   定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数
   make_heap、push_heap和pop_heap来自动完成此操作。

使用

#include<iostream>
#include<queue>
using namespace std;
typedef priority_queue<int> i;
int main()
{i qt;qt.push(4);qt.push(5);qt.push(6);qt.push(9);qt.push(1);while (!qt.empty()){cout << qt.top() << endl;qt.pop();}return 0;
}

结果:

如果要想priority_queue是从小到大可以使用greater 类型

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
typedef priority_queue<int, vector<int>, greater<int>> i;
int main()
{i qt;qt.push(4);qt.push(5);qt.push(6);qt.push(9);qt.push(1);while (!qt.empty()){cout << qt.top() << endl;qt.pop();}return 0;
}

模拟

priority_queue的底层是堆，所以，我们模拟的时候，可以理解为是堆的插入和删除

可以看出 这个容器有三个类型， T 、 vector 、 less

普通模拟

template<class T, class contaier = vector<T> >
class my_priorty_queue
{
public:void push(const T& num){//尾插a.push_back(num);//建堆,向上调整upajust();}void pop(){//首尾交换swap(a[0], a[a.size() - 1]);//删除尾部a.pop_back();//向下调整downadjust();}void upajust(){this->a;//向上调整,建大堆int i = (this->a).size() - 1;while (i > 0){if (a[i] > a[(i - 1) / 2]){swap(a[i], a[(i - 1) / 2]);i = (i - 1) / 2;}elsebreak;}}void downadjust(){int father = 0;while (father < a.size()){//进行分类,如果没有孩子,只有一个孩子,两个孩子if (a.size()-1< 2 * father + 1)break;else if (a.size() - 1 < 2 * father + 2){if (a[father] < a[2 * father + 1]){swap(a[father], a[2 * father + 1]);}elsebreak;}else{int leftchila = 2 * father + 1;int rightchila = leftchila + 1;int pos = 0;if (a[leftchila] < a[rightchila]){pos = rightchila;}else{pos = leftchila;}if (a[pos] > a[father])swap(a[pos], a[father]);elsebreak;father = pos;}}//孩子比较出最小的}bool empty(){return a.empty();}T top(){assert(a.size());return a[0];}
private:contaier a;};

这样写只能手动改代码进行建立大小堆，不太好用，
我们有两个方法进行控制其中的大小堆，
一个是C语言的的回调函数，一个是c++的仿函数

类似C语言的回调函数方法

template<class T, class contaier = vector<T>>class my_priorty_queue{public:my_priorty_queue(bool(*pf)(T, T)):a(*new contaier()),_pf(pf){}void push(const T& num){//尾插a.push_back(num);//建堆,向上调整upajust();}void pop(){//首尾交换std::swap(a[0], a[a.size() - 1]);//删除尾部a.pop_back();//向下调整downadjust();}void upajust(){this->a;//向上调整,建大堆int i = (this->a).size() - 1;while (i > 0){if (_pf(a[i],a[(i - 1) / 2])){std::swap(a[i], a[(i - 1) / 2]);i = (i - 1) / 2;}elsebreak;}}void downadjust(){int father = 0;while (father < a.size()){//进行分类,如果没有孩子,只有一个孩子,两个孩子if (a.size() - 1 < 2 * father + 1)break;else if (a.size() - 1 < 2 * father + 2){if (_pf(a[2 * father + 1], a[father])){std::swap(a[father], a[2 * father + 1]);}elsebreak;}else{int leftchila = 2 * father + 1;int rightchila = leftchila + 1;int pos = 0;//孩子比较大小if (_pf( a[rightchila], a[leftchila])){pos = rightchila;}else{pos = leftchila;}//孩子和父亲比较if (_pf(a[pos] ,a[father]))std::swap(a[pos], a[father]);elsebreak;father = pos;}}}bool empty(){return a.empty();}T top(){assert(a.size());return a[0];}private:contaier a;bool(*_pf)(T,T);};template<class T >bool funtionmin(T a, T b){return a < b;}template<class T >bool funtionmax(T a, T b){return a > b;}

这样写的话,就有点别扭,实例化要传入函数指针，这和我们使用库函数提供的差别很大

仿函数

本质就是一个类, 这个类重载了(), 可以理解为重载了()的类就是仿函数,
所以,仿函数的调用就是, 对象名(形参, 形参)
例如:

class AA
{void operator()(int a, int b){cout << "a+b=" << a + b;}
};
int main()
{AA elemest;elemest(1,1);return 0;
}

模拟priority_queueu使用仿函数,如图所示,这也就解释了,为啥会有三个类模板参数了

template<class T, class contaier = vector<T> , class conpart = upsortjust<T>> class my_priorty_queue{public:void push(const T& num){//尾插a.push_back(num);//建堆,向上调整upajust();}void pop(){//首尾交换std::swap(a[0], a[a.size() - 1]);//删除尾部a.pop_back();//向下调整downadjust();}void upajust(){this->a;//向上调整,建大堆int i = (this->a).size() - 1;while (i > 0){if (_pf(a[i],a[(i - 1) / 2])){std::swap(a[i], a[(i - 1) / 2]);i = (i - 1) / 2;}elsebreak;}}void downadjust(){int father = 0;while (father < a.size()){//进行分类,如果没有孩子,只有一个孩子,两个孩子if (a.size() - 1 < 2 * father + 1)break;else if (a.size() - 1 < 2 * father + 2){if (_pf(a[2 * father + 1], a[father])){std::swap(a[father], a[2 * father + 1]);}elsebreak;}else{int leftchila = 2 * father + 1;int rightchila = leftchila + 1;int pos = 0;//孩子比较大小if (_pf(a[rightchila], a[leftchila])){pos = rightchila;}else{pos = leftchila;}//孩子和父亲比较if (_pf(a[pos] ,a[father]))std::swap(a[pos], a[father]);elsebreak;father = pos;}}}bool empty(){return a.empty();}T top(){assert(a.size());return a[0];}private:contaier a;conpart _pf;};template<class T>class upsortjust{public:bool operator()(const T& a, const T& b){return a > b;}};template<class T>class downsortjust{public:bool operator()(const T& a, const T& b){return a < b;}};};

小总结

可以看出，仿函数的使用和函数指针的使用是相似的，如果碰见仿函数对象传递的变量
例如：

sort函数的Compart comp 这个参数，也可以传函数指针，
如果不懂的话，也可以看我模拟的方法，