C++双端数组容器deque
微凉秋意 人气:0deque容器的概念模型
是双端数组,可以对头部进行插入删除操作
示意图
值得注意的是deque容器比vector容器多了头插、头删的操作以及front()和back(),后面这两个分别代表容器的第一个元素和最后一个元素,并不是迭代器,调用他们会得到具体的值。
deque与vector的区别:
- vector对于头部的插入删除效率低,数据量越大,效率越低
- deque相对而言,对头部的插入删除速度会比vector快
- vector访问元素时的速度会比deque快,这和两者内部实现有关
deque的内部工作原理:
1.deque内部有个中控器,维护每段缓冲区中的内容,缓冲区中存放真实数据。
2.中控器维护的是每个缓冲区的地址,使得使用deque时像一片连续的内存空间
3.deque的迭代器也是支持随机访问的
4.图示:
deque进行插入的时候是在结点对应的缓冲区操作的,缓冲区不有位置的时候直接插入到缓冲区中,缓冲区满的话就开辟新节点,再进行插入,所以才说像是连续的存储空间。
deque容器的基本操作
包括构造方法、赋值、计算大小、插入删除等
构造函数
deque容器的构造
函数原型
- deque<T> 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_iterator for (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); //resize d.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插入指定元素e
- insert(const_iterator pos,int count ,e); 插入count个指定元素e
- insert(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) << " "; }
排序
需要引入头文件:<algorithm>
利用算法实现对deque容器的排序
算法:sort(iterator beg,iterator en); 对beg和en的区间升序排序
tips:对于支持随机访问的迭代器都可以用sort进行排序
加载全部内容