c++ deque 的使用

 

目录

1. deque 的介绍

2. deque 底层原理

3. deque 的迭代器 

4. deque 的接口使用 

5. deque 和 vector，list 的比较

---

1. deque 的介绍

下面是 deque 的介绍，来自于：deque - C++ Reference (cplusplus.com)  的翻译，您可以不用看，我稍后会对 deque 的一种实现做讲解，以便您能更好的理解 deque 。deque 在编程中并不如 vector 和 list 使用得频繁。模拟实现 deque，这是意义不大的行为。

1：deque（通常读作 "deck"）是双端队列的不规则缩写。双端队列是具有动态大小的序列容器，可以在两端（前端或后端）扩展或收缩。

2：特定的库可能会以不同的方式实现 deque，通常是作为某种形式的动态数组。但无论如何，它们都允许通过随机访问迭代器直接访问单个元素，并根据需要通过扩展和收缩容器自动处理存储。

因此，它们提供了与 vector 类似的功能，但也能在序列的开头（而不仅仅是结尾）有效地插入和删除元素。但与 vector 不同的是，deque 不能保证将所有元素都存储在连续的存储位置：通过偏移指向另一个元素的指针来访问 deque 中的元素会导致未定义的行为。

3：vector 和 deque 提供了非常相似的接口，可用于类似的目的，但两者内部的工作方式却截然不同： vector 使用的是单个数组，偶尔需要重新分配以适应增长；而 deque 的元素可以分散在不同的存储块中，容器内部保存必要的信息，可以在恒定时间内直接访问其中的任何元素，并提供统一的顺序接口（通过迭代器）。

因此，deque 的内部结构要比 vector 复杂一些，但在某些情况下，deque 可以更高效地增长，尤其是在处理超长序列时，重新分配的代价会更高。

4：与 list 和 forward_list 相比，对于频繁插入或移除位于开头或结尾以外位置的元素的操作，deques 的性能更差，迭代器和引用的一致性也更差。

2. deque 底层原理

deque 中文名，双端队列。但并不是一个队列，因为队列要求先进先出，而 deque 可以头插，头删，尾插，尾删，不符合队列的特征！

下面将会讲解 deque 的底层原理：

1：deque 维护了若干个 buff 数组，用于存储数据。除此之外，deque 还维护了一个中控数组 (指针数组)，数组中的元素指向 deque 维护的 buff 数组。

2：中控数组的使用时从中间开始，当中控数组满了之后会直接扩容，然后释放原来的空间。

3：头插，头删数据。

下图中橙色的部分表示已经右数据啦！下面演示依次头插数据：1，2。

 头删数据就是删除 2 啦，如果再次头删，就是删除 1 啦！

4. 尾插，尾删数据。

下图中橙色的部分表示已经右数据啦！下面演示依次尾插数据：1，2。

 依次尾删数据：先删除 2 再删除 1。

5：deque 是支持下标随机访问的，在这看似不连续的空间上，是如何做到的呢？

关键就是每个 buff 的大小必须一样！下面我们来看看是如何做到下标随机访问的！

橙色部分代表有数据。

1)：我们要访问下标为 i 的位置，首先要判断他在不在第一个 buff 里面，如果在第一个 buff 里面，那么就可以通过这个 buff 的指针直接访问了。

2)：如果下标为 i 的位置不在第一个 buff 里面，那就让 i -= 第一个 buff 数据的个数。然后通过数学运算：

i /= buff.size()

i %= buff.size()

找到下标为 i 的元素在第几个 buff 数组，在这个 buff 数组的第几个位置。

然后通过中控数组，找到这个 buff 访问对应位置上的数据即可。

插入，删除，operator[] 的逻辑倒是讲通了！但是具体怎么实现的呢！deque 的迭代器发挥了至关重要的作用。

3. deque 的迭代器 

deque 的迭代器封转了四个指针：

1：cur：指向一个 buff 中的某个位置，表示该位置的迭代器。

2：first：指向一个 buff 数组的第一个位置，是第一个位置，不是第一个有效元素。

3：last：指向一个 buff 数组的最后一个位置的下一个位置，不是最后一个有效元素的下一个位置。

4：node：指向 buff 在中控数组的位置。

我们来看 deque 是如何通过迭代器遍历元素的：

我们观察 deque 的源代码，发现在 deque 的实现是维护了两个迭代器的，start，finish。分别表示deque 中 front (deque 的第一个元素) 位置对应的迭代器，和 back (deque 的最后一个元素) 位置对应的迭代器。

1：初始化 deque 的迭代器 it = begin()，begin() 就是 start 。

2：it++，这里的加加实际上是让迭代器封装的四个指针指针中的 cur++。

如果 it++ 之后不等于 last，那么直接加加即可。

如果 it++ 之后等于 last，那么我们需要通过 node 找到当前的 buff 数组在中控数组中的位置，让 node++，指向下一个 buff 数组。同时修改 first 和 last 的值，让 cur 指向新的 first。

3：与 end() 的比较，就是当前迭代器的 cur指针 和 deque 内部维护的迭代器 finish 的 cur指针 比较就行啦！

按照上述过程就能实现迭代器遍历整个 deque 。

4. deque 的接口使用 

deque 的接口也是很简单哇！STL 库中的代码风格都差不多，经常使用的接口我在代码中已经贴出来了！

#include
#include
using namespace std;
 
int main()
{
	deque<int> d;
 
	d.push_back(5);
	d.push_back(6);
	d.push_back(7);
	d.push_back(8);
 
	//输出：5 6 7 8
	for (auto e : d)
		cout << e << " ";
	cout << endl;
 
 
	d.push_front(4);
	d.push_front(3);
	d.push_front(2);
	d.push_front(1);
 
 
	//输出：1 2 3 4 5 6 7 8
	for (auto e : d)
		cout << e << " ";
	cout << endl;
 
	d.pop_front();
	d.pop_back();
 
	//输出：2 3 4 5 6 7
	for (int i = 0; i < d.size(); i++)
		cout << d[i] << " ";
	cout << endl;
 
 
	cout << d.size() << endl; //输出：6
 
	cout << d.front() << endl; //输出：2
 
	cout << d.back() << endl; //输出：7
 
	cout << d.empty() << endl; //输出：0
 
 
	return 0;
}

5. deque 和 vector，list 的比较

deque 被发明出来，本来不仅想解决 vector 头插，头删，扩容拷贝数据带来的效率问题的，还想解决 list 频繁申请释放节点，cpu 高速缓存效率低的问题的！但发现 deque 谁都代替不了。

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不 需要搬移大量的元素，因此其效率是必vector高的。

与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

但是，deque有致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构 时，大多数情况下优先考虑 vector 和 list。

还有一个问题就是：deque 想要在中间插入删除，那可老麻烦了，正是因为 每个 buff 数组 的大小相同，才使得 operator[] 比较高效，因此，deque 的插入删除是不能改变 buff 数组的大小的。这不就理了个大谱了嘛。

最后的问题就是：deque 的 operator[] 需要通过计算，在 频繁使用 operator[] 的时候，效率也会变低。

deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack 和 queue 的底层数据结构。

好啦，我们模拟实现 stack 和 queue 的时候再见！