企业网站做静态网站还是,wordpress+单页模版,jquery网站模版,手机怎么建设视频网站文章目录 仿函数优先队列的模拟实现 仿函数
上回我们说到#xff0c;优先队列的实现需要用到仿函数的特性
让我们再回到这里 这里我们发现他传入的用于比较的东西竟然是一个类模板#xff0c;而不是我们所见到的函数
我们可以先创建一个类#xff0c;用于比较大小
struc… 文章目录 仿函数优先队列的模拟实现 仿函数
上回我们说到优先队列的实现需要用到仿函数的特性
让我们再回到这里 这里我们发现他传入的用于比较的东西竟然是一个类模板而不是我们所见到的函数
我们可以先创建一个类用于比较大小
struct Less
{bool operator()(int x, int y){return x y;}
};这里我们创建了一个Less类并且重载了圆括号让他比较xy是否成立
我们可以这样使用
Less ls;
cout ls(1, 2) endl;结果是1
我们单单从cout这一句来看ls就好像一个函数一样可以比较1和2的大小但是实际上是由Less创建的一个对象来比较的
我们把这一句还原
Less ls;
cout ls(1, 2) endl;
cout ls.operator()(1, 2) endl;实际上后面这一句才是原本的样子
如果我们给这个类加上个模板
例如
templateclass T
struct Less
{bool operator()(T x, T y){return x y;}
};这样就可以用来比较不止整形的大小了
这样我们就可以在别的类内部通过类模板来传递函数的功能
讲到这我们就明白了这个仿函数实际上的功能类似于函数指针是用来传递函数的逻辑的
这样做的好处是我们可以自行定义需要的函数
例如当堆中的数据为自定义类型通用的less和greater比较就不起作用了需要自行定义传入了
优先队列的模拟实现
#include iostream
using namespace std;
#include vector
namespace xu
{templateclass Tstruct less{bool operator()(const T left, const T right){return left right;}}; // 仿函数的实现templateclass Tstruct greater{bool operator()(const T left, const T right){return left right;}}; // 仿函数的实现templateclass T, class Container std::vectorT, class Compare lessTclass priority_queue{public:// 创造空的优先级队列priority_queue() : c() {}templateclass Iteratorpriority_queue(Iterator first, Iterator last): c(first, last){// 将c中的元素调整成堆的结构int count c.size();int root ((count - 2) 1);for (; root 0; root--)AdjustDown(root);}void push(const T data){c.push_back(data);AdjustUP(c.size() - 1);}void pop(){if (empty())return;swap(c.front(), c.back());c.pop_back();AdjustDown(0);}size_t size()const{return c.size();}bool empty()const{return c.empty();}const T top()const{return c.front();}private:// 向上调整void AdjustUP(int child){int parent ((child - 1) 1);while (child){if (Compare()(c[parent], c[child])){swap(c[child], c[parent]);child parent;parent ((child - 1) 1);}else{return;}}}// 向下调整void AdjustDown(int parent){size_t child parent * 2 1;while (child c.size()){// 找以parent为根的较大的孩子if (child 1 c.size() Compare()(c[child], c[child 1]))child 1;// 检测双亲是否满足情况if (Compare()(c[parent], c[child])){swap(c[child], c[parent]);parent child;child parent * 2 1;}elsereturn;}}private:Container c;};
}
