• 【STL源码剖析】vector类模拟实现 了解底层-走进底层-掌握底层【超详细的注释和解释】


     

    今天博主继续带来STL源码剖析专栏的第二篇博客了!
    今天带来vector的模拟实现!
    其实在很多人学习C++过程中,都是只学习一些STL的使用方式,并不了解底层的实现。博主本人认为,这样的学习这样的技术是不深的。如果我们想要熟悉的掌握一门语言,我认为,底层的实现必不能少!
    但是,想从0开始模拟实现STL的容器,需要我们熟悉C++的语法,特别是类和对象部分的知识!
    博主学习C++到现在,我认为C++类和对象基本语法的学习比任何部分都要重要,而我花在这上面的时间也是最多的!只要搞清楚C++面向对象编程的基本规则,我们才能在STL的世界里游刃有余!
    所以我希望大家在学习STL之前,先将数据结构与算法,C++的类和对象部分内容掌握熟悉!


    前言

    那么这里博主先安利一下一些干货满满的专栏啦!

    手撕数据结构https://blog.csdn.net/yu_cblog/category_11490888.html?spm=1001.2014.3001.5482这里包含了博主很多的数据结构学习上的总结,每一篇都是超级用心编写的,有兴趣的伙伴们都支持一下吧!
    算法专栏https://blog.csdn.net/yu_cblog/category_11464817.html这里是STL源码剖析专栏,这个专栏将会持续更新STL各种容器的模拟实现。

    STL源码剖析https://blog.csdn.net/yu_cblog/category_11983210.html?spm=1001.2014.3001.5482


    实现过程中要注意的一些点

    vector类其实是我们非常常用的一个容器,其底层其实就是一个顺序表。

    博主在带大家实现的过程中,并不会把STL里面每一个成员函数都去模拟实现一次,我们模拟实现容器底层的目的其实是去学习里面实现的思路。

    因此,博主只会将一些重要、常用的成员函数模拟实现给大家。

    另外,除了博主实现的源代码之外,博主还提供一份测试代码,它可以帮助我们检查自己写的代码是否准确。

    在测试代码中遇到的问题和解决思路以及一些细节的处理,博主都在.h和.cpp代码里用注释的形式给大家说明白(注释满满干货不要错过噢)。

    希望大家可以从中学到知识。

    MyVector.h完整源代码

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6. namespace yufc {
    7. template<class T>
    8. class vector {
    9. public:
    10. typedef T* iterator;//这个要放成共有,不然迭代器外面访问不了 -- 定义迭代器类型是指针类型
    11. typedef const T* const_iterator;
    12. //vector的迭代器就是原生指针
    13. iterator begin() {
    14. return _start;
    15. }
    16. iterator end() {
    17. return _finish;
    18. }
    19. //如果不提供const迭代器 -- 如果传了const的vector是遍历不了的,因为权限不能放大
    20. const_iterator begin()const { //不能返回普通迭代器,要返回const迭代器
    21. return _start;
    22. }
    23. const_iterator end()const {
    24. return _finish;
    25. }
    26. vector() :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}
    27. ~vector() {
    28. delete[] _start;
    29. _start = _finish = _end_of_storage = nullptr;
    30. }
    31. //stl的vector还支持使用迭代器区间去构造
    32. //为什么需要一个其它类型的迭代器?
    33. //因为他要支持用其它容器的迭代器的区间构造
    34. template<class InputIterator>
    35. vector(InputIterator first, InputIterator last)
    36. :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
    37. {
    38. while (first != last) {
    39. //不能直接push_back(),直接push_back()会崩溃 -- 因为没有初始化 -- 野指针
    40. push_back(*first);
    41. ++first;
    42. }
    43. }
    44. vector(size_t n, const T& val = T())
    45. :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
    46. {
    47. //用n个值去构造
    48. reserve(n);
    49. for (size_t i = 0; i < n; i++) {
    50. push_back(val);
    51. }
    52. }
    53. //传统拷贝构造
    54. #if 0
    55. vector(const vector& v) {
    56. _start = new T[v.size()];//这里是给size还是capacity呢?STL没有要求
    57. //memcpy(_start, v._start, sizeof(T) * v.size());
    58. //解决vector>深拷贝的情况,memcpy不能帮助内层的自定义类型完成深拷贝,赋值可以(我们写好了自定义类型的赋值)
    59. for (size_t i = 0; i < v.size(); i++) {
    60. _start[i] = v._start[i];
    61. }
    62. _finish = _start + v.size();
    63. _end_of_storage = _start + v.size();//因为T[]里面给了size(),所以这里也应该是v.size()
    64. }
    65. #endif
    66. //写法2
    67. #if 0
    68. vector(const vector& v)
    69. :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
    70. {
    71. reserve(v.size());
    72. for (const auto& e : v) { //注意:这里拷贝过去一定要引用,不然又要拷贝了
    73. //写深拷贝自己还要调深拷贝 -- 肯定是会出问题的
    74. push_back(e);
    75. }
    76. //不需要去调整_finish,因为push_back()已经搞定了
    77. }
    78. #endif
    79. //现代写法拷贝构造 -- 复用迭代器区间构造函数
    80. void swap(vector& v) {
    81. std::swap(_start, v._start);
    82. std::swap(_finish, v._finish);
    83. std::swap(_end_of_storage, v._end_of_storage);
    84. }
    85. #if 1
    86. vector(const vector& v)
    87. :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
    88. {
    89. vectortmp(v.begin(), v.end());
    90. swap(tmp);//当然自定义类型自己写的swap更高效 -- 我们自己实现一个
    91. }
    92. #endif
    93. vector& operator=(vector v) { //v1=v2
    94. //v是v2的拷贝,而且是局部的,swap完之后给到v1,v还会自动析构(因为是局部对象)
    95. swap(v);
    96. return *this;
    97. }
    98. size_t capacity()const {
    99. return _end_of_storage - _start;
    100. }
    101. size_t size()const {
    102. return _finish - _start;
    103. }
    104. void reserve(size_t n) {
    105. if (n > capacity()) {
    106. T* tmp = new T[n];
    107. size_t sz = size();
    108. if (_start) {
    109. //memcpy(tmp, _start, sizeof(T) * sz);//拷贝size()个字节过去,先放到tmp里面
    110. //同样,解决
    111. //vector<自定义类型>的问题
    112. for (size_t i = 0; i < sz; i++) {
    113. tmp[i] = _start[i];//当T是自定义类型时,调用T类型的operator=
    114. }
    115. delete[] _start;
    116. }
    117. _start = tmp;
    118. //_finish = _start + size();//这里不要现场去算size()
    119. //因为size()是用start减出来的,上面那一行start已经变了
    120. //所以在前面我们最好保留一下size先
    121. _finish = _start + sz;
    122. _end_of_storage = _start + n;
    123. }
    124. }
    125. void resize(size_t n, const T& val = T()) {
    126. //1.扩容+初始化
    127. //2.初始化
    128. //3.删除数据
    129. if (n > capacity()) {
    130. reserve(n);
    131. }
    132. if (n > size()) {
    133. //初始化填值
    134. while (_finish < _start+n) {
    135. *_finish = val;
    136. ++_finish;
    137. }
    138. }
    139. else {
    140. _finish = _start + n;
    141. }
    142. }
    143. T& operator[](size_t pos) {
    144. assert(pos < size());
    145. return _start[pos];
    146. }
    147. const T& operator[](size_t pos) const {
    148. assert(pos < size());
    149. return _start[pos];
    150. }
    151. void push_back(const T& x) {
    152. //加了const保证传什么类型都行,因为隐式类型转换临时变量具有常性
    153. if (_finish == _end_of_storage) {
    154. reserve(capacity() == 0 ? 4 : capacity() * 2);
    155. }
    156. *_finish = x;
    157. ++_finish;
    158. }
    159. void pop_back() {
    160. assert(_finish > _start);//为空是不能删的
    161. --_finish;
    162. }
    163. void insert(iterator pos, const T& x) {
    164. assert(pos >= _start);
    165. assert(pos <= _finish);
    166. if (_finish == _end_of_storage) {//扩容
    167. //记住pos和start的相对位置
    168. size_t len = pos - _start;
    169. reserve(capacity() == 0 ? 4 : capacity() * 2);
    170. pos = _start + len;//更新pos的位置 -- 解决迭代器失效
    171. }
    172. //挪动数据
    173. iterator end = _finish - 1;
    174. while (end >= pos) { // insert要扩容的时候,这个循环就失效了,停不下来了,为什么?
    175. *(end + 1) = *end;
    176. end--;
    177. }
    178. //扩容之后,旧空间的数据拷贝到新空间
    179. //旧空间已经被释放了 -- pos是指向旧空间的一个数字的位置的
    180. //pos成了野指针! -- 迭代器失效
    181. //所以我们要把pos更新一下
    182. // -- 修改了内部的pos之后,其实问题还没有根本的解决
    183. *pos = x;
    184. ++_finish;
    185. }
    186. iterator erase(iterator pos) {
    187. assert(pos >= _start);
    188. assert(pos < _finish);
    189. //挪动覆盖删除
    190. iterator begin = pos + 1;
    191. while (begin < _finish) {
    192. *(begin - 1) = *begin;
    193. ++begin;
    194. }
    195. --_finish;
    196. //删除了位置的下一个位置 -- 还是pos
    197. return pos;
    198. }
    199. T& front() {
    200. assert(size() > 0);
    201. return *_start;
    202. }
    203. T& back() {
    204. assert(size() > 0);
    205. return *(_finish - 1);
    206. }
    207. private:
    208. iterator _start;//start相当于整个数组的开始位置
    209. iterator _finish;//[_start,_finish)
    210. iterator _end_of_storage;
    211. };
    212. }

     test.cpp测试源文件完整代码

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"MyVector.h"
    3. #include
    4. #include
    5. using namespace std;
    6. void PrintVector(yufc::vector<int>& v) {//在没有写拷贝构造的时候,这里一定要引用的,不然浅拷贝,释放两次会出问题
    7. yufc::vector<int>::iterator it = v.begin();
    8. while (it != v.end()) {
    9. cout << *it << " ";
    10. it++;
    11. }
    12. cout << endl;
    13. }
    14. void PrintVector(const yufc::vector<int>& v) {
    15. yufc::vector<int>::const_iterator it = v.begin();
    16. while (it != v.end()) {
    17. cout << *it << " ";
    18. it++;
    19. }
    20. cout << endl;
    21. }
    22. void test_vector1() {
    23. yufc::vector<int>v;
    24. v.push_back(1);
    25. v.push_back(2);
    26. v.push_back(3);
    27. v.push_back(4);
    28. v.push_back(5);
    29. v.push_back(6);
    30. for (int i = 0; i < v.size(); i++) {
    31. ++v[i];
    32. cout << v[i] << " ";
    33. }
    34. cout << endl;
    35. }
    36. void test_vector2() {
    37. yufc::vector<int>v;
    38. v.push_back(1);
    39. v.push_back(2);
    40. v.push_back(3);
    41. v.push_back(4);
    42. v.push_back(5);
    43. v.push_back(6);
    44. yufc::vector<int>::iterator it = v.begin();
    45. while (it != v.end()) {
    46. (*it)--;
    47. cout << *it << " ";
    48. it++;
    49. }
    50. cout << endl;
    51. for (auto& e : v) {
    52. e++;
    53. cout << e << " ";
    54. }
    55. cout << endl;
    56. it = v.begin();
    57. while (it != v.end()) {
    58. cout << *it << " ";
    59. it++;
    60. }
    61. cout << endl;
    62. PrintVector(v);
    63. }
    64. void test_vector3() {
    65. const yufc::vector<int>v;
    66. #if 0 //改不了的
    67. v.push_back(1);
    68. v.push_back(2);
    69. v.push_back(3);
    70. v.push_back(4);
    71. v.push_back(5);
    72. v.push_back(6);
    73. #endif
    74. PrintVector(v);
    75. //范围for虽然是傻瓜式的替换 -- 但是它也是会调用const迭代器的
    76. }
    77. //迭代器失效问题
    78. void test_vector4() {
    79. yufc::vector<int>v;
    80. v.push_back(1);
    81. v.push_back(2);
    82. v.push_back(3);
    83. v.push_back(4);
    84. //v.push_back(5); // 我们发现 -- 原来4个数据,insert之后要扩容的时候,就出现问题了!
    85. //v.push_back(6);
    86. yufc::vector<int>::iterator it = v.begin();
    87. while (it != v.end()) {
    88. cout << *it << " ";
    89. it++;
    90. }
    91. cout << endl;
    92. //
    93. auto p = find(v.begin(), v.end(), 3);
    94. if (p != v.end()) {
    95. v.insert(p, 30);
    96. //在内部初步解决迭代器失效之后,其实问题还是没有根本解决!
    97. //因为内部的pos更新不会影响p
    98. //所以我们在使用的时候
    99. //在p位置插入数据以后,不要访问p,因为p可能失效了
    100. //因为我们使用STL的时候,不了解底层的扩容机制,所以以后我们insert之后,不要去访问p位置! -- 可能会有问题
    101. //那能否把insert第一个参数改成&行吗? -- 尽量不要这样做 -- 和库保持一致好
    102. //虽然我们看似解决了问题 -- 但是改了可能会引出其它问题 -- 比如,头插,我们想传v.begin();v.insert(v.begin(), 0);
    103. //编不过,因为类型不匹配
    104. #if 0
    105. cout << *p << endl;
    106. v.insert(p, 40);
    107. #endif
    108. }
    109. PrintVector(v);
    110. }
    111. //erase迭代器会失效吗?
    112. //库里面的erase会失效吗? -- 不知道
    113. //STL并没有规定什么机制
    114. //有没有一种可能,当size()
    115. //反正用完那个别访问,别动那个p就行了!
    116. void test_vector5() {
    117. yufc::vector<int>v;
    118. v.push_back(1);
    119. v.push_back(2);
    120. v.push_back(3);
    121. v.push_back(4);
    122. auto p = find(v.begin(), v.end(), 3);
    123. if (p != v.end()) {
    124. v.erase(p);
    125. }
    126. PrintVector(v);
    127. }
    128. void test_vector6() {
    129. yufc::vector<int>v;
    130. #if 0
    131. v.push_back(1);
    132. v.push_back(2);
    133. v.push_back(3);
    134. v.push_back(4);
    135. v.push_back(5);
    136. #endif
    137. //情况1和2
    138. //我们发现此时有这个5 -- 程序正常,没有 -- 崩溃
    139. #if 1
    140. //情况3
    141. v.push_back(1);
    142. v.push_back(2);
    143. v.push_back(2);
    144. v.push_back(3);
    145. v.push_back(4);
    146. v.push_back(5);
    147. #endif
    148. //要求删除所有的偶数
    149. auto it = v.begin();
    150. //情况3的时候,it会跳过end(),直接继续往后了 -- 崩溃
    151. //所以下面这段算法是不正确的!
    152. //其实我们看源代码可以发现 -- erase是有返回值的 -- 会更新一下迭代器
    153. //STL规定erase返回删除位置下一个位置的迭代器!
    154. //vs这个编译器是查的很严格的 -- erase之后不允许去访问! -- 访问就报错
    155. //Linux下就不同
    156. while (it != v.end()) {
    157. if (*it % 2 == 0) {
    158. it = v.erase(it);//我们要返回一个it才行
    159. }
    160. else {
    161. ++it;
    162. }
    163. }
    164. PrintVector(v);
    165. }
    166. //总结
    167. //其实迭代器失效,我们在自己做OJ的时候也能体会的,插入或者删除之后,迭代器指向了它不该指向的地方
    168. //在使用vector的迭代器的时候,要多调试!
    169. void test_vector7() {
    170. //系统默认的拷贝
    171. //1.自定义类型 -- 调拷贝构造 -- 默认生成的 -- 浅拷贝
    172. //2.内置类型 -- 值拷贝 -- 浅拷贝
    173. yufc::vector<int>arr;
    174. arr.push_back(1);
    175. arr.push_back(2);
    176. arr.push_back(3);
    177. for (auto i : arr) {
    178. cout << i << " ";
    179. }
    180. cout << endl;
    181. yufc::vector<int>arr2 = arr;
    182. //调用系统默认的话就是浅拷贝,这样程序肯定会崩溃的 -- 析构了两次
    183. //而且如果是浅拷贝,改一边的值另一边也会被改变
    184. arr2[0] = 100; //两边都会被改变的 -- 所以我们需要深拷贝!
    185. for (auto i : arr) {
    186. cout << i << " ";
    187. }
    188. cout << endl;
    189. for (auto i : arr2) {
    190. cout << i << " ";
    191. }
    192. }
    193. void test_vector8() {
    194. string s("hell");
    195. yufc::vector<int>vs(s.begin(), s.end());
    196. for (auto i : vs) {
    197. cout << i << " ";
    198. }
    199. cout << endl;
    200. //赋值
    201. yufc::vector<int>v;
    202. v.push_back(1);
    203. v.push_back(2);
    204. v.push_back(3);
    205. v.push_back(4);
    206. v.push_back(5);
    207. v.push_back(1);
    208. v.push_back(2);
    209. v.push_back(3);
    210. v.push_back(4);
    211. vs = v;//要实现一个深拷贝
    212. //当然,如果f11 -- 这里是先进去拷贝的,因为传参要拷贝
    213. //走完拷贝就进去赋值了
    214. for (auto i : vs) {
    215. cout << i << " ";
    216. }
    217. }
    218. //其实内置类型也有构造
    219. void test_type() {
    220. int i = 0;
    221. int j = int();
    222. int k = int(10);
    223. }
    224. void test_vector9() {
    225. //vectorv = { 1,2,3,4,5 };
    226. vector<int>v(10);
    227. yufc::vector<int>v(10, 1);//这样就报错了,如果传了两个参数都是int
    228. //这里出问题就是匹配问题,它匹配到不该去的地方去了
    229. //为什么 -- 因为迭代器区间构造那个函数,更适合这样传参 -- 所以进到那里去了
    230. //解决:
    231. //1.传参的时候写(10u,1)表示这个是个usigned int类型
    232. //2.把vector(size_t n,const T&val=T())里面的size_t改成int,也可以解决 -- 但是stl官方给的是size_t
    233. //3.复制一份,改成int,弄个重载就行 -- stl_3.0是这样解决的
    234. for (auto i : v) {
    235. cout << i << " ";
    236. }
    237. cout << endl;
    238. }
    239. void test_vector10() {
    240. yufc::vector<int>v;
    241. v.resize(10, 1);
    242. for (auto e : v) {
    243. cout << e << " ";
    244. }
    245. cout << endl;
    246. yufc::vector<int>v1;
    247. v1.reserve(10);
    248. v1.push_back(1);
    249. v1.push_back(2);
    250. v1.push_back(3);
    251. v1.push_back(4);
    252. v1.resize(8, 8);
    253. for (auto e : v1) {
    254. cout << e << " ";
    255. }
    256. cout << endl;
    257. v1.resize(20, 20);
    258. for (auto e : v1) {
    259. cout << e << " ";
    260. }
    261. cout << endl;
    262. v1.resize(3);
    263. for (auto e : v1) {
    264. cout << e << " ";
    265. }
    266. cout << endl;
    267. }
    268. //vector到目前为止还有最后一个坑还没有解决
    269. //我们用自己的vector测试一下杨辉三角
    270. class Solution {
    271. public:
    272. yufc::vectorint>> generate(int numRows) {
    273. yufc::vectorint>> ret(numRows);
    274. for (int i = 0; i < numRows; ++i) {
    275. ret[i].resize(i + 1);
    276. ret[i][0] = ret[i][i] = 1;
    277. for (int j = 1; j < i; ++j) {
    278. ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
    279. }
    280. }
    281. return ret;
    282. }
    283. };
    284. void test_vector11() {
    285. Solution().generate(10);
    286. //报错 -- 在函数结束的时候崩溃了
    287. //修改一下 -- 把函数改成void类型,不return -- 没事了
    288. //为什么?
    289. //拷贝有问题了 -- 普通的vector深拷贝没问题 -- 这里的深拷贝有问题
    290. //里面是浅拷贝,外面是深拷贝
    291. // // //即:我们的vector是深拷贝了 -- 但是里面的自定义类型没有深拷贝!!!!!!!!!!
    292. //我们拷贝的时候,外面的空间是深拷贝,但是里面的东西,还是指向以前的地方
    293. //传统写法是因为memcpy导致的 -- 我们将memcpy改成一个一个赋值就行了(这样的话自定义类型也可以完成深拷贝(调用自己的deepcopy))
    294. //现代写法是因为因为要调用push_back(),而push_back()里面调用reserve(),是reserve()里面的memcpy出问题
    295. }
    296. int main() {
    297. //test_vector1();
    298. //test_vector2();
    299. //test_vector3();
    300. //test_vector4();
    301. //test_vector5();
    302. //test_vector6();
    303. //test_vector7();
    304. //test_vector8();
    305. //test_type();
    306. //test_vector9();
    307. //test_vector10();
    308. test_vector11();
    309. return 0;
    310. }
    311. //我们一定要清晰一个点:
    312. //STL只是一个规范
    313. //这个规范怎么去实现,是没有规定的!
    314. //VS-PJ版 g++ SGI版

    尾声

    看到这里,相信大家对vector类的模拟实现已经有一定的了解了!vector的模拟实现,是我们掌握STL的开始,后面,博主将会给大家带来list,stack等等STL容器的模拟实现,持续关注,订阅专栏,点赞收藏都是我创作的最大动力。

    转载时请注明作者和出处。未经许可,请勿用于商业用途 )
    更多文章请访问我的主页

    @背包https://blog.csdn.net/Yu_Cblog?spm=1000.2115.3001.5343

  • 相关阅读:
    【Flutter 面试题】什么是异步编程 Flutter中如何处理异步操作?
    Leetcode算法入门与数组丨2. LeetCode入门
    中国地表水体、大坝、水库和湖泊数据集
    Java开发快递物流项目
    基于复合优化加速算法研究实际问题
    全国机动车达4.3亿辆 驾驶人达5.2亿人 新能源汽车保有量达1821万辆
    Excel函数2
    什么专业最适合学网络安全?一篇文章告诉你
    商城积分系统的设计方案(上)-- 需求分析
    Redis的常用命令&集群节点管理
  • 原文地址:https://blog.csdn.net/Yu_Cblog/article/details/126930337