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

一、vector是什么?

vector是表示可变大小数组的序列容器,它也采用连续存储空间来存储元素,因此可以采用下标对vector的元素进行访问,它的大小是动态改变的,vector使用动态分配数组来存储它的元素;

二、容器特性

1.顺序序列

顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素;

2.动态数组

支持对序列中的任意元素进行快速直接访问,甚至可以通过指针进行该操作。操供了在序列末尾相对快速地添加/删除元素的操作;

3.能够感知内存分配器的

容器使用一个内存分配器对象来动态地处理它的存储需求;

三、vector的模拟实现

定义一个类:

  1. template<class T>
  2. class Vector
  3. {
  4. T* _start; //首元素地址
  5. T* _finish; //最后一个元素地址的下一个地址
  6. T* _endOfStorage; //空间的尾地址
  7. public
  8. //成员函数
  9. };

构造函数

  1. Vector()
  2. :_start(nullptr)
  3. , _finish(nullptr)
  4. , _endOfStorage(nullptr)
  5. {}
  6.  
  7. Vector(size_t n, const T& value = T())
  8. :_start(nullptr)
  9. , _finish(nullptr)
  10. , _endOfStorage(nullptr)
  11. {
  12. reserve(n);
  13. while (n--)
  14. {
  15. push_back(value);
  16. }
  17. }
  18. Vector(InputInterator first, InputInterator last)
  19. :_start(nullptr)
  20. , _finish(nullptr)
  21. , _endOfStorage(nullptr)
  22. {
  23. while (first != last)
  24. {
  25. pushBack(*first);
  26. ++first;
  27. }
  28. }
  29.  

数据大小、空间大小

  1. size_t size() const
  2. {
  3. return _finish - _start;
  4. }
  5.  
  6. size_t capacity() const
  7. {
  8. return _endOfStorage - _start;
  9. }
  10.  

尾插

  1. void pushBack(const T& value)
  2. {
  3. if (_finish == _endOfStorage)
  4. {
  5. size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity();
  6. reverse(value);
  7. }
  8. *_finish = value;
  9. ++_finish;
  10. }

扩容

有资源进行拷贝时,使用深拷贝;类型为自定义类型时,发生浅拷贝,调用自定义类型析构函数,释放资源,导致资源二次释放,所以自定义类型的拷贝有资源时进行深拷贝;

深拷贝与浅拷贝的区别及应用

  1. void reserve(size_t n)
  2. {
  3. if (n &gt; capacity())
  4. {
  5. size_t sz = size();
  6. T* arr = new T[n];
  7. if (_start)
  8. {
  9. memcpy(arr, _start, sizeof(T) * sz);
  10. delete[] _start;
  11. }
  12. //update
  13. _start = arr;
  14. _finish = _start + sz;
  15. _endOfStorage = _start + n;
  16. }
  17. }

改变数据大小

  1. void resize(size_t n, const T& val = T())
  2. {
  3. if (n > capacity())
  4. {
  5. reserve(n);
  6. }
  7. else if (n > size())
  8. {
  9. while (_finish != _start + n)
  10. {
  11. *_finish = val;
  12. _finish++;
  13. }
  14. }
  15. _finish = _start + n;
  16. }

位置插入值

  1. void insert(iterator pos, const T& val)
  2. {
  3. size_t sz = pos - _start;
  4. //检查位置
  5. if (pos >= _start && pos <= _finish)
  6. {
  7. //检查容量
  8. if (_finish == _endOfStoage)
  9. {
  10. size_t n = _endOfStorage == nullptr ? 1 : 2 * capacity();
  11. reserve(n);
  12. //更新迭代器
  13. pos = _start + sz;
  14. }
  15. //移动元素
  16. iterator end_u = _finish;
  17. while (end_u != pos)
  18. {
  19. *end = *(end_u - 1);
  20. --end_u();
  21. }
  22. //插入元素
  23. *pos = val;
  24. //更新位置
  25. ++_finish;
  26. }
  27. }

删除数据

  1. iterator erase(iterator pos)
  2. {
  3. //检查位置
  4. if (pos < _finish && pos >= _start)
  5. {
  6. //移动元素
  7. iterator start = pos + 1;
  8. while (start!=_finish)
  9. {
  10. *(start - 1) = *start;
  11. start++;
  12. }
  13. //更新
  14. --_finish;
  15. }
  16. return pos;
  17. }
  18. //返回删除数据的下一个元素的位置

operator[] 重载

  1. T& operator[](size_t pos)
  2. {
  3. if (pos >= 0 && pos < size())
  4. return _start[pos];
  5. }

operator= 重载

  1. Vector<T>& operator=(const Vector<T>& v)
  2. {
  3. if (this != &v)
  4. {
  5. delete[]_start;
  6. size_t n = v.capacity();
  7. _start = new T[n];
  8. for (size_t i = 0; i < v.capacity(); ++i)
  9. {
  10. _start[i] = v._start[i];
  11. }
  12. _finish = _start + v.size();
  13. _finish = _start + n;
  14. }
  15. return *this;
  16. }

迭代器

  1. //vector迭代器:T*
  2. typedef T* iterator;
  3. typedef const T* const_iterator;
  4.  
  5. iterator begin()
  6. {
  7. return _start;
  8. }
  9.  
  10. iterator end()
  11. {
  12. return _finish;
  13. }
  14.  
  15. const_iterator begin() const
  16. {
  17. return _start;
  18. }
  19.  
  20. const_iterator end() const
  21. {
  22. return _finish;
  23. }
  24.  

析构函数

  1. ~Vector()
  2. {
  3. if (_start)
  4. {
  5. delete[] _start;
  6. _start = _finish = _endOfStorage = nullptr;
  7. }
  8. }

总结

到此这篇关于c++ vector模拟实现的文章就介绍到这了,更多相关c++ 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号