1 适配器
1.1 适配器的介绍
在C语言中，如果我们要实现栈和队列，就需要我们自己去手搓代码，并且实现底层利用的是顺序表还是链表也是有所不同的！在C++中还这样做，那你就慢了！在C++中我们学习了一些STL库中的容器，那么我们可不可以利用STL库中已经实现好的容器（vector，list，deque）呢？利用我们所学的模版，答案是可以的，所以像栈和队列这样的，并不需要自己去实现具体的函数，而是通过调用其他容器的函数而实现的，我们就称为适配器！事实上，适配器就是一种设计模式，它就是将一个类的接口转化成客户希望的另一个接口！
1.2 代码实现
我们首先来看看C++中对于栈的实现
#include <list> namespace demo { template<class T,class Container = list<T>> class stack { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_back(); } T& top() { return _con.top(); } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: Container _con; }; }
可以发现，我们只是调用list已经实现好的函数，就可以实现一个栈了！我们甚至可以将上面的容器换成vector，接下来我们在看一下C++库中是默认什么容器来实现的：
从图中我们可以发现：
1️⃣库里面是利用deque这个容器来实现栈的（队列其实也是）
2️⃣凡是一个容器，只要实现了以上5个红框中的函数，就可以实现栈！
1.3 总结
栈和队列的实现都是套用了其他容器中的函数而完成的，这里只是简单的介绍了栈，队列其实也是同理的！
2 仿函数
在了解完什么事适配器之后，我们在来实现一下priority_queue
namespace demo{ template<class T,class Container = deque<T>> class priority_queue { public: void adjust_up(size_t child) { //大根堆为例 size_t parent = (child - 1) / 2; while (child > 0) { if (_con[child]>_con[parent]) { swap(_con[parent], _con[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } void adjust_down(size_t parent) { size_t child = 2 * parent + 1; while (child<_con.size()) { if (child + 1 < _con.size() && _con[child + 1] > _con[child]) { child++; } if(_con[child]> _con[parent]) { swap(_con[child], _con[parent]); parent = child; child = 2 * parent + 1; } else { break; } } } bool empty() { return _con.empty(); } void push(const T& x) { _con.push_back(x); //堆向上调整 adjust_up(_con.size()-1); } size_t size() { return _con.size(); } void pop() { swap(_con[0], _con[_con.size()-1]); _con.pop_back(); //堆进行向下调整 adjust_down(0); } T& top() { return _con.front(); } private: Container _con; }; }
我们可以发现，这里只是实现了大根堆，那么我们如果要实现小根堆呢？我们还要亲自动手在改调整堆中的大于小于的符号吗？就不可以指定一个规则让它自己去比较大小呢，从而实现大根堆与小根堆之间的切换。库里面就是利用仿函数来实现的！在上面的代码中做出如下修改，并且多加入一个模版参数
我们可以发现。只需要改变第三个模版参数，使用less< T >就是小根堆，使用greater< T >就是大根堆，就可以改变你要建立的是大根堆还是小根堆！那么明白了以上的场景，那么什么又是仿函数呢？
1️⃣仿函数不是一个函数，是一个类，在类中重载实现了运算符（）
2️⃣我们是将该类的对象作为参数，传入到priority_queue中，从而调用（）函数
3 deque的原理（了解）
deque的底层就如上图所示：数据会存储在大小一样的数据块上，有一个map数组，记录每段数据块的首地址，有两个迭代器，迭代器中四个指针的作用分为别：
cur：指向当前正在遍历的元素；
first：指向当前连续空间的首地址；
last：指向当前连续空间的末尾地址；
node：它是一个二级指针，用于指向 map 数组中存储的指向当前连续空间的指针。
正是由于deque有这样的结构，所以对于两端的插入与删除的效率就显得非常的高效，所以库底层会选择用deque来作为栈和队列的作为默认容器来配置！但是对于删除数据，以及遍历数据还是不如list与vector，所以deque还是不可以取代我们之前学过的这两个容器！
