C++ STL 中Deque 与 Vector 对比

Deque在C++标准模板库（STL）中

双端队列是一种序列容器，既能从两端扩展和收缩，也能在两端插入和删除第一个元素。

它们类似于向量，但支持以O(1)的时间复杂度插入和删除第一个元素。与向量不同的是，它们不能保证连续存储分配。

双端队列基本上是数据结构双端队列的一个实现。队列数据结构只允许从尾部插入和从头部删除。这就像现实生活中的队列，人们会从前面删除，从后面添加。双端队列是队列的一种特殊情况，其中插入和删除操作在两端都可以执行。

双端队列的函数与向量相同，并增加了对前后两端的push和pop操作。

向量在C++ STL中

向量与动态数组相同，能够在元素插入或删除时自动调整大小，它们的存储由容器自动处理。向量元素放置在连续存储中，因此可以使用迭代器访问和遍历。在向量中，数据插入到末尾。在末尾插入需要不同的时间，因为有时候可能需要扩展数组。删除最后一个元素只需要常数时间，因为没有调整大小。在开头或中间插入和删除是线性的。

Deque和Vector的区别：

向量	双端队列
提供中间和末尾的插入和删除方法	提供开始、中间和末尾的插入和删除方法
在开头插入和删除的性能不佳	在开头插入和删除具有良好的性能
存储元素连续	它包含存储元素连续的内存块列表
在末尾添加和删除元素的性能良好	在末尾添加和删除元素的性能良好
在C++中，存储在`<vector>`头文件中	在C++中，存储在`<deque>`头文件中
在前面或中间插入的时间复杂度为O(N)	在前面和末尾插入的时间复杂度为O(1)
删除的时间复杂度为O(N)	删除的时间复杂度为O(1)