devbox
花生_TL007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【C++】理解vector的底层原理并模拟实现（手撕vector）

作者：花生_TL007 | 2024-04-07 20:38:56

赞

踩

【C++】理解vector的底层原理并模拟实现（手撕vector）

目录

01.成员变量

02.构造与析构

 03.管理内存

1.reserve函数

2.reszie函数

04.访问元素

05.修改元素

之前的一篇博客讲到了vector的介绍及其运用：vector的介绍及使用说明 但是我们不仅要会用，还要理解它的底层原理，今天我们通过手撕一个自己的vector，来进一步加深对vector容器的理解。

01.成员变量

  1.  
  2. namespace my_std
  3. {
  4.     template<typename T>
  5.     class vector
  6.     {
  7.     public:
  8.         // Vector的迭代器是一个原生指针
  9.         typedef T* iterator;
  10.         typedef const T* const_iterator;
  11.     private:
  12.         iterator _start; // 指向数据块的开始
  13.         iterator _finish; // 指向有效数据的尾
  14.         iterator _endOfStorage; // 指向存储容量的尾
  15.     };
  16. }

vector是一个通过类模版实现的容器，通过类定义，可以使其更为灵活，泛用性更强。

在我们定义的vector类中，我们把iterator定义为原生指针T*，虽然vector迭代器严格意义上并不等同于指针，但是其在很多方面与原生指针行为类似，比如可以通过‘++’来递增，通过‘*’来解引用等等。因此这里我们将其定义为原生指针也是比较贴近标准库中的vector的实现的。

  1. iterator _start;：指向 vector 内部数据块的开始位置的迭代器。

  2. iterator _finish;：指向 vector 内部有效数据的尾部。有效数据是指在 vector 中存储的实际元素，而 _finish 指向的位置是有效数据的下一个位置。

  3. iterator _endOfStorage;：指向 vector 内部存储容量的尾部的下一个位置。存储容量是指 vector 内部实际分配的内存空间的大小，而 _endOfStorage 指向的位置是分配的内存空间的末尾的下一个位置。这个位置之后的内存空间是 vector 可以进行扩展的空间。

迭代器声明为私有的成员类型可以确保用户不能直接访问和操作迭代器，这样可以保护vector内部的状态和数据。但是用户必须通过迭代器才能访问并操作vector内的元素，所以需要有获取迭代器的成员函数，分为读写和只读访问两个版本：

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

02.构造与析构

1.无参构造：

  1.         vector()
  2.             :_start(nullptr)
  3.             ,_finish(nullptr)
  4.             ,_endOfStorage(nullptr)
  5.         {}

都初始化为空指针

2.带参构造：

  1.         vector(int n, const T& value = T()) {
  2.             _start = new T[n];
  3.             for (int i = 0; i < n; i++) {
  4.                 _start[i] = value;
  5.             }
  6.             _finish = _endOfStorage =  _start + n;
  7.         }

_start迭代器是T*类型的原生指针，实际上是一个数组，因此可以使用new关键字为其动态分配内存，元素添加后要记得将_finish移到正确的偏移位置。

3.迭代器构造：

  1.         template<class InputIterator>
  2.         vector(InputIterator first, InputIterator last) {
  3.             int size = last - first;
  4.             _start = new T[size];
  5.             int i = 0;
  6.             for (auto it = first; it != last; it++) {
  7.                 _start[i] = *it;
  8.                 i++;
  9.             }
  10.             _finish = _endOfStorage =  _start + size;
  11.         }

vector还支持迭代器进行构造，通过迭代器遍历源数组，将数据拷贝到目标容器中。迭代器相减可以得到构造的元素数量，再用new关键字对_start进行空间分配，迭代器遍历实现数据拷贝。

4.拷贝构造：

  1.         vector(const vector<T>& v) {
  2.             _start = new T[v.size()];
  3.             for (size_t i = 0; i < v.size(); i++) {
  4.                 _start[i] = v[i];
  5.             }
  6.             _finish = _endOfStorage = _start + v.size();
  7.         }

拷贝构造其实与迭代器构造类似，不过拷贝构造只支持vector容器类型之间的拷贝，而迭代器构造还支持数组的拷贝以及片段的拷贝，这两者是有区别的。这里的size()函数用于获取元素个数，后面会有关于函数的声明及定义。

5.析构函数：

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

