做网站需求江门网站建设方案推广

做网站需求,江门网站建设方案推广,小程序开发实例教程,网站正在建设中 html 模板STL deque 的详细特征 基本特性 #include deque using namespace std;dequeint dq; // 声明一个int类型的双端队列 双端队列#xff1a;允许在两端进行高效插入和删除动态数组#xff1a;支持随机访问#xff0c;可以像数组一样通过下标访问内存结构dequeusingnamespacestd;dequeintdq;// 声明一个int类型的双端队列· 双端队列允许在两端进行高效插入和删除· 动态数组支持随机访问可以像数组一样通过下标访问· 内存结构分段连续存储由多个固定大小的内存块组成内存结构与实现原理内部结构示意图deque内存布局 [块1] → [块2] → [块3] → [块4] → [块5] ↓ ↓ ↓ ↓ ↓ [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] ↑front ↑back 每个块固定大小通常是512字节或容纳元素的内存对齐大小 维护一个中央控制器map存储各个块的指针关键特征// 1. 分块存储// deque将元素存储在多个固定大小的内存块中// 当需要扩容时分配新的内存块而不是重新分配整个数组// 2. 随机访问复杂度 O(1)dequeintdq{1,2,3,4,5};coutdq[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 的对比性能对比#includedeque#includevector#includelist#includeiostreamvoidbenchmark(){// 1. 前端插入 - deque 最优dequeintdq;vectorintvec;listintlst;// push_front 测试for(inti0;i100000;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)内存开销 中等 低 高缓存友好 中等 高 低迭代器类型 随机访问 随机访问 双向迭代器特征迭代器特性dequeintdq{1,2,3,4,5};// 1. 随机访问迭代器autoitdq.begin();it3;// 支持随机访问cout*it;// 输出4// 2. 迭代器失效规则dq.push_front(0);// 所有迭代器失效dq.push_back(6);// 所有迭代器失效// 3. 插入/删除中间元素itdq.begin()2;dq.insert(it,99);// it失效迭代器失效情况操作 迭代器失效情况push_front() 所有迭代器失效push_back() 所有迭代器失效pop_front() 指向被删元素的迭代器失效pop_back() 指向被删元素的迭代器失效insert() 所有迭代器失效erase() 被删位置之后的迭代器失效resize() 所有迭代器失效常用操作示例基本操作#includedeque#includeiostream#includealgorithmvoidbasic_operations(){dequeintdq;// 1. 两端插入dq.push_back(10);// 后: 10dq.push_front(5);// 前: 5, 后: 10 → 5,10dq.emplace_back(15);// C11: 5,10,15dq.emplace_front(0);// C11: 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. 构造函数dequeintdq1(5,100);// 5个100dequeintdq2{1,2,3,4,5};// 初始化列表dequeintdq3(dq2.begin(),dq2.begin()3);// 复制部分// 2. 交换dequeinta{1,2,3};dequeintb{4,5,6};a.swap(b);// O(1)操作// 3. 调整大小dequeintdq{1,2,3};dq.resize(5);// 变为: 1,2,3,0,0dq.resize(2);// 变为: 1,2dq.resize(4,99);// 变为: 1,2,99,99// 4. 容量相关dequeintdq4;dq4.reserve(100);// ❌ deque没有reserve()// 只能通过resize预先分配空间dq4.resize(100);// 分配100个元素空间}实际应用场景场景1滑动窗口// 滑动窗口最大值vectorintmaxSlidingWindow(vectorintnums,intk){dequeintdq;// 存储下标vectorintresult;for(inti0;inums.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(ik-1)result.push_back(nums[dq.front()]);}returnresult;}场景2任务队列classTaskScheduler{private:dequepairint,stringtaskQueue;// 优先级, 任务名public:voidaddHighPriorityTask(string task){taskQueue.push_front({1,task});// 前端插入}voidaddLowPriorityTask(string task){taskQueue.push_back({0,task});// 后端插入}stringgetNextTask(){if(taskQueue.empty())return;string tasktaskQueue.front().second;taskQueue.pop_front();returntask;}};场景3回文字符串判断boolisPalindrome(conststrings){dequechardq;// 填充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代替pushC11及以上dequepairint,stringdq;dq.emplace_back(1,test);// 避免临时对象构造// 等价于: dq.push_back(make_pair(1, test));// 2. 预先分配空间dequeintdq;dq.resize(1000);// 如果知道大致大小预先分配// 3. 批量操作使用assigndq.assign(100,0);// 100个0比循环push_back快// 4. 避免频繁的中间插入删除// 如果需要频繁中间操作考虑使用list// 5. 使用swap释放内存dequeintdq;// ... 使用dq ...dequeint().swap(dq);// 清空并释放内存注意事项常见陷阱// 1. 迭代器失效问题dequeintdq{1,2,3,4,5};autoitdq.begin()2;dq.push_front(0);// ❌ it失效// cout *it; // 未定义行为// 2. 没有capacity()和reserve()dequeintdq;// dq.capacity(); // ❌ 没有这个函数// dq.reserve(100); // ❌ 没有这个函数// 3. 中间操作性能差for(inti0;i10000;i){dq.insert(dq.begin()dq.size()/2,i);// O(n) 很慢}// 4. 内存不是完全连续int*ptrdq[0];// ptr dq.size() 可能不指向有效内存最佳实践优先使用deque的场景· 需要双端队列功能· 既需要随机访问又需要两端操作· 不确定前端还是后端操作更频繁选择vector的场景· 主要在后端操作· 需要连续内存· 需要最高缓存友好性选择list的场景· 频繁在中间插入删除· 不需要随机访问· 需要稳定的迭代器C11/14/17/20 新特性// C11: emplace, initializer_listdequeintdq{1,2,3,4,5};dq.emplace_front(0);// C17: try_emplace, insert_or_assign (对于map)// deque本身变化不大// C20: 范围构造vectorintvec{1,2,3,4,5};dequeintdq(vec.begin(),vec.end());// C20: 概念约束templatetypenameTrequiresstd::random_access_iteratortypenameT::iteratorvoidprocess(Tcontainer){// 只接受支持随机访问的容器}总结deque是STL中一个平衡了随机访问和两端操作性能的数据结构适用于特定的使用场景但需要注意其迭代器失效规则和内存特性。