STL deque 的详细特征
- 基本特性
#include<deque>usingnamespacestd;deque<int>dq;// 声明一个int类型的双端队列· 双端队列：允许在两端进行高效插入和删除
· 动态数组：支持随机访问，可以像数组一样通过下标访问
· 内存结构：分段连续存储，由多个固定大小的内存块组成
- 内存结构与实现原理
内部结构示意图
deque内存布局： [块1] → [块2] → [块3] → [块4] → [块5] ↓ ↓ ↓ ↓ ↓ [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] ↑front ↑back 每个块：固定大小（通常是512字节或容纳元素的内存对齐大小） 维护一个中央控制器（map）：存储各个块的指针关键特征
// 1. 分块存储// deque将元素存储在多个固定大小的内存块中// 当需要扩容时，分配新的内存块，而不是重新分配整个数组// 2. 随机访问复杂度 O(1)deque<int>dq={1,2,3,4,5};cout<<dq[2];// O(1) 访问// 3. 两端操作复杂度 O(1)dq.push_front(0);// O(1)dq.push_back(6);// O(1)dq.pop_front();// O(1)dq.pop_back();// O(1)- 时间复杂度分析
操作 时间复杂度 说明
push_front() O(1) 平均分摊
push_back() O(1) 平均分摊
pop_front() O(1) 平均分摊
pop_back() O(1) 平均分摊
operator[] O(1) 随机访问
insert() O(n) 中间插入
erase() O(n) 中间删除
front()/back() O(1) 访问首尾
- 与 vector/list 的对比
性能对比
#include<deque>#include<vector>#include<list>#include<iostream>voidbenchmark(){// 1. 前端插入 - deque 最优deque<int>dq;vector<int>vec;list<int>lst;// push_front 测试for(inti=0;i<100000;++i){dq.push_front(i);// 快：O(1)lst.push_front(i);// 快：O(1)vec.insert(vec.begin(),i);// 慢：O(n)}}详细对比表
特性 deque vector list
内存布局 分段连续 连续 不连续
随机访问 O(1) O(1) O(n)
前端插入 O(1) O(n) O(1)
后端插入 O(1) 分摊O(1) O(1)
中间插入 O(n) O(n) O(1)
内存开销 中等 低 高
缓存友好 中等 高 低
迭代器类型 随机访问 随机访问 双向
- 迭代器特征
迭代器特性
deque<int>dq={1,2,3,4,5};// 1. 随机访问迭代器autoit=dq.begin();it+=3;// 支持随机访问cout<<*it;// 输出4// 2. 迭代器失效规则dq.push_front(0);// 所有迭代器失效！dq.push_back(6);// 所有迭代器失效！// 3. 插入/删除中间元素it=dq.begin()+2;dq.insert(it,99);// it失效迭代器失效情况
操作 迭代器失效情况
push_front() 所有迭代器失效
push_back() 所有迭代器失效
pop_front() 指向被删元素的迭代器失效
pop_back() 指向被删元素的迭代器失效
insert() 所有迭代器失效
erase() 被删位置之后的迭代器失效
resize() 所有迭代器失效
- 常用操作示例
基本操作
#include<deque>#include<iostream>#include<algorithm>voidbasic_operations(){deque<int>dq;// 1. 两端插入dq.push_back(10);// 后: 10dq.push_front(5);// 前: 5, 后: 10 → 5,10dq.emplace_back(15);// C++11: 5,10,15dq.emplace_front(0);// C++11: 0,5,10,15// 2. 访问元素cout<<"第一个元素: "<<dq.front()<<endl;// 0cout<<"最后一个元素: "<<dq.back()<<endl;// 15cout<<"第三个元素: "<<dq[2]<<endl;// 10cout<<"大小: "<<dq.size()<<endl;// 4// 3. 删除元素dq.pop_front();// 移除0 → 5,10,15dq.pop_back();// 移除15 → 5,10// 4. 中间操作dq.insert(dq.begin()+1,7);// 5,7,10dq.erase(dq.begin()+1);// 移除7 → 5,10// 5. 清空和检查dq.clear();cout<<"是否为空: "<<dq.empty()<<endl;// true}高级用法
voidadvanced_usage(){// 1. 构造函数deque<int>dq1(5,100);// 5个100deque<int>dq2={1,2,3,4,5};// 初始化列表deque<int>dq3(dq2.begin(),dq2.begin()+3);// 复制部分// 2. 交换deque<int>a={1,2,3};deque<int>b={4,5,6};a.swap(b);// O(1)操作// 3. 调整大小deque<int>dq={1,2,3};dq.resize(5);// 变为: 1,2,3,0,0dq.resize(2);// 变为: 1,2dq.resize(4,99);// 变为: 1,2,99,99// 4. 容量相关deque<int>dq4;dq4.reserve(100);// ❌ deque没有reserve()！// 只能通过resize预先分配空间dq4.resize(100);// 分配100个元素空间}- 实际应用场景
场景1：滑动窗口
// 滑动窗口最大值vector<int>maxSlidingWindow(vector<int>&nums,intk){deque<int>dq;// 存储下标vector<int>result;for(inti=0;i<nums.size();++i){// 移除窗口外的元素if(!dq.empty()&&dq.front()==i-k)dq.pop_front();// 维护单调递减队列while(!dq.empty()&&nums[dq.back()]<nums[i])dq.pop_back();dq.push_back(i);if(i>=k-1)result.push_back(nums[dq.front()]);}returnresult;}场景2：任务队列
classTaskScheduler{private:deque<pair<int,string>>taskQueue;// 优先级, 任务名public:voidaddHighPriorityTask(string task){taskQueue.push_front({1,task});// 前端插入}voidaddLowPriorityTask(string task){taskQueue.push_back({0,task});// 后端插入}stringgetNextTask(){if(taskQueue.empty())return"";string task=taskQueue.front().second;taskQueue.pop_front();returntask;}};场景3：回文字符串判断
boolisPalindrome(conststring&s){deque<char>dq;// 填充deque（忽略空格和大小写）for(charc:s){if(isalnum(c))dq.push_back(tolower(c));}// 两端比较while(dq.size()>1){if(dq.front()!=dq.back())returnfalse;dq.pop_front();dq.pop_back();}returntrue;}- 性能优化技巧
优化建议
// 1. 使用emplace代替push（C++11及以上）deque<pair<int,string>>dq;dq.emplace_back(1,"test");// 避免临时对象构造// 等价于: dq.push_back(make_pair(1, "test"));// 2. 预先分配空间deque<int>dq;dq.resize(1000);// 如果知道大致大小，预先分配// 3. 批量操作使用assigndq.assign(100,0);// 100个0，比循环push_back快// 4. 避免频繁的中间插入删除// 如果需要频繁中间操作，考虑使用list// 5. 使用swap释放内存deque<int>dq;// ... 使用dq ...deque<int>().swap(dq);// 清空并释放内存- 注意事项
常见陷阱
// 1. 迭代器失效问题deque<int>dq={1,2,3,4,5};autoit=dq.begin()+2;dq.push_front(0);// ❌ it失效！// cout << *it; // 未定义行为// 2. 没有capacity()和reserve()deque<int>dq;// dq.capacity(); // ❌ 没有这个函数// dq.reserve(100); // ❌ 没有这个函数// 3. 中间操作性能差for(inti=0;i<10000;++i){dq.insert(dq.begin()+dq.size()/2,i);// O(n) 很慢！}// 4. 内存不是完全连续int*ptr=&dq[0];// ptr + dq.size() 可能不指向有效内存！最佳实践
优先使用deque的场景：
· 需要双端队列功能
· 既需要随机访问又需要两端操作
· 不确定前端还是后端操作更频繁选择vector的场景：
· 主要在后端操作
· 需要连续内存
· 需要最高缓存友好性选择list的场景：
· 频繁在中间插入删除
· 不需要随机访问
· 需要稳定的迭代器C++11/14/17/20 新特性
// C++11: emplace, initializer_listdeque<int>dq={1,2,3,4,5};dq.emplace_front(0);// C++17: try_emplace, insert_or_assign (对于map)// deque本身变化不大// C++20: 范围构造vector<int>vec={1,2,3,4,5};deque<int>dq(vec.begin(),vec.end());// C++20: 概念约束template<typenameT>requiresstd::random_access_iterator<typenameT::iterator>voidprocess(T&container){// 只接受支持随机访问的容器}总结：deque是STL中一个平衡了随机访问和两端操作性能的数据结构，适用于特定的使用场景，但需要注意其迭代器失效规则和内存特性。
