文章目录
- 一、仿函数
- 二、priority_queue含义及接口
- 三、priority_queue模拟实现
- 四、仿函数的特殊作用
一、仿函数
1.在类中运算符重载了()，也就是函数调用时后面的()
则该类称作仿函数类，该类实例化出的对象称作仿函数
2.该类实例化出的对象称作仿函数是因为该对象可以像函数一样被调用
（ 对象(参数列表) ） == 对象.operator()(参数列表)
3.仿函数类也是类，所以仿函数类也可以拥有普通类的成员变量和成员函数
4.仿函数使用
（1）通过模板和类型转变函数体内比较逻辑
（2）< 是升序，> 是降序
（3）假设此时有一个排序算法应用于网站商品的排序
当需要购买高端商品时需要使用价格的降序，此时高端商品排在前面
当需要购买低端商品时需要使用价格的升序，此时低端商品排在前面
而我们在编写排序算法时，一般会固定该排序算法是升序还是降序
那么随着用户的选择不同所需要执行的排序顺序也会不同
总不能当用户选择不同时再手动更改排序顺序，显然不现实
面对上述这种情况可以先两套排序算法，一套为升序，一套为降序
这种方式显然会使得代码变的冗余，因为排序顺序的改变只需要改变比较符号
面对上述这种情况还可以在参数位置使用函数指针，在比较逻辑位置通过函数指针
回调比较函数，虽然这种方式可行，但是也会引发一些问题
函数指针的写法比较麻烦而且太死板，参数位置返回值类型一旦写好，就无法更改
参数的个数，参数的类型，返回值的类型都是写死的
如果此时需要使用该排序算法对其他类型的数据进行排序时
该类型数据的排序的比较函数很有可能和排序算法的参数的函数指针接口不统一
就无法调用该排序算法
（4）根据上述说法，很明显使用函数指针回调也是不可取的
那么面对此问题就可以使用一个类，类中封装比较函数，在函数参数位置传递给类的
对象，在函数体内部比较逻辑位置使用该对象进行调用比较函数，但是此时又会出现
一个问题，比较函数命名为“什么”，在函数体内调用是对象.成员函数，成员函数命
名不同，会导致在函数体内无法调用，所以为了统一就可以使用仿函数
对象.(参数列表)，这样就可以统一调用比较函数，再配合函数模板，实现泛型
那么该排序算法就可以根据排序对象类型的不同，使用不同的比较逻辑
二、priority_queue含义及接口
1.优先级队列其实就是堆
2.优先级队列priority_queue是一个容器适配器，默认容器为vector
因为priority_queue是一个堆，堆是一个完全二叉树，最后一层必须连续
出来最后一层其余层都满了，整体必须连续，适合使用数组结构来存储
那么为什么不是deque呢？因为堆的插入删除数据需要使用的向上调整和向下调整算法
需要大量使用[]下标，vector的[]下标效率高
3.priority_queue还需要一个模板参数就是仿函数类，该仿函数类微观角度是
用来控制向上调整和向下调整算法的比较逻辑以及比较细节
宏观角度是用来控制堆为大堆还是小堆
4.priority_queue默认是大堆(每一个父结点 >= 子节点)
默认的仿函数类是less，就表示仿函数类为less时是大堆，仿函数类为greater时为小堆
5.priority_queue在queue头文件当中，所以无论是使用queue还是priority_queue
都只需要包含头文件<queue>就可以了
6.priority_queue接口
需要注意的是top接口，priority_queue的top接口返回的是堆顶的数据值实现了const版本
其他容器的top都是const和非const版本，为什么priority_queue的top只有const版本？
因为为了维护堆的结构，如果堆顶的数据可以更改，那么就会破坏堆的结构
7.priority_queue每次出数据时，都是出优先级最高的数据
大堆以大为优先级，小堆以小为优先级
三、priority_queue模拟实现
1.因为priority_queue是一个容器适配器大部分接口是去适配其他容器的接口
priority_queue底层结构是一个堆
所以priority_queue最核心的是向上调整和向下调整算法
所以首先实现向上调整和向下调整算法
向上调整和向下调整算法因为只服务于堆，所以就可以为priority_queue的私有
已知子求父：（child - 1）/ 2
已知父求子：左子：parent * 2 + 1 右子：parent * 2 + 2
向上调整：child > 0 （child == 0 表示此时child为堆顶，不可能再有父）
向下调整：child < size（child > size 表示parent已经为叶子）
2.向上调整算法
向上调整算法需要保证，在插入该数据之前，本身就是一个堆
那么从最开始插入数据时，插入一个数据就向上调整一次
就可以保证为一个堆
插入新数据时只会影响到祖先这一条路径
假设为大堆：
3.向下调整算法
向下调整算法需要保证左右子树都为堆结构
每次调整只会改变左右子树中的一颗子树不会全盘打乱
假设为大堆
选出子结点中最大的，只会影响左右子树的其中一颗子树
如果与其比较是否需要交换，如果没有交换，表明已经为一个大堆
直接break推出循环，如果交换，就使得parent = child刷新父
再使得child = parent * 2 + 1 刷新子（为左子）
4.默认构造函数
因为priority_queue是容器适配器，成员变量为一个容器对象，也就是自定义类型
当不显示编写构造函数时，编译器默认生成的构造函数对于自定义类型成员变量
会自动调用该自定义类型的默认构造函数，所以priority_queue不需要写构造函数
5.push
插入一个数据就向上调整一次，就可以保证始终为一个堆
6.pop
堆的删除不是直接将堆顶数据覆盖，那样会使的整个堆的结构就乱套了
堆的结构只保证关系父子之间的大小关系，并不保证兄弟和叔侄之间的关系
所以只需要将堆顶和堆尾的数据进行交换，再进行尾删，就可以将堆顶数据进行删除
然后再对新的堆顶进行向下调整，因为只变换了堆顶和队尾，并且已经删除原来堆顶的数据
此时除去堆顶，剩下的左右子树皆为堆，并且向下调整每次调整只会影响左右子树其中一颗
子树，所以使用先交换堆顶和堆尾数据，再进行尾删，再进行向下调整的效率高
7.priority_queue的push和pop表明适配器不仅仅只是像stack和queue简单的封装已有对象，
转换其接口名字就可以了，适配器是可以封装已有对象，在转换其接口中添加一些步骤和细节
来实现适配器接口
8.priority_queue其余接口的实现跟stack和queue的实现一致，只是转换被适配容器接口的名字
9.完整
四、仿函数的作用
1.相比普通函数，仿函数可以自带一些成员变量和成员函数
2.仿函数和函数指针都可以在函数内部进行回调
仿函数和函数指针都可以控制函数体内部的逻辑及其细节
函数指针的参数个数，参数类型，返回值类型都是写死的
使用仿函数时，是使用仿函数类的对象实现仿函数
那么只需要将仿函数类在模板参数位置写成泛型，就可以传任意类型的仿函数类
回调任意的仿函数，并且仿函数中参数的类型和参数的个数都不再形成干扰
但是函数指针是写死的，如果指针类型不同，就不能进行传参
所以在c++中回调函数最好使用仿函数
3.仿函数控制函数体内部的逻辑和细节
（1）此时有一个Date类重载了<和>
（2）当priority_queue中存储Date类型数据时，没问题，因为重载了> <
可以实现堆结构
（3）但如果此时存储的Date*，就有问题了，此时less和greater仿函数中比较的
是指针的大小，而不是Date的大小，因为申请空间时也是随机的也不知道是
谁大谁小
比较指针的大小本身就无意义啊 就像将指针强制类型转换为int一样无意义
存储指针是为了得到指针指向的数据，存储指针比较是为了比较指针指向的数据
而不是单纯的存储指针和比较指针，光看指针是无意义的
指针虽然是一串数字编号，但是指针表达的是该数据的地址，得到了指针是为了*
可以找到该地址位置的数据，而不是为了得到一串数字编号
（4）此时为了得到想要的结果，也就是存储Date的指针但是比较的时候是比较指针指向
的数据，那么就可以自定再定义一个仿函数，控制比较逻辑和比较细节
然后在实例化类时将仿函数类传递给模板参数
（5）假设此时priority_queue中存储的是string
string重载运算符< >，但是string的< >的比较逻辑和细节是按照ascii走的
此时如果想要根据字符串的长度来决定大小，该怎么做？
第一更改string的> <运算符重载函数，但是又不能动库中的东西
第二提供新的仿函数类，在仿函数类中转变比较逻辑和细节
4.综上，仿函数使得我们可以在不破坏类和函数内部的前提下，有更大的空间对
类和函数的逻辑和细节进行操作，灵活地扩展和定制类和函数的行为
5.仿函数特性：
（1）不破坏封装性
内部逻辑不变：使用仿函数时，原有的类或函数不需要暴露内部实现细节
无侵入式扩展：通过传递不同的仿函数对象，可以改变操作逻辑，无需更改原有代码
（2）灵活定制行为
仿函数可以携带状态（成员变量）
（3）operator()定义在类中，那么仿函数就会成为inline