deque
容器deque是一个双向队列（double-ended queue），可以在队列的两端进行元素的插入和删除操作。deque 和 vector 非常相似。也采用dynamic array(动态数组) 来管理元素，提供随机访向，并有着和 vector 几乎一模一样的接口。不同的是:
deque的dynamic array 头尾都开放，因此能在头尾两端进行快速插入和删除。
使用 deque之前，必须先包含头文件
#include <deque>
deque和vector相比,有如下特点:
1.两端都能快速的插入和删除元素(vector只能在尾部快速的插入和删除数据)。
2.deque的内存重分配优于vector,因为从其内部结构可以看出,deque在扩容时不必复制所有数据,而vector在内存重新分配时需要复制所有的数据。
deque和vector相似的地方:
1.在中间插入和删除数据速度相对较慢,因为要移到其它的数据。
2.迭代器属于随机访问迭代器。
2.1 定义及初始化
它的定义和操作和vector非常类似,这里做简单的介绍,具体情况可以参考vs2022帮助手册。
下表列出定义deque对象的常用方法
#include <iostream>
#include <deque>
using namespace std;
//输出双端队列d的所有数据
void Show(const deque<int>& d)
{
for (const auto& x : d)
cout << x << " ";
cout << endl;
}
int main()
{
deque<int>d0;//创建一个空的双端队列
deque<int>d1(3);//创建一个包含3个0的双端队列
deque<int>d2(4,2);//创建一个包含4个2的双端队列
deque<int>d3{1,2,3,4,5};//创建包含1,2,3,4,5的双端队列
cout << "d0:"; Show(d0);
cout << "d1:"; Show(d1);
cout << "d2:"; Show(d2);
cout << "d3:"; Show(d3);
return 0;
}
2.2 向deque对象中添加元素
最常见的做法是定义一个空的deque对象,在运行时利用push_front(头部插入),push_back(尾部插入)函数添加元素。
例如:
//输出双端队列d的所有数据
void Show(const deque<int>& d)
{
for (const auto& x : d)
cout << x << " ";
cout << endl;
}
int main()
{
deque<int> d;//创建一个空的双端队列
d.push_front(1); //头部插入1
d.push_front(2); //头部插入2
d.push_front(3); //头部插入3
d.push_back(10);//尾部插入10
d.push_back(20);//尾部插入20
d.push_back(30);//尾部插入30
Show(d);//输出d的数据
return 0;
}
2.3 deque常用迭代器
int main()
{
deque<int> d{1,2,3,4,5};
//从头到尾输出d的数据
cout << "从头到尾:";
for (deque<int>::const_iterator it = d.cbegin(); it != d.cend(); ++it)
cout << *it << " ";
cout << endl;
//所有数据扩大2倍
for (auto it = d.begin(); it != d.end(); ++it)
*it *= 2;
//也可以使用范围for
//for (auto& x : d)
// x *= 2;
//从后往前输出
cout << "从后往前:";
for (auto it = d.rbegin(); it != d.rend(); ++it)//也可以使用crbegin()和crend()
cout << *it << " ";
cout << endl;
return 0;
}
2.4 deque常用运算符
//输出双端队列d的所有数据
void Show(const deque<int>& d)
{
for (auto& x : d)
cout << x << " ";
cout << endl;
}
int main()
{
deque<int>q1{1, 2, 3, 4, 5};
deque<int>q2;
q2 = q1; //把q1的值全部赋值给q2
cout << "q1:";
Show(q1);
cout << "q2:";
Show(q2);
if (q1 == q2) //判断q1是否等于q2
cout << "q1==q2" << endl << endl;
q1[1] = 50; //通过[]修改q1的元素
cout << "q1[1]=50后" << endl << "q1:";
Show(q1);
cout << "q2:";
Show(q2);
if (q1 != q2)//判断两个deque对象是否不相等
cout << "q1 != q2" << endl;
if (q1 < q2) //判断q1,q2的大小
cout << "q1 < q2" << endl;
else if (q1 > q2)
cout << "q1 > q2" << endl;
else
cout << "q1 == q2" << endl;
return 0;
}
2.5 deque常用成员函数
empty成员函数
判断deque对象是否为空。
front成员函数
获取第一个元素的引用。
back成员函数
获取最后一个元素的引用。
push_front成员函数
往头部插入数据。容量不够会自动扩容。
pop_front成员函数
从头部删除数据。
int main()
{
deque<int>d;
//下面的操作类似队列
for (int i = 0; i < 5; i++)//尾插5个数据 0,1,2,3,4
d.push_back(i);
while (!d.empty())//只要d不空,循环继续
{
cout << d.front() << " "; //输出头部数据
d.pop_front(); //头删
}
cout << endl;
return 0;
}
本篇完！