C++学习笔记_18 线性容器(vector_list_deque)总结 2021-05-18

1. //C++学习笔记_18 线性容器(vector_list_deque)总结
2. //
3. #include<iostream>
4. #include<string>
5. #include<vector>
6. #include<deque>
7. #include<list>
8. using namespace std;
9. void TestAll()
10. {
11. vector<int>  iVec({ 1, 2, 3, 4});
12.     vector<int>::iterator vIt;
13. 
14.     cout << "元素地址: ";
15. for (vIt = iVec.begin(); vIt != iVec.end(); vIt++){
16. //注意，这里先去 *  再去& 地址，不能 直接消掉 *vIt 是元素的引用
17.         cout << &(*vIt) << " ";
18.     }
19.     cout << endl;
20.     cout << "Capacity:" << iVec.capacity() << endl;
21. //vector 所有元素地址连续
22. 
23.     iVec.push_back(5);
24.     cout << "首元素地址：" << &(iVec.front()) << endl;
25.     cout << "Capacity:" << iVec.capacity() << endl;
26. //为什么后端插入元素，首元素地址会变？
27. //原来容量是 4 ，新插入一个元素，但是内存不够
28. //   ---》重新申请一片内存，复制原数据后，再做插入操作
29. 
30.     iVec.push_back(11);
31.     cout << "首元素地址：" << &(iVec.front()) << endl;
32.     cout << "Capacity:" << iVec.capacity() << endl;
33. //再插入元素，空间足够，则直接插入
34. 
35. //如果中间插入数据 ===》 插入点后的所有元素都会后移 (腾出位置)
36. 
37.     deque<int>  iDeq{ 1, 2, 3, 4, 5 };
38.     deque<int>::iterator dIt;
39. 
40.     cout << endl;
41.     cout << "元素地址: ";
42. for (dIt = iDeq.begin(); dIt != iDeq.end(); dIt++){
43.         cout << &(*dIt) << " ";
44.     }
45.     cout << endl;
46. 
47.     iDeq.push_back(11);
48.     cout << "元素地址: ";
49. for (dIt = iDeq.begin(); dIt != iDeq.end(); dIt++){
50.         cout << &(*dIt) << " ";
51.     }
52.     cout << endl;
53. //新申请了一片空间，并把 11 存在这个空间的开始位置
54. 
55.     iDeq.push_front(22);
56.     cout << "元素地址: ";
57. for (dIt = iDeq.begin(); dIt != iDeq.end(); dIt++){
58.         cout << &(*dIt) << " ";
59.     }
60.     cout << endl;
61. //新插入一个元素，如果第一个元素位置还有空间，直接放到第一个元素前面
62. //否则，新申请一片空间，并存在空间的最后
63. 
64. //deque 在中间插入数据。把插入点位置之前的元素前移 或者 把插入点后的元素后移
65. //      前移后者后移的判断原则： 保证移动的元素最少
66. 
67. list<int>  iList({ 1, 2, 3, 4, 5 });
68.     list<int>::iterator lIt;
69.     cout << endl << "元素地址: ";
70. for (lIt = iList.begin(); lIt != iList.end(); lIt++){
71.         cout << &(*lIt) << " ";
72.     }
73.     cout << endl;
74. //list 每个元素地址都不连续
75. //任意位置插入元素，都不涉及元素移动
76. }
77. 
78. //vector list deque 通用的 print 函数
79. template<template <typename, typename> class C, typename T>
80. void PrintC(const C<T, allocator<T>>  &tContainer)
81. {
82. typename C<T, allocator<T>>::const_iterator  it;
83. for (it = tContainer.begin(); it != tContainer.end(); it++){
84.         cout << *it << " ";
85.     }
86.     cout << endl;
87. }
88. 
89. void TestIterator()
90. {
91. //迭代器失效
92. vector<int> iVec({ 1, 2, 2, 3, 4, 5, 2, 6, 7 });
93.     vector<int>::iterator it;
94. //我们想删除 iVec中 值为 2  的元素
95. for (it = iVec.begin(); it != iVec.end(); ){
96. if (*it == 2){
97. //iVec.erase(it);
98. //为什么出错？ erase(it) 删除了这个节点，这个节点 ++ 就没有意义了
99. //解决办法： erase(it) 返回一个 迭代器，指向下一个节点
100.             it = iVec.erase(it);
101.         }
102. //为什么还有一个 2 没有删掉？因为一旦2后面还是2，会被it++调过去
103. //所以删掉2的时候，不要进行 it++,直接判断当前值是否为2
104. else  it++;
105.     }
106. PrintC(iVec);
107. 
108. //list，deque 同样存在这个问题
109. list<int> iList({ 1, 2, 3, 4, 5, 6 });
110.     list<int>::iterator lIt;
111. 
112.     lIt = ++iList.begin();
113.     lIt = iList.erase(lIt);
114.     cout << "list::lIt: " << *lIt << endl;
115. 
116. //插入元素也会导致迭代器失效
117.     iVec.assign({ 1, 2, 3, 4, 5, 6, 7, 8 });
118.     it = iVec.begin() + 2;
119.     cout << *it << endl;
120. 
121. 
122.     it = iVec.insert(it, 99); //迭代器新插入的元素，占用了原来元素的地址
123. //但是 它可能涉及重新申请内存，重新申请内存，迭代器指向的内存被释放了
124. // ---> 迭代器失效
125. //iVec.insert(it, 88);
126.     cout << *it << endl;
127. 
128. 
129.     iList.insert(lIt, 99); //list 插入元素，不会改变其它元素，lIt 这个迭代器指向的内存不变
130. //插入前后，迭代器指向的值是一样的(不失效)
131. //大部分情况下，我们插入一个元素，插入后要使用这个新插入元素的迭代器
132. //   --》 使用返回值： 返回新插入元素的迭代器
133.     lIt = iList.insert(lIt, 88);
134.     cout << "list::lIt: " << *lIt << endl;
135. 
136. 
137. deque<int> iDeq({ 1, 2, 3, 4, 5 });
138.     deque<int>::iterator dIt;
139. 
140.     dIt = iDeq.begin() + 1;
141.     cout << "deque::dIt: " << *dIt << endl;
142. 
143.     dIt = iDeq.insert(dIt, 99);
144. //中间插入元素，99 可能占用 插入点之前的元素位置（元素前移） -- dIt 指向的元素不变
145. //也有可能 占用 插入点位置(元素后移) --》dIt 指向了 99
146. //这样插入 dIt 的变化是不确定的
147. //也涉及申请空间 --》迭代器失效
148.     cout << "deque::dIt: " << *dIt << endl;
149. 
150. //总之：vector list deque 的 插入删除元素的时候，都需要考虑迭代器失效问题
151. //一般情况下，都 使用 迭代器 接受返回值
152. //  插入元素 --》返回新元素的迭代器
153. //  删除元素 --》返回下一个元素的迭代器
154. }
155. 
156. int main()
157. {
158. TestAll();
159. TestIterator();
160. system("pause");
161.  return 0;
162. }