🚀 深入浅出deque容器：双端队列的奇幻漂流

摘要：想拥有既能"头铁"插入数据，又能"尾行"删除元素的神奇容器吗？快来解锁STL中的瑞士军刀——deque容器！本文用趣味比喻+实战代码，带你玩转双端队列的骚操作，附赠超实用评委打分案例，包教包会！

🌈 1. deque的奇妙物语：双端队列的诞生

定位：双端数组，头尾操作666的"双头蛇"容器

必杀技：

• 头部插入删除：O(1)时间复杂度，秒杀vector
• 随机访问：速度略逊vector，但仍是王者级别
• 内存管理：中控器智能调度，像管理地铁线路一样优雅

内部揭秘：

• 中控器：像地铁调度中心，维护多个缓冲区地址
• 缓冲区：真实数据存放区，如同一个个地铁车厢，使得使用deque时像一片连续的内存空间
• 迭代器：支持随机访问的智能导航系统

deque与vector区别：

特性	deque	vector
头部操作	⚡闪电侠	🐢龟速
内存扩展	分段式管理	整体搬迁
访问速度	稍慢	光速

分析总结： 

• vector对于头部的插入删除效率低，数据量越大，效率越低
• deque相对而言，对头部的插入删除速度回比vector快
• vector访问元素时的速度会比deque快,这和两者内部实现有关

🛠️ 2. deque的百宝箱：从构造到操作一网打尽

2.1 四大构造姿势

代码演绎：

void test_construction() {deque<int> d1;                   // 空队列deque<int> d2(d1.begin(),d1.end()); // 复制构造deque<int> d3(5, 100);           // 5个100deque<int> d4(d3);               // 拷贝构造// 验证构造结果cout << "d3元素：";for(auto it = d3.begin(); it != d3.end(); ++it) cout << *it << " "; // 100 100 100 100 100
}

代码分析：

• deque<T>默认构造创建空队列
• deque(beg, end)迭代器范围构造适合复制部分元素
• (n, elem) 构造快速生成重复元素队列
• deque(const deque &deq)拷贝构造是深拷贝，新旧队列互不影响

案例代码：

