Learning C++ No.18【STL No.8】

引言：

北京时间：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，所以接下来，让我们一起看一下优先级队列中最关键的两个函数，如下代码：

在写这两个函数的时候，我们可以和上图（堆的结构图）在脑海中想象，然后结合在一起，可以很好的把代码正确的写出来。

搞定了上述优先级队列中的几个函数关键函数和向上建堆、向下建堆的两个函数，此时优先级队列的大致我们就实现了，但是此时可以发现，在上述的代码中，我们默认都是建一个小堆，如果此时我们要建大堆怎么办，虽然此时是可以通过直接将大于改成小于的方式来实现，但是这样并不是很好，所以此时我们引入一个新概念，也就是昨天浅浅的了解了的仿函数概念。

浅谈仿函数

如下图：

如上图，我们通过函数重载的形式实现了两个模板类（用于比较大小），此时优先级队列就可以通过调用上述的模板类来实现建大堆和建小堆的直接切换，如下代码所示：

所以，如上图，当我们使用了仿函数之后，我们就可以直接通过更改模板参数的类型来进行仿函数的切换，来进行大堆和小堆的切换，不需要去使用什么函数指针的方法去调用相应的函数来实现，所以仿函数的发明，就是为了可以让一个模板类（运算符重载）直接被另一个模板类的模板参数使用，然后该模板类直接通过使用模板参数来实现相应的类似函数的功能，不需要使用函数指针，进而调用相应的函数；

总：模板的设计真的非常的牛，什么都可以通过模板的形式进行直接传递和使用

优先级队列完整代码如下：

#include<iostream>
#include<queue>
#include<vector>
using namespace std;//要明白，此时的堆是一个数组（容器适配器默认是vector），就是使用数组的形式，给我们弄成了一个树的结构，就叫堆
namespace wwx
{template<class T>struct less//小堆仿函数{bool operator()(const T& x, const T& y){return x < y;}};template<class T, class Container = vector<T>>//建大堆，我们用小于struct greater//大堆仿函数{bool operator()(const T& x, const T& y){return x > y;}};template<class T, class Container = vector<T>, class Compare = greater<T>>//此时就可以不需要使用函数指针来调用某个函数了，可以直接使用模板类型来调用仿函数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_queue<int> 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的时候，已经将正向迭代器给实现了，所以现在，我们就来实现一下返向迭代器，区分为（我们认为的反向迭代器和源码中的反向迭代器），如下代码：

如上图就是我们认为的，反向迭代器和正向迭代器的实现和区别，但是在真正的源码中却不是如上图中一样，而是实现了更高级的写法，如下代码所示：

通过上述的结构图，实现代码如下：

总：反向迭代器的源码是非常的高级的

总结：周末不摆烂，睡觉啦！