devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++STL容器之deque

作者：小小林熬夜学编程 | 2024-02-29 19:10:00

赞

踩

C++STL容器之deque

目录

一、基本概念

1、功能

2、deque与vector的区别

3、工作原理 

二、构造函数

1、函数

2、测试 

三、赋值操作

1、函数 

2、测试

四、大小操作

1、函数

2、测试

五、插入和删除

1、函数

2、测试

六、数据存取

1、函数(和vector容器里面是一样样的)

2、测试

七、deque排序

1、函数

2、测试

一、基本概念

1、功能

双端数组，可以对头端进行插入删除操作 

2、deque与vector的区别

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

 

3、工作原理 

  • deque内部有一个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据
  • 中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间
  • deque容器的迭代器也是支持随机访问的

  

二、构造函数

1、函数

deque<T> deqT;                                        //默认构造

deque(beg,end);                                       //构造函数将[beg,end]区间中的元素拷贝给本身

deque(n,elem);                                         //构造函数将n个elem拷贝给本身

deque(const deque &deq);                     //拷贝构造函数

2、测试 

  1. #include<deque>
  2.  
  3. //deque构造函数
  4. void printDeque(const deque<int>& d) {//此时这个函数为只读状态,不可修改
  5. 	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
  6. 		//*it = 100;参数变为const,迭代器也变为const,此时容器中的数据就不可以修改了
  7. 		cout << *it << " ";
  8. 	}
  9. 	cout << endl;
  10. }
  11. void Test01() {
  12. 	deque<int> d1;
  13. 	for (int i = 0; i < 10; i++)
  14. 	{
  15. 		d1.push_back(i);
  16. 	}
  17. 	printDeque(d1);//0 1 2 3 4 5 6 7 8 9
  18.  
  19. 	deque<int> d2(d1.begin(),d1.end());
  20. 	printDeque(d2);//0 1 2 3 4 5 6 7 8 9
  21.  
  22. 	deque<int> d3(10, 100);
  23. 	printDeque(d3);//100 100 100 100 100 100 100 100 100 100
  24.  
  25. 	deque<int> d4(d3);
  26. 	printDeque(d4);//100 100 100 100 100 100 100 100 100 100
  27. }
  28. int main() {
  29. 	Test01();
  30. 	return 0;
  31. }

三、赋值操作

1、函数 

deque& operator=(const deque &deq);              //重载等号操作符

assign(beg,end);                                                  //将[beg,end]区间中的数据拷贝赋值给本身

assign(n,elem);                                                    //将n个elem拷贝赋值给本身

2、测试

  1. #include<deque>
  2.  
  3. //deque赋值操作
  4. void printDeque(const deque<int>& d) {
  5. 	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
  6. 		//*it = 100;参数变为const,迭代器也变为const,此时容器中的数据就不可以修改了
  7. 		cout << *it << " ";
  8. 	}
  9. 	cout << endl;
  10. }
  11. void Test02() {
  12. 	deque<int> d1;
  13. 	for (int i = 0; i < 10; i++)
  14. 	{
  15. 		d1.push_back(i);
  16. 	}
  17. 	printDeque(d1);//0 1 2 3 4 5 6 7 8 9
  18.  
  19. 	deque<int> d2;
  20. 	d2 = d1;
  21. 	printDeque(d2);//0 1 2 3 4 5 6 7 8 9
  22.  
  23. 	deque<int> d3;
  24. 	d3.assign(d1.begin(),d1.end());
  25. 	printDeque(d3);//0 1 2 3 4 5 6 7 8 9
  26.  
  27. 	deque<int> d4;
  28. 	d4.assign(10, 100);
  29. 	printDeque(d4);//100 100 100 100 100 100 100 100 100 100
  30. }
  31. int main() {
  32. 	Test02();
  33. 	return 0;
  34. }

四、大小操作

1、函数

deque.empty();                                                          //判断容器是否为空

deque.size();                                                             //返回容器中元素的个数

deque.resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置；若容器变短，则末尾超出容器长度的元素被删除

deque.resize(int num,elem);// 重新指定容器的长度为num，若容器变长，则以elem填充新位置；若容器变短，则末尾超出容器长度的元素被删除

与vector相比,vector有capacity()容量函数,但deque是没有的 

2、测试

  1. #include<deque>
  2.  
  3. //deque大小操作
  4. void printDeque(const deque<int>& d) {
  5. 	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
  6. 		//*it = 100;参数变为const,迭代器也变为const,此时容器中的数据就不可以修改了
  7. 		cout << *it << " ";
  8. 	}
  9. 	cout << endl;
  10. }
  11. void Test03() {
  12. 	deque<int> d1;
  13. 	for (int i = 0; i < 10; i++)
  14. 	{
  15. 		d1.push_back(i);
  16. 	}
  17. 	printDeque(d1);//0 1 2 3 4 5 6 7 8 9
  18.     //判断是否为空
  19. 	if (d1.empty()) {
  20. 		cout << "d1为空" << endl;
  21. 	}
  22. 	else {
  23. 		cout << "d1不为空" << endl;
  24. 		cout << "d1的大小" << d1.size() << endl;//10
  25. 		//deque容器没有容量的概念
  26. 	}
  27. 	
  28. 	//重新定义大小   
  29. 	d1.resize(12);
  30. 	printDeque(d1);//0 1 2 3 4 5 6 7 8 9 0 0
  31.  
  32. 	d1.resize(14, 1);
  33. 	printDeque(d1);//0 1 2 3 4 5 6 7 8 9 0 0 1 1
  34.  
  35. 	d1.resize(4);
  36. 	printDeque(d1);//0 1 2 3
  37. }
  38. int main() {
  39. 	Test03();
  40. 	return 0;
  41. }

