deque=Double Ended Queues(双向队列)

deque和vector很相似，但是它允许在容器头部快速插入和删除（就像在尾部一样）。所耗费的时间复杂度也为常数阶O(1)。

并且更重要的一点是，deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。

C++ STL deque容器（详解版） (biancheng.net) 这个网站真的好好用啊~

deque的创建

    deque<int> dq1();   //创建一个空的双向队列 deque<int> dq2(10); //创建一个大小为10的双向队列,//其中每个元素都默认为0 deque<int> dq3(10,5);//创建一个包含10个5的双向队列 deque<int> dq4(dq2); //通过拷贝dq2创建一个新的deque容器//通过拷贝其他类型容器中指定区域内的元素，创建一个双向队列 array<int,5>arr{11,12,13,14,15}; //适用于所有类型的容器 deque<int> dq5(arr.begin()+2,arr.end());//拷贝arr容器中的{13，14，15} 

deque容器可利用的成员函数

基于 deque 双端队列的特点，该容器包含一些 array、vector 容器都没有的成员函数。

参考：C++ STL deque容器（详解版） (biancheng.net)

#include <iostream>
#include <deque>
using namespace std;
int main()
{//初始化一个空deque容量deque<int>d;//向d容器中的尾部依次添加 1，2,3d.push_back(1); //{1}d.push_back(2); //{1,2}d.push_back(3); //{1,2,3}//向d容器的头部添加 0 d.push_front(0); //{0,1,2,3}//调用 size() 成员函数输出该容器存储的字符个数。printf("元素个数为：%d\n", d.size());//使用迭代器遍历容器for (auto i = d.begin(); i < d.end(); i++) {cout << *i << " ";}cout << endl;return 0;
}

需要注意的是，在使用反向迭代器进行 ++ 或 -- 运算时，++ 指的是迭代器向左移动一位，-- 指的是迭代器向右移动一位，即这两个运算符的功能也“互换”了。

除此之外，当向 deque 容器添加元素时，deque 容器会申请更多的内存空间，同时其包含的所有元素可能会被复制或移动到新的内存地址（原来占用的内存会释放），这会导致之前创建的迭代器失效。

deque访问元素

和 array、vector 容器一样，可以采用普通数组访问存储元素的方式，访问 deque 容器中的元素，比如：

#include <iostream>
#include <deque>
using namespace std;
int main()
{deque<int>d{ 1,2,3,4 };cout << d[1] << endl;//修改指定下标位置处的元素d[1] = 5;cout << d[1] << endl;return 0;
}
输出 
2
5

可以看到，容器名[n]的这种方式，不仅可以访问容器中的元素，还可以对其进行修改。但需要注意的是，使用此方法需确保下标 n 的值不会超过容器中存储元素的个数，否则会发生越界访问的错误。

如果想有效地避免越界访问，可以使用 deque 模板类提供的 at() 成员函数，由于该函数会返回容器中指定位置处元素的引用形式，因此利用该函数的返回值，既可以访问指定位置处的元素，如果需要还可以对其进行修改。

不仅如此，at() 成员函数会自行判定访问位置是否越界，如果越界则抛出std::out_of_range异常。

例如：

#include <iostream>
#include <deque>
using namespace std;
int main()
{deque<int>d{ 1,2,3,4 };cout << d.at(1) << endl;d.at(1) = 5;cout << d.at(1) << endl;//下面这条语句会抛出 out_of_range 异常//cout << d.at(10) << endl;return 0;
}

除此之外，deque 容器还提供了 2 个成员函数，即 front() 和 back()，它们分别返回 vector 容器中第一个和最后一个元素的引用，通过利用它们的返回值，可以访问（甚至修改）容器中的首尾元素。

总结：deque访问、修改元素可以用d[1]和at（1）两种方式，不过使用at时越界会有提示。

注意，和 vector 容器不同，deque 容器没有提供 data() 成员函数，同时 deque 容器在存储元素时，也无法保证其会将元素存储在连续的内存空间中，因此尝试使用指针去访问 deque 容器中指定位置处的元素，是非常危险的。

可以实现遍历 deque 容器中指定区域元素的方法。例如：

#include <iostream>
#include <deque>
using namespace std;
int main()
{deque<int> d{ 1,2,3,4,5 };//从元素 2 开始遍历auto first = d.begin() + 1;//遍历至 5 结束（不包括 5）auto end = d.end() - 1;while (first < end) {cout << *first << " ";++first;}return 0;
}

deque容器添加、删除元素方法

C++ STL deque容器添加和删除元素方法完全攻略 (biancheng.net)

在实际应用中，常用 emplace()、emplace_front() 和 emplace_back() 分别代替 insert()、push_front() 和 push_back(）。

#include <deque>
#include <iostream>
using namespace std;
int main()
{deque<int>d;//调用push_back()向容器尾部添加数据。d.push_back(2); //{2}//调用pop_back()移除容器尾部的一个数据。d.pop_back(); //{}//调用push_front()向容器头部添加数据。d.push_front(2);//{2}//调用pop_front()移除容器头部的一个数据。d.pop_front();//{}//调用 emplace 系列函数，向容器中直接生成数据。d.emplace_back(2); //{2}d.emplace_front(3); //{3,2}//emplace() 需要 2 个参数，第一个为指定插入位置的迭代器，第二个是插入的值。d.emplace(d.begin() + 1, 4);//{3,4,2}for (auto i : d) {cout << i << " ";}//erase()可以接受一个迭代器表示要删除元素所在位置//也可以接受 2 个迭代器，表示要删除元素所在的区域。d.erase(d.begin());//{4,2}d.erase(d.begin(), d.end());//{}，等同于 d.clear()return 0;
}

insert函数的使用方法：

#include <iostream>
#include <deque>
#include <array>
using namespace std;
int main()
{std::deque<int> d{ 1,2 };//第一种格式用法d.insert(d.begin() + 1, 3);//{1,3,2}//第二种格式用法d.insert(d.end(), 2, 5);//{1,3,2,5,5}//第三种格式用法std::array<int, 3>test{ 7,8,9 };d.insert(d.end(), test.begin(), test.end());//{1,3,2,5,5,7,8,9}//第四种格式用法d.insert(d.end(), { 10,11 });//{1,3,2,5,5,7,8,9,10,11}for (int i = 0; i < d.size(); i++) {cout << d[i] << " ";}return 0;
}