【C++】容器适配器 + stack/queue/deque详解

上文链接

• 【 list 简介与模拟实现（详解）】

一、STL 中的 stack/queue

STL 中的 stack (栈) 与 vector、list 这些容器不太一样，它不是一种容器而是一种容器适配器。像 vector、list 这样的容器的底层是自己来管理自己的结构与数据，而栈并不是自己去管理自己的结构与数据，而是由其他的容器进行适配的。观察上图可以发现它的模板参数第二个值是一个容器，这也就意味着它是由另外的容器 (deque) 适配出来的。

同样的，queue (队列) 也是如此。

二、容器适配器

适配器是一种设计模式（设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码啊设计经验的总结），该模式是将一个类的接口转换成客户希望的另外一个接口。

我们在用电脑的时候可能会用到电源适配器，它可以将日常使用的 220V 的电压转换成为电脑需要的电压大小。而适配的本质其实就是一种转换。

比如，现在我想自己实现一个 stack，那么我们可以利用库中的 vector，用 vector 中的接口将其转换成为我们希望的 stack 的接口。

#include<vector>

namespace mine
{
	template<class T>
	class stack
	{
	public:
		void push(const T& x) { _con.push_back(x); }
		void pop() { _con.pop_back(); }
		T& top() { return _con.back(); }
		const T& top() const { return _con.back(); }
		bool empty() const { return _con.empty(); }

	private:
		std::vector<T> _con;  // 用 vector 的接口实现 stack
	};
}

当然，我们不止可以用 vector 实现一个顺序结构的栈，我们也可以实现一个链式结构的栈，比如我们可以用 list 来实现。

#include<list>

namespace mine
{
	template<class T>
	class stack
	{
	public:
		// ...

	private:
		std::list<T> _con;  // 用 list 的接口实现 stack
	};
}

可以看到我们有很多容器都可以转换成为一个栈，于是我们就可以将这个容器写在模板中作为一个参数 Container，与 STL 库中一致。

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

	private:
		Container _con;
	};
}

我们在使用时，只需要指定你想要利用的容器即可。

mine::stack<int, vector<int>> st;
mine::stack<int, list<int>> st;

上面的例子很好地展示了适配器这种模式的应用，queue 的模拟实现也是同理。但是注意 queue 最好不要用 vector 去实现。这是因为 queue 的出队操作是从队头出队，对应到 vector 中就是头删操作，而 vector 不像 list，它没有直接的 pop_front 接口，想要强行实现头删操作只能用 erase 函数，而 erase 函数进行头删是一个 $O(n)$ 的接口，效率很低，最好不要用。

我们还发现，STL 库中 stack 和 queue 的 Container 模板参数设置了一个默认参数 deque，熟悉数据结构的同学应该知道这是一种双端队列。当我们定义一个栈时不指定特定的容器时，就用这个 deque 去适配这个栈，如果显式地传入了一个容器时，那么就用传入的容器去适配。

三、deque

deque 名叫双端队列，虽然名叫队列，但是其实和队列没有什么太大的关系。它支持下边随机访问，支持 $O(1)$ 时间内的头插头删和尾插尾删操作，可以认为它是一个综合了 vector 和 list 优点的一种新容器。

1. vector 和 list 的对比

关于什么是高速缓存命中率，这里做个简单的讲解。

当 CPU 想要访问一个数据时，要看这个数据是否在缓存区域，在就叫缓存命中，不在就是不命中。如果数据不在缓存，那么就要先将数据从内存中加载到缓存，然后再访问缓存。而加载的过程需要读取数据，往往都是一段一段地读取，像 vector 这样的连续的空间，容易成片地被读取到然后加载到缓存中，因此缓存命中率较高；而像 list 这样的链式结构，物理空间上不连续，大概率只能一个数据一个数据地被读取到缓存中，因此缓存命中率相对较低。

2. deque 的诞生

可以看到 vector 和 list 的优缺点都是互补的，vector 有的 list 没有，而 list 有的 vector 没有。因此将二者折中一下就诞生了 deque 这样的容器。

deque 既不是 vector 这样的完全连续的空间，也不是 list 这样完全单个单个的空间，而是用一个一个的小数组 (buffer) 来存储数据。一个 buffer 数组存储满了之后又再开一个新的 buffer 数组来存储数据，buffer 数组本身不会去扩容。这一个一个的 buffer 数组则由一个中控数组来管理的。中控数组本质是一个指针数组，数组的内部存储的是每一个 buffer 数组的地址 (指针)，扩容时只需要扩这个中控数组即可。

由于扩容只需要扩这个中控数组，而它内部仅存储指针，所以扩容的成本较低。并且如果一个 buffer 数组的大小为 10，那么扩充 10 个中控数组的空间就等同于扩充了 10 个 buffer 数组，即 100 个空间。

3. deque 的迭代器

deque 的迭代器设计要比我们之前学习的 list 的迭代器复杂得多，list 的迭代器内部只封装了一个指针，而 deque 的迭代器内部封装了 4 个指针，分别是 cur、first、last、node。

• cur：指向当前要访问的位置。
• first：指向对应 buffer 数组的开始位置。
• last：指向对应 buffer 数组的结束位置。
• node：一个二级指针，指向中控数组中当前访问的 buffer 数组的地址。

下面是 deque 的底层结构示意图：

4. deque 的优缺点

为什么说 deque 不适合遍历呢？因为在遍历时，deque 的迭代器要频繁的去检测其是否移动到 buffer 数组的边界，导致效率低下。而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 或 list，deque 的应用并不多，而目前能看到的一个应用就是，STL 中用其作为 stack 和 queue 的底层数据结构。

5. 为什么选择 deque 作为 stack 和 queue 的底层默认容器

根据 stack 和 queue 的性质我们知道，stack 的底层容器可以选择 vector 或者 list，queue 的底层容器可以选择 list，那么为什么 STL 中要选择 deque 作为其底层容器呢？主要有以下两点：

1. stack 和 queue 不需要遍历 (因此 stack 和 queue 没有迭代器)，只需要在固定的一端或者两端进行操作。

2. 在 stack 中元素增长时，deque 比 vector 的效率高 (扩容时不需要搬移大量数据)；queue 中的元素增长时，deque 不仅效率高，而且内存使用率高。

四、stack/queue模拟实现（完整）

#include<deque>

namespace mine
{
	template<class T, class Container = std::deque<T>>
	// template<class T, class Container = std::vector<T>>
	// template<class T, class Container = std::list<T>>

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

#include<deque>

namespace mine
{
	template<class T, class Container = std::deque<T>>
	// template<class T, class Container = std::list<T>>

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