【C++】 deque 双端队列详解

目录1. 什么是 deque2. 基本用法3. 常用方法4. 其他实用操作5. deque 与 vector 和 list 的对比6. deque 的底层逻辑 与 缺陷7. 性能对比8. 总结1. 什么是 dequedeque 是 C 标准模板库STL中提供的双端队列double-ended queue容器定义在deque头文件中。它支持在队列的两端高效地添加和删除元素时间复杂度均为 O(1)非常适合需要频繁在头部和尾部进行操作的场景。例如stack 和 queue 类中通常会把deque 用作默认适配器。2. 基本用法使用 deque 前需要先包含头文件#include deque #include iostream // 创建空的双端队列 std::dequeint d; // 创建带初始元素的双端队列 std::dequeint d2 {1, 2, 3, 4, 5};3. 常用方法deque 提供了丰富的操作方法下面通过示例逐一说明#include deque #include iostream int main() { std::dequeint d {1, 2, 3}; // 在尾部添加元素 d.push_back(4); // deque: 1 2 3 4 // 在头部添加元素 d.push_front(0); // deque: 0 1 2 3 4 // 从尾部弹出元素 d.pop_back(); // 移除 4deque: 0 1 2 3 // 从头部弹出元素 d.pop_front(); // 移除 0deque: 1 2 3 // 访问首尾元素 std::cout d.front(); // 输出 1 std::cout d.back(); // 输出 3 return 0; }4. 其他实用操作除了基本的增删操作deque 还支持以下常用功能#include deque #include iostream int main() { std::dequeint d {1, 2, 3, 4, 5}; // 随机访问 std::cout d[2]; // 输出 3 std::cout d.at(3); // 输出 4 // 获取大小 std::cout d.size(); // 输出 5 // 判断是否为空 std::cout d.empty(); // 输出 0false // 清空队列 d.clear(); // deque 变为空 // 迭代遍历 for (int x : d2) { std::cout x ; } return 0; }5. deque 与 vector 和 list 的对比注意只针对库给的函数dequevectorlistoperator[]√√×push_back()√√√pop_back()√√√push_front()√×√pop_front()√×√vector 想要实现实现头插头删是可但时间消耗上会都比较长list 想要实现随机访问也可用行以同样需要较长的时间消耗。deque 当然也不是最强的仍然有缺点。6. deque 的底层逻辑 与 缺陷deque 的存储方式 和 扩容方式deque 存储空间示意图 6.1deque 的扩容方式类似list 的扩容方式但是与 list 的不同deque 是一个数组一个数组的扩容方式的通常SGI STL deque 的 buffer 大小默认按 512 字节 尾插尾删的方式就与 vector 的都没有差别头插是申请新 buffer中控数组新增指针。关于 operator[]deque 和 vector 都支持operator[]随机访问可以通过下标直接获取元素例如d[2]返回第 3 个元素。与at()不同operator[]不做越界检查当下标超出范围时行为未定义因此使用时需要自行确保下标合法。list 由于底层是双向链表不支持operator[]只能通过迭代器或std::advance逐个移动访问时间复杂度为 O(n)。operator[] 缺陷deque 与 vector operator[] 随机访问还是有本质区别 vector 可以直接做到直接访问deque 需要进行计算利用除于取余计算出第几列几位时间上还是略微慢上一点。insert 缺陷deque 的insert在中间位置插入元素时性能较差。虽然两端操作是 O(1)但在中间插入需要移动插入点之后的所有元素时间复杂度为 O(n)。与 vector 相比deque 的中间插入虽然避免了整体搬移但仍需在多个连续存储块之间搬运元素且可能触发扩容因此并不适合频繁在中间插入的场景。若需要频繁在任意位置插入应优先考虑 list。补充deque 迭代器 iteratordeque_iterator 示意图 6.2deque 的迭代器属于随机访问迭代器random access iterator支持、--、n、-n、[]以及迭代器之间的比较运算因此可以像指针一样灵活地遍历和定位元素。与 vector 的迭代器不同deque 的迭代器内部封装了指向存储块的指针和块内偏移遍历时会在多个连续存储块之间跳转所以单次自增的开销略高于 vector但整体仍为 O(1)。下面通过示例演示 deque 迭代器的常见用法#include deque #include iostream int main() { std::dequeint d {1, 2, 3, 4, 5}; // 正向遍历 for (auto it d.begin(); it ! d.end(); it) { std::cout *it ; // 输出 1 2 3 4 5 } // 反向遍历 for (auto rit d.rbegin(); rit ! d.rend(); rit) { std::cout *rit ; // 输出 5 4 3 2 1 } // 随机访问跳转到第 3 个元素 auto it d.begin() 2; std::cout *it; // 输出 3 // 通过迭代器修改元素 *it 30; // d: 1 2 30 4 5 return 0; }需要注意的是deque 在头部或尾部插入删除元素时不会使已有迭代器失效但在中间位置插入或删除元素时会使所有迭代器失效这一点与 vector 类似。因此若需要在遍历过程中修改 deque应谨慎处理迭代器的失效问题。7. 性能对比下面从时间复杂度、内存布局和实际场景三个维度对比 deque、vector 和 list 的性能表现。7.1 时间复杂度对比操作dequevectorlist尾部插入/删除O(1)O(1)均摊O(1)头部插入/删除O(1)O(n)O(1)中间插入/删除O(n)O(n)O(1)随机访问O(1)O(1)最快性能最强O(n)7.2 内存与缓存性能vector 的元素在内存中连续存储缓存命中率最高遍历和随机访问速度最快。deque 采用分段连续存储缓存命中率略低于 vector但明显优于 list。list 的每个节点单独分配内存且节点间通过指针连接遍历时缓存命中率最低在大数据量下性能差距尤为明显。7.3 实际场景选择建议需要频繁头尾操作优先选择 deque两端操作均为 O(1)且内存利用率高于 list。需要频繁随机访问优先选择 vector连续内存带来更高的缓存命中率。需要频繁在任意位置插入删除优先选择 list前提是已持有目标位置的迭代器。需要头尾操作且偶尔随机访问deque 是折中方案兼顾两端操作效率和随机访问能力。总体而言deque 在头尾操作和随机访问之间取得了较好的平衡适合实现队列、双端队列等场景vector 适合以随机访问和尾部操作为主的场景list 则适合频繁在中间位置插入删除的场景。8. 总结deque 总体而言就是都没有 vector 和 list 两个类的优点都没有达到特别的明显如果作为默认类型适配器是最佳优解。deque 分段数组结构兼顾两端 O (1) 增删和随机访问 缺点随机访问慢于 vector中间插入删除性能差 迭代器是随机访问迭代器头尾操作不失效中间增删迭代器全部失效。 vector 胜在连续内存与随机访问list 擅长任意位置插入删除。