---

前言

  适配器也是STL六大组件之一，请跟我一起领悟它的智慧！
  正文开始！

---

一、适配器模式

概念

  适配器（配接器）是 STL 中的六大组件之一，扮演着轴承、转换器的角色，使得 STL 中组件的使用更为灵活，比如 栈和队列 就是属于适配器而非容器，以及神秘的反向迭代器也属于适配器

有点像这个

分类

  我们可以把适配器分为以下三种：

 容器适配器 container adapters
 迭代器适配器 iterator adapters
 仿函数适配器 functor adapters

  容器适配器可修改底层指定容器，如由 vector 构成的栈、由 list 构成的队列；迭代器适配器可以实现其他容器的反向迭代器（后续介绍）；最后的仿函数适配器就厉害了，几乎可以无限制的创造出各种可能的表达式

出自侯捷老师的《STL源码剖析》

二、Stack

核心作用

  栈Stack其实是老熟人了，只是这里以另一种视角再次审视它一下

Stack特点是元素特定容器的尾部(即是栈顶)被压入和弹出

我们可以看到Stack的核心接口有：

1. empty：判空操作
2. size：获取元素个数操作
3. back：获取尾部元素操作
4. push_back：尾部插入元素操作
5. pop_back：尾部删除元素操作

并且我们再看第二个模板参数 Container 表示实现栈时用到的底层容器，这里为缺省参数，缺省结构为 双端队列 deque< T >

代码实现

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

只要底层容器有我需要的函数接口，那么我就可以为其适配出一个容器适配器

三、Queue

核心作用

也是老熟人

Queue的最大特点是元素从队尾入队列，从队头出队列

我们可以看到Queue的核心接口有：

1. empty:检测队列是否为空
2. size:返回队列中有效元素的个数
3. front:返回队头元素的引用
4. back:返回队尾元素的引用
5. push_back:返回队尾元素的引用
6. pop_front:在队列头部出队列

并且我们看到第二个模板参数也为 deque< T >

代码实现

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

栈和队列都属于特殊的数据结构，原则上是不支持遍历的，因为一旦进行遍历，其中的数据必然被弹出，因此两者都没有提供迭代器

四、deque双端队列

貌似兼收并蓄？

  我们一看，它好像可以下标访问，也可以进行头部的插入和删除，功能很全面

  我们先要明确，deque(双端队列):是一种双开可口得"连续"空间数据结构

双开口的含义是:可以在头尾两端进行插入和删除操作，且时间复杂度O（1），与vector比较，头插效率高，不需要搬移元素，在扩容时，也不需要搬运大量的数据；与list比较，空间利用率比较高，不需要存储额外的字段

实则也难以兼得~

马跟驴生下了骡子，有一定的意义，但并不是说骡子完全在继承马跟驴的优点的基础上，完全规避了两者的缺点

  但是deque并不是真的连续的空间，而是由一段连续的小空间拼接而成的，实际上deque类似于一个动态的二维数组，其底层结构如下

  双端队列底层是一段假象的连续空间，实际是**分段且连续（一个buffer连续，几个buffer分段）**的，为了维护其"整体连续"以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计比较复杂

  那deque是如何借助其迭代器维护其假想连续的结构呢

实现下标随机访问的原理

1. (下标 - 前预留位) / 单个数组长度 获取对应小数组位置
2. (下标 - 前预留位) % 单个数组长度 获取其在小数组中的对应下标

  不适合遍历，因为在遍历时，deque的迭代器需要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而且在序列场景中，可能需要经常遍历。因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目能看到的一个应用就是，STL用其作为stack和queue的底层数据结构，某种程度上，deque还真的蛮适合的

---

总结

  感觉如何，是不是被STL的魅力所折服了呢！