进行测试：

 03.管理内存

首先我们需要两个函数分别获取vector的数据个数以及容量大小：

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

将其申明为const，确保不会修改成员变量的值。

1.reserve函数

vector的reserve函数用于预留一定的容量，只开辟空间，不进行赋值，空间足够就不进行操作：

  1.         void reserve(size_t n) {
  2.             if (n > capacity()) {
  3.                 size_t old_size = size();
  4.                 T* tmp = new T[n];
  5.                 if (_start != nullptr) {
  6.                     for (int i = 0; i < size(); i++) {
  7.                         tmp[i] = _start[i];
  8.                     }
  9.                 }
  10.                 delete[] _start;
  11.                 _start = tmp;
  12.                 _finish = _start + old_size;
  13.                 _endOfStorage = _start + n;
  14.             }
  15.         }

使用reserve函数后，会在堆上重新申请一块空间，原来的空间就失效了，需要进行空间释放，这里使用delete操作符，因为_start是通过new操作符进行空间开辟的。_finish与_endOfStorage实际上表示的是相对于_start的偏移量，因此我们需要记录这个偏移量，使得_start指针修改之后_finish与_endOfStorage可以来到正确的位置。

2.reszie函数

resize函数用于改变vector的大小，调整vector中元素的数量，如果调整后的大小大于当前大小，则会在末尾添加新的元素并进行赋值（默认构造值），如果调整后的大小小于当前大小，则会删除末尾的元素。

  1.         void resize(size_t n, const T& value = T()) 
  2.         {
  3.             T* tmp = new T[n];
  4.             if (n <= size()) {
  5.                 for (size_t i = 0; i < n; i++) {
  6.                     tmp[i] = _start[i];
  7.                 }
  8.             }
  9.             else {
  10.                 for (size_t i = 0; i < size(); i++) {
  11.                     tmp[i] = _start[i];
  12.                 }
  13.                 for (size_t i = size(); i < n; i++) {
  14.                     tmp[i] = value;
  15.                 }
  16.             }
  17.             delete[] _start;
  18.             _start = tmp;
  19.             _finish = _endOfStorage =  _start + n;
  20.         }

同样的，需要开辟一块新的空间并将数据进行迁移，释放原空间内存，由于空间可能扩大也可能缩小，所以要分情况讨论。

运行测试：

04.访问元素

1.‘[]’运算符的重载

为了方便对容器内元素的访问，我们需要重载‘[]’运算符，模拟数组的下标访问：

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

由于迭代器_start实际上就是数组的头指针，因此可以直接调用

2.front、back函数

vector的front函数可以直接访问容器的首元素，back函数可以直接访问容器的尾元素：

  1.         T& front()
  2. 		{
  3. 			return *_start;
  4. 		}
  5.  
  6. 		const T& front()const
  7. 		{
  8. 			return *_start;
  9. 		}
  10.  
  11. 		T& back()
  12. 		{
  13. 			return *(_finish - 1);
  14. 		}
  15.  
  16. 		const T& back()const
  17. 		{
  18. 			return *(_finish - 1);
  19. 		}

05.修改元素

1.尾插尾删

在尾部插入元素时，首先要考虑内存是否充足，内存不足的情况下，我们考虑二倍扩容。

  1.         void push_back(const T& x) {
  2.             if (_finish = _endOfStorage){
  3.                 int newcapacity = capacity() == 0 ? 2 : 2 * capacity();
  4.             }
  5.             *_finish = x;
  6.             ++_finish;
  7.         }
  8.  
  9.         void pop_back() {
  10.             assert(size() > 0);
  11.             --_finish;
  12.         }

修改元素后要记得实时更新迭代器。

2.swap交换

vector支持不同类型元素的交换，其原理是通过交换两个容器内部的指针和大小，而并不修改实际的内存块，所以不受元素类型的影响：

  1.         void swap(vector<T>& v) {
  2.             vector<T> tmp(v);
  3.             delete[] v._start;
  4.             v._start = _start;
  5.             v._finish = _finish;
  6.             v._endOfStorage = _endOfStorage;
  7.             _start = tmp._start;
  8.             _finish = tmp._finish;
  9.             _endOfStorage = tmp._endOfStorage;
  10.         }

C++标准库也提供了‘std::swap’函数，因此可以直接用‘std::swap’函数实现vector的swap：

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

