<C++>快速掌握双端数组容器deque的使用
✅作者简介:C/C++领域新星创作者,为C++和java奋斗中
✨个人主页:微凉秋意的主页
🔥系列专栏:C++STL快速上手
📃推荐一款模拟面试、刷题神器👉注册免费刷题
🔥前言
书接上文,今天分享的是和
vector
容器功能很像的容器——deque
,了解deque容器的本质,使用方法以及与vector容器的不同之处,再后面的文章里会有vector和deque容器结合的具体案例分享给大家。
文章目录
- deque容器的概念模型
- deque容器的基本操作
-
- 构造函数
- 赋值操作
- 容器大小
- 插入和删除
- 数据存取
- 排序
- 结语
deque容器的概念模型
是双端数组,可以对头部进行插入删除操作
- 示意图
值得注意的是
deque
容器比vector容器多了头插、头删的操作以及front()
和back()
,后面这两个分别代表容器的第一个元素和最后一个元素,并不是迭代器,调用他们会得到具体的值。
deque与vector的区别:
- vector对于头部的插入删除效率低,数据量越大,效率越低
- deque相对而言,对头部的插入删除速度会比vector快
- vector访问元素时的速度会比deque快,这和两者
内部实现
有关
deque的内部工作原理:
- deque内部有个中控器,维护每段缓冲区中的内容,缓冲区中存放真实数据。
- 中控器维护的是每个缓冲区的地址,使得使用deque时像一片连续的内存空间
- deque的迭代器也是支持随机访问的
- 图示:
deque
进行插入的时候是在结点对应的缓冲区
操作的,缓冲区不有位置的时候直接插入到缓冲区中,缓冲区满的话就开辟新节点,再进行插入,所以才说像是连续的存储空间。
deque容器的基本操作
包括构造方法、赋值、计算大小、插入删除等
构造函数
- deque容器的构造
函数原型
deque deq;
其中T是泛型,用来存放数据类型,这是默认构造函数,较为常用deque(deq.begin(),deq.end());
将[deq.begin(),deq.end)前闭后开的区间内的元素拷贝给本身容器deque(n,elem);
构造函数将n个elem值拷贝给本身容器deque(const deque &ans);
拷贝构造函数
代码示例:
//打印void printDeque(const deque<int>& d)//只读容器不可改{//迭代器变为 const_iteratorfor (deque<int>::const_iterator it = d.begin(); it != d.end(); it++){cout << *it << " ";}cout << endl;}void testa(){//构造://第一种deque<int>d1;for (int i = 0; i < 10; i++){//d1.push_back(i); 头插尾插都可以d1.push_front(i);}//第二种deque<int>d2(d1.begin(), d1.end());//第三种deque<int>d3(d2);//第四种deque<int>d4(6, 100);//测试输出printDeque(d1);printDeque(d2);printDeque(d3);printDeque(d4);//排序cout << "排序" << endl;sort(d1.begin(), d1.end());printDeque(d1);}
tips:如果将打印语句设为只读,那么迭代器类型也要变为:const_iterator
。
赋值操作
- 给deque容器赋值
函数原型:
deque& operator=(const deque &ans);
重载赋值操作符assign(be,en);将[be,en);
将[be,en)区间内的数组拷贝赋值给自己assign(n,elem);
将n个elem拷贝赋值给自己
代码示例:
void testb(){//赋值:deque<int>d1;for (int i = 0; i < 10; i++){d1.push_back(i);}//第一种deque<int>d2 = d1;//第二种deque<int>d3;d3.assign(d1.begin(), d1.end());//第三种deque<int>d4;d4.assign(6, 88);//测试:printDeque(d2);printDeque(d3);printDeque(d4);}
容器大小
-
对deque的大小进行操作
-
deque.empty();
判断容器是否为空 -
deque.size();
返回容器中元素的个数 -
deque.resize(m);
重新指定容器长度为num,容器变长以默认值填充,容器变短则超出部分删除 -
deque.resize(m,elem);
同上,区别是默认值填充变为elem值填充
代码示例:
void testc(){//大小的操作://size:deque<int>d;if (d.empty()){cout << "此时容器为空" << endl;cout << "打印容器的大小:" << d.size() << endl;}for (int i = 0; i < 7; i++){d.push_back(i);}cout << "打印容器的大小:" << d.size() << endl;printDeque(d);//resized.resize(10,100);cout << "打印容器的大小:" << d.size() << endl;printDeque(d);d.resize(5);cout << "打印容器的大小:" << d.size() << endl;printDeque(d);}
tips:
- deque没有容量概念
- 判断是否为空——empty
- 返回元素个数——size
- 重新指定个数——resize
插入和删除
- 向deque容器中插入和删除数据
函数原型:
-
两端操作:
push_back(e);
尾插push_front(e);
头插pop_back();
尾删pop_front();
头删
-
指定位置:
insert(const_iterator pos,e);
迭代器指向位置pos插入指定元素einsert(const_iterator pos,int count ,e);
插入count个指定元素einsert(const_iterator pos,beg,en);
插入指定区域的元素erase(const_iterator pos);
删除迭代器指向的元素erase(const_iterator begin,const_iterator end);
删除迭代器从begin到end之间的元素clear();
清空容器内所有元素
代码示例:
//两端操作void test01(){deque<int>d1;//尾插d1.push_back(10);d1.push_back(20);//头插d1.push_front(100);d1.push_front(200);PrintDeque(d1);//尾删d1.pop_back();PrintDeque(d1);//头删d1.pop_front();PrintDeque(d1);}void test02(){deque<int>d2;//尾插d2.push_back(10);d2.push_back(20);//头插d2.push_front(100);d2.push_front(200);PrintDeque(d2);//insert插入d2.insert(d2.begin(), 1000);PrintDeque(d2);d2.insert(d2.begin(), 2,10000);PrintDeque(d2);//按照区间进行插入deque<int>d3;d3.push_back(1);d3.push_back(2);d3.push_back(3);d2.insert(d2.begin(), d3.begin(), d3.end());PrintDeque(d2);}void test03(){deque<int>d4;//尾插d4.push_back(10);d4.push_back(20);//头插d4.push_front(100);d4.push_front(200);PrintDeque(d4);//删除deque<int>::iterator it = d4.begin();it++;d4.erase(it);PrintDeque(d4);//按照区间方式删除d4.erase(d4.begin(), d4.end());PrintDeque(d4);//清空d4.clear();PrintDeque(d4);}
数据存取
- 对deque中的元素进行存取操作
函数原型:
at(int dex);
返回索引dex所指的数据operator[];
同上front();
返回容器中第一个数据back();
返回容器中最后一个数据
代码示例:
//通过[]方式访问元素for (int i = 0; i < d1.size(); i++){cout << d1[i] << " ";}cout << endl;//通过at方式访问元素for (int i = 0; i < d1.size(); i++){cout << d1.at(i) << " ";}
排序
- 需要引入头文件:
- 利用算法实现对deque容器的排序
算法:sort(iterator beg,iterator en);
对beg和en的区间升序排序
tips:对于支持随机访问的迭代器都可以用sort进行排序
结语
deque容器与vector容器功能很是相似,下篇博客带来二者结合的具体案例,期待你的关注和鼓励~