#include<iostream>
using namespace std;
#include<deque>// deque 构造函数void Print(const deque<int> &d)
{for(deque<int>::const_iterator it=d.begin(); it!=d.end(); it++){// *it = 100;   容器中的数据不可修改cout<<*it<<" ";}cout<<endl;
}void test01()
{deque<int>d1;for(int i=0;i<10;i++){d1.push_back(i);}Print(d1);deque<int>d2(d1.begin(), d1.end());Print(d2);deque<int>d3(10, 100);Print(d3);deque<int>d4(d3);Print(d4);}int main()
{test01();system("pause");return 0;
}

总结：deque容器和vector容器的构造方式几乎一致，灵活使用即可。

2.2 三大赋值绝技

代码秀：

void test_assignment() {deque<int> d1{1,3,5,7,9};deque<int> d2 = d1;            // 等号赋值deque<int> d3;d3.assign(d1.begin()+1, d1.end()-1); // 3 5 7d4.assign(3, 666);             // 666 666 666
}

要点解析：

• operator= 直接复制整个队列
• assign() 更灵活，支持区间assign(beg, end);和填充式赋值assign(n, elem);
• 注意迭代器失效问题（赋值后原迭代器不可用）

案例代码：

#include<iostream>
using namespace std;
#include<deque>// deque 赋值操作void Print(const deque<int> &d)
{for(deque<int>::const_iterator it=d.begin(); it!=d.end(); it++){// *it = 100;   容器中的数据不可修改cout<<*it<<" ";}cout<<endl;
}void test01()
{deque<int>d1;for(int i=0;i<10;i++){d1.push_back(i);}Print(d1);// operator=赋值deque<int>d2;d2 = d1;Print(d2);// assign赋值deque<int>d3;d3.assign(d1.begin(), d1.end());Print(d3);deque<int>d4;d4.assign(10, 100);Print(d4);}int main()
{test01();system("pause");return 0;
}

总结：deque赋值操作也与vector相同，需熟练掌握。

2.3 尺寸自由伸缩

代码示例：

void test_size() {deque<int> d{1,2,3};d.resize(5);       // 1 2 3 0 0 d.resize(3);       // 裁掉末尾两个0d.resize(5, 999);  // 1 2 3 999 999
}

使用技巧：

• resize(n) 默认填充0，resize(n, val) 自定义填充值
• 缩容时优先删除尾部元素
• 没有容量概念，即没有capacity()方法，内存管理更智能
• 判断容器是否为空用empty()，判断元素个数多少用size()

案例代码：

#include<iostream>
using namespace std;
#include<deque>// deque 大小操作void Print(const deque<int> &d)
{for(deque<int>::const_iterator it=d.begin(); it!=d.end(); it++){cout<<*it<<" ";}cout<<endl;
}void test01()
{deque<int>d1;for(int i=0;i<10;i++){d1.push_back(i);}Print(d1);if(d1.empty()){cout<<"d1为空"<<endl;}else{cout<<"d1不为空"<<endl;cout<<"d1的大小为:"<<d1.size()<<endl;// deque没有容量的概念}//重新指定大小// d1.resize(15);d1.resize(15, 9);Print(d1);d1.resize(5);Print(d1);}int main()
{test01();system("pause");return 0;
}

总结：

• deque没有容量的概念
• 判断是否为空   --- empty
• 返回元素个数   --- size
• 重新指定个数   --- resize

2.4 插入删除七十二变

操作大全：

void test_modify() {deque<int> d;// 双端操作d.push_front(10);  // 头插d.push_back(20);   // 尾插d.pop_front();     // 头删d.pop_back();      // 尾删// 定点插入d.insert(d.begin()+1, 3, 666); // 在第二个位置插入3个666d.erase(d.end()-2);            // 删除倒数第二个元素
}

避坑指南：

• 插入删除会导致迭代器失效，建议操作后重新获取
• 头部操作首选push_front/pop_front
• 中间插入效率较低，慎用！

指定位置操作：

• insert(pos,elem);        //在pos位置插入一个elem元素的拷贝，返回新数据的位置。
• insert(pos,n,elem);     //在pos位置插入n个elem数据，无返回值。
• insert(pos,beg,end);   //在pos位置插入[beg,end)区间的数据，无返回值。
• clear();                        //清空容器的所有数据
• erase(beg,end);          //删除[beg,end)区间的数据，返回下一个数据的位置。
• erase(pos);                 //删除pos位置的数据，返回下一个数据的位置。

案例代码：

#include<iostream>
using namespace std;
#include<deque>// deque 插入和删除void Print(const deque<int> &d)
{for(deque<int>::const_iterator it=d.begin(); it!=d.end(); it++){cout<<*it<<" ";}cout<<endl;
}// 两端操作
void test01()
{deque<int>d1;//尾插法d1.push_back(10);d1.push_back(15);d1.push_back(20);//头插法d1.push_front(99);d1.push_front(100);Print(d1);      // 100 99 10 15 20//尾删          d1.pop_back();Print(d1);      // 100 99 10 15 //头删d1.pop_front();Print(d1);      // 99 10 15
}void test02()
{deque<int>d1;d1.push_back(555);d1.push_back(444);d1.push_front(666);d1.push_front(999);Print(d1);      // 999 666 555 444// insert插入d1.insert(d1.begin(), 1000);Print(d1);      // 1000 999 666 555 444d1.insert(d1.begin(), 2, 1001);Print(d1);      // 1001 1001 1000 999 666 555 444// 按照区间进行插入deque<int>d2;d2.push_back(1);d2.push_back(2);d2.push_back(3);d1.insert(d1.begin(), d2.begin(), d2.end());Print(d1);      // 1 2 3 1001 1001 1000 999 666 555 444// 删除cout<<"删除操作"<<endl;deque<int>::iterator it = d1.begin();it++;d1.erase(it);Print(d1);     // 1 3 1001 1001 1000 999 666 555 444//按照区间删除// d1.erase(d1.begin(), d1.end());// 清空d1.clear();Print(d1);}int main()
{// test01();test02();system("pause");return 0;
}

 总结：

• 插入和删除提供的位置是迭代器！
• 尾插   ---  push_back
• 尾删   ---  pop_back
• 头插   ---  push_front
• 头删   ---  pop_front

2.5 数据存取三重奏

存取方法：

void test_access() {deque<int> d{10,20,30,40};cout << d[1];         // 20（不检查越界）cout << d.at(2);      // 30（越界抛异常）cout << d.front();    // 10cout << d.back();     // 40
}

安全建议：

• 优先使用at()进行安全访问
• operator[] 效率更高但需自行检查边界
• front()/back() 快速获取首尾元素

案例代码：

#include<iostream>
using namespace std;
#include<deque>// deque 数据存取void Print(const deque<int> &d)
{for(deque<int>::const_iterator it=d.begin(); it!=d.end(); it++){cout<<*it<<" ";}cout<<endl;
}void test01()
{deque<int>d1;d1.push_back(1);d1.push_back(23);d1.push_back(45);d1.push_back(2);d1.push_front(10);d1.push_front(20);d1.push_front(30);// 利用[]方式访问数组中元素for(int i=0; i<d1.size();i++){cout<<d1[i]<<" ";       // 30 20 10 1 23 45 2}cout<<endl;// 利用at方式访问数组中元素for(int i=0;i<d1.size();i++){cout<<d1.at(i)<<" ";    // 30 20 10 1 23 45 2}cout<<endl;// 获取第一个元素  30cout<<"第一个元素为："<<d1.front()<<endl;// 获取最后一个元素 2cout<<"最后一个元素为："<<d1.back()<<endl;}int main()
{test01();system("pause");return 0;
}

总结：

• 除了用迭代器获取deque容器中元素，[ ]和at也可以
• front返回容器第一个元素
• back返回容器最后一个元素

2.6  deque 排序

        利用算法实现对deque容器进行排序

算法：

• sort(iterator beg, iterator end)  //对beg和end区间内元素进行排序

案例代码：

#include<iostream>
using namespace std;
#include<deque>
#include<algorithm>// deque 排序操作void Print(const deque<int> &d)
{for(deque<int>::const_iterator it=d.begin(); it!=d.end(); it++){cout<<*it<<" ";}cout<<endl;
}void test01()
{deque<int>d1;d1.push_back(1);d1.push_back(23);d1.push_back(45);d1.push_back(5);d1.push_front(10);d1.push_front(2);d1.push_front(40);cout<<"排序前："<<endl;Print(d1);// 排序    默认排序规则  从小到大 升序// 对于支持随机访问的迭代器的容器，都可以利用sort算法直接对其进行排序// vector容器也可以利用sort进行排序cout<<"排序后："<<endl;sort(d1.begin(), d1.end());Print(d1);}int main()
{test01();system("pause");return 0;
}

总结：

• 排序默认排序规则是从小到大（升序）
• 对于支持随机访问的迭代器的容器，都可以利用sort算法直接对其进行排序
• vector容器也可以利用sort进行排序
• sort算法非常实用，使用时包含头文件 algorithm即可

🎯 3. 实战案例：评委打分系统

需求场景：

• 5名选手（ABCDE）
• 10个评委打分（60-100）
• 去除最高/最低分，计算平均分

实现思路：

1. 创建选手对象容器
2. 使用deque存储评委分数（方便去头尾）
3. sort排序 + 删除首尾
4. 计算平均分

完整代码：

#include<iostream>
using namespace std;
#include<vector>
#include<deque>
#include<random>
#include<algorithm>
#include<time.h>/*
案例描述有5名选手：选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委中最低分，取平均分。
*/void Print(const deque<int> &d)
{for(deque<int>::const_iterator it=d.begin(); it!=d.end(); it++){cout<<*it<<" ";}cout<<endl;
}void test()
{srand((unsigned int)time(NULL));vector<char>v;//  选手ABCDE  创建五名选手，放到vector中v.push_back('A');v.push_back('B');v.push_back('C');v.push_back('D');v.push_back('E');deque<int>d;for(int i = 0; i<v.size(); i++)   // 遍历vector容器，取出来每一个选手{d.clear();for(int i=0; i<10; i++)   // 执行for循环，可以把10个评分打分存到deque容器中{d.push_back((rand()%41 + 60));}// sort算法对deque容器中分数排序，去除最高和最低分sort(d.begin(), d.end());d.pop_front();d.pop_back();int sum = 0;//  deque容器遍历一遍，累加总分for(int i = 0; i<d.size(); i++){sum += d[i];}// 获取平均分cout<<"选手："<<v[i]<<"\t平均分为"<<(sum/d.size())<<endl;}}int main()
{test();system("pause");return 0;
}

代码解析：

1. 使用deque存储分数，充分利用其头尾删除的高效性
2. sort + pop_front/back 快速去除极值
3. accumulate 算法简化求和操作
4. 平均分计算使用整数除法，根据需求可改为浮点

总结：选取不同的容器操作数据，可以提升代码的效率。

💡 4. 性能优化小贴士

1. 场景选择：

   • 频繁头尾操作 → deque
   • 纯尾部操作 → vector
   • 中间频繁插入 → list

2. 内存管理：

   • deque的内存碎片比vector多，但扩容代价小
   • 超大容量时优先考虑deque

3. 迭代器陷阱：

deque<int> d{1,2,3};
auto it = d.begin();
d.push_front(0);  // 导致迭代器失效！
cout << *it;      // 未定义行为！

---

🚨 5. 常见问题Q&A

Q：deque真的在任何情况下都比vector快吗？

A：错！虽然头插快，但：

• 遍历速度vector更快（连续内存）
• 中间插入两者都慢
• 小数据量时差异不明显

Q：如何清空deque最高效？

A：三种方式：

1. d.clear() ← 推荐！
2. d.erase(d.begin(), d.end())
3. deque<int>().swap(d) ← 彻底释放内存

Q：deque的迭代器属于哪种类型？

A：随机访问迭代器，支持：

• it + n
• it - n
• it[n]
• 比较运算符