经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
C++ STL vector的模拟实现
来源:jb51  时间:2021/5/7 12:38:53  对本文有异议

1. vector的介绍和使用

  • vector是表示可变大小数组的序列容器。
  • 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
  • 本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。
  • vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何,重新分配都应该是对数增长的间隔大小,以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
  • 因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长。
  • 与其它动态序列容器相比(deques, lists and forward_lists), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作,效率更低。比起lists和forward_lists统一的迭代器和引用更好。

更为详细的可以查看vector文档介绍

2. vector的模拟实现

vector的嵌套型别定义

  1. typedef _Ty value_type;
  2. typedef value_type* iterator;
  3. typedef value_type& reference;
  4. typedef size_t size_type;

vector的成员变量

  1. private:
  2. iterator _start;
  3. iterator _last;
  4. iterator _end;

2.1 vector构造函数和拷贝构造函数

  1. vector():_start(nullptr),_last(nullptr),_end(nullptr)
  2. {}
  3. vector(size_type n,const _Ty& value):_start(nullptr),_last(nullptr),_end(nullptr)
  4. {
  5. insert(n,value);
  6. }
  7. vector(iterator f,iterator l):_start(nullptr),_last(nullptr),_end(nullptr)
  8. {
  9. insert(f,l);
  10. }
  11. vector(const vector<int>& iv)
  12. {
  13. reserve(iv.capacity());
  14. iterator it = begin();
  15. iterator vit = iv.end();
  16. while (vit != iv.begin())
  17. {
  18. *it++ = *vit--;
  19. }
  20. }

2.2 insert函数和eraser函数

  1. iterator insert(iterator pos,const _Ty& value)
  2. {
  3. //1.当size()==capacity()时,表明vector已满,再进行插入前需要进行扩容
  4. if(size()== capacity())
  5. {
  6. size_type oldpos = pos - begin();
  7. //这里需要防止一种情况:若vector为空的时候,他的capacity为0,这个时候给他直接扩容2倍是行不通的,
  8. //因为2*0 = 0,因此就需要进行判断
  9. size_type newcapacity = (capacity() == 0)? 1 : 2*capacity();
  10.  
  11. reserve(newcapacity);
  12.  
  13. //这里空间发生了变化,pos迭代器会失效,因此需要重新对pos进行设置
  14. //reserve不会使vector的成员变量失效
  15. pos = begin() + oldpos;
  16. }
  17. //2.当size() < capacity()时,表明vector未满,插入直接在pos的位置进行插入
  18. //需要注意的是插入是在pos指向的位置进行插入,并且插入需要挪动数据,
  19. //将pos位置之后的数据全部向后挪动一个,为防止元素被改写,则需要从后向前进行挪动
  20. iterator tail = _last;
  21. while(tail > pos)
  22. {
  23. *tail = *(tail-1);
  24. --tail;
  25. }
  26. //这里要注意的是挪动数据时,因为没有对pos位置进行操作,所以pos位置的迭代器并没有失效,
  27. //但是pos位置之后的迭代器全部失效了,但在这里并没有关系,我们并不会用到那些迭代器
  28. *pos = value;
  29.  
  30. //插入完之后,一定要对_last指针+1,因为全部向后挪动了一个元素
  31. ++_last;
  32.  
  33. return pos;
  34. }
  35.  
  36. void insert(size_type n,const _Ty& value)
  37. {
  38. for(int i = 0;i < n; ++i)
  39. {
  40. insert(end(),value);
  41. }
  42. }
  43. void insert(iterator f,iterator l)
  44. {
  45. while(f!=l)
  46. {
  47. insert(end(),*f);
  48. ++f;
  49. }
  50. }
  51.  
  52.  
  53. iterator erase(iterator pos)
  54. {
  55. assert(pos >= _start || pos < _last);
  56. //1.删除pos位置的元素,就是将[pos,end()]这个区间向前挪动一个即可
  57. iterator it = pos + 1;
  58. while(it != _last)
  59. {
  60. *(it-1) = *(it);
  61. ++it;
  62. }
  63.  
  64. --_last;
  65. return pos;
  66. }

2.3 reserve函数和resize函数

  1. void reserve(size_type n)
  2. {
  3. //若 n 的值大于vector的容量,则开辟空间
  4. //若 n 的值小于等于,则不进行任何操作
  5. if(n > capacity())
  6. {
  7. //1.新开辟一个空间
  8. size_type oldSize = size();
  9. _Ty* newVector = new _Ty[n];
  10. //2.将原空间的数值赋值到新空间
  11. if(_start)
  12. {
  13. //注意:这里不能使用memcpy,因为memcpy是一个浅拷贝。
  14. //memcpy(newVector,_start,sizeof(_Ty)*size());
  15. for(size_type i = 0; i < oldSize; ++i)
  16. {
  17. newVector[i] = _start[i];
  18. }
  19. }
  20. //3.改变三个指针的指向
  21. //这里直接重新给三个成员进行赋值,所以调用reserve()函数不用担心迭代器失效的问题
  22. _start = newVector;
  23. _last = _start + oldSize;
  24. _end = _start + n;
  25. }
  26. }
  27.  
  28. void resize(size_type n,const _Ty& value = _Ty())
  29. {
  30. //1.如果n的值小于等于size()的时候,则只需要将_last的指针往前移动即可
  31. if(n <= size())
  32. {
  33. _last = _start + n;
  34. return;
  35. }
  36. //2.如果n的值大于capacity()的时候,则需调用reserve()函数,重新设置容量大小
  37. if(n > capacity())
  38. {
  39. reserve(n);
  40. }
  41. //若当n的值大于size()而小于capacity()的时候,只需将_last的指针往后移即可
  42.  
  43. iterator it = _last;
  44. _last = _start + n;
  45.  
  46. while(it != _last)
  47. {
  48. *it = value;
  49. ++it;
  50. }
  51. //resize()函数也不需要担心迭代器失效的问题
  52. }

