网站建设是多少钱,响应式网页技术,安徽网站开发与维护专业,语言网站建设引言#xff1a;
北京时间#xff1a;2023/3/18/21:47#xff0c;周末#xff0c;不摆烂#xff0c;但是欠钱终于还是遭报应了#xff0c;导致坐牢7小时#xff08;上午3.5#xff0c;下午3.5#xff09;#xff0c;难受#xff0c;充分意识到行哥是那么的和蔼可亲…引言
北京时间2023/3/18/21:47周末不摆烂但是欠钱终于还是遭报应了导致坐牢7小时上午3.5下午3.5难受充分意识到行哥是那么的和蔼可亲励志下次上蛋哥的课可以还清债务所以下一篇乃至更多篇博客都将是关于系统编程的知识周末时光昨天12点睡觉今天7点40起床然后到9点上课12:50追一集动漫1点整睡觉睡到2点25分起床上第二节课到6点下楼丢垃圾然后洗澡到7点开始看最后一节C的录屏现在写博客吃饭都是在上课的时候完成无论是上午还是下午牢底坐穿但是不怕小强有韧性记录周末第一天还行不怎么摆烂但是感觉自己似乎也没学什么东西这篇博客我们就来学习一下上篇博客谈到的优先级队列堆的实现和反向迭代器等知识。
自我实现优先级队列堆
上篇博客我们了解到了优先级队列基本使用就是类似于一个堆的结构二叉堆并且大致结构和二叉树是没有什么区别的所以总的来说优先级队列有如下几个特点优先级队列是一个容器适配器优先级最高的数据是位于堆的顶部top并且实现优先级队列可以使用任意类型的容器但一般使用vector了解了这些此时我们就来正式的自我实现一下优先级队列吧
结构如图所示 功能函数 empty()检测容器是否为空 size()返回容器中有效元素个数 front()返回容器中第一个元素的引用 push_back()在容器尾部插入元素 pop_back()删除容器尾部元素 如下图 如上代码我们可以发现 在一个堆中插入和删除数据为了提高效率最终都需要重新建堆才可以所以此时就涉及到了两个建堆的函数adjust_up、adjust_down所以接下来让我们一起看一下优先级队列中最关键的两个函数如下代码 在写这两个函数的时候我们可以和上图堆的结构图在脑海中想象然后结合在一起可以很好的把代码正确的写出来。
搞定了上述优先级队列中的几个函数关键函数和向上建堆、向下建堆的两个函数此时优先级队列的大致我们就实现了但是此时可以发现在上述的代码中我们默认都是建一个小堆如果此时我们要建大堆怎么办虽然此时是可以通过直接将大于改成小于的方式来实现但是这样并不是很好所以此时我们引入一个新概念也就是昨天浅浅的了解了的仿函数概念。
浅谈仿函数
如下图 如上图我们通过函数重载的形式实现了两个模板类用于比较大小此时优先级队列就可以通过调用上述的模板类来实现建大堆和建小堆的直接切换如下代码所示 所以如上图当我们使用了仿函数之后我们就可以直接通过更改模板参数的类型来进行仿函数的切换来进行大堆和小堆的切换不需要去使用什么函数指针的方法去调用相应的函数来实现所以仿函数的发明就是为了可以让一个模板类运算符重载直接被另一个模板类的模板参数使用然后该模板类直接通过使用模板参数来实现相应的类似函数的功能不需要使用函数指针进而调用相应的函数
总模板的设计真的非常的牛什么都可以通过模板的形式进行直接传递和使用
优先级队列完整代码如下
#includeiostream
#includequeue
#includevector
using namespace std;//要明白此时的堆是一个数组容器适配器默认是vector就是使用数组的形式给我们弄成了一个树的结构就叫堆
namespace wwx
{templateclass Tstruct less//小堆仿函数{bool operator()(const T x, const T y){return x y;}};templateclass T, class Container vectorT//建大堆我们用小于struct greater//大堆仿函数{bool operator()(const T x, const T y){return x y;}};templateclass T, class Container vectorT, class Compare greaterT//此时就可以不需要使用函数指针来调用某个函数了可以直接使用模板类型来调用仿函数class priority_queue{public:void adjust_up(int child){int parent (child - 1) / 2;//这边一定要去把堆排序给复习一下这个是可以自己推出来的while (child 0)//建大堆最坏的情况就是当child为根结点的时候也就是下标为0的时候当下标为0就可以停下来了不然它是会自己break出去的{Compare com;//if (_con[parent] _con[child])//建大堆if (com(_con[parent], _con[child]))//调用仿函数去比较{std::swap(_con[parent], _con[child]);child parent;//建大堆孩子结点大此时就是让孩子变成父亲然后重复再去寻找它的父结点parent (child - 1) / 2;//迭代走走}else{break;//此时此时只是向上调整并不是堆排序}}}void adjust_down(int parent)//注意此时是在类和对象中所以可以直接使用this指针所以可以直接使用我们的适配器来存储数据{int child parent * 2 1;//父亲结点是唯一的但是孩子结点是有两个while (child _con.size())//这个条件不会写就是把this指针给漏掉了{Compare com;//if (child 1 _con.size() _con[child] _con[child 1])//左孩子小于右孩子但是前提是右孩子存在因为有的地方右孩子是不存在的所以又漏了一个条件if (child 1 _con.size() com(_con[child], _con[child 1]))//if (child 1 _con.size() Compare()(_con[child], _con[child 1]))//使用匿名对象的写法{child 1;}//if (_con[parent] _con[child])//但是这种写法是有一个前提的那种没有前提的写法要去复习if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent child;child parent * 2 1;//迭代}else{break;} }}//总结写这种代码就是要把堆的结构给深深的烙印在脑海里面树状结构void push(const T x){_con.push_back(x);adjust_up(_con.size() - 1);//尾插数据之后建堆通过向上调整的形式}void pop()//上述是堆的插入现在是堆的删除{//这边可以刚好去把堆排序给复习一下std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_priority_queue(){priority_queueint pq;pq.push(1);pq.push(2);pq.push(3);pq.push(4);pq.push(5);while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;}
}
int main()
{wwx::test_priority_queue();return 0;
}反向迭代器
我们当时在学习list的时候已经将正向迭代器给实现了所以现在我们就来实现一下返向迭代器区分为我们认为的反向迭代器和源码中的反向迭代器如下代码 如上图就是我们认为的反向迭代器和正向迭代器的实现和区别但是在真正的源码中却不是如上图中一样而是实现了更高级的写法如下代码所示 通过上述的结构图实现代码如下
总反向迭代器的源码是非常的高级的 总结周末不摆烂睡觉啦
