前言
本文章主要介绍容器适配器的功能，以及一个适配的场景。
一、什么是容器适配器？
容器适配器，按字面意思理解的话，就是用来对一个容器进行匹配的。在C++STL中，容器有：vector，list，deque，map，set等。
而在C++STL中不把stack和queue纳入容器的范围而是纳入容器适配器的范围是因为：
stack和queue没有下标随机访问等操作，只有普通的pop_front,push_back,pop_back()等操作，而这些函数在其他容器中完全可以有，栈和队列的实现完全可以将其他容器的操作进行复用，这就是stack和queue作为容器适配器的原因。
至于为什么用deque（双端队列）作为stack和queue的默认适配容器，先看一看stack和queue的基本函数使用。
二、stack的基本函数和模拟实现
可以看到在stl库开放的栈的接口中，仅有寥寥无几的几个接口，主要为：push，pop，size，empty，top。
由于栈的后进先出的特性，
- 1.push是往栈顶进行push元素。
- 2.pop是删除栈顶元素。
- 3.size是计算当前的栈有多少元素
- 4.empty是判断栈是否为空
- 5.top是取栈顶元素
这几个函数完全可以复用其他容器的函数。
所以栈其实可以用vector，list等容器进行适配。
下面来模拟实现：
namespace dzt { template<class T, class container = deque<T> > class stack { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_back(); } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } T& top() { return _con.back(); } private: container _con; }; }
为了和库里面的stack不冲突，这里给了一个命名空间域dzt作为限定。
三、queue的基本函数和模拟实现
与stack类似，主要的函数有：
push，pop，front，back，size，empty。
由于队列先进先出的特性
- 1.push，向队列尾部插入元素
- 2.pop，删除队头元素
- 3.front，取队头元素
- 4.back，取队尾元素
- 5.size，计算当前队列的元素个数
- 6.empty，判断当前队列是否为空
下面来模拟实现queue
namespace dzt { template<class T, class container = deque<T> > class queue { public: void push(const T& x) { _con.insert(_con.end(),x); } void pop() { _con.erase(_con.begin()); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } //取队头 T& front() { return _con.front(); } //取队尾 T& back() { return _con.back(); } private: container _con; }; }
四、deque
4.1deque的底层结构
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组
deque的底层结构如下：
- 1.使用一个中控指针数组来存储各个位置的指针，而存储的位置一般只在数组的中间部分，大多数指针指向的内容都是一小块连续的空间，并且这些连续的空间的大小都是一样的。
- start(iterator)记录头部数据，finish(iterator)记录尾部数据，头尾的插入删除效率非常高，O(1)。
- cur记录指向的连续空间的第一个位置，first和last是该空间的区间，node反指回中控数组，方便找到下一个连续空间。
但是deque也有缺点，虽然它重载了[]访问，但是在访问中间元素时不够极致，需要进行计算。假设给定的下标为i，计算过程如下：
- 1.i如果在第一个数组的范围，直接访问
- 2.如果不在，i-=第一个数组的size
- i/buffersize = 第i个数组的位置
- 此时i指向了第i个数组，再用i/buffersize = 第i个位置的元素。
相比于vector，deque的下标访问的效率不够高，
相比于list，deque的中间位置插入删除效率不够高。
4.2使用deque适配stack和queue的原因
- deque作为栈和队列的容器适配器而不是用vector/list的优点：
- 1.deque的底层结构是使用中控指针数组来存储头和尾等各个空间的地址，对头尾的插入删除效率极高O(1)
- 2.栈就需要push_back()和pop_back(),队列需要支持pop_front()和push_back() ——— 战胜了vector
- 3.每一小块空间都是连续的，可以提高cpu高速缓存加载的效率。 ————战胜了list
- 4.stack和queue都不需要[]随机访问，而deque的缺陷就是下标随机访问的效率不够高
- 5.这样栈和队列的需求完美迎合了deque的优点，避开了deque的缺点
总结
本篇文章简单讲述了deque容器的底层原理以及相比于vector和list的缺点，还有用deque作为stack和queue的适配器的原因。
