前言std::dequedouble-ended queue双端队列是 STL 序列容器家族里最容易被「顺带一提」的一个 大多数教程讲完vector和list只用一句话带过它。但它是std::stack和std::queue的默认底层容器也是「先进先出队列」这个数据结构的直接实现 值得单独讲清楚。初学者对deque有两个常见误解「deque就是vector加了个push_front」——不对。deque的内存模型和vector完全不同元素的存储不连续因此没有data()成员也不能把首元素地址当数组用。「deque和vector一样扩容时会把旧元素搬走」——不对。deque的「扩容」只是增加一块新的存储块已有元素不会因为两端插入而搬家 这正是它「两端插入后引用仍然有效」的底气。本文按内存模型、常用操作、迭代器失效规则、选型对比四条线来讲。 代码按C17标准编写目标编译器为 GCC 13 / Clang 17 / MSVC 19.3x。一、deque 的内存模型分段连续vector用一整块连续内存存放所有元素list用一堆互不相邻的结点deque走的是中间路线——分段连续元素被分成若干条固定大小的连续块chunk / block另外有一个映射数组通常叫 map每个槽位是一个指向块的指针逻辑上的下标i先算出落在第几个块、块内第几个元素再通过 map 跳过去。块的大小是实现定义的标准不作规定libstdcGCC 使用的标准库实现在bits/stl_deque.h里的__deque_buf_size给出sizeof(T) 512时一块放512 / sizeof(T)个元素 否则一块只放 1 个元素。也就是说它大致按 512 字节来切块。MSVC STL与libc各自使用自己的启发式块内元素个数同样是实现细节标准没有任何要求。由此可以推出几条硬结论元素不保证连续。d[0]只是一个元素的地址d[0] 1未必指向d[1]大多时候确实指向但跨块时就越界了。所以绝对不要把d[0]传给需要连续内存的 C 接口 memcpy、fwrite、strlen之类把d.size()当数组长度传出去是典型的 UB 来源。deque没有data()成员函数。这一点和vector、array、string都不同。随机访问仍然是 O(1)只是比vector多一次间接寻址先查 map 再取块内偏移。迭代器比裸指针重。vector的迭代器在多数实现里就是指针deque的迭代器通常要保存当前指针、块首、块尾等多个字段这也是遍历deque通常比遍历vector稍慢的原因之一——不是慢在算法而是慢在每次解引用的额外计算上。二、常用成员函数与基本用法#include deque #include iostream #include string int main() { std::dequestd::string history; history.push_back(打开文件); // 尾部追加 history.push_back(编辑文本); history.push_front(启动程序); // 头部插入 std::cout history.front() \n; // 启动程序 std::cout history.back() \n; // 编辑文本 std::cout history.size() \n; // 3 history.pop_front(); // 丢掉最早的一条记录 for (const std::string s : history) { std::cout s \n; // 打开文件 / 编辑文本 } return 0; }主要接口一览T指元素类型成员函数作用复杂度push_back/pop_back尾部插入 / 删除均摊常数push_front/pop_front头部插入 / 删除均摊常数emplace_back/emplace_front原地构造省一次拷贝或移动均摊常数front/back首 / 尾元素的引用常数operator[]/at随机访问at越界抛std::out_of_range常数begin/end/rbegin/rend迭代器属于随机访问迭代器常数size/empty元素个数 / 是否为空常数insert/emplace中间插入线性erase删除单元素或区间线性assign用新内容整体替换线性resize改变元素个数多出来的按值初始化线性clear清空全部元素线性swap交换两个容器常数shrink_to_fit请求释放未使用的块非强制实现定义没有的成员reserve、capacity、data。这三者都是vector专有的概念deque的内存是按块管理的没有「容量」这个统一指标。还要注意at与operator[]的区别operator[]不做边界检查越界是UB 标准不保证任何行为at会做检查并抛std::out_of_range。同样 在空的deque上调用front()、back()、pop_front()、pop_back()都是 UB。三、迭代器失效规则这是deque最容易记混的地方。记忆的入口是deque的元素不搬家所以引用往往能活下来 但迭代器还要记住「块」的位置块一变就可能失效。标准对插入的表述语义如下操作迭代器引用/指针在两端插入push_front/push_back/emplace_front等全部失效仍然有效在中间插入insert、emplace全部失效全部失效删除首元素且不同时删除尾元素只有被删元素的迭代器失效只有被删元素的引用失效删除尾元素且不同时删除首元素只有被删元素和end()失效只有被删元素的引用失效中间erase首尾都没删到全部失效含end()全部失效clear()全部失效全部失效swap指向元素的迭代器仍有效end()可能失效仍然有效一句话总结成口诀「两端插——引用活、迭代器死中间插——全死」。看个例子#include deque #include iostream int main() { std::dequeint d{1, 2, 3}; int r d[1]; // 引用下标 1 的元素值为 2 d.push_front(0); // 两端插入迭代器全失效但 r 仍然有效标准保证 std::cout r \n; // 2 —— 合法不是 UB // 此时 d 的内容是 {0, 1, 2, 3}但下面这行不能写 // auto it d.begin(); // 插入前拿到的任何迭代器都已经失效再用是 UB std::dequeint e{1, 2, 3, 4, 5}; e.insert(e.begin() 2, 99); // 中间插入所有迭代器与引用全部失效 std::cout e.size() \n; // 6 return 0; }对照vector记会更清楚vector在扩容时会把元素整体搬到新内存 连引用都会失效deque的两端插入不会搬元素所以引用安然无恙。 这个差异在「用一个引用长期持有队列尾部元素」的场景里非常实用。四、与 vector、list 的对比与选型维度vectordequelist内存布局一整块连续分段连续块 map双向链表结点分散随机访问O(1)最快O(1)多一次间接寻址不支持只能线性走迭代器类别随机访问随机访问双向头部插入删除O(n)要整体搬移均摊 O(1)O(1)尾部插入删除均摊 O(1)均摊 O(1)O(1)中间插入删除O(n)O(n)O(1)已定位时两端插入后引用是否有效可能失效扩容时有效不适用每个元素的额外开销无少量块内未用空间 map两个指针通常 16 字节能否std::sort能能随机访问迭代器不能要用list::sortdata()成员有无无典型用途顺序遍历、需要连续内存、栈两端进出的队列、工作窃取队列中间频繁插删、稳定引用选型经验只是先进先出FIFO的队列或者需要频繁头部插入选deque。std::queue默认就用deque做底层容器正是这个原因。需要std::sort或者需要把数据整块交给 C 接口选vector。deque虽然支持std::sort但元素不连续意味着每次访问都要多算一次块偏移 缓存局部性也差一些具体差距请在你自己的数据上实测不要照搬任何结论。需要在中间频繁插删、且要求「插入不影响已有元素的地址」选list。常见坑点场景❌ 错误写法✅ 正确写法传给 C 接口fwrite(d[0], sizeof(int), d.size(), fp);元素不连续越界 UB先std::vectorint v(d.begin(), d.end());再传v.data()取连续内存d.data()deque没有这个成员编译错误没有等价写法改用vector预留空间d.reserve(100);不存在编译错误没有对应概念deque的两端插入本身就是均摊常数中间插删后继续使用之前保存的迭代器或引用重新获取迭代器或改成「只在两端操作」空容器操作空deque上调front()/back()/pop_front()UB先if (!d.empty())判断越界访问d[d.size()]依赖「反正只是垃圾值」UB用d.at(i)获得异常或先检查下标bool 特化以为std::dequebool也像std::vectorbool那样按位压缩vectorbool才是特化dequebool是普通容器滑动窗口每轮都用d.erase(d.begin())做窗口左移是 O(n)不是 O(1)窗口左移用pop_front()均摊 O(1)排序假设认为deque上没有std::sortstd::sort(d.begin(), d.end())可以编译随机访问迭代器但性能受内存布局影响最后再强调两个「反直觉」的点std::dequebool没有特化。只有std::vectorbool是位压缩的特化版本这也是为什么vectorbool的operator[]返回一个代理对象而不是bool。dequebool老老实实一个bool存一个元素d[0]返回的是真正的bool。deque的迭代器不是指针。写模板代码时不要假设Container::iterator能隐式转成T*那只有vector在多数实现上成立。总结问题结论元素连续吗不连续是「块 映射数组」的分段结构块大小实现定义libstdc 大致按 512 字节切块MSVC STL / libc 各有启发式两端插入快吗均摊 O(1)且不搬移已有元素引用保持有效迭代器会失效吗两端插入 → 迭代器全失效、引用有效中间插删 → 全失效有data()/reserve()吗都没有什么时候用它需要两端进出的队列、先进先出、需要稳定引用时只要记住「分段连续」这四个字deque的绝大多数行为都能推导出来 因为分段所以没有data()、迭代器不是指针、访问要多一次间接寻址 因为分段而不是整块所以两端插入不搬家、引用能活下来。 把这个模型记住比背那张失效规则表更管用。