别院深深夏席清，石榴开遍透帘明。
树阴满地日当午，梦觉流莺时一声。
目录
契子✨
deque （ double-ended queue ，双端队列）是有下标顺序容器，它允许在其首尾两段快速插入及删除。另外，在 deque 任一端插入或删除不会非法化指向其余元素的指针或引用。
deque 是一块连续的空间（至少逻辑看来如此），连续空间我们可能会想到 array（数组）或者vector。array 无法成长，vector 虽然可以成长但是只有尾端成长，而且扩容（成长）只是假象，实际上是：<1>另寻更大的空间、<2>将原资料拷贝过去、<3>释放原空间。这样的话 vector 成长所带来的代价是相当高的。
deque 的想象结构：就是相同的连续空间拼接而成
而 deque 巧妙的避开了 vector 的缺点，deque 的结构有一段一段的定量空间组成。一旦有必要在 deque 的前端或者尾端增加新空间，便配置一定量的连续空间，串在整个 deque 的头端或者尾端。deque 便是在这些分段的定量连续空间上，维序其连续的假象，并提供随机存取的界面。简单来讲就是 vector、list 的结合体，大小相同的连续空间串在一起。这样就避开了 vector 的【重新配置、拷贝、释放】的轮回。不过呢？有舍就有得，代价是迭代器的框架很复杂。
现在我们已经对 deque 有了一定的了解 ~ 接下来我们看看它的结构
deque 的结构
和 vector 容器采用连续的线性空间不同，deque 容器存储数据的空间是由一段一段等长的连续空间构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域。为了管理这些连续空间，deque 容器用数组 map （注意，不是 STL 的 map）存储着各个连续空间的首地址。也就是说，map 数组中存储的都是指针，指向那些真正用来存储数据的各个连续空间。我们称 map 数组为中控区，存储的空间位置为缓冲区。
这个时候我们的老铁可能就会问， 要是中控区的空间满了怎么办，我们知道 deque 是一块连续空间拼接而成的，一般情况下空间是足够的，并不会频繁扩容。如果 map 不够用了，我们这边需要找一块更大的空间来做我们的中控器 map，这个时候 map 就会有更多的节点空间来存储我们的缓冲区。
我们再来细致的了解一下中控器、缓冲区、迭代器之间的相互关系：
简单来讲我们的迭代器就是一块 4 个空间的节点，cur 指向缓冲区的数据元素，first 指向缓冲区的首地址，last 指向缓冲区的末地址，而 node 则指向在中控区的节点，那如果我们要访问 deque 内的数据该怎么办呢 ？
举个栗子 ~ 我想访问 12 位置的元素
首先我们先来分析一下：
这是一个空间大小为 8 的数组 Buff（通常用 Buff 来表示缓冲区的空间）
我们要找到是第几个 Buff 数组存放了 12 位置：i = pos/N（设 pos 是访问位置，N 是 Buff 空间的大小）所以 i = 12/8，即第二个 Buff 数组存放了该访问元素
然后我们要找到该元素在 Buff 空间的第几号位置：j = pos%N，j = 12%8，即该元素在 Buff 空间的第 4 号位置（Buff 空间从 0 开始）
deque 的迭代器剖析
deque 容器底层将序列中的元素分别存储到了不同段的连续空间中，因此要想实现迭代器的功能，必须先解决如下 2 个问题：
| 迭代器在遍历 deque 容器时，必须能够确认各个连续空间在 map 数组中的位置 |
| 迭代器在遍历某个具体的连续空间时，必须能够判断自己是否已经处于空间的边缘位置。如果是，则一旦前进或者后退，就需要跳跃到上一个或者下一个连续空间中 |
为了控制 deque 的迭代功能，deque 专门设置了以下的结构：
template <class T ,...,size_t BufSiz>
struct __deque_iterator
{
// ...
typedef T** map_pointer;
private:
T* cur;
T* first;
T* last;
map_pointer node;
};| cur | 指向迭代器当前在缓冲区遍历的元素 |
| first | 指向缓冲区的首节点 |
| last | 指向缓冲区的末节点 |
| node | 指向中控区的节点 |
借助这 4 个指针，deque 迭代器对各种运算符进行了重载、封装：
template <class T,..., size_t BufSiz>
struct __deque_iterator
{
//...
typedef __deque_iterator self;
typedef T** map_pointer;
typedef ptrdiff_t difference_type;
public:
inline size_t __deque_buf_size(size_t n, size_t sz)
{
return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
}
static size_t buffer_size()
{
return __deque_buf_size(0, sizeof(T));
}
void set_node(map_pointer new_node)
{
//记录新的空间在 map 中的位置
node = new_node;
first = *new_node;
//更新 last 指针，difference_type(buffer_size())表示每段连续空间的长度
last = first + difference_type(buffer_size());
}
T* operator*() const
{
return *cur;
}
T* operator->() const
{
return &(operator *());
}
self& operator++()
{
++cur;
if (cur == last)
{
//如果 cur 位于连续空间边缘，则先将迭代器跳跃到下一个连续空间中
set_node(node + 1);
cur = first;
}
return *this;
}
self& operator--()
{
if (cur == first)
{
//如果 cur 位于连续空间边缘，则先将迭代器跳跃到前一个连续空间中
set_node(node - 1);
cur == last;
}
--cur;
return *this;
}
T* operator[](difference_type n) const
{
return *(*this + n);
}
bool operator==(const self& x) const
{
return cur == x.cur;
}
bool operator!=(const self& x) const
{
return !(*this == x);
}
private:
T* cur;
T* first;
T* last;
map_pointer node;
};
关于我们 typedef 的 ptrdiff_t 具体是什么：不同机器下，他都有对应的类是为了适应不同平台下定义的
我们的迭代器就已经大致完成了 ~
这样就可以借助 start 和 finish，以及 deque 迭代器中重载的诸多运算符，就可以实现 deque 容器提供的大部分成员函数：
template <class T, size_t BufSiz = 0>
class deque
{
typedef __deque_iterator<T, ..., BufSiz> iterator;
typedef pointer* map_pointer;
public:
iterator begin()
{
return start;
}
iterator end()
{
return finish;
}
T* operator[](size_type n)
{
return start[difference_type(n)];
}
T* front()
{
return *start;
}
T* back()
{
iterator tmp = finish;
--tmp;
return *tmp;
}
size_t size() const
{
return finish - start;
}
bool empty() const
{
return finish == start;
}
protected:
iterator start;
iterator finish;
map_pointer map;
size_t map_size;
};
对了以上的代码都是伪代码，不能使用的哦 ~ 只是为了更好了解 deque 的结构
需要源码的老铁可以点击文章顶部的资源管理
接下来我们聊一聊使用：
deque 的使用
在讲使用之前，我们可以先来参考一下文档 deque 文档
deque 的初始化
deque<int> a; // 定义一个int类型的双端队列a
deque<int> a(10); // 定义一个int类型的双端队列a，并设置初始大小为10
deque<int> a(10, 1); // 定义一个int类型的双端队列a，并设置初始大小为10且初始值都为1
deque<int> b(a); // 定义并用双端队列a初始化双端队列b
deque<int> b(a.begin(), a.begin()+3); // 将双端队列a中从第0个到第2个(共3个)作为双端队列b的初始值
deque<int> b=a; // 定义一个int类型的双端队列b，并将双端队列a赋值给b
我们之前学过 vector、list 所以应该很容易理解以上的意义：
无参构造、链式构造、 拷贝构造、迭代器区间构造、赋值构造
这里就不一一讲解了
注意：除此之外，deque 还可以直接使用数组来初始化
int a[] = { 1,2,3,4,5 };
deque<int> str(a, a+5);我们简单来测试一下 ~
void deque_test()
{
int a[] = { 1,2,3,4,5 };
deque<int> str(a, a + 5);
while (!str.empty())
{
cout << str.front() << " ";
str.pop_front();
}
}
deque 的容量操作
| size() 计算容器大小 |
| max_size() 计算容器最大容量 （不经常用的接口函数） |
| resize() 预留容器的空间大小 |
| empey() 判断容器是否为空 |
deque 的访问操作
<1> 支持下标 [ ] 访问：越界报错
<2> 支持 at 访问：越界抛异常
<3> front：访问第一个元素
<4> back：访问最后一个元素
代码测试：
void deque_test() { deque<int> str = { 1,2,3,4,5 }; cout << str.front() << endl; cout << str.back() << endl; }
老铁们 ~ 我想开摆了（挑重点讲）：
在 pos 位置插入另一个向量的 [forst，last] 间的数据
注意：插入元素不一定要同一个容器，但是要同一种类型
代码测试：
void deque_test()
{
deque<int> str = { 1,2,3,4,5 };
vector<int> arr = { 7,8,9,10,11 };
str.insert(str.begin()+2, arr.begin(), arr.end());
while (!str.empty())
{
cout << str.front() << " ";
str.pop_front();
}
}
删除 [first，last] 之间的元素
代码测试：
void deque_test()
{
deque<int> str = { 1,2,3,4,5 };
str.erase(str.begin(), str.begin()+3);
while (!str.empty())
{
cout << str.front() << " ";
str.pop_front();
}
}
assign的用法
assign 简单来讲就是初始化，而且不仅支持迭代器区间初始化还支持用 n 个 val 初始化
代码测试
void deque_test()
{
deque<int> str;
str.assign(5, 0);
deque<int> arr;
arr.assign(str.begin(), str.end());
while (!arr.empty())
{
cout << arr.front() << " ";
arr.pop_front();
}
}
deque 的优缺点
我们先来看看 vector、list 的特点：
deque 的优势：
<1> 与 vector 比较：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是比 vector 高的
<2> 与 list 比较：其底层是连续空间，空间利用率比较高，不需要存储额外字段
deque的缺点：
deque 不适合遍历，因为在遍历时，deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而排序场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list。deque 的应用并不多，不适合大量的头部和中间插入删除，也不适合大量的随机访问。而目前能看到的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构。
使用场景：
（1）如果你需要高效的随即存取，而不在乎插入和删除的效率，使用 vector
（2）如果你需要大量的插入和删除，而不关心随机存取，则应使用 list
（3）如果你需要随机存取，而且关心两端数据的插入和删除，则应使用 deque
我们上次说起 stack、queue 空间适配器都有 duque 的影子，那么为什么 deque 会作为 stack 和 queue 的底层结构呢？
| stack 和 queue 不需要遍历(因此 stack 和 queue 没有迭代器)，只需要在固定的一端或者两端进行操作 |
| 在 stack 中元素增长时，deque 比 vector 的效率高(扩容时不需要搬移大量数据)，queue 中的元素增长时，使用 deque 作为底层默认容器，不仅效率高，而且内存使用率高 |