3.随机插入

vector也支持在指定位置进行元素插入的操作，由于vector内元素是顺序连续存储的，因此每次插入操作都要对当前位置之后的所以元素进行挪动，同样的，在插入操作前需要进行内存检查：

  1. 		iterator insert(iterator pos, const T& x)
  2. 		{
  3. 			assert(pos <= _finish);
  4.  
  5. 			// 空间不够先进行增容
  6. 			if (_finish == _endOfStorage)
  7. 			{
  8. 				//size_t size = size();
  9. 				size_t newCapacity = (0 == capacity()) ? 1 : capacity() * 2;
  10. 				reserve(newCapacity);
  11.  
  12. 				// 如果发生了增容，需要重置pos
  13. 				pos = _start + size();
  14. 			}
  15.  
  16. 			iterator end = _finish - 1;
  17. 			while (end >= pos)
  18. 			{
  19. 				*(end + 1) = *end;
  20. 				--end;
  21. 			}
  22.  
  23. 			*pos = x;
  24. 			++_finish;
  25. 			return pos;
  26. 		}

 pos迭代器指向插入的位置，其本质是在_start迭代器地址基础上的一个偏移，扩容操作会使_start指向一块新的空间，其值会发生改变，因此pos迭代器也要进行改变。

4.随机删除

删除元素也同样需要挪动数据，将pos位置之后的元素以此往前移动覆盖，就可以实现删除效果。删除元素后记得更新_finish指针：

  1.         iterator erase(iterator pos)
  2. 		{
  3. 			// 挪动数据进行删除
  4. 			iterator begin = pos + 1;
  5. 			while (begin != _finish) {
  6. 				*(begin - 1) = *begin;
  7. 				++begin;
  8. 			}
  9.  
  10. 			--_finish;
  11. 			return pos;
  12. 		}

