做外贸常用的网站,win10 wordpress安装,如何海外网站建设,申请自媒体账号目录
前言#xff1a;
1 优先级队列的使用
2 优先级队列的实现
3 仿函数 前言#xff1a;
栈和队列相对其他容器来说是比较简单的#xff0c;在stl里面#xff0c;有一种容器适配器是优先级队列#xff08;priority_queue#xff09;#xff0c;它也是个队列#…目录
前言
1 优先级队列的使用
2 优先级队列的实现
3 仿函数 前言
栈和队列相对其他容器来说是比较简单的在stl里面有一种容器适配器是优先级队列priority_queue它也是个队列但是不大像队列本文中简略介绍如何使用和模拟实现它。 1 优先级队列的使用
要使用先文档 文档黑体第一句话就是优先级队列是一种容器配置器容器配置器是电脑有电源适配器起到提供电源的作用但是这个适配器不是充电器即充电的时候电源来自于电线但是我们不能直接拿电线充电吧这时候适配器就有用了通过封装使得两边达到一个配合的效果容器配置器同理。当然这不是重点。
模板是必要的模板参数有3个参考栈和队列第二个参数是底层用的哪种容器进行实现的这里的默认是使用的顺序表第三个参数是仿函数后面介绍。
那么在来看看成员函数 很少是吧可以说成员函数和队列没有什么差别所以我们现在简单使用一下
int main()
{priority_queueint q1;q1.push(2);q1.push(1);q1.push(4);q1.push(3);q1.push(5);cout q1.size() endl;while (!q1.empty()){cout q1.top() ;q1.pop();}cout endl;cout q1.size() endl;return 0;
} 使用很简单但是打印的结果却有点奇怪
这就是优先级队列的特殊之处了我们并没有对它进行排序但是打印出来是默认有序的这是因为它的本质是堆而模板参数第三个仿函数的参与决定了它是大堆还是小堆默认是升序的可以理解为升序状态下谁最小谁优先级最高所以先被打印。
但是实际上不用管那么多就把它认为是堆就ok了所以我们实现的时候需要实现向上调整算法和向下调整算法。
对于仿函数我们放在实现了80%在介绍。 2 优先级队列的实现
我们需要实现以下几个接口
empty,size,push,pop,top接口不多另外还要实现向上调整算法和向下调整算法。
优先级队列的一般结构为
template class T,class container vectorT
class priority_queue
{
public:private:container _con;};
模板的第三个参数先不急。
简单的几个接口我们一股脑实现就完事了
void push(const T val)
{_con.push_back(val);adjust_up(_con.size() - 1);
}bool empty()
{return _con.empty();
}void pop()
{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);
}size_t size()
{return _con.size();
}const T top()
{return _con[0];
}
这部分是没什么难度的。
随机要实现的是push和pop这里提问为什么默认的底层实现是vector呢
因为堆的本质就是一块连续的空间我们只是把它抽象为了完全二叉树。
push数据之后堆本身的结构被破坏了所以我们需要向上调整数据在数据结构初级的时候已经介绍过两种算法这里过一下就Ok
向上调整算法是通过孩子节点和父节点的值进行比较然后交换位置可能有点倒反天罡谁的值大谁就当爸爸我们知道孩子节点的下标之后父节点的下标就是孩子下标 - 1 / 2如果不熟悉可以拿图推演一下最后一次交换的时候孩子节点的下标变成了父节点的下标所以判断条件应该是孩子节点的下标是否合法即是否大于0
void adjust_up(size_t child)
{size_t parent (child - 1) / 2;while (child 0){if(_con[parent] _con[child]){swap(_con[parent],_con[child]);child parent;parent (child - 1) / 2;}else{break;}}
}
此时push的的准备工作就做好了插入调整完成
void push(const T val)
{_con.push_back(val);adjust_up(_con.size() - 1);
}
与之对应的是poppop对应的准备工作是向下调整算法向下调整算法有几个需要注意的点就是我们建大堆那么就要在孩子节点中找到两个孩子中较大的那一个除此之后不是所有的节点都有两个子节点所以我们需要保证孩子 1不小于size这是基础工作随机就是比较大小谁大谁就往上
void adjust_down(size_t parent)
{size_t child parent * 2 1;while (child _con.size()){if (child 1 _con.size() _con[child] _con[child 1]){child;}if (_con[child] _con[parent]){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}
pop的准备工作也是完毕了那么pop就行对于堆部分有些遗忘的同学就会想为什么涉及到向下调整因为删除为了效率和不破坏堆的结构我们的措施是首尾交换向下调整。
void pop()
{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);
} 3 仿函数
仿函数是本文的重点我们需要先知道什么是仿函数
先看一段这样的代码
template class T
struct Less
{bool operator()(const T a,const T b){return a b;}
};
void Func(int ,int)
{cout endl;
}int main()
{Lessint Fun;Fun(1,2);Func(1,2);return 0;
}
如果说只看主函数的代码就会容易觉得这不就是两个函数调用吗仿函数仿函数顾名思义模仿函数因为调用的时候挺像函数的但是实际上它是一个类这个类实例化对象使用重载后的()我们称这个过程叫做仿函数调用仿函数实际上只有一个东西就是重载的()。
重载的()没有其他东西只有比较对于内置类型我们可以直接比较对于自定义类型我们可能要重载一下 或者 。
所以仿函数是个类类里面的函数是重载的()一般是两个参数用于比较使用。
所以我们在向上调整算法和向下调整算法的实现里面的比较就可以用仿函数完成进而控制升序降序那么我们就还要写两个类
//仿函数
template class T
struct less
{bool operator()(const T x,const T y){return x y;}
};template class T
struct greater
{bool operator()(const T x, const T y){return x y;}
};
那么对应更新的就是我们的两个算法
template class T,class container vectorT,class compare greaterTvoid adjust_up(size_t child)
{compare com;size_t parent (child - 1) / 2;while (child 0){//if (_con[parent] _con[child])if(com(_con[parent] , _con[child])){swap(_con[parent],_con[child]);child parent;parent (child - 1) / 2;}else{break;}}
}void adjust_down(size_t parent)
{compare com;size_t 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;}}
}
向下调整算法这里有个注意的if(child 1 _con.size() com(_con[child], _con[child 1]))第一个判断条件放在前面是最好的因为越界了不用了比较了代码逻辑更严密。
但是这里使用了仿函数好像也没有什么特别的无非就是用了一个像函数调用一样的类而已为什么不用C语言中qsort里面的函数指针呢
在C里面函数指针并不常用难写不说代码的可移植性还不高目前我们针对的内置类型使用的仿函数效果不明显我们引入一个日期类一个自定义类型进行日期的比较。
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);}
private:size_t _year;size_t _month;size_t _day;
};
对于自定义类型的比较重载已经写在了类里面现在直接比较就可以了
class DateGreater
{bool operator()(const Date d1, const Date d2){return d1 d2;}
};
class DateLess
{bool operator()(const Date d1, const Date d2){return d1 d2;}
};
void Test2_priority_queue()
{priority_queueDate q1;q1.push({ 2024, 4, 17 });q1.push({ 2024, 4, 18 });q1.push({ 2024, 4, 19 });q1.push({ 2024, 4, 20 });cout q1.size() endl;while (!q1.empty()){cout q1.top() ;q1.pop();}cout endl;
}
对比淘宝淘宝的的排序比如综合评分排序销量排序等用户点击对应按钮系统就会调用对应的函数使用的就是仿函数函数指针在C里面不太常用它的类型和变量名混杂一起看起来不太舒服。
仿函数的一般使用差不多了但是如果我们给优先级队列里面存放日期类的指针但是相比较日期类的大小怎么办呢
void Test3_priority_queue()
{priority_queueDate*, vectorDate* q1;q1.push(new Date(2024,5,20));q1.push(new Date(2024,5,21));q1.push(new Date(2024,5,22));q1.push(new Date(2024,5,23));while (!q1.empty()){cout *(q1.top()) ;q1.pop();}cout endl;
}
比如这样里面都是指针我们push的也是new出来的指针我们使用的仿函数是
class DateGreater
{bool operator()(const Date d1, const Date d2){return d1 d2;}
};
class DateLess
{bool operator()(const Date d1, const Date d2){return d1 d2;}
};
那么这个仿函数就不可以了比较出来的都是随机结果这是因为new出来的地址都是随机的而默认的是比较的指针打印出来的是对应的日期所以结果一会儿是对的一会儿是错的这是因为仿函数的错误使用我们应该解引用之后再进行比较这里就要另外提供一个仿函数了
class PDateGreater
{
public:bool operator()(Date* d1, Date* d2){return *d1 *d2;}
};
光提供了还不行我们还要显式调用
void Test3_priority_queue()
{priority_queueDate*, vectorDate*,PDateGreater q1;q1.push(new Date(2024,5,20));q1.push(new Date(2024,5,21));q1.push(new Date(2024,5,22));q1.push(new Date(2024,5,23));while (!q1.empty()){cout *(q1.top()) ;q1.pop();}cout endl;
}
这样就是完美的了。仿函数的简单介绍就到这里。 感谢阅读
