Cstd::deque双端队列详解std::deque(Double-Ended Queue发音为 “deck”) 是 C 标准模板库 (STL) 中的一种序列式容器。它的核心特性是支持在容器的头部和尾部进行常数时间O(1)O(1)O(1)的插入和删除操作同时保留了类似数组的随机访问能力。与std::vector不同deque的内存布局是分段连续的由多个固定大小的缓冲区组成这使得它在头部扩展时无需像vector那样搬运所有数据但也导致了其遍历性能略低于vector。1. 核心接口速查表下表列出了std::deque最常用的成员函数。** 请特别注意“特殊返回值/行为”一列其中标明了空容器访问、异常抛出等关键细节。**分类函数签名功能描述时间复杂度特殊返回值 / 行为说明构造deque()默认构造空队列O(1)O(1)O(1)-deque(n, val)构造含 n 个 val 的队列O(n)O(n)O(n)-容量size()返回元素个数O(1)O(1)O(1)返回size_type(无符号整数)empty()判断是否为空O(1)O(1)O(1)返回bool空则 truemax_size()返回最大可容纳元素数O(1)O(1)O(1)理论上限通常受内存限制resize(n)调整大小为 nO(n)O(n)O(n)若 nsize()新元素默认初始化若 nsize()尾部被丢弃访问operator[]下标访问 (不检查边界)O(1)O(1)O(1)未定义行为 (UB)若下标越界不报错但程序可能崩溃at(n)下标访问 (检查边界)O(1)O(1)O(1)抛异常若下标越界抛出std::out_of_rangefront()返回首元素引用O(1)O(1)O(1)未定义行为 (UB)若在空容器上调用back()返回尾元素引用O(1)O(1)O(1)未定义行为 (UB)若在空容器上调用修改push_back(val)尾部插入元素O(1)∗O(1)*O(1)∗*均摊常数时间可能触发内存分配push_front(val)头部插入元素O(1)∗O(1)*O(1)∗*均摊常数时间vector 不支持此操作pop_back()删除尾部元素O(1)O(1)O(1)未定义行为 (UB)若在空容器上调用无返回值(void)pop_front()删除头部元素O(1)O(1)O(1)未定义行为 (UB)若在空容器上调用无返回值(void)insert(pos, val)在 pos 位置插入O(n)O(n)O(n)返回指向新元素的迭代器pos 可以是begin()到end()erase(pos)删除 pos 位置元素O(n)O(n)O(n)返回指向被删元素下一位置的迭代器迭代器失效clear()清空所有元素O(n)O(n)O(n)销毁所有元素size 变为 0swap(other)交换两个 deque 内容O(1)O(1)O(1)仅交换内部指针不复制元素注UB (Undefined Behavior)意味着代码不会报错但结果不可预测如返回垃圾值、段错误。调用front(),back(),pop_*()前务必检查!empty()。迭代器失效除了两端操作 (push/pop_front/back) 外在中间插入或删除会导致指向该位置及之后元素的迭代器失效。2. 接口简要介绍2.1 构造与容量构造deque支持默认构造、填充构造指定数量和初始值以及范围构造从其他容器复制。size()vsempty()虽然size() 0也能判断空但empty()语义更清晰且在某些实现中效率略高。resize()常用于预分配空间或截断数据。如果扩大新增部分会被值初始化基本类型为 0类类型调用默认构造函数。2.2 元素访问 (关键区别)operator[]最快但不安全。适用于循环遍历或确信下标合法的场景。at()安全但稍慢因为有边界检查。推荐在调试阶段或处理用户输入索引时使用它能通过抛出std::out_of_range异常帮你定位越界 bug。front()/back()直接引用首尾元素。切记在空 deque 上调用它们是 C 中最常见的崩溃原因之一。2.3 修改操作 (核心优势)双端插入/删除push_front和pop_front是deque区别于vector的最大特征。vector的insert(begin(), ...)是O(N)O(N)O(N)的而deque是O(1)O(1)O(1)。pop系列无返回值与stack适配器不同deque的pop_front()和pop_back()返回void。正确用法先获取值再弹出。if(!dq.empty()){intvaldq.front();// 1. 取值dq.pop_front();// 2. 删除}错误用法int val dq.pop_front();(编译错误)insert/erase虽然支持中间操作但效率较低 (O(N)O(N)O(N))因为需要移动元素。如果频繁在中间插删应考虑std::list。3. 代码示例#includeiostream#includedeque#includestdexceptintmain(){std::dequeintdq;// 1. 双端插入dq.push_back(10);dq.push_back(20);dq.push_front(5);// 现在: 5, 10, 20// 2. 安全访问 (at)try{std::coutElement at 0: dq.at(0)std::endl;// 输出 5// dq.at(10); // 如果取消注释会抛出 std::out_of_range}catch(conststd::out_of_rangee){std::cerrOut of range error: e.what()std::endl;}// 3. 不安全访问 ([]) - 必须确保不越界if(!dq.empty()){std::coutFront element: dq[0]std::endl;}// 4. 正确的 pop 用法if(!dq.empty()){intfirstdq.front();// 取值dq.pop_front();// 删除 (无返回值)std::coutPopped: first, New size: dq.size()std::endl;}// 5. 遍历for(intx:dq){std::coutx ;}std::coutstd::endl;return0;}