下面给出完整代码：

  1. #pragma once
  2. #include<iostream>
  3. using namespace std;
  4. #include<assert.h>
  5.  
  6. namespace my_std
  7. {
  8.     template<typename T>
  9.     class vector
  10.     {
  11.     public:
  12.         // Vector的迭代器是一个原生指针
  13.         typedef T* iterator;
  14.         typedef const T* const_iterator;
  15.         iterator begin() {
  16.             return _start;
  17.         }
  18.         iterator end() {
  19.             return _finish;
  20.         }
  21.         const_iterator cbegin() {
  22.             return _start;
  23.         }
  24.         const_iterator cend() const {
  25.             return _finish;
  26.         }
  27.  
  28.         // 创建和销毁
  29.         vector()
  30.             :_start(nullptr)
  31.             ,_finish(nullptr)
  32.             ,_endOfStorage(nullptr)
  33.         {}
  34.  
  35.         vector(int n, const T& value = T()) {
  36.             _start = new T[n];
  37.             for (int i = 0; i < n; i++) {
  38.                 _start[i] = value;
  39.             }
  40.             _finish = _endOfStorage =  _start + n;
  41.         }
  42.  
  43.         template<class InputIterator>
  44.         vector(InputIterator first, InputIterator last) {
  45.             int size = last - first;
  46.             _start = new T[size];
  47.             int i = 0;
  48.             for (auto it = first; it != last; it++) {
  49.                 _start[i] = *it;
  50.                 i++;
  51.             }
  52.             _finish = _endOfStorage =  _start + size;
  53.         }
  54.  
  55.         vector(const vector<T>& v) {
  56.             _start = new T[v.size()];
  57.             for (size_t i = 0; i < v.size(); i++) {
  58.                 _start[i] = v[i];
  59.             }
  60.             _finish = _endOfStorage = _start + v.size();
  61.         }
  62.  
  63.         vector<T>& operator= (vector<T> v) {
  64.             vector<T> new_v(v);
  65.             return new_v;
  66.         }
  67.  
  68.         ~vector()
  69.         {
  70.             if (_start)
  71.             {
  72.                 delete[] _start;
  73.                 _start = _finish = _endOfStorage = nullptr;
  74.             }
  75.         }
  76.  
  77.         // 内存管理
  78.         size_t size() const {
  79.             return _finish - _start;
  80.         }
  81.         size_t capacity() const {
  82.             return _endOfStorage - _start;
  83.         }
  84.  
  85.         void reserve(size_t n) {
  86.             if (n > capacity()) {
  87.                 size_t old_size = size();
  88.                 T* tmp = new T[n];
  89.                 if (_start != nullptr) {
  90.                     for (int i = 0; i < size(); i++) {
  91.                         tmp[i] = _start[i];
  92.                     }
  93.                 }
  94.                 delete[] _start;
  95.                 _start = tmp;
  96.                 _finish = _start + old_size;
  97.                 _endOfStorage = _start + n;
  98.             }
  99.         }
  100.  
  101.         void resize(size_t n, const T& value = T()) {
  102.             T* tmp = new T[n];
  103.             if (n <= size()) {
  104.                 for (size_t i = 0; i < n; i++) {
  105.                     tmp[i] = _start[i];
  106.                 }
  107.             }
  108.             else {
  109.                 for (size_t i = 0; i < size(); i++) {
  110.                     tmp[i] = _start[i];
  111.                 }
  112.                 for (size_t i = size(); i < n; i++) {
  113.                     tmp[i] = value;
  114.                 }
  115.             }
  116.             delete[] _start;
  117.             _start = tmp;
  118.             _finish = _endOfStorage =  _start + n;
  119.         }
  120.  
  121.         // 元素访问
  122.         T& operator[](size_t pos)
  123.         {
  124.             assert(pos < size());
  125.             return _start[pos];
  126.         }
  127.  
  128.         const T& operator[](size_t pos)const
  129.         {
  130.             assert(pos < size());
  131.             return _start[pos];
  132.         }
  133.  
  134.         T& front()
  135.         {
  136.             return *_start;
  137.         }
  138.  
  139.         const T& front()const
  140.         {
  141.             return *_start;
  142.         }
  143.  
  144.         T& back()
  145.         {
  146.             return *(_finish - 1);
  147.         }
  148.  
  149.         const T& back()const
  150.         {
  151.             return *(_finish - 1);
  152.         }
  153.  
  154.         // 增删
  155.         void push_back(const T& x) {
  156.             if (_finish = _endOfStorage){
  157.                 int newcapacity = capacity() == 0 ? 2 : 2 * capacity();
  158.             }
  159.             *_finish = x;
  160.             ++_finish;
  161.         }
  162.  
  163.         void pop_back() {
  164.             assert(size() > 0);
  165.             --_finish;
  166.         }
  167.  
  168.         void swap(vector<T>& v) {
  169.             vector<T> tmp(v);
  170.             delete[] v._start;
  171.             v._start = _start;
  172.             v._finish = _finish;
  173.             v._endOfStorage = _endOfStorage;
  174.             _start = tmp._start;
  175.             _finish = tmp._finish;
  176.             _endOfStorage = tmp._endOfStorage;
  177.         }
  178.  
  179.         iterator insert(iterator pos, const T& x) {
  180.             assert(pos < _finish&& pos >= _start);
  181.  
  182.             if (_finish == _endOfStorage)
  183.             {
  184.                 size_t site = pos - _start;
  185.                 int newcapacity = capacity() == 0 ? 2 : 2 * (capacity());
  186.                 reserve(newcapacity);
  187.  
  188.                 pos = _start + site;//pos到新空间的位置上
  189.             }
  190.             iterator end = _finish - 1;
  191.             while (end >= pos)//开始整体向后退
  192.             {
  193.                 *(end + 1) = *end;
  194.                 end--;
  195.             }
  196.             *pos = x;
  197.             ++_finish;
  198.  
  199.             return pos;
  200.         }
  201.  
  202.         iterator erase(iterator pos){
  203.             assert(pos < _finish&& pos >= _start);
  204.             assert(size() > 0);
  205.             //开始向前移动
  206.             iterator start = pos + 1;
  207.             while (start < _finish)
  208.             {
  209.                 *(start - 1) = *start;
  210.                 start++;
  211.             }
  212.             _finish--;
  213.             return pos;//返回删除的位置
  214.         }
  215.     private:
  216.         iterator _start; // 指向数据块的开始
  217.         iterator _finish; // 指向有效数据的尾
  218.         iterator _endOfStorage; // 指向存储容量的尾
  219.     };
  220. }

那么以上就是vector的模拟实现了，欢迎在评论区留言，觉得这篇博客对你有帮助的可以点赞关注收藏支持一波喔~

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/380474
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。