文章目录

• 模拟实现priority_queue
• • 1. priority_queue的介绍
  • 2. priority_queue的使用
  • 3. 仿函数
  • • 3.1 仿函数的介绍
    • 3.2 仿函数的好处
  • 4. priority_queue的模拟实现
  • 5. 用仿函数实现日期比较

模拟实现priority_queue

1. priority_queue的介绍

priority_queue文档介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

• empty()：检测容器是否为空
• size()：返回容器中有效元素个数
• front()：返回容器中第一个元素的引用
• push_back()：在容器尾部插入元素
• pop_back()：删除容器尾部元素

5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

2. priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue 。注意：默认情况priority_queue是大堆。

[注意]

1. 默认情况下，priority_queue是大堆。

#include 
#include 
#include  // greater算法的头文件
int main()
{// 默认情况下，创建的是大堆，其底层按照小于号比较vector v{ 3,2,7,6,0,4,1,9,8,5 };priority_queue q1;for (auto& e : v)q1.push(e);cout << q1.top() << endl;// 如果要创建小堆，将第三个模板参数换成greater比较方式priority_queue, greater> q2(v.begin(), v.end());cout << q2.top() << endl;
}

2. 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

3. 仿函数

3.1 仿函数的介绍

对于上面的创建成小堆的格式，发现有一个：greater 参数，priority_queue中自带的缺省参数为less，即升序大堆，因此想要建大堆就不需要进行换参数的操作，直接priority_queue就是大堆，上面的结果就是这样，想要换成小堆就得这样：priority_queue, greater>通过利用仿函数可以将比较的顺序进行颠倒，通过改变内置的比较符号从而灵活的改变按照大小的排序。

仿函数又叫函数对象，仿函数就是一个类，仿函数的函数对象就是类对象，成员是什么无所谓，下面先看一个简单的例子：

namespace yj
{templateclass less{public://operator()就是一个运算符重载bool operator()(const T& x, const T& y) const{return x < y;}};templateclass greater{public:bool operator()(const T& x, const T& y) const{return x > y;}};
}int main()
{yj::less lessFunc;lessFunc(1, 2);//lessFunc.operator()(1, 2);//实际上是这样的展开过程return 0;
}

即在之前的印象中，通过调用lessFunc，就可以把lessFunc看成一个函数名，但在这里lessFunc是一个函数对象，仿函数的对象，这个对象可以像函数一样去使用，但实际上这个对象不是直接像往常的函数一样直接调用。而是调用了运算符重载,即实际上就是这样: lessFunc.operator()(1, 2);但不会这样去写,因为运算符重载就是为了可读性。

3.2 仿函数的好处

在C语言中qsort的升降序是使用函数指针，传入大于就是大于比较，传入小于就是小于比较。那C++为什么不使用函数指针呢?

候捷老师总结:

为什么函数指针可以达到“将数组操作当做算法的参数”，那又何必有所谓的仿函数呢？函数指针毕竟不能满足STL对抽象性的要求，也不能满足软件积木的要求---->函数指针无法和STL其他组件搭配,产生更灵活的变化。

4. priority_queue的模拟实现

学习了优先级队列中的仿函数的相关知识，就可以模拟实现一个priority_queue了，与上次的stack/queue的模拟实现类似，底层也是适配器实现，没有用到迭代器。

namespace yj
{template  struct less        //大堆{bool operator()(const T& x, const T& y){return x < y;}};template struct greater        //小堆{bool operator()(const T& x, const T& y){return x > y;}};template, class Compare = less>class priority_queue{public:void adjust_up(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])//if (Compare()(_con[parent], _con[child]))    //匿名对象if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(int parent){Compare com;int child = parent * 2 + 1;while (child < _con.size()){//找左右孩子中最大的那个if(child+1<_con.size() && com(_con[child], _con[child + 1]))++child;//if (_con[child] > _con[parent])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent=child;child = parent * 2 + 1;}else{break;}}}void push(const T& x)     //插入元素 + 向上调整{_con.push_back(x);adjust_up(_con.size() - 1);     }void pop()                //删除元素(交换堆顶元素和堆尾元素，后删除) + 向下调整{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private: Container _con;};
}

5. 用仿函数实现日期比较

日期类的比较用仿函数：

namespace yj: 
{template struct less        //大堆{bool operator()(const T& x, const T& y){return x < y;}};template struct greater     //小堆{bool operator()(const T& x, const T& y){return x > y;}};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){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}private:int _year;int _month;int _day;};void test2(){priority_queue q0;q0.push(Date(2018, 10, 29));q0.push(Date(2018, 10, 30));q0.push(Date(2018, 10, 28));cout << q0.top() << endl;priority_queue,  greater> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 30));q1.push(Date(2018, 10, 28));cout << q1.top() << endl;}
}

如果是Date*，就需要自己再去写一个仿函数：即地址解引用的仿函数。

namespace yj: 
{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){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}private:int _year;int _month;int _day;};    class PDateLess        //大堆{public:bool operator()(const Date* p1, const Date* p2){return *p1 < *p2;}};class PDateGreater        //小堆{public:bool operator()(const Date* p1, const Date* p2){return *p1 > *p2;}};void test2(){priority_queue, PDateLess> q1;q1.push(new Date(2018, 10, 29));q1.push(new Date(2018, 10, 30));q1.push(new Date(2018, 10, 28));cout << *(q1.top()) << endl;priority_queue, PDateGreater> q2;q2.push(new Date(2018, 10, 29));q2.push(new Date(2018, 10, 30));q2.push(new Date(2018, 10, 28));cout << *(q2.top()) << endl;}
}