std:: deque

std::deque （双端队列）是一种支持通过索引访问的序列容器，允许在其首尾两端快速进行插入和删除操作。此外，在双端队列任意一端进行插入或删除操作时，绝不会导致指向其余元素的指针或引用失效。

与 std::vector 不同，deque 的元素并非连续存储：典型实现使用一系列单独分配的固定大小数组，并附带额外的簿记信息。这意味着对 deque 进行索引访问需要执行两次指针解引用，而 vector 的索引访问只需执行一次。

deque的存储空间会根据需要自动扩展和收缩。deque的扩展比 std::vector 的扩展成本更低，因为它不需要将现有元素复制到新的内存位置。另一方面，deque通常具有较高的最小内存开销；一个仅包含单个元素的deque也必须分配其完整的内部数组（例如在64位libstdc++上为对象大小的8倍；在64位libc++上为对象大小的16倍或4096字节中的较大者）。

双端队列常见操作的时间复杂度（效率）如下：

• 随机访问 - 常数时间复杂度 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 元素的任何引用失效。

成员类型

成员函数

非成员函数

注释

示例

#include <deque>
#include <iostream>
int main()
{
    // 创建包含整数的双端队列
    std::deque<int> d = {7, 5, 16, 8};
    // 在双端队列的开头和末尾添加整数
    d.push_front(13);
    d.push_back(25);
    // 遍历并打印双端队列的值
    for (int n : d)
        std::cout << n << ' ';
    std::cout << '\n';
}

13 7 5 16 8 25

缺陷报告

以下行为变更缺陷报告被追溯应用于先前发布的C++标准。

参见