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++标准。

另请参阅