• 【C++】vector的模拟实现


    目录

    前言:vector的简单介绍

     一、Member variables

    二、Iterators

    三、Capacity

    1、size

    2、capacity

    3、reserve

    4、resize

    四、Modifiers

    1、push_back

    2、pop_back()

    3、insert

    4、erase

    5、swap

    六、Element access

    1、[ ]操作符重载

    2、front

    3、back

    七、Member functions

    1、构造函数

    (1)无参构造

    (2)迭代器区

    (3)拷贝构造

    (4)用n个元素构造

    2、析构函数

    3、=操作符重载

    八、完整代码

    总结


    前言:vector的简单介绍

    vector是STL中特别常用的容器,它能够给我们提供类似于C语言的数组的用法,[ ]是它最常用的遍历方式

    它具有多个构造函数 

    在后面我们会一一实现

    vector是一个模板类,类中的元素可以是任意数据类型,最常用的就是二维数组vector> 最外层的vector的每个元素都是vector类型,内部的vector的每个元素的数据类型是int,这种结构使用起来就特别像C语言的二维数组

    vector的其它成员函数,与string中的类似,就不一一赘述了。

    文章目录参考:https://cplusplus.com


     一、Member variables

    vector的成员变量与string不一样,它的成员变量都是迭代器,因为vector的空间是连续的,所以它的迭代器是原生指针。

     

    它的基本构造是这样的,也就是说它有三个成员变量,_start ,_finish, _end_of_storage

    我们再看看stl源码是怎样写的

     

    与我们的猜想一致 

    二、Iterators

    迭代器,我们前面说过,它就是原生指针,那么就比较简单了,它的迭代器的写法与string的差不多

    1. typedef T* iterator;
    2. typedef const T* const_iterator;

    因为vector是模板类,所以它的迭代器就是T*的指针

    1. iterator begin()
    2. {
    3. return _start;
    4. }
    5. const_iterator begin()const
    6. {
    7. return _start;
    8. }
    9. iterator end()
    10. {
    11. return _finish;
    12. }
    13. const_iterator end()const
    14. {
    15. return _finish;
    16. }

    这些都是最基本的内容

    三、Capacity

    这里面一共实现了四个成员函数

    1、size

    size就是_finish减去_start就是vector的size

    1. const size_t size()const
    2. {
    3. return _finish - _start;
    4. }

    2、capacity

    capacity是_end_of_storage 减去_start

    1. const size_t capacity()const
    2. {
    3. return _end_of_storage - _start;
    4. }

    3、reserve

    resize与string的类似,都是先开辟空间,拷贝数据,释放旧空间,调整_start,_finish,_end_of_storage

    不过这里有两个要点需要注意,这里是vector它的成员变量是指针,我们开辟空间之后只会把_start的值更改为新空间的起始地址,但是_finish和_end_of_storage需要我们手动的修改

    而如何求出_finish在新空间的位置呢?

    很简单,我们只需要记录_finish和_start之间的偏移量就可以了,开辟新空间后偏移量加上_start就是_finish的位置,而end_of_storage的位置也就好办了,因为我们开辟空间开辟的是n个元素的空间,偏移量就是n,end_of_storage就是_start加上n

    另外一个注意点就是拷贝数据,对于像string这样的类来说拷贝数据十分的简单,因为它的元素的类型是固定的就是char,我们直接strcpy就能够拷贝,但是vector的数据类型是不确定的,如果直接使用strcpy或者是memcpy很容易造成浅拷贝,如果是vector>这样的类型呢?

    因此我们不能这样做,我们需要手动赋值,而手动赋值就需要我们实现T这个vector的变量类型的赋值=操作符重载(如果不是内置类型)

    1. //扩容,为了兼容T是自定义类型,为了实现深拷贝,不使用memcpy
    2. void reserve(size_t n)
    3. {
    4. if(n > capacity())
    5. {
    6. size_t len = _finish - _start;
    7. T* tmp = new T[n];
    8. if(_start)
    9. {
    10. //拷贝数据,为了实现深拷贝,不使用memcpy
    11. for(size_t i = 0; i < len; i++)
    12. {
    13. tmp[i] = _start[i];
    14. }
    15. delete[] _start;
    16. }
    17. _start = tmp;
    18. _finish = _start + len;
    19. _end_of_storage = _start + n;
    20. }
    21. }

    4、resize

    resize与reserve类似,在reserve的基础上加入了初始化,缩容等

    resize分为三种情况:

    1、n > capacity  扩容+初始化

    2、n > size 初始化

    3、n < size 缩容

    缩容十分的简单,我们直接将_finish减小就可以了

    剩下的就没有什么要点了

    1. //三种情况,比capacity()大,在size()和capacity之间,比size()小
    2. void resize(size_t n, const T& val = T())
    3. {
    4. if(n > capacity())
    5. {
    6. reserve(n);
    7. }
    8. //初始化
    9. if(n > size())
    10. {
    11. while(_finish < _start + n)
    12. {
    13. *_finish = val;
    14. _finish++;
    15. }
    16. }
    17. else
    18. {
    19. _finish = _start + n;
    20. }
    21. }

    四、Modifiers

    1、push_back

    尾插,与我们前面所学过的数据结构和string的大体相差不大

    检查容量,插入元素,size++

    1. //使用cosnt &为了能够传临时对象
    2. void push_back(const T& x)
    3. {
    4. if(_finish == _end_of_storage)
    5. {
    6. reserve(capacity() == 0 ? 4 : capacity() * 2);
    7. }
    8. *_finish = x;
    9. _finish++;
    10. }

    2、pop_back()

    _finish直接向前挪动一位就可以了

    1. void pop_back()
    2. {
    3. assert(size() > 0);
    4. _finish--;
    5. }

    3、insert

    insert要注意的问题就比较多了,它会出现迭代器失效的问题,

    它的大体框架与string的insert没有什么差别

    不过vector的insert要传入的是插入位置的iterator,与string的不同,string传入的是下标

    因为C++并没有对标realloc的操作符,导致我们只能new一块新空间然后将数据拷贝,但是这就会导致pos位置失效,因为pos指向的是原空间,但是我们是先扩容再插入,所以我们就需要手动修正pos位置,修正的过程与前面的reserve类似,先记录偏移量,然后与空间起始位置相加

    1. //返回值是iterator 返回的是最近一次插入的元素位置
    2. iterator insert(iterator pos, const T& x)
    3. {
    4. assert(pos >= _start);
    5. assert(pos <= _finish);
    6. if(_finish == _end_of_storage)
    7. {
    8. //修正pos的位置
    9. size_t len = pos - _start;
    10. reserve(capacity() == 0 ? 4 : capacity() * 2);
    11. pos = _start + len;
    12. }
    13. iterator end = _finish - 1;//是地址,怎末写都无所谓
    14. while(end >= pos)
    15. {
    16. *(end + 1) = *end;
    17. end--;
    18. }
    19. *pos = x;
    20. _finish++;
    21. return pos;
    22. }

    4、erase

    erase会不会发生迭代器失效呢?

    答案是不确定的:因为STL只是一个规范,他没有要求具体的实现细节,如果会出现迭代器失效,那么可能它的底层实现了缩容,如果没有失效可能没有缩容。

    eraser实现与string类似都是将需要删除的数据位置,那后面的数据覆盖,这里面就不用担心浅拷贝的问题,因为只要T实现了深拷贝,我们直接调用它的=操作符重载就可以了

    1. //返回值同理,删除元素的下一个位置
    2. iterator erase(iterator pos)
    3. {
    4. assert(pos >= _start);
    5. assert(pos < _finish);
    6. iterator begin = pos + 1;
    7. while(begin < _finish)
    8. {
    9. *begin = *(begin - 1);
    10. begin++;
    11. }
    12. return pos;
    13. }

    5、swap

    这里实现的swap与std里面的swap功能相同,不过效率不同,std里面的swap使用了拷贝构造

    同时这里面的swap是为了拷贝构造和=操作符重载的现代写法打基础

    1. void swap(vector& v)
    2. {
    3. std::swap(_start, v._start);
    4. std::swap(_finish, v._finish);
    5. std::swap(_end_of_storage, v._end_of_storage);
    6. }

    六、Element access

    这里就十分的简单了

    1、[ ]操作符重载

    1. T& operator[](size_t pos)
    2. {
    3. assert(pos < size());
    4. return _start[pos];
    5. }
    6. const T& operator[](size_t pos)const
    7. {
    8. assert(pos < size());
    9. return _start[pos];
    10. }

    2、front

    1. T& front()
    2. {
    3. assert(size() > 0);
    4. return *_start;
    5. }

    3、back

    1. T& back()
    2. {
    3. assert(size() > 0);
    4. return *(_finish - 1);
    5. }

    七、Member functions

    终于来到了最后

    1、构造函数

    (1)无参构造

    无参构造直接将所有的成员变量置为nullptr

    1. //无参构造
    2. vector()
    3. :_start(nullptr)
    4. ,_finish(nullptr)
    5. ,_end_of_storage(nullptr)
    6. {}

    (2)迭代器区

    迭代器区间构造就需要我们再定义一套模板参数,因为vector可以拿别的容器的迭代器区间来构造

    1. //构造函数,用其它容器的迭代器来构造
    2. template<class InputIterator>
    3. vector(InputIterator first, InputIterator last)
    4. :_start(nullptr)
    5. ,_finish(nullptr)
    6. ,_end_of_storage(nullptr)
    7. {
    8. while(first != last)
    9. {
    10. push_back(*first);
    11. first++;
    12. }
    13. }

    (3)拷贝构造

    我们直接使用现代写法,直接与形参交换数据

    1. //拷贝构造,现代写法
    2. vector(const vector& v)
    3. :_start(nullptr)
    4. ,_finish(nullptr)
    5. ,_end_of_storage(nullptr)
    6. {
    7. vector tmp(v.begin(), v.end());
    8. swap(tmp);
    9. }

    (4)用n个元素构造

    这里面比较复杂,我们需要重载多个这种函数来实现,因为如果直接只有一种参数是size_t,那么传入两个int类型的参数时就会被前面的迭代器区间的构造函数调用,造成非法的间接寻址的错误,因为前面的构造函数的参数比size_t这个函数的参数更加吻合,为了应对这种情况,所以使用了多个重载

    这是库中的实现也是多个构造函数重载

    1. vector(int n, const T& value)
    2. :_start(nullptr)
    3. ,_finish(nullptr)
    4. ,_end_of_storage(nullptr)
    5. {
    6. for(int i = 0; i < n; i++)
    7. {
    8. push_back(value);
    9. }
    10. }
    11. vector(long n, const T& value)
    12. :_start(nullptr)
    13. ,_finish(nullptr)
    14. ,_end_of_storage(nullptr)
    15. {
    16. for(long i = 0; i < n; i++)
    17. {
    18. push_back(value);
    19. }
    20. }
    21. vector(size_t n, const T& value = T())
    22. :_start(nullptr)
    23. ,_finish(nullptr)
    24. ,_end_of_storage(nullptr)
    25. {
    26. for(size_t i = 0; i < n; i++)
    27. {
    28. push_back(value);
    29. }
    30. }

     

    2、析构函数

    1. ~vector()
    2. {
    3. delete[] _start;
    4. _start = _finish = _end_of_storage = nullptr;
    5. }

    3、=操作符重载

    1. //赋值=重载
    2. vector& operator=(vector v)
    3. {
    4. swap(v);
    5. return *this;
    6. }

    八、完整代码

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6. namespace ww
    7. {
    8. template<class T>
    9. class vector
    10. {
    11. typedef T* iterator;
    12. typedef const T* const_iterator;
    13. public:
    14. //无参构造
    15. vector()
    16. :_start(nullptr)
    17. ,_finish(nullptr)
    18. ,_end_of_storage(nullptr)
    19. {}
    20. const size_t size()const
    21. {
    22. return _finish - _start;
    23. }
    24. const size_t capacity()const
    25. {
    26. return _end_of_storage - _start;
    27. }
    28. iterator begin()
    29. {
    30. return _start;
    31. }
    32. const_iterator begin()const
    33. {
    34. return _start;
    35. }
    36. iterator end()
    37. {
    38. return _finish;
    39. }
    40. const_iterator end()const
    41. {
    42. return _finish;
    43. }
    44. ~vector()
    45. {
    46. delete[] _start;
    47. _start = _finish = _end_of_storage = nullptr;
    48. }
    49. T& operator[](size_t pos)
    50. {
    51. assert(pos < size());
    52. return _start[pos];
    53. }
    54. const T& operator[](size_t pos)const
    55. {
    56. assert(pos < size());
    57. return _start[pos];
    58. }
    59. //扩容,为了兼容T是自定义类型,为了实现深拷贝,不使用memcpy
    60. void reserve(size_t n)
    61. {
    62. if(n > capacity())
    63. {
    64. size_t len = _finish - _start;
    65. T* tmp = new T[n];
    66. if(_start)
    67. {
    68. //拷贝数据,为了实现深拷贝,不使用memcpy
    69. for(size_t i = 0; i < len; i++)
    70. {
    71. tmp[i] = _start[i];
    72. }
    73. delete[] _start;
    74. }
    75. _start = tmp;
    76. _finish = _start + len;
    77. _end_of_storage = _start + n;
    78. }
    79. }
    80. //使用cosnt &为了能够传临时对象
    81. void push_back(const T& x)
    82. {
    83. if(_finish == _end_of_storage)
    84. {
    85. reserve(capacity() == 0 ? 4 : capacity() * 2);
    86. }
    87. *_finish = x;
    88. _finish++;
    89. }
    90. void pop_back()
    91. {
    92. assert(size() > 0);
    93. _finish--;
    94. }
    95. //构造函数,用其它容器的迭代器来构造
    96. template<class InputIterator>
    97. vector(InputIterator first, InputIterator last)
    98. :_start(nullptr)
    99. ,_finish(nullptr)
    100. ,_end_of_storage(nullptr)
    101. {
    102. while(first != last)
    103. {
    104. push_back(*first);
    105. first++;
    106. }
    107. }
    108. void swap(vector& v)
    109. {
    110. std::swap(_start, v._start);
    111. std::swap(_finish, v._finish);
    112. std::swap(_end_of_storage, v._end_of_storage);
    113. }
    114. //拷贝构造,现代写法
    115. vector(const vector& v)
    116. :_start(nullptr)
    117. ,_finish(nullptr)
    118. ,_end_of_storage(nullptr)
    119. {
    120. vector tmp(v.begin(), v.end());
    121. swap(tmp);
    122. }
    123. //赋值=重载
    124. vector& operator=(vector v)
    125. {
    126. swap(v);
    127. return *this;
    128. }
    129. vector(int n, const T& value)
    130. :_start(nullptr)
    131. ,_finish(nullptr)
    132. ,_end_of_storage(nullptr)
    133. {
    134. for(int i = 0; i < n; i++)
    135. {
    136. push_back(value);
    137. }
    138. }
    139. vector(long n, const T& value)
    140. :_start(nullptr)
    141. ,_finish(nullptr)
    142. ,_end_of_storage(nullptr)
    143. {
    144. for(long i = 0; i < n; i++)
    145. {
    146. push_back(value);
    147. }
    148. }
    149. vector(size_t n, const T& value = T())
    150. :_start(nullptr)
    151. ,_finish(nullptr)
    152. ,_end_of_storage(nullptr)
    153. {
    154. for(size_t i = 0; i < n; i++)
    155. {
    156. push_back(value);
    157. }
    158. }
    159. //三种情况,比capacity()大,在size()和capacity之间,比size()小
    160. void resize(size_t n, const T& val = T())
    161. {
    162. if(n > capacity())
    163. {
    164. reserve(n);
    165. }
    166. //初始化
    167. if(n > size())
    168. {
    169. while(_finish < _start + n)
    170. {
    171. *_finish = val;
    172. _finish++;
    173. }
    174. }
    175. else
    176. {
    177. _finish = _start + n;
    178. }
    179. }
    180. //返回值是iterator 返回的是最近一次插入的元素位置
    181. iterator insert(iterator pos, const T& x)
    182. {
    183. assert(pos >= _start);
    184. assert(pos <= _finish);
    185. if(_finish == _end_of_storage)
    186. {
    187. //修正pos的位置
    188. size_t len = pos - _start;
    189. reserve(capacity() == 0 ? 4 : capacity() * 2);
    190. pos = _start + len;
    191. }
    192. iterator end = _finish - 1;//是地址,怎末写都无所谓
    193. while(end >= pos)
    194. {
    195. *(end + 1) = *end;
    196. end--;
    197. }
    198. *pos = x;
    199. _finish++;
    200. return pos;
    201. }
    202. //返回值同理,删除元素的下一个位置
    203. iterator erase(iterator pos)
    204. {
    205. assert(pos >= _start);
    206. assert(pos < _finish);
    207. iterator begin = pos + 1;
    208. while(begin < _finish)
    209. {
    210. *begin = *(begin - 1);
    211. begin++;
    212. }
    213. return pos;
    214. }
    215. T& front()
    216. {
    217. assert(size() > 0);
    218. return *_start;
    219. }
    220. T& back()
    221. {
    222. assert(size() > 0);
    223. return *(_finish - 1);
    224. }
    225. private:
    226. iterator _start;
    227. iterator _finish;
    228. iterator _end_of_storage;
    229. };
    230. void test_vector1()
    231. {
    232. vector<int> v;
    233. v.push_back(1);
    234. v.push_back(2);
    235. v.push_back(3);
    236. v.push_back(4);
    237. v.push_back(5);
    238. for(auto e : v)
    239. {
    240. cout << e << " ";
    241. }
    242. cout << endl;
    243. }
    244. void test_vector2()
    245. {
    246. vector<int> v;
    247. v.push_back(1);
    248. v.push_back(2);
    249. v.push_back(3);
    250. v.push_back(4);
    251. v.push_back(5);
    252. v.push_back(6);
    253. for(auto e : v)
    254. {
    255. cout << e << " ";
    256. }
    257. cout << endl;
    258. v.pop_back();
    259. for(auto e : v)
    260. {
    261. cout << e << " ";
    262. }
    263. cout << endl;
    264. v.pop_back();
    265. for(auto e : v)
    266. {
    267. cout << e << " ";
    268. }
    269. cout << endl;
    270. v.pop_back();
    271. for(auto e : v)
    272. {
    273. cout << e << " ";
    274. }
    275. cout << endl;
    276. v.pop_back();
    277. for(auto e : v)
    278. {
    279. cout << e << " ";
    280. }
    281. cout << endl;
    282. v.pop_back();
    283. for(auto e : v)
    284. {
    285. cout << e << " ";
    286. }
    287. cout << endl;
    288. v.pop_back();
    289. for(auto e : v)
    290. {
    291. cout << e << " ";
    292. }
    293. cout << endl;
    294. v.pop_back();
    295. for(auto e : v)
    296. {
    297. cout << e << " ";
    298. }
    299. cout << endl;
    300. }
    301. void test_vector3()
    302. {
    303. vector<int> v;
    304. v.push_back(1);
    305. v.push_back(2);
    306. v.push_back(3);
    307. v.push_back(4);
    308. v.push_back(5);
    309. v.push_back(6);
    310. for(size_t i = 0; i < v.size(); i++)
    311. {
    312. cout << v[i] << " ";
    313. }
    314. cout << endl;
    315. }
    316. void test_vector4()
    317. {
    318. string str("Hello World");
    319. vector<char> v(str.begin(), str.end());
    320. for(auto e : v)
    321. {
    322. cout << e;
    323. }
    324. cout << endl;
    325. }
    326. class Solution {
    327. public:
    328. vectorint>> generate(int numRows) {
    329. vectorint>> vv;
    330. vv.resize(numRows);//只能使用resize要初始化
    331. for (size_t i = 0; i < vv.size(); i++)
    332. {
    333. vv[i].resize(i + 1, 0);
    334. vv[i].front() = vv[i].back() = 1;
    335. }
    336. for (size_t i = 0; i < vv.size(); i++)
    337. {
    338. for (size_t j = 0; j < vv[i].size(); j++)
    339. {
    340. if (vv[i][j] == 0)
    341. {
    342. vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
    343. }
    344. }
    345. }
    346. return vv;
    347. }
    348. };
    349. void test_vector5()
    350. {
    351. vectorint>> ans = Solution().generate(8);
    352. for(auto e : ans)
    353. {
    354. for(auto m : e)
    355. {
    356. cout << m << " ";
    357. }
    358. }
    359. cout << endl;
    360. }
    361. void test_vector6()
    362. {
    363. vector<int> v1;
    364. v1.push_back(1);
    365. v1.push_back(2);
    366. v1.push_back(3);
    367. v1.push_back(4);
    368. v1.push_back(5);
    369. v1.push_back(6);
    370. v1.push_back(7);
    371. for(auto e : v1)
    372. {
    373. cout << e << " ";
    374. }
    375. cout << endl;
    376. vector<int> v2(v1);
    377. for(auto e : v2)
    378. {
    379. cout << e << " ";
    380. }
    381. cout << endl;
    382. }
    383. void test_vector7()
    384. {
    385. vector ans(10, "Hello World");
    386. for(auto e : ans)
    387. {
    388. cout << e << endl;
    389. }
    390. cout << endl;
    391. }
    392. void test_vector8()
    393. {
    394. vectorint>> dp(10, vector<int>(10, 1));
    395. for(auto e : dp)
    396. {
    397. for(auto m : e)
    398. {
    399. cout << m << " ";
    400. }
    401. cout << endl;
    402. }
    403. cout << endl;
    404. }
    405. }


    总结


    以上就是今天要讲的内容,本文仅仅简单实现了vector

  • 相关阅读:
    【实战-05】 flinksql look up join
    springboot 简单配置mongodb多数据源
    【java面试】Redis篇
    《腾讯精选练习50题》专题
    数据分析案例-基于sklearn随机森林算法探究影响预期寿命的因素
    【华为OD机试真题 python】一种字符串压缩表示的解压 【2022 Q4 | 100分】
    知识图谱推理研究综述9.3
    C++DAY39
    Vue computed计算和watch监听
    如何计算质心
  • 原文地址:https://blog.csdn.net/m0_62179366/article/details/126917680