1 deque容器基本概念
（1）功能：
双端数组，可以对头端进行插入删除操作
（2）deque与vector区别：
vector对于头部的插入删除效率低，数据量越大，效率越低
deque相对而言，对头部的插入删除速度回比vector快
vector访问元素时的速度会比deque快,这和两者内部实现有关
（3）deque内部工作原理:
deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据
中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间
deque容器的迭代器也是支持随机访问的
2 deque构造函数
功能描述：
deque容器构造
函数原型：
1. deque<T> deqT; //默认构造形式 2. deque(beg, end); //构造函数将[beg, end)区间中的元素拷贝给本身。 3. deque(n, elem); //构造函数将n个elem拷贝给本身。 4. deque(const deque &deq); //拷贝构造函数
1. void printDeque(const deque<int>& d) 2. { 3. for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) { 4. cout << *it << " "; 5. 6. } 7. cout << endl; 8. } 9. //deque构造 10. void test01() { 11. 12. deque<int> d1; //无参构造函数 13. for (int i = 0; i < 10; i++) 14. { 15. d1.push_back(i); 16. } 17. printDeque(d1); 18. deque<int> d2(d1.begin(),d1.end()); 19. printDeque(d2); 20. 21. deque<int>d3(10,100); 22. printDeque(d3); 23. 24. deque<int>d4 = d3; 25. printDeque(d4); 26. } 27. 28. int main() 29. { 30. test01(); 31. return 0; 32. }
总结：deque容器和vector容器的构造方式几乎一致，灵活使用即可
3、deque赋值操作
功能描述：
给deque容器进行赋值
函数原型：
1. deque& operator=(const deque &deq); //重载等号操作符 2. assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。 3. assign(n, elem); //将n个elem拷贝赋值给本身。
1. void printDeque(const deque<int>& d) 2. { 3. for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) { 4. cout << *it << " "; 5. 6. } 7. cout << endl; 8. } 9. //赋值操作 10. void test01() 11. { 12. deque<int> d1; 13. for (int i = 0; i < 10; i++) 14. { 15. d1.push_back(i); 16. } 17. printDeque(d1); 18. 19. deque<int>d2; 20. d2 = d1; 21. printDeque(d2); 22. 23. deque<int>d3; 24. d3.assign(d1.begin(), d1.end()); 25. printDeque(d3); 26. 27. deque<int>d4; 28. d4.assign(10, 100); 29. printDeque(d4); 30. 31. } 32. 33. int main() 34. { 35. test01(); 36. return 0; 37. }
总结：deque赋值操作也与vector相同，需熟练掌握
4、deque大小操作
功能描述：
对deque容器的大小进行操作
函数原型：
1. deque.size(); //返回容器中元素的个数 2. deque.resize(num); //重新指定容器的长度为num,若容器变长，则以默认值填充新位置。 3. //如果容器变短，则末尾超出容器长度的元素被删除。 4. deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置。 5. //如果容器变短，则末尾超出容器长度的元素被删除
1. #include <deque> 2. 3. void printDeque(const deque<int>& d) 4. { 5. for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) { 6. cout << *it << " "; 7. 8. } 9. cout << endl; 10. } 11. 12. //大小操作 13. void test01() 14. { 15. deque<int> d1; 16. for (int i = 0; i < 10; i++) 17. { 18. d1.push_back(i); 19. } 20. printDeque(d1); 21. 22. //判断容器是否为空 23. if (d1.empty()) { 24. cout << "d1为空!" << endl; 25. } 26. else { 27. cout << "d1不为空!" << endl; 28. //统计大小 29. cout << "d1的大小为：" << d1.size() << endl; 30. } 31. 32. //重新指定大小 33. d1.resize(15, 1); 34. printDeque(d1); 35. 36. d1.resize(5); 37. printDeque(d1); 38. } 39. 40. int main() 41. { 42. test01(); 43. return 0; 44. }
总结：
deque没有容量的概念
判断是否为空 --- empty
返回元素个数 --- size
重新指定个数 --- resize
5、deque 插入和删除
功能描述：
向deque容器中插入和删除数据
函数原型：
1. 两端插入操作： 2. push_back(elem); //在容器尾部添加一个数据 3. push_front(elem); //在容器头部插入一个数据 4. pop_back(); //删除容器最后一个数据 5. pop_front(); //删除容器第一个数据 6. 7. 指定位置操作： 8. insert(pos,elem); //在pos位置插入一个elem元素的拷贝，返回新数据的位置。 9. insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值。 10. insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据，无返回值。 11. clear(); //清空容器的所有数据 12. erase(beg,end); //删除[beg,end)区间的数据，返回下一个数据的位置。 13. erase(pos); //删除pos位置的数据，返回下一个数据的位置
1. void printDeque(const deque<int>& d) 2. { 3. for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) { 4. cout << *it << " "; 5. 6. } 7. cout << endl; 8. } 9. //两端操作 10. void test01() 11. { 12. deque<int> d; 13. //尾插 14. d.push_back(10); 15. d.push_back(20); 16. //头插 17. d.push_front(100); 18. d.push_front(200); 19. 20. printDeque(d); 21. 22. //尾删 23. d.pop_back(); 24. //头删 25. d.pop_front(); 26. printDeque(d); 27. } 28. 29. //插入 30. void test02() 31. { 32. deque<int> d; 33. d.push_back(10); 34. d.push_back(20); 35. d.push_front(100); 36. d.push_front(200); 37. printDeque(d); 38. 39. d.insert(d.begin(), 1000); 40. printDeque(d); 41. 42. d.insert(d.begin(), 2,10000); 43. printDeque(d); 44. 45. deque<int>d2; 46. d2.push_back(1); 47. d2.push_back(2); 48. d2.push_back(3); 49. 50. d.insert(d.begin(), d2.begin(), d2.end()); 51. printDeque(d); 52. 53. } 54. 55. //删除 56. void test03() 57. { 58. deque<int> d; 59. d.push_back(10); 60. d.push_back(20); 61. d.push_front(100); 62. d.push_front(200); 63. printDeque(d); 64. 65. d.erase(d.begin()); 66. printDeque(d); 67. 68. d.erase(d.begin(), d.end()); 69. d.clear(); 70. printDeque(d); 71. } 72. 73. int main() 74. { 75. //test01(); 76. //test02(); 77. test03(); 78. return 0; 79. }
总结：
插入和删除提供的位置是迭代器！
尾插 --- push_back
尾删 --- pop_back
头插 --- push_front
头删 --- pop_front
6、deque 数据存取
功能描述：
对deque 中的数据的存取操作
函数原型：
1. at(int idx); //返回索引idx所指的数据 2. operator[]; //返回索引idx所指的数据 3. front(); //返回容器中第一个数据元素 4. back(); //返回容器中最后一个数据元素
1. void printDeque(const deque<int>& d) 2. { 3. for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) { 4. cout << *it << " "; 5. 6. } 7. cout << endl; 8. } 9. 10. //数据存取 11. void test01() 12. { 13. 14. deque<int> d; 15. d.push_back(10); 16. d.push_back(20); 17. d.push_front(100); 18. d.push_front(200); 19. 20. for (int i = 0; i < d.size(); i++) { 21. cout << d[i] << " "; 22. } 23. cout << endl; 24. 25. 26. for (int i = 0; i < d.size(); i++) { 27. cout << d.at(i) << " "; 28. } 29. cout << endl; 30. 31. cout << "front:" << d.front() << endl; 32. 33. cout << "back:" << d.back() << endl; 34. } 35. 36. int main() 37. { 38. test01(); 39. return 0; 40. }
总结：
除了用迭代器获取deque容器中元素，[ ]和at也可以
front返回容器第一个元素
back返回容器最后一个元素
7、deque排序
功能描述：
利用算法实现对deque容器进行排序
算法：
sort(iterator beg, iterator end) //对beg和end内元素进行排序
1. void printDeque(const deque<int>& d) 2. { 3. for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) { 4. cout << *it << " "; 5. 6. } 7. cout << endl; 8. } 9. 10. void test01() 11. { 12. 13. deque<int> d; 14. d.push_back(10); 15. d.push_back(20); 16. d.push_front(100); 17. d.push_front(200); 18. 19. printDeque(d); 20. sort(d.begin(), d.end()); 21. printDeque(d); 22. } 23. 24. int main() 25. { 26. test01(); 27. return 0; 28. }
总结：sort算法非常实用，使用时包含头文件 algorithm即可
