通过栈/队列/优先级队列/了解容器适配器，仿函数和反向迭代器

vector和list我们称为容器，而stack和queue却被称为容器适配器。

这和它们第二个模板参数有关系，可以看到stack和queue的第二个模板参数的缺省值都是deque，即双端队列容器。也就是说栈和队列都是以容器为主材料构建的，而且因为第二个参数是一个缺省值，我们不但可以使用deque构建，同样可以使用vector和list来构建。

用已经存在的容器来封装转换成不存在的容器，这种方式就被称之为适配器模式。

有了deque提供的接口，再要实现栈和队列就会变得很简单。

一.stack

栈的特点就是后进先出，，插入和删除都是在尾部进行，栈不提供迭代器（因为栈只能访问栈顶的元素）。

#include<deque>
namespace wbm
{template <class T, class Container = deque<T>>class stack{public:bool empty()const{return _con.empty();}void push(const T&x){_con.push_back(x);}void pop(){_con.pop_back();}size_t size()const{return _con.size();}const T& top()const{return _con.back();}private:Container _con;};}

栈不但可以通过deque来封装，还可以通过vector和list来封装，只要支持尾插尾删即可

二.queue

队列的特点是先进先出，队尾入，队头出，可以访问队头和队尾的数据，也不提供迭代器

#include<deque>namespace wbm
{template<class T,class Container=deque<T>>class queue{public:bool empty()const{return _con.empty();}void push(const T& x){_con.push_back();}void pop(){_con.pop_front();}size_t size()const{return _con.size();}const T& fornt()const{return _con.front();}const T& back()const{return _con.back();}private:Container _con;};
}

只要是支持尾插头删的容器都可以做queue的适配器，但是不建议使用数组，因为数组的头删效率太低

三.deque（双端队列）

因为vector和list都各有优缺点，因此大佬们就想是否可以创造一个容器兼具vector和list的优点又避免缺点，于是便有了双端队列deque，虽然deque的名字带着队列，但是它和队列毫无关系。

观察它提供的接口发现：它既支持随机访问，又支持头插头删和尾插尾删，看起来似乎确实是一个完美的容器。但如果真的那么完美，vector和list岂不是早就被淘汰了。

其实deque的底层是一个指针数组+多个buffer数组（buffer数组的大小是固定的）的组成形式；这个指针数组是一个中控数组，其中存放的元素是属于这个deque的buffer数组的地址。

第一次插入数据开辟的buffer数组的地址存放在中控数组的中间元素，如果buffer数组满了要继续尾插，则继续开辟新的buffer数组，此时第二个buffer数组的地址，存放在中控数组中间元素的下一个。如果你要头插，则开辟一个新的buffer数组，并将这个buffer数组的地址存放在中间元素的前一个。

deque的优点：

1.扩容代价小于vector：它只有在中控满了以后才需要扩容，并且不需要拷贝原生数据，只要将中控数组与buffer之间的映射关系拷贝下来即可。

2.因为是一段一段的空间，所以CPU高速缓存命中率高于list。

3.头尾插入删除效率都较高，并且支持随机访问

但是deque也有自己的缺点:

1.随机访问效率不如vector，它的随机访问要通过计算得到，假设每个buffer数组的大小为size，你要访问第10个元素，首先要10/size来确定这个元素在哪一个buffer数组中，再用10%size来确定这个元素在这个buffer数组中的哪个位置，所以deque也不适合排序，因为排序需要大量的随机访问。

2.中间插入删除不如list，它在中间插入删删同样需要挪动一定量的数据

3.迭代器实现复杂：它的迭代器中有四个指针，当cur==last时，说明本段空间被使用完毕++node继续去访问下一段空间，并更新first和last

---

四.优先级队列

优先级队列的特点就是优先级高的先出，它也是一个容器适配器，不提供迭代器，底层是一个堆并且默认是大堆。

priority_queue<int> //小堆
priority_queue<int,vector<int>,greater<int>> //大堆

优先级队列中的仿函数

仿函数是一个函数对象，它是一个类函数的对象，要达到类函数，所以这个类中必须要重载()。优先级队列中默认是大堆，如果我们要改成小堆，除了要显示传递第三个参数以外还要更改比较大小的算法。在C语言中，为了能让qsort排序任意类型，库中使用了函数指针的办法，让使用者显示的去写一个比较函数，并将该函数的地址作为参数传递过去。仿函数的一个应用场景就类似于函数指针。

namespace wbm
{template<class T>struct less //可以使用struct，也可以使用class，它们都是类，只是默认的访问限定不同{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;}};
}
int main()
{wbm::less<int> func;//两者等价：func(1, 2)==func.operator()(1, 2);return 0;
}

手搓优先级队列

#include<vector>
#include<iostream>
namespace wbm
{template<class T>struct less //可以使用struct，也可以使用class，它们都是类，只是默认的访问限定不同{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 =std:: vector<T>,class Compare = less<T>>class priority_queue{private:void Adjustdown(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;//默认是less，也就是左孩子比右孩子小}//将孩子节点和父节点做比较if (com(_con[parent], _con[child])) {std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void Adjustup(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}public:priority_queue(){//要有一个默认构造，不写就会报错}//迭代器区间构造,直接构造出一个堆，使用向下调整更佳template<class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last)  //初始化列表，vector支持迭代器区间构造{//初始化建堆，使用向下调整，从第一个非叶子节点开始for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){Adjustdown(i);}}void push(const T& x){_con.push_back(x);Adjustup(_con.size() - 1);}void pop(){//将首元素和末尾元素换位置删除后调整std::swap(_con.front(), _con.back());_con.pop_back();Adjustdown(0);}bool empty()const{return _con.empty();}size_t size()const{return _con.size();}const T& top()const{return _con.front();}private:Container _con;};
}

如果优先级队列中存放的是某个类的地址，又需要我们比较地址中值的优先级，那就需要使用仿函数来进行特殊处理。否则只会按照地址来比较。

五.反向迭代器

反向迭代器采用的是适配器模式，是通过正向迭代器的再封装实现的，你给它某个容器的正向迭代器，它就产生这个容器的反向迭代器，它与正向迭代器的位置是对称的并且正好相反。所以要控制反向迭代器，只需要使用运算符重载，篡改方向迭代器中++和--的规则就可以。

reverse_iterator rbegin(){return reverse_iterator(end());}
reverse_iterator rend(){return reverse_iterator(begin());}

rbegin和end一样，指向的是最后一个元素的下一个位置，要想访问到3，要先--再访问，这个问题可以通过重载*来解决

template<class Iterator,class Ref,class Ptr>
Ref operator*()
{Iterator tmp=it;return *(--tmp);
}

手搓反向迭代器

namespace wbm
{//反向迭代器，使用正向迭代器封装template<class Iterator,class Ref,class Ptr>  //迭代器,T&/const T&,T*/const T*class ReverseIterator{typedef ReverseIterator<Iterator, Ref, Ptr> Self;public:ReverseIterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp;return *(--tmp);}Ptr operator->(){return &(operator*())}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Ref& rit)const//两个迭代器之间的比较{return _it != rit;}private:Iterator _it;//这里给的参数是一个正向迭代器};
}