✨个人主页： 北 海
?所属专栏： C++修行之路
?每篇一句： 图片来源
文章目录
?前言?️正文1、适配器模式2、栈 stack2.1、常用接口学习2.2、模拟实现 3、队列 queue3.1、常用接口学习3.2、模拟实现 4、小结5、双端队列 deque（了解） ?总结
?前言
适配器（配接器）是 STL 中的六大组件之一，扮演着轴承、转换器的角色，使得 STL 中组件的使用更为灵活，比如 栈和队列 就是属于适配器而非容器，以及神秘的反向迭代器也属于适配器
具有多种功能的电源适配器，可以满足多种需求
?️正文
1、适配器模式
从应用角度出发，STL 中的适配器可以分为三类：
container adapters迭代器适配器 iterator adapters仿函数适配器 functor adapters 其中，容器适配器 可修改底层为指定容器，如由 vector 构成的栈、由 list 构成的队列；迭代器适配器可以 实现其他容器的反向迭代器（后续介绍）；最后的仿函数适配器就厉害了，几乎可以 无限制的创造出各种可能的表达式
本文介绍的是容器适配器，即 栈 和 队列，最后还会介绍一下常作为这两种容器适配器的默认底层容器 双端队列
出自 《STL源码剖析》
2、栈 stack
栈 stack 是一种特殊的数据结构，主要特点为 先进后出 FILO，主要操作有：入栈、出栈、查看栈顶元素、判断栈空等；栈在原则上是不允许进行中部或头部操作的，这样会破坏栈结构的完整性
栈在生活中比较少见，比较形象的例子是米缸，最先倒进去的米总是最后才能吃到，这正好契合了栈先进后出的思想
官方文档中 stack 的接口也是比较少的
可以看出，栈有两个模板参数
T 栈中的元素类型，同时也是底层容器中的元素类型参数2：Container 实现栈时用到的底层容器，这里为缺省参数，缺省结构为 双端队列 deque 如何优雅的创建一个栈对象？
#include <iostream>#include <stack>#include <vector>#include <list>using namespace std;int main(){stack<int> s;//默认底层容器为 dequestack<int, vector<int>> sv;//显示实例化底层容器为 vectorstack<char, list<char>> sl;//显示实例化底层容器为 listcout << typeid(s).name() << endl;//查看具体类型cout << typeid(sv).name() << endl;cout << typeid(sl).name() << endl;return 0;}
注意： 关于参数3 allocator 是空间配置器，这里先不作讲解，后续再学习
2.1、常用接口学习
学习使用接口时，直接使用默认的底层容器即可（不需要传递模板参数2）
因为接口少且非常简单，所以上手起来很方便
#include <iostream>#include <stack>using namespace std;int main(){stack<int> s;//构造一个栈对象cout << "Original:>" << endl;cout << "empty(): " << s.empty() << endl;cout << "size(): " << s.size() << endl;cout << endl << "Push:>" << endl;s.push(1);//入栈3个元素s.push(2);s.push(3);cout << "empty(): " << s.empty() << endl;cout << "size(): " << s.size() << endl;cout << "top(): " << s.top() << endl;cout << endl << "Pop:>" << endl;s.pop();//出栈两次s.pop();cout << "empty(): " << s.empty() << endl;cout << "size(): " << s.size() << endl;cout << "top(): " << s.top() << endl;return 0;}
栈的常用接口就这几个，多用几次就熟悉了
2.2、模拟实现
因为是容器适配器，所以在模拟实现时，需要借助其他容器，这里选择使用 vector
#pragma once#include <vector>using namespace std;namespace Yohifo{//这里选择模板参数2 底层容器 的缺省值为 vectortemplate<class T, class Container = vector<int>>class stack{public://需要提供一个带缺省参数的构造函数，因为默认构造函数不接受传参stack(const Container& c = Container()):_c(c){}//不需要显式的去写析构函数，默认生成的够用了//同理拷贝构造、赋值重载也不需要bool empty() const{return _c.empty();}size_t size() const{return _c.size();}//top 需要提供两种版本T& top(){return _c.back();}const T& top() const{return _c.back();}//选取的底层容器必须支持尾部操作void push(const T& val){_c.push_back(val);}void pop(){//空栈不能弹出，可在底层容器中检查出来_c.pop_back();}private:Container _c;//成员变量为具体的底层容器};}适配器的厉害之处就在于 只要底层容器有我需要的函数接口，那么我就可以为其适配出一个容器适配器，比如 vector 构成的栈、list 构成的栈、deque 构成的栈，甚至是 string 也能适配出一个栈，只要符合条件，都可以作为栈的底层容器，当然不同结构的效率不同，因此库中选用的是效率较高的 deque 作为默认底层容器
3、队列 queue
队列 queue 是另一种特殊的数据结构，遵循先进先出 FIFO，主要操作：入队、出队、判断队空、查看队头尾元素等
队列是一种生活中无处不见的场景，比如食堂打饭、柜台办理业务、排队出车站等等，所谓先来后到，形容的就是队列了
作为容器适配器，queue 官方提供的接口也是一样的少
和栈一样，队列也有两个模板参数：
T 队列中的元素类型，同时也是底层容器中的元素类型参数2：Container 实现队列时用到的底层容器，这里为缺省参数，缺省结构为 双端队列 deque 双端队列的优点在于高效的头尾操作和极致的空间使用，正好符合 栈和队列 的特殊需求
创建队列对象时，我们也可以指定其底层容器
#include <iostream>#include<queue>#include <vector>#include <list>using namespace std;int main(){queue<int> qDeque;//默认使用 dequequeue<double, vector<double>> qVector;//指定使用 vectorqueue<char, list<char>> qList;//指定使用 listcout << typeid(qDeque).name() << endl;//查看具体类型cout << typeid(qVector).name() << endl;cout << typeid(qList).name() << endl;return 0;}
3.1、常用接口学习
queue 中的接口与 stack 差不多，不过 queue 出元素时是在队头操作，同时它支持访问队头、队尾元素，而 stack 只能访问栈顶元素
#include <iostream>#include <queue>using namespace std;int main(){queue<int> q;//构建出一个队列对象cout << "Original:>" << endl;cout << "empty(): " << q.empty() << endl;cout << "size(): " << q.size() << endl;cout << endl << "Push:>" << endl;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);cout << "empty(): " << q.empty() << endl;cout << "size(): " << q.size() << endl;cout << "front(): " << q.front() << endl;cout << "back(): " << q.back() << endl;cout << endl << "Pop:>" << endl;q.pop();q.pop();q.pop();cout << "empty(): " << q.empty() << endl;cout << "size(): " << q.size() << endl;cout << "front(): " << q.front() << endl;cout << "back(): " << q.back() << endl;return 0;}
3.2、模拟实现
队列的模拟实现也是相当简单，这里选用 list 作为底层容器
#pragma once#include <list>using namespace std;namespace Yohifo{template<class T, class Container = list<T>>class queue{public:queue(const Container& c = Container()):_c(c){}//这里也不需要提供拷贝构造、赋值重载、析构函数bool empty() const{return _c.empty();}size_t size() const{return _c.size();}//选取的底层容器中，已经准备好了相关函数，如 front、backT& front(){return _c.front();}const T& front() const{return _c.front();}T& back(){return _c.back();}const T& back() const{return _c.back();}void push(const T& val){_c.push_back(val);//队列只能尾插}void pop(){_c.pop_front();//队列只能头删}private:Container _c;//成员变量为指定的底层容器对象};}队列和栈在进行适配时，都是在调用已有的接口，若是特殊接口，比如 top、push、pop 等，进行相应转换即可
top -> back 尾元素栈、队列 push -> push_back 尾插栈 pop -> pop_back 尾删队列 pop -> pop_front 头删 
4、小结
栈和队列在实际开发中作为一种辅助结构被经常使用，比如内存空间划分中的栈区，设计规则符合栈 FILO；操作系统中的各种队列，如阻塞队列，设计规则符合 队列 FIFO。除此以外，在很多 OJ 题中，都需要借助栈和队列进行解题
注：二叉树的最近公共祖先可以借助栈完成时间复杂度 O(N) 的解法
注意：
栈和队列都属于特殊的数据结构，原则上是不支持遍历的，因为一旦进行遍历，其中的数据必然被弹出，因此两者都没有提供迭代器假设容器没有提供头尾操作，比如map 和 set，那么就不能拿它们适配出 栈或队列，强行使用会报错 
5、双端队列 deque（了解）
双端队列是官方指定的底层容器，其结构上的特殊设计决定了它只适合于头尾操作需求高的场景：双端队列 = vector + list，设计时就想汲取二者的优点（下标随机访问 + 极致的空间使用），但鱼和熊掌不可兼得，在复杂结构的加持之下，双端队列趋于中庸，无法做到 vector 和 list 那样极致，因此实际中也很少使用，比较适合当作适配器的底层容器
双端队列的数据结构：list + vector
list 构造出一个 map 作为主控数组（通过链式结构链接），数组中元素为数组指针利用 vector 构造出大小为 N 的小数组（缓冲区），这些小数组才是双端队列存储元素的地方 注意： 此处的 map 并非是容器 map，仅仅是名字相同而已
将二者结合起来，就得到了复杂的双端队列
deque 的扩容机制：只需要对中控数组 map 进行扩容，再将原 map 中的数组指针拷贝过来即可，效率比较高
deque 中的随机访问：
(下标 - 前预留位) / 单个数组长度 获取对应小数组位置(下标 - 前预留位) % 单个数组长度 获取其在小数组中的对应下标 由此可见，单个数组大小（缓冲区大小）需要定长，否则访问时计算会比较麻烦，但长度定长后，会引发中间位置插入删除效率低的问题
对此 SGI 版的 STL 选择牺牲中间位置插入，提高下标随机访问速度，令小数组定长，这也是将它作为 栈和队列 默认底层容器的原因之一，因为 栈和队列 不需要对中间进行操作
因为中控数组是链式结构，因此双端队列的迭代器设计极为复杂
cur 指向当前需要的数据位置first 指向 buffer 数组起始位置last 指向 buffer 数组终止位置node 反向指向中控数组 
这个迭代器还是一个随机迭代器，因此可以使用 std::sort
deque 还是 list，直接排序的效率都不如借助 vector 间接排序效率高 deque 的缺点
vector 和 list 极致致命缺陷：不适合遍历，迭代器需要频繁检测是否移动某段小空间的边界，效率很低 凑巧的是，栈和队列 可以完美避开所有缺陷，全面汲取其优点，因此 双端队列 为容器适配器的默认底层容器
对于这种中庸且复杂的容器，只需要做简单了解就行了
?总结
以上就是本篇关于 C++ STL学习之【容器适配器】的全部内容了，在本文中，我们首先学习了适配器默认，了解它存在的意义及种类；其次学习和模拟实现了两种容器适配器 栈和队列；最后认识了容器适配器的默认底层容器 双端队列，见识了其复杂的结构设计及优缺点。关于适配的下一种形态：迭代器适配器 将在下文中学习，同时 反向迭代器 的神秘面纱也将被揭开
如果你觉得本文写的还不错的话，可以留下一个小小的赞?，你的支持是我分享的最大动力！
如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正
相关文章推荐
STL 之 list 类
C++ STL学习之【list的模拟实现】
C++ STL学习之【list的使用】
===============
STL 之 vector 类
C++ STL学习之【vector的模拟实现】
C++ STL学习之【vector的使用】
===============
STL 之 string 类
C++ STL学习之【string类的模拟实现】
C++ STL 学习之【string】
