✨个人主页： 夜 默
🎉所属专栏： C++修行之路
🎊每篇一句： 图片来源

• A year from now you may wish you had started today.
  • 明年今日，你会希望此时此刻的自己已经开始行动了。

---

文章目录

• 🌇前言
• 🏙️正文
• • 1、适配器模式
  • 2、栈 stack
  • • 2.1、常用接口学习
    • 2.2、模拟实现
  • 3、队列 queue
  • • 3.1、常用接口学习
    • 3.2、模拟实现
  • 4、小结
  • 5、双端队列 deque（了解）
• 🌆总结

---

🌇前言

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

具有多种功能的电源适配器，可以满足多种需求

---

🏙️正文

1、适配器模式

从应用角度出发，STL 中的适配器可以分为三类：

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

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

本文介绍的是容器适配器，即 栈 和 队列，最后还会介绍一下常作为这两种容器适配器的默认底层容器 双端队列

出自 《STL源码剖析》

---

2、栈 stack

栈 stack 是一种特殊的数据结构，主要特点为 先进后出 FILO，主要操作有：入栈、出栈、查看栈顶元素、判断栈空等；栈在原则上是不允许进行中部或头部操作的，这样会破坏栈结构的完整性

栈在生活中比较少见，比较形象的例子是米缸，最先倒进去的米总是最后才能吃到，这正好契合了栈先进后出的思想

官方文档中 stack 的接口也是比较少的

可以看出，栈有两个模板参数

• 参数1：T 栈中的元素类型，同时也是底层容器中的元素类型
• 参数2：Container 实现栈时用到的底层容器，这里为缺省参数，缺省结构为 双端队列 deque

如何优雅的创建一个栈对象？

#include <iostream>
#include <stack>
#include <vector>
#include <list>

using namespace std;

int main()
{
	stack<int> s;	//默认底层容器为 deque

	stack<int, vector<int>> sv;	//显示实例化底层容器为 vector
	
	stack<char, list<char>> sl;	//显示实例化底层容器为 list

	cout << 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 底层容器 的缺省值为 vector
	template<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 官方提供的接口也是一样的少

和栈一样，队列也有两个模板参数：

• 参数1：T 队列中的元素类型，同时也是底层容器中的元素类型
• 参数2：Container 实现队列时用到的底层容器，这里为缺省参数，缺省结构为 双端队列 deque

双端队列的优点在于高效的头尾操作和极致的空间使用，正好符合 栈和队列 的特殊需求

创建队列对象时，我们也可以指定其底层容器

#include <iostream>
#include<queue>
#include <vector>
#include <list>

using namespace std;

int main()
{
	queue<int> qDeque;	//默认使用 deque
	queue<double, vector<double>> qVector;	//指定使用 vector
	queue<char, list<char>> qList;	//指定使用 list

	cout << 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、back
		T& 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 中的随机访问：

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

由此可见，单个数组大小（缓冲区大小）需要定长，否则访问时计算会比较麻烦，但长度定长后，会引发中间位置插入删除效率低的问题

对此 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】