C++模拟实现priority_queue(仿函数)

优先级队列

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)
学习优先级队列时最主要的是仿函数的使用，如下less和greater

#include <vector>
namespace QBL
{template<class T>//仿函数,本质就是运算符重载class less{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>class greater{public:bool operator()(const T& x, const T& y){return x > y;}};//仿函数默认传小于，则是大堆//less这点库里面也是和人的直觉是反着的，明明是less，却是大堆template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{public:void adjust_up(size_t child){int parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])//if (_con[parent] < _con[child])if(Compare()(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && Compare()(_con[child], _con[child + 1]))++child;//if (_con[child] > _con[parent])if(Compare()(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& val){_con.push_back(val);adjust_up(_con.size() - 1);}void pop()//删除堆顶{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}

仿函数

仿函数本质就是一个类，其中重载了operator()，我们可以根据我们的需要改变比较逻辑。
关于仿函数的使用，不仅仅局限于上面代码的比较，还可以进行类的比较，不如日期类或者日期类的指针。如果比较日期类的指针就如下：

class ComparePDate
{
public:bool operator()(const Date* x, const Date* y){return *x < *y;}
};

通过上述代码，即使优先级队列插入的是日期类的指针，同样可以按照我们需要的大小输出。

不仅仅是日期类，还有库中的sort函数，传参也可以传仿函数类型
看手册的描述可以发现，我们需要传我们需要的比较逻辑，sort会根据bool类型的返回确定仿函数的两个参数哪一个排在前面。
用法如下：

struct goods
{ string _name;//名字double _price;//价格int _evaluate;//评价goods(const char* str, double price, int evaluate):_name(str), _price(price), _evaluate(evaluate){}
};
struct ComparePriceLess
{bool operator()(const goods& gl, const goods& gr){return gl._price < gr._price;}
};
struct ComparePriceGreater
{bool operator()(const goods& gl, const goods& gr){return gl._price > gr._price;}
};
struct CompareEvaluateLess
{bool operator()(const goods& gl, const goods& gr){return gl._evaluate < gr._evaluate;}
};
struct CompareEvaluateGreater
{bool operator()(const goods& gl, const goods& gr){return gl._evaluate > gr._evaluate;}
};
int main()
{vector<goods> gs = { {"苹果",3.1,5},{"香蕉",2.1,4} ,{"菠萝",1.1,3} ,{"葡萄",4.1,2} };sort(gs.begin(), gs.end(), ComparePriceLess());//将仿函数的匿名对象做参数传入，就是我们的比较方式sort(gs.begin(), gs.end(), ComparePriceGreater());sort(gs.begin(), gs.end(), CompareEvaluateLess());sort(gs.begin(), gs.end(), CompareEvaluateGreater());return 0;
}