容器适配器

💦 什么是适配器

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

💦 STL标准库中stack和queue的底层结构

虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为 stack 和队列只是对其他容器的接口进行了包装，STL 中 stack 和 queue 默认使用 deque，比如：

💦 deque的简单介绍(了解)

deque文档介绍

这里我们只是了解了解，想更深入可以去配合着源码看候捷老师的《STL源码剖析》。

1、deque的简单使用

void test_deque()
{
	deque<int> dq;
	dq.push_back(1);
	dq.push_back(2);
	
	dq.push_front(3);
	dq.push_front(4);

	//dq.insert();
	//dq.erase();	

	dq.pop_back();
	dq.pop_front()
		
	for(size_t i = 0; i < dq.size(); ++i)
	{
		cout << dq[i] << " ";	
	}
	cout << endl;
}

📝说明

通过以上操作我们可以看出 deque 融合了 vector and list 的优点，并且从使用的角度避开了 vector and list 各自的缺点。

• vector 的缺点是需要扩容，且头部和中间的插入删除。
• list 的缺点是 “ [ ] ”，它不支持任意位置的随机访问。

那就目前来看 deque 可以认为是最完美的线性表。那我们直接学 deque 就行了，还学啥 vector and list 呢 ？ 实际 deque 并没有崭露头角，想要了解从使用方面 deque 这么牛逼，却没有把 vector and list 替换掉，就需要了解 deque 的底层实现(这里我们也只是了解，不会模拟实现)。

2、deque的原理介绍

deque(双端队列)：但是记住，它与实际队列的先进先出的性质没有关联，也就是说 deque 并不要求先进先出。它是一种双开口的 " 连续 " 空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)，与 vector 比较，头插效率高，不需要搬移元素；与 list 比较，空间利用率比较高。

我们要继续分析 deque 就要先分析 vector and list，因为开发者肯定是从它们俩上受启发的。

1. vector 是连续的物理空间，它的优点是 a)尾插、尾删效率很高，最重要的是它支持随机访问 b)cpu高速缓存命中率很高。它的缺点是 a)空间不够，就需要增容，增容代价大，还存在一定的空间浪费。 b)头部和中间的插入删除是 O(N)，效率低。
2. list 是非连续的物理空间，它的优点是 a)按需申请释放空间。b)任意位置插入删除都是 O(1)，效率高。它的缺点是 a)不支持随机访问。b)cpu高速缓存命中率低。

可以看到 vector and list 的优缺点是互补的，vector 的优点大概就是 list 的缺点，vector 的缺点大概是 list 的优点，list 的优点大概就是 vector 的缺点，list 的缺点大概是 vector 的优点。

结合 vector and list 的优缺点，开发者就设计了 deque(但这似乎在很多场景下是一个相对比较无用的设计)。

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

deque 设计的真正复杂的是它的迭代器，这也是它的核心。我们碰到的迭代器要么是原生指针，要么是类封装的指针。而 deque 的迭代器封装了 4 个指针。
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其 “ 整体连续 ” 以及随机访问的假象，任务就落在了 deque 的迭代器身上，因此 deque 的迭代器设计就比较复杂，如下图所示：

📝说明：

1. 它的迭代器有 4 个指针，其中 first and last 分别指向一段 buff 的开始和结束，cur 指向当前迭代器所访问的位置，node 指向中控数组。
2. 遍历：begin() 给了第一个 buff 里面，*cur 就是第一个数据，++cur 就指向第二个数据，cur == last 时，第一个 buff 走完，随后 node = *node++，把 first and last 定位到下一个 buff 的对应位置，然后接着遍历即可。

以上内容在时间有富余的情况下可以在深挖。不过有人也遇到过相关面试题。

【面试题】

结合 vector and list 的优缺点，有没有什么改进的方案 ❓

这里呢，不要一上嘴就谈 deque 迭代器的 4 个指针啥的，你可以先不需要谈细节的实现。就谈可以实现固定数组的 buff，头插、尾插，再通过中控数组也就是指针数组来管理 buff，如果中控满了，扩容中控。在没有良好功底的情况下，面试官不问迭代器的实现就不谈，避免踩坑，因为往下会把这个问题扯的很深。

2、deque的缺陷及优点

咦，上面 deque 不是挺牛逼的吗 ？

deque 叫双端队列，说明它很适合头插头删，尾插尾删，也说明 deque 很适合 (比 vector and list 都适合) 去做 stack and queue 的默认适配容器，它尾插数据相比 vector 没有扩容，相比 list 它的缓存利用率很高。所以说 deque 最大的优点是做 stack and queue 的默认适配容器。

deque 的一大缺陷就是中间插入、删除，效率很低，比如要删除一个数据，这里有两种实现方案：

1. 可以头往前挪，可以尾往前挪，也可以哪一端少就挪哪一端，这又回到 vector 的问题了。
2. 只挪当前 buff 的数据，记录当前 buff 的 size(可以定义结构体，它里面放中控数组及 size)，少一个就缩容，多一个就增容，但它始终都要挪动数据。且当 buff 的大小不是固定后，“ [ ] ” 就不好计算了。

整体而言，第一种，中间插入删除的效率就和 vector 一样了，而 " [ ] " 的效率好歹高点；第二种，中间插入删除的效率变高了，而 " [ ] " 的效率变低了。所以对于 deque 中间插入删除操作类似于一碗水端不平的问题。大家可以去瞅下 SGI 版本的 deque 是怎么实现中间插入删除的。

deque 的另一个缺陷是不够极致， deque 是一种折中的方案设计。随机访问效率不及 vector，任意位置插入删除不及 list，它真正的优点是头尾插入删除。你可以理解 vector 是一面很锋利的刀，list 也是一面很锋利的刀，所以铁匠就设计铸造出一把两面都很锋利的刀，这就导致了两面都不够锋利，它是一种不够极致，折中的设计。所以严格来说 deque 是一个挺失败的设计。

使用场景 ❓

1. 数据排序，使用 vector。
2. 任意位置插入、删除，使用 list。
3. 头尾插入删除 (stack and queue) 用 deque。