文章目录
- 前言
- 一、适配器模式
- 概念
- 分类
- 二、Stack
- 核心作用
- 代码实现
- 三、Queue
- 核心作用
- 代码实现
- 四、deque双端队列
- 貌似兼收并蓄？
- 实则也难以兼得~
- 总结
前言
适配器也是STL六大组件之一，请跟我一起领悟它的智慧！
正文开始！
一、适配器模式
概念
适配器（配接器）是 STL 中的六大组件之一，扮演着轴承、转换器的角色，使得 STL 中组件的使用更为灵活，比如 栈和队列 就是属于适配器而非容器，以及神秘的反向迭代器也属于适配器
有点像这个
分类
我们可以把适配器分为以下三种：
容器适配器 container adapters
迭代器适配器 iterator adapters
仿函数适配器 functor adapters
容器适配器可修改底层指定容器，如由 vector 构成的栈、由 list 构成的队列；迭代器适配器可以实现其他容器的反向迭代器（后续介绍）；最后的仿函数适配器就厉害了，几乎可以无限制的创造出各种可能的表达式
出自侯捷老师的《STL源码剖析》
二、Stack
核心作用
栈Stack其实是老熟人了，只是这里以另一种视角再次审视它一下
Stack特点是元素特定容器的尾部(即是栈顶)被压入和弹出
我们可以看到Stack的核心接口有：
- empty：判空操作
- size：获取元素个数操作
- back：获取尾部元素操作
- push_back：尾部插入元素操作
- 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的核心接口有：
- empty:检测队列是否为空
- size:返回队列中有效元素的个数
- front:返回队头元素的引用
- back:返回队尾元素的引用
- push_back:返回队尾元素的引用
- 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是如何借助其迭代器维护其假想连续的结构呢
实现下标随机访问的原理
- (下标 - 前预留位) / 单个数组长度 获取对应小数组位置
- (下标 - 前预留位) % 单个数组长度 获取其在小数组中的对应下标
不适合遍历，因为在遍历时，deque的迭代器需要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而且在序列场景中，可能需要经常遍历。因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目能看到的一个应用就是，STL用其作为stack和queue的底层数据结构，某种程度上，deque还真的蛮适合的
总结
感觉如何，是不是被STL的魅力所折服了呢！
