std::deque

std::deque （ double-ended queue ，双端队列）是有下标顺序容器，它允许在其首尾两段快速插入及删除。另外，在 deque 任一端插入或删除不会非法化指向其余元素的指针或引用。

与 std::vector 相反， deque 的元素不是相接存储的：典型实现用单独分配的固定大小数组的序列，外加额外的登记，这表示下标访问必须进行二次指针解引用，与之相比 vector 的下标访问只进行一次。

deque 的存储按需自动扩展及收缩。扩张 deque 比扩展 std::vector 便宜，因为它不涉及到复制既存元素到新内存位置。另一方面， deque 典型地拥有较大的最小内存开销；只保有一个元素的 deque 必须分配其整个内部数组（例如 64 位 libstdc++ 上为对象大小 8 倍； 64 位 libc++ 上为对象大小 16 倍或 4096 字节的较大者）。

deque 上常见操作的复杂度（效率）如下：

• 随机访问——常数 O(1)
• 在结尾或起始插入或移除元素——常数 O(1)
• 插入或移除元素——线性 O(n)

std::deque 满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、序列容器 (SequenceContainer) 和可逆容器 (ReversibleContainer) 的要求。

模板形参

迭代器非法化

此节有仍少量不准确处，更多细节请查看涉及单独成员函数的页面

非法化注意

• 从 deque 任一端插入时， insert 和 emplace 不会非法化引用。
• push_front 、 push_back 、 emplace_front 和 emplace_back 不会非法化任何到 deque 元素的引用。
• 从 deque 任一端擦除时， erase 、 pop_front 和 pop_back 不会非法化到未擦除元素的引用。
• 以较小的大小调用 resize 不会非法化任何到未擦除元素的引用。
• 以较大的大小调用 resize 不会非法化任何到 deque 元素的引用。

成员类型

成员函数

非成员函数

推导指引(C++17 起)

示例

#include <iostream>
#include <deque>
 
int main()
{
    // 创建容纳整数的 deque
    std::deque<int> d = {7, 5, 16, 8};
 
    // 从 deque 的首尾添加整数
    d.push_front(13);
    d.push_back(25);
 
    // 迭代并打印 deque 的值
    for(int n : d) {
        std::cout << n << '\n';
    }
}

13
7
5
16
8
25