046-C++之STL-->deque

moc

1、deque简介
deque是双端队列（double ended queue）的缩写，不论在尾部或头部插入元素，都十分迅速。而在中间插入元素则会比较费时，因为必须移动中间其他的元素。
双端队列是一种随机访问的数据类型，提供了在序列两端快速插入和删除操作的功能，它可以在需要的时候改变自身大小。
vector与deque的对比：
        Vector是单向开口的连续线性空间，deque则是一种双向开口的连续线性空间。
        deque对象在队列的两端放置元素和删除元素是高效的，而向量vector只是在插入序列的末尾时操作才是高效的。
        deque允许于常数时间内对头端进行元素的插入或移除操作，没有所谓的capacity观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。
        vector则采用动态申请内存空间，会为新元素预留空间，因此旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间，这样的事情在deque中是不会发生的。  
        deque迭代器并不是普通指针，其复杂度和vector不可同日而语，这当然涉及到各个运算层面。因此，除非必要，我们应尽可能选择使用vector而非deque。
        deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector身上，将vector排序后（利用STL的sort算法），再复制回deque。
deque是一种优化了的对序列两端元素进行添加和删除操作的基本序列容器。通常由一些独立的区块组成，第一区块朝某方向扩展，最后一个区块朝另一方向扩展。它允许较为快速地随机访问但它不像vector一样把所有对象保存在一个连续的内存块，而是多个连续的内存块。并且在一个映射结构中保存对这些块以及顺序的跟踪。

2、deque构造函数

1. deque<int> c;        // 默认构造函数 创建一个空的deque                         
   
2. deque<int> c1(c);    //拷贝构造
   
3. deque<int> c2 = c1;  //拷贝构造
   
4. deque<int> c3(5, 6); //指定元素个数创建,创建5个6
   
5. deque<int> c4(c3.begin() + 2, c3.begin() + 3);   // 指定区间创建
   
6. deque<int> c5({ 2,3,4,5 });        // 指定初始化列表创建
   
7. deque<int> c6 = { 2,3,4,5 };       // 指定初始化列表创建

复制代码

3、deque操作

1. deque<int> c = { 1,2,3,4,5 };
   
2. deque<int> c1;
   
3. 
   
4. // 赋值初始化
   
5. c1.assign(c.begin(), c.end());
   
6. for (auto i : c1) {
   
7.         cout << i << ",";
   
8. }
   
9. cout << "assign()" << endl;
   
10. 
    
11. //在尾部插入
    
12. c1.push_back(6);
    
13. for (auto i : c1) {
    
14.         cout << i << ",";
    
15. }
    
16. cout << "push_back()" << endl;
    
17. 
    
18. //头插入
    
19. c1.push_front(0);
    
20. for (auto i : c1) {
    
21.         cout << i << ",";
    
22. }
    
23. cout << "push_front()" << endl;
    
24. 
    
25. //弹尾元素
    
26. c1.pop_back();
    
27. for (auto i : c1) {
    
28.         cout << i << ",";
    
29. }
    
30. cout << "pop_back()" << endl;
    
31. 
    
32. //弹头元素
    
33. c1.pop_front();
    
34. for (auto i : c1) {
    
35.         cout << i << ",";
    
36. }
    
37. cout << "pop_front()" << endl;
    
38. 
    
39. //指定位置插入元素
    
40. c1.insert(c1.begin() + 3, 10);
    
41. for (auto i : c1) {
    
42.         cout << i << ",";
    
43. }
    
44. cout << "insert()" << endl;
    
45. 
    
46. //删除指定位置元素
    
47. c1.erase(c1.begin() + 3);
    
48. for (auto i : c1) {
    
49.         cout << i << ",";
    
50. }
    
51. cout << "erase()" << endl;
    
52. 
    
53. //清空deque
    
54. c.clear();
    
55. for (auto i : c) {
    
56.         cout << i << ",";
    
57. }
    
58. cout << "clear()" << endl;
    
59. 
    
60. //构造
    
61. c1.emplace(c1.end(), 100);
    
