容器适配器
我们可以看出，栈中没有空间配置器（内存池），而是适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口
栈的实现
#include<vector> #include<iostream> using namespace std; namespace myspace { template<class T> class Stack { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_back(); } T& top() { return _con.back();//back接口访问尾部的数据 } T& top()const { return _con.back();//back接口访问尾部的数据 } bool empty() { return _con.empty(); } size_t size()const { return _con.size(); } private: vector<T> _con; }; }
此时这个栈并不是适配器，因为底层被写死了，底层是用vector实现的，如果想让它适配，加上适配器即可
此时就是适配器
list
注意队列不能用vector，编译会报错，因为不支持头删，没有pop_front
queque实现
namespace myspace { template<class T, class Container = deque<T>> class queue { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_front(); } T& back() { return _con.back(); } T& front() { return _con.front(); } const T& back() const { return _con.back(); } const T& front() const { return _con.front(); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; }; }
dequeque
我们发现栈和队列都有一个dequeque
dequeque不是队列，是vector和list的结合体
1.支持任意位置的插入删除
2.支持随机访问
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：
dequeque的缺陷
vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下（中间的插入删除效率很低），
而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构
测试之后，dequeque显然效率低
void test_op() { srand(time(0)); const int N = 100000; vector<int> v; v.reserve(N); deque<int> dp; for (int i = 0; i < N; ++i) { auto e = rand(); v.push_back(e); dp.push_back(e); } int begin1 = clock(); sort(v.begin(), v.end());
