deque：双端操作与稳定性的边界

能随机访问，不表示物理连续

deque 适合持续从一端加入、从另一端移除的工作队列，也能用下标常数时间访问中间元素。标准不要求元素连续，因此不能把 &d[0] 当作整个容器的数组首地址交给需要连续缓冲区的函数。需要这种接口时应选择 vector，或显式复制到连续存储。

常见实现使用多个数据块和块索引表，解释了它为何能兼顾双端增长与随机访问；块大小、索引表布局和内存开销并非标准承诺。deque 没有 vector 那样的 capacity() 或 reserve() 接口，不能通过预留一个总容量来推导其迭代器稳定性。

两端便宜，中间仍有移动成本

标准对两端插入单个元素给出常数时间复杂度；一般位置插入的复杂度与插入元素数，加上到较近一端的距离成线性关系。中间删除同样可能移动前缀或后缀。这里的复杂度不是实时系统中的延迟上限，底层分配仍可能有不可忽略的实际耗时。

若主要工作是两端推进，deque 能避免 vector 反复删除首元素的线性搬移；若主要是紧凑扫描，vector 常有更好的局部性。二者的选择应由访问模式和地址需求决定，而不是看到一个常数复杂度便断言它总是更快。

分别判断元素引用、迭代器与 end

两端插入不使已有元素的引用和指针失效，但会使全部迭代器失效；中间插入则连已有引用也失效。这个区别来自标准接口保证，不能用“地址没变”推导旧迭代器仍可递增、比较或解引用。示例跨越尾插只保存元素指针，随后重新获取迭代器。

删除最后元素会使旧尾后迭代器及被删元素句柄失效；仅删除首元素而不删除末元素，只使被删元素句柄失效；删除既不含首元素也不含末元素的中间范围，会使全部迭代器和引用失效。空队列不能调用 front、back 或 pop；先检查 empty，并避免在变化的队列上缓存 end。

最低标准 C++11 · 完整程序 · 下载 .cpp

#include <cassert>
#include <deque>
#include <iostream>

int main() {
    std::deque<int> jobs{10, 20, 30};
    int* middle = &jobs[1];
    jobs.push_front(5);
    jobs.push_back(40);
    assert(*middle == 20 && middle == &jobs[2]);

    auto keep = jobs.begin() + 2;
    jobs.pop_front();
    assert(*keep == 20);
    assert(keep == jobs.begin() + 1);
    jobs.pop_back();
    assert(*keep == 20);
    assert((jobs == std::deque<int>{10, 20, 30}));
    std::cout << jobs.front() << ' ' << *keep << ' ' << jobs.back() << '\n';
}

在本地编译

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread stl-deque.cpp -o example && ./example

预期结果

10 20 30

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

非空 deque 保存了指向首元素的 int* p 和迭代器 it，随后 push_back 一个元素。哪些句柄还能访问原首元素？如何修复遍历代码？

继续查证

• 标准草案 [deque.modifiers]：位置相关的失效与复杂度

标准草案链接会随工作草案更新；本文版本标记对应示例最低要求，不表示草案中的所有新规则都适用于旧标准。