五、插入和删除

1、函数

  • 两端位置操作

push_back(elem);                                      //在容器尾部添加一个数据

push_front(elem);                                      //在容器头部添加一个数据

pop_back();                                                //删除容器最后一个数据

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位置的数据,返回下一个数据的位置

2、测试

  1. #include<deque>
  2.  
  3. //deque插入和删除
  4. void printDeque(const deque<int>& d) {
  5. 	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
  6. 		//*it = 100;参数变为const,迭代器也变为const,此时容器中的数据就不可以修改了
  7. 		cout << *it << " ";
  8. 	}
  9. 	cout << endl;
  10. }
  11. //两端操作
  12. void Test04() {
  13. 	deque<int> d1;
  14. 	//尾插
  15. 	d1.push_back(10);
  16. 	d1.push_back(20);
  17. 	//头插
  18. 	d1.push_front(100);
  19. 	d1.push_front(200);
  20. 	printDeque(d1);//200 100 10 20
  21.  
  22. 	//尾删
  23. 	d1.pop_back();
  24. 	printDeque(d1);//200 100 10
  25. 	//头删
  26. 	d1.pop_front();
  27. 	printDeque(d1);//100 10
  28. }
  29. //在指定位置插入操作
  30. void Test05() {
  31. 	deque<int> d1;
  32. 	d1.push_back(10);
  33. 	d1.push_back(20);
  34. 	d1.push_front(100);
  35. 	d1.push_front(200);
  36. 	printDeque(d1);//200 100 10 20
  37.  
  38. 	//insert插入
  39. 	d1.insert(d1.begin(), 1000);
  40. 	printDeque(d1);//1000 200 100 10 20
  41.  
  42. 	d1.insert(d1.begin(),2, 10000);
  43. 	printDeque(d1);//10000 10000 1000 200 100 10 20
  44.  
  45. 	//按区间进行插入
  46. 	deque<int> d2;
  47. 	d2.push_back(1);
  48. 	d2.push_back(2);
  49. 	d2.push_back(3);
  50. 	d1.insert(d1.begin(), d2.begin(), d2.end());
  51. 	printDeque(d1);
  52. }
  53. //在指定位置删除操作
  54. void Test06() {
  55. 	deque<int> d1;
  56. 	d1.push_back(10);
  57. 	d1.push_back(20);
  58. 	d1.push_front(100);
  59. 	d1.push_front(200);
  60. 	printDeque(d1);//200 100 10 20
  61.  
  62. 	//删除
  63. 	deque<int>::iterator it = d1.begin();
  64. 	it++;//迭代器位置是可以移动的,此时指向的是100的位置
  65. 	d1.erase(it);
  66. 	printDeque(d1);//200 10 20
  67. 	//按区间方式删除
  68. 	//d1.erase(d1.begin(), d1.end());
  69. 	//清空
  70. 	d1.clear();
  71. 	printDeque(d1);
  72. }
  73. int main() {
  74. 	Test04();
  75. 	Test05();
  76. 	Test06();
  77. 	return 0;
  78. }

六、数据存取

1、函数(和vector容器里面是一样样的)

at(int idx);                                            //返回索引idx所指的数据

opeartor[];                                           //返回索引idx所指的数据

front();                                                 //返回容器中第一个数据元素

back();                                                 //返回容器中最后一个数据元素

2、测试

 除了用迭代器获取deque容器中的元素,[]和at方式也可以

  1. #include<deque>
  2.  
  3. //deque数据存取
  4. void Test07() {
  5. 	deque<int> d1;
  6. 	d1.push_back(10);
  7. 	d1.push_back(20);
  8. 	d1.push_back(30);
  9. 	d1.push_front(100);
  10. 	d1.push_front(200);
  11. 	d1.push_front(300);
  12.  
  13. 	//通过[]方式访问元素
  14. 	for (int i = 0; i < d1.size(); i++) {
  15. 		cout << d1[i] << " ";
  16. 	}
  17. 	cout << endl;//300 200 100 10 20 30
  18.  
  19. 	//通过at方式访问元素
  20. 	for (int i = 0; i < d1.size(); i++) {
  21. 		cout << d1.at(i) << " ";
  22. 	}
  23. 	cout << endl;//300 200 100 10 20 30
  24.  
  25. 	cout << "第一个元素为:" << d1.front() << endl;//300
  26. 	cout << "最后一个元素为:" << d1.back() << endl;//30
  27. }
  28. int main() {
  29. 	Test07();
  30. 	return 0;
  31. }

七、deque排序

1、函数

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

  • 需要包含头文件#include<algorithm>才可使用 
  • 默认排序规则是从小到大 升序
  • 对于支持随机访问的迭代器的容器,都可以利用sort算法直接对其进行排序
  • vector容器也可以利用sort算法进行排序

2、测试

  1. #include<deque>
  2. #include<algorithm>
  3. //deque排序
  4. void printDeque(const deque<int>& d) {
  5. 	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
  6. 		//*it = 100;参数变为const,迭代器也变为const,此时容器中的数据就不可以修改了
  7. 		cout << *it << " ";
  8. 	}
  9. 	cout << endl;
  10. }
  11. void Test08() {
  12. 	deque<int> d1;
  13. 	d1.push_back(10);
  14. 	d1.push_back(20);
  15. 	d1.push_back(30);
  16. 	d1.push_front(100);
  17. 	d1.push_front(200);
  18. 	d1.push_front(300);
  19.  
  20. 	printDeque(d1);
  21. 	sort(d1.begin(), d1.end());
  22. 	cout << "排序后:";
  23. 	printDeque(d1);//排序后:10 20 30 100 200 300
  24. }
  25. int main() {
  26. 	Test08();
  27. 	return 0;
  28. }
声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号