62. for (auto i : c1) {
    
63.         cout << i << ",";
    
64. }
    
65. cout << "emplace()" << endl;
    
66. 
    
67. //头位置插入元素
    
68. c1.emplace_front(111);
    
69. for (auto i : c1) {
    
70.         cout << i << ",";
    
71. }
    
72. cout << "emplace_front()" << endl;
    
73. 
    
74. //尾位置插入元素
    
75. c1.emplace_back(111);
    
76. for (auto i : c1) {
    
77.         cout << i << ",";
    
78. }
    
79. cout << "emplace_back()" << endl;
    
80. 
    
81. //交换
    
82. c.swap(c1);
    
83. for (auto i : c) {
    
84.         cout << i << ",";
    
85. }
    
86. cout << "swap()" << endl;
    
87. 
    
88. int tmp;
    
89. tmp = c.front();
    
90. cout << "第一个元素" << tmp << endl;
    
91. 
    
92. tmp = c.back();
    
93. cout << "最后一个元素" << tmp << endl;
    
94. 
    
95. tmp = c.at(1);
    
96. cout << "指定下标元素" << tmp << endl;
    
97. 
    
98. tmp = c[1];
    
99. cout << "指定[]下标元素" << tmp << endl;
    
100. 
     
101. // vector的迭代器遍历     //begin指向头元素， end指向最后一个元素的后面
     
102. for (vector<int>::iterator it = v4.begin(); it != v4.end(); it++)
     
103. {
     
104.         cout << *it << " ";
     
105. }
     
106. cout << endl;
     
107. // vector的逆向迭代器遍历
     
108. for (vector<int>::reverse_iterator rit = v4.rbegin(); rit != v4.rend(); rit++)
     
109. {
     
110.         cout << *rit << " ";
     
111. }
     
112. 
     
113. // 区间删除操作
     
114. v4.erase(v4.begin(), v4.begin() + 3);
     
115. v4.erase(v4.begin());
     
116. cout << endl;
     
117. for (vector<int>::iterator it = v4.begin(); it != v4.end(); it++)
     
118. {cout << *it << " ";}
     
119. cout << endl;
     
120. // 删除指定值的元素
     
121. for (vector<int>::iterator it = v4.begin(); it != v4.end();)
     
122. {
     
123.         if (*it == 7)
     
124.         {
     
125.                 it = v4.erase(it); // 当删除迭代器所指向元素的时候，erase操作会让it自动下移
     
126.         }
     
127.         else
     
128.         {
     
129.                 it++;
     
130.         }       
     
131. }
     
132. for (vector<int>::iterator it = v4.begin(); it != v4.end(); it++)
     
133. {cout << *it << " ";}
     
134. cout << endl;
     
135. 
     
136. // 插入元素
     
137. v4.insert(v4.begin(), 111);
     
138. v4.insert(v4.end(), 222);
     
139. for (vector<int>::iterator it = v4.begin(); it != v4.end(); it++)
     
140. {cout << *it << " ";}

复制代码

4、deque的一些特点
1. 支持随机访问，即支持[ ]以及at()，但是性能没有vector好。
2. 可以在内部进行插入和删除操作，但性能不及list。
3. deque两端都能够快速插入和删除元素，而vector只能在尾端进行。
4. deque的元素存取和迭代器操作会稍微慢一些，因为deque的内部结构会多一个间接过程。
5. deque迭代器是特殊的智能指针，而不是一般指针，它需要在不同的区块之间跳转。
6. deque可以包含更多的元素，其max_size可能更大，因为不止使用一块内存。
7. deque不支持对容量和内存分配时机的控制。
8. 在除了首尾两端的其他地方插入和删除元素，都将会导致指向deque元素的任何pointers、references、iterators失效。不过，deque的内存重分配优于vector，因为其内部结构显示不需要复制所有元素。
9. deque的内存区块不再被使用时，会被释放，deque的内存大小是可缩减的。不过，是不是这么做以及怎么做由实际操作版本定义。
10. deque不提供容量操作：capacity()和reverse()，但是vector可以。