$deque$ 知识点整理总结

往期内容： STL总目录-超详细

时隔......整整三个月呢，我们再回来看一看STL的另一个容器——$deque$.
$deque$的内部结构极其复杂，本人也只是略懂一二，以下内容仅供参考和初步了解，如有错误请指正
($Ps$:$deque$是$queue$和$vector$的升级或者说是特殊版本，所以看本篇分享前希望能尽可能掌握$queue$的基本知识 -> 传送门(queue) & 传送门(vector) )

目录

• 简介
• 成员函数
• 运用实例演示

$Deque$

与他的好兄弟$queue$和$vector$相同的，他也是STL中的一个容器，中文名为“双端队列”（或者也称为双尾队列），不要以为他的英文大名名是$deque$，这其实是他的小名简称，他的全称是“double-ended queue”。
容器$deque$（发音为“deck”）和vector很相似，因为他也是具有动态大小的序列容器，可以在两端（前端或后端）扩展或收缩。

所以我们不妨把这个神奇的$deque$看成$queue$和$vector$的孩子结合体：一个可以从两侧拓展的$queue$，一个可以从两端扩展的$vector$
而且$deque$随然名字与$queue$更加相似，但实际更像是$vector$
因此后面我们会对$deque$和$vector$进行大量对比

关于$deque$的优势：

这里贴上一段官方的文档：

Both vectors and deques provide a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors use a single array that needs to be occasionally reallocated for growth, the elements of a deque can be scattered in different chunks of storage, with the container keeping the necessary information internally to provide direct access to any of its elements in constant time and with a uniform sequential interface (through iterators). Therefore, deques are a little more complex internally than vectors, but this allows them to grow more efficiently under certain circumstances, especially with very long sequences, where reallocations become more expensive.

大家可以选择翻译软件，为了尽可能的不误导大家，我这里不加上谷歌的翻译了，那我用我自己的话来表述一下：
deque没有所谓的容器概念，因为它是动态地以分段连续空间组合而成（如下图）随时可以增加一块新的内存空间并拼接起来，因此deque可以运行常数时间对头端或尾端进行元素的插入和删除操作，并且这允许它们在某些情况下更有效地增长，特别是对于非常长的序列。
并且$deque$的内存重分配优于$vector$，$deque$还会释放不再使用的内存区块。

关于$deque$的劣势

对于涉及在开头或结尾以外的位置频繁插入或删除元素的操作，与list相比，双端队列的性能更差:

访问元素时$deque$内部结构会多一个间接过程，所以元素的访问和迭代器的动作会稍稍慢一些
同时$deque$不支持对容量和内存重新分配时的控制，特别要注意的是，除了头尾两端，在任何地点安插或删除元素都将导致指向$deque$元素的任何$pointer$，$reference$，$iterator$失效。

迭代器和引用的一致性也更低

迭代器需要在不同区块间跳转，所以必须是一个smart pointer，不能是寻常pointer。

我们该在什么时候使用$deque$？

• 当你需要在两端安插和移除元素（deque的拿手好戏）
• 无需指向（refer）容器内的元素
• 要求 不再使用的元素必须释放

（$Ps$:由于$vector$和$deque$的接口几乎一样，所以如果你不需要什么特殊性质，两者都可以试一试，而且我个人更加建议$vector$）

$deque$的成员函数

fist of all，$deque$作为一个STL容器，当然也有自己的头文件

#include <deque>

接着，我们正式来看$deque$常用的函数

构造函数

常用的构造方式共有3种

1.构造一个空的$deque$，其中没有任何元素

deque<Type> deq;
// NULL

2.构造一个$deque$，其中有n个元素（默认为0）

deque<Type> deq(5);
// 0 0 0 0 0

3.构造一个$deque$，其中有n个元素（值均为m）

deque<Type> deq(5, 1);
// 1 1 1 1 1

析构函数

deque<Type> deq;
deq.~deque();

销毁所有元素并释放内存

非更易型操作

.empty()

一如既往的，作为STL中的容器，$deque$依然能够通过.empty()函数来返回是否容器为空
（相当于size() == 0但也许较快）

.size()

依然是老朋友了，不多赘述，只是用来返回存入元素的个数。

.front() && .back()

既然与队列能扯上关系，那队列的函数我们也拿来用
同队列，用于返回第一元素/最末元素

以上两个函数.front()及.back()在执行时不会检查是否存在第一元素/最末元素

.begin() && .end()

与前两个函数不同的，这两个函数返回的不再是一个值，而是一个迭代器(iterator)

更易型操作

swap()

功能如其名，即置换deq1和deq2的数据，共有两种用法
1.

deq1.swap(deq2);

2.

swap(deq1, deq2);

.push_back() && .pop_back && .push_front() && .pop_front()

同队列，只不过是一个双端的罢了，所以大概不需要细说了吧（雾）

.insert()

相比前面的插入函数，.insert()需要的太多了，这是一个在迭代器位置插入元素的函数，如果你并没有迭代器，就用不了它
也就是说，这样写是错的：

//错误示范：
deq.insert(num);

正解：

deque<Type>::iterator it = deq.end();
deq.insert(it, num);

.erase()

与.insert()相对的就是.erase()了，同样，.erase()也是一个依赖迭代器的函数，他的功能是将传入位置的值删除

deque<Type>::iterator it = deq.end();
deq.erase(it);

.clear()

最后一个就是.clear()了，一如既往，它的功能是删除deque中的所有元素，将整个容器清空

deque.clear();

应用实例演示

#include <iostream>
#include <string>
#include <deque> //头文件不能少

using namespace std;

deque<string> deq;//这里用一个string类型的deque来做演示，初始为空
deque<string>::iterator it; //提前准备一个迭代器，写法一如既往 

int main() {

    //我们先来传入几个数据
    deq.push_back("last string");
    deq.push_front("front string");

    for (it = deq.begin(); it != deq.end(); it++) {
        cout << *it << endl;
    } //遍历及输出元素 

    cout << endl;

    //再用insert试试
    it = deq.begin();
    it++;
    deq.insert(it, "middle"); 

    for (it = deq.begin(); it != deq.end(); it++) {
        cout << *it << endl;
    } //遍历及输出元素

    cout << endl;

    //删除一下
    it = deq.begin();
    it++;
    deq.erase(it);

    for (it = deq.begin(); it != deq.end(); it++) {
        cout << *it << endl;
    } //遍历及输出元素  

    cout << endl;

    //清空deque
    deq.clear();
    cout << deq.size() << endl;

    cout << endl;

    //析构
    deq.~deque(); 
    return 0;
}

程序输出如下：

front string
last string

front string
middle
last string

front string
last string

0

好啦，deque就介绍到这里吧，托更了挺久的，开学还挺忙的，最主要还是懒
可能较为粗糙，有任何问题希望大佬们指正，我会尽量完善
另外最近新一轮疫情挺严重的，我也被封在学校里了，大家一定要注意安全啊~

拜拜ヾ(•ω•`)o