2.4 push_back函数和pop_back函数

  1. void push_back(const _Ty& value)
  2. {
  3. insert(end(),value);
  4. }
  5. void pop_back()
  6. {
  7. erase(end()-1);
  8. }

2.5 begin函数和end函数

  1. iterator begin()const
  2. {
  3. return _start;
  4. }
  5. iterator end() const
  6. {
  7. return _last;
  8. }

2.6 size函数、capacity函数

  1. size_type size()
  2. {
  3. return end()-begin();
  4. }
  5. size_type capacity()const
  6. {
  7. return _end-begin();
  8. }

2.7 empty函数和operator[]重载

  1. bool empty()const
  2. {
  3. return end() == begin();
  4. }
  5.  
  6. reference operator[](size_type n)
  7. {
  8. return *(begin() + n);
  9. }
  10.  

2.8 完整代码和相应测试

  1. #include <iostream>
  2. #include <assert.h>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. namespace mytest{
  8. template<class _Ty>
  9. class vector
  10. {
  11. public:
  12. typedef _Ty value_type;
  13. typedef value_type* iterator;
  14. typedef value_type& reference;
  15. typedef size_t size_type;
  16. public:
  17. iterator begin()const
  18. {
  19. return _start;
  20. }
  21. iterator end() const
  22. {
  23. return _last;
  24. }
  25. size_type size()
  26. {
  27. return end()-begin();
  28. }
  29. size_type capacity()const
  30. {
  31. return _end-begin();
  32. }
  33. bool empty()const
  34. {
  35. return end() == begin();
  36. }
  37. reference operator[](size_type n)
  38. {
  39. return *(begin() + n);
  40. }
  41.  
  42. public:
  43. vector():_start(nullptr),_last(nullptr),_end(nullptr)
  44. {}
  45. vector(size_type n,const _Ty& value):_start(nullptr),_last(nullptr),_end(nullptr)
  46. {
  47. insert(n,value);
  48. }
  49. vector(iterator f,iterator l):_start(nullptr),_last(nullptr),_end(nullptr)
  50. {
  51. insert(f,l);
  52. }
  53. vector(const vector<int>& iv)
  54. {
  55. reserve(iv.capacity());
  56. iterator it = begin();
  57. iterator vit = iv.end();
  58. while (vit != iv.begin())
  59. {
  60. *it++ = *vit--;
  61. }
  62. }
  63. public:
  64. void reserve(size_type n)
  65. {
  66. //若 n 的值大于vector的容量,则开辟空间
  67. //若 n 的值小于等于,则不进行任何操作
  68. if(n > capacity())
  69. {
  70. //1.新开辟一个空间
  71. size_type oldSize = size();
  72. _Ty* newVector = new _Ty[n];
  73. //2.将原空间的数值赋值到新空间
  74. if(_start)
  75. {
  76. //注意:这里不能使用memcpy,因为memcpy是一个浅拷贝。
  77. //memcpy(newVector,_start,sizeof(_Ty)*size());
  78. for(size_type i = 0; i < oldSize; ++i)
  79. {
  80. newVector[i] = _start[i];
  81. }
  82. }
  83. //3.改变三个指针的指向
  84. //这里直接重新给三个成员进行赋值,所以调用reserve()函数不用担心迭代器失效的问题
  85. _start = newVector;
  86. _last = _start + oldSize;
  87. _end = _start + n;
  88. }
  89. }
  90.  
  91. void resize(size_type n,const _Ty& value = _Ty())
  92. {
  93. //1.如果n的值小于等于size()的时候,则只需要将_last的指针往前移动即可
  94. if(n <= size())
  95. {
  96. _last = _start + n;
  97. return;
  98. }
  99. //2.如果n的值大于capacity()的时候,则需调用reserve()函数,重新设置容量大小
  100. if(n > capacity())
  101. {
  102. reserve(n);
  103. }
  104. //若当n的值大于size()而小于capacity()的时候,只需将_last的指针往后移即可
  105. iterator it = _last;
  106. _last = _start + n;
  107.  
  108. while(it != _last)
  109. {
  110. *it = value;
  111. ++it;
  112. }
  113. //resize()函数也不需要担心迭代器失效的问题
  114. }
  115.  
  116. void push_back(const _Ty& value)
  117. {
  118. insert(end(),value);
  119. }
  120. void pop_back()
  121. {
  122. erase(end()-1);
  123. }
  124.  
  125.  
  126. iterator insert(iterator pos,const _Ty& value)
  127. {
  128. //1.当size()==capacity()时,表明vector已满,再进行插入前需要进行扩容
  129. if(size()== capacity())
  130. {
  131. size_type oldpos = pos - begin();
  132. //这里需要防止一种情况:若vector为空的时候,他的capacity为0,
  133. //这个时候给他直接扩容2倍是行不通的,因为2*0 = 0,因此就需要进行判断
  134. size_type newcapacity = (capacity() == 0)? 1 : 2*capacity();
  135.  
  136. reserve(newcapacity);
  137.  
  138. //这里空间发生了变化,pos迭代器会失效,因此需要重新对pos进行设置
  139. //reserve不会使vector的成员变量失效
  140. pos = begin() + oldpos;
  141. }
  142. //2.当size() < capacity()时,表明vector未满,插入直接在pos的位置进行插入
  143. //需要注意的是插入是在pos指向的位置进行插入,并且插入需要挪动数据,
  144. //将pos位置之后的数据全部向后挪动一个,为防止元素被改写,则需要从后向前进行挪动
  145. iterator tail = _last;
  146. while(tail > pos)
  147. {
  148. *tail = *(tail-1);
  149. --tail;
  150. }
  151. //这里要注意的是挪动数据时,因为没有对pos位置进行操作,所以pos位置的迭代器并没有失效,
  152. //但是pos位置之后的迭代器全部失效了,但在这里并没有关系,我们并不会用到那些迭代器
  153. *pos = value;
  154.  
  155. //插入完之后,一定要对_last指针+1,因为全部向后挪动了一个元素
  156. ++_last;
  157.  
  158. return pos;
  159. }
  160.  
  161. void insert(size_type n,const _Ty& value)
  162. {
  163. for(int i = 0;i < n; ++i)
  164. {
  165. insert(end(),value);
  166. }
  167. }
  168. void insert(iterator f,iterator l)
  169. {
  170. while(f!=l)
  171. {
  172. insert(end(),*f);
  173. ++f;
  174. }
  175. }
  176.  
  177.  
  178. iterator erase(iterator pos)
  179. {
  180. assert(pos >= _start || pos < _last);
  181. //1.删除pos位置的元素,就是将[pos,end()]这个区间向前挪动一个即可
  182. iterator it = pos + 1;
  183. while(it != _last)
  184. {
  185. *(it-1) = *(it);
  186. ++it;
  187. }
  188.  
  189. --_last;
  190. return pos;
  191.  
  192. }
  193.  
  194.  
  195.  
  196. private:
  197. iterator _start;
  198. iterator _last;
  199. iterator _end;
  200. };
  201.  
  202. };
  203.  
  204. void Test1()
  205. {
  206. mytest::vector<int> iv;
  207.  
  208. cout << "iv.size() = " << iv.size() << endl;
  209. cout << "iv.capacity() = " << iv.capacity() << endl;
  210. iv.push_back(1);
  211. iv.push_back(2);
  212. iv.push_back(3);
  213. iv.push_back(4);
  214. cout << "iv.size() = " << iv.size() << endl;
  215. cout << "iv.capacity() = " << iv.capacity() << endl;
  216.  
  217. mytest::vector<int>::iterator it = iv.begin();
  218.  
  219. while(it != iv.end())
  220. {
  221. cout << *it << " ";
  222. ++it;
  223. }
  224. cout << endl;
  225. iv.pop_back();
  226. iv.pop_back();
  227. it = iv.begin();
  228. while(it != iv.end())
  229. {
  230. cout << *it << " ";
  231. ++it;
  232. }
  233. cout << endl;
  234.  
  235.  
  236. }
  237.  
  238. void Test2()
  239. {
  240. mytest::vector<int> iv(10,2);
  241. mytest::vector<int>::iterator it = iv.begin();
  242. while(it != iv.end())
  243. {
  244. cout << *it << " ";
  245. ++it;
  246. }
  247. cout << endl;
  248. }
  249.  
  250. void Test3()
  251. {
  252. int ar[] = {1,2,3,3,4,5};
  253. mytest::vector<int> iv(ar,ar+6);
  254. mytest::vector<int>::iterator it = iv.begin();
  255. while(it != iv.end())
  256. {
  257. cout << *it << " ";
  258. ++it;
  259. }
  260. cout << endl;
  261.  
  262. }
  263. int main()
  264. {
  265. // Test1();
  266. // Test2();
  267. Test3();
  268. return 0;
  269. }
  270.  

到此这篇关于C++ STL vector的模拟实现的文章就介绍到这了,更多相关C++ STL vector内容请搜索w3xue以前的文章或继续浏览下面的相关文章希望大家以后多多支持w3xue!

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号