• 【C++】vector从理解到深入

    前言

            大家好呀！欢迎来到我的C++系列学习笔记！~上一篇是有关STL标准模板库的string的理解到深入，传送门在这里哦：【C++】从使用string类到模拟实现string类_柒海啦的博客-CSDN博客_c++引入string

            vector同样是STL里的一个容器，其功能就是存放任意数据的一个动态数组。这篇文章我会从会用vector的容器开始，理解到最后的模拟实现vector的基本框架，以便达到我们对此容器的一个熟练操作的目的。

    目录

    一、熟练使用vector 

    1.大致框架

    2.代码演示

    构造函数：

    插入、遍历操作：

    迭代器失效：

    容量 

    二、简单模拟实现vector 

    1.代码分析

     成员变量：

    插入成员变量变化演示： 

    迭代器相关实现：

     无参构造函数：

    迭代器区间构造函数：

    交换&拷贝构造：

    析构函数：

    数据个数和容量：

    赋值重载：

    []重载：

    开空间或者初始化reserve&resize:

    front、back、empty：

    操作：插入、删除

    2.综合代码：

    一、熟练使用vector 

            因为是STL，所以里面的容器操作还是熟悉的操作，我们只需要明白其容器的大致框架，然后具体的对这些进行模拟实现即可，所以我们针对这些框架去熟练使用vector。

    1.大致框架

            vector的理解流程大致如上图所示。首先自然了解其构造函数，明确内部所拥有的成员变量，其次也要明确析构。

            然后容量来说就是对整个空间进行申请或者初始化操作了，运算符重载要么就是方便使用，要么就是重载一些比较常用且重要的（比如赋值重载）。操作就是一个动态线性表一般的操作，随机插入，随机删除，尾插，尾删.......

            接下来我会用具体代码来对对应的模块进行演示，帮助我们一起理解vector这个容器。

            比较好的C++文档在这里：https://cplusplus.com/reference/vector/vector/

    2.代码演示

    构造函数：

            空数组、几个相同的数构造、拷贝构造、迭代器构造。

             参考代码：

    1. void test1()
    2. {
    3. 	vector<int> v1;										// 空
    4. 	vector<int> v2(6, 6);                               // 初始化6个6
    5. 	vector<int> v3(v2); // 或者 vector v3 = v2     // 拷贝构造
    6. 	vector<int> v4(v3.begin(), v3.end());			    // 迭代器构造
    7. }

            

             

             可以发现v1 v2 v3 v4对象均构造成功，v2对应的就是构造6个6，v3就是拷贝构造，v4用了两个迭代器进行构造。（一般线性顺序表的迭代器的底层实际上就是指针）

            既然构造成功了，那么我们就需要对其进行操作了。

    插入、遍历操作：

            首先，可以简单的看一下我们耳熟能详的push_back:(push_back实际上底层也就是调用的insert())。

             同样的，在vector里面也支持[]运算符重载，所以我们就可以通过下标的方式去遍历vector，自然同样存在size()是统计当前数据的个数的。

             参考代码：

    1. void test2()
    2. {
    3. 	// 插入 遍历
    4. 	vector<int> v1(6, 1);
    5. 	v1.push_back(2); // 尾插
    6. 	// 利用下标去遍历数据
    7. 	for (size_t i = 0; i < v1.size(); ++i)
    8. 	{
    9. 		cout << v1[i] << " ";
    10. 	}
    11. 	cout << endl;
    12.  
    13. }

     

            上述取出数据我们使用的是[]重载，实际上，我们取出数据的方式有很多种，这里介绍两种：一个取出头的数据front()，一个取出尾的数据back()。

     

             插入数据的话自然也就是有insert之类的函数：

             当然，和插入对应的就是删除了，erase()即随机删除：

     

             也存在尾删pop_back()：

             需要注意的是，上述传入的参数并不是size_t或者int的下标，而是迭代器iterator哦~

            提到迭代器自然就不会忘记end(),begin(),rend(),rbegin()...... 并且实际上此迭代器的实现底层也就是简单的指针，且类型应该是：std::vector::iterator

            那么我们可以利用其进行遍历--同时就可以使用范围for，然后进行一些基本的随机插入删除等操作：

    1. void test3()
    2. {
    3. 	// 插入遍历
    4. 	// 迭代器及其迭代器遍历：
    5. 	vector<int> v(3, 2);
    6. 	vector<int>::iterator it = v.begin();
    7. 	while (it != v.end())  // end为最后的元素的下一个
    8. 	{
    9. 		cout << *it << " ";  // 像指针一样的进行访问
    10. 		++(*it);  // 同样的可以进行修改
    11. 		++it;
    12. 	}
    13. 	cout << endl;
    14.  
    15. 	// 支持迭代器，也就支持范围for
    16. 	for (auto& e : v)
    17. 	{
    18. 		cout << e << " ";
    19. 	}
    20. 	cout << endl;
    21.  
    22. 	v[0] = 1;
    23. 	v[2] = 0;
    24. 	// 打印头尾，不用[]重载
    25. 	cout << "头：" << v.front() << endl;
    26. 	cout << "尾：" << v.back() << endl;
    27.  
    28. 	// 随机插入 先寻找
    29. 	it = find(v.begin(), v.end(), 3);
    30. 	// 在3前插入 2
    31. 	v.insert(it, 2);
    32.  
    33. 	for (auto& e : v)
    34. 	{
    35. 		cout << e << " ";
    36. 	}
    37. 	cout << endl;
    38.  
    39. 	// 随机删除
    40. 	//v.erase(it);  // 在把此位置删除  直接这样会出现失效的问题，所以必须重新寻找或者接收insert的返回值
    41. 	it = find(v.begin(), v.end(), 2);
    42. 	v.erase(it);
    43. 	for (auto& e : v)
    44. 	{
    45. 		cout << e << " ";
    46. 	}
    47. 	cout << endl;
    48.  
    49. }

             这里提到了迭代器失效的情况，那么这个是什么情况呢？

    迭代器失效：

            所谓迭代器失效，也就是在进行insert或者erase，即移动空间的时候，就可能会产生当前位置地址被释放掉，转移到其他地方去了，那么此时地址也就是野指针了，这就是迭代器失效。

    1. void test4()
    2. {
    3. 	vector<int> v(2, 2);
    4. 	auto it = v.begin();  // 头结点值地址
    5. 	printf("%p\n", it);
    6. 	v.erase(it);
    7. 	//验证it是否失效
    8. 	printf("%p\n", it);
    9. 	printf("%p\n", v.begin());
    10. 	for (auto& e : v)
    11. 	{
    12. 		cout << e << " ";
    13. 	}
    14. 	cout << endl;
    15. }

            此时可以发现三者的地址完全不一样，说明发生了变化，也就是所谓的迭代器失效了。

            其实，在不同的平台下，编译器对此迭代器失效的方法也存在不一样的地方：

            比如，我们测试程序12345，对此数组中的偶数进行删除：在linuxg++和Windows下的vs2022分别进行测试：

    1. void test5()
    2. {
    3. 	// 迭代器遍历随机删除
    4. 	vector<int> v;
    5. 	v.push_back(1);
    6. 	v.push_back(2);
    7. 	v.push_back(3);
    8. 	v.push_back(4);
    9. 	v.push_back(5);
    10.  
    11. 	for (auto& e : v)
    12. 	{
    13. 		cout << e << " ";
    14. 	}
    15. 	cout << endl;
    16.  
    17. 	vector<int>::iterator it = v.begin();
    18. 	// 迭代器失效
    19. 	while (it != v.end())
    20. 	{
    21. 		if (*it % 2 == 0)
    22. 		{
    23. 			// 偶数删除
    24. 			v.erase(it);
    25. 		}
    26. 		++it;
    27. 	}
    28. 	for (auto& e : v)
    29. 	{
    30. 		cout << e << " ";
    31. 	}
    32. 	cout << endl;
    33. }

     vs2022 直接崩溃

     Linux下的g++却没有。

            上述情况也就说明了：

    VS下和Linux下可能会不一样：STL只是一个规范-->不同的平台下面实现是不同的。

    VS下对迭代器会进行强制检查，如果原本指向的数据被清除了，下次在对此处指向（存在数据，不是野指针），但是会检查报错
    Linux下：12345没有问题（删去偶数，不正确使用）1235
        -- 数据排列的偶然性（最后一个不是偶数，没有连续的偶数）

            但是当我们遍历插入或者删除的时候就会产生很多不便，那么insert以及erase要如何处理才能优化好呢？对返回值进行操作：

     

            insert返回的就是新插入的那个元素位置的迭代器，而erase返回的就是被删除元素的下一个元素的迭代器。

            知晓这些之后，我们就可以稍微修改一下上面的代码，使其能在Windows平台下也能够跑起来：

    1. 	while (it != v.end())
    2. 	{
    3. 		if (*it % 2 == 0)
    4. 		{
    5. 			// 偶数删除
    6. 			it = v.erase(it);
    7. 		}
    8. 		else 
    9. 			++it;
    10. 	}

            此时就能够在Windows平台上跑了。

    容量 

            跟string这个类类似，实际上在STL内基本都有这个扩容以及初始化的reserve和resize，用法都基本一致，一个就是一开始申请多大空间，另一个就是申请的同时也初始化多少数据。

             其实我们发现resize默认给的是value_type(),其实有的时候存储的数据并不是内置类型，而是自定义类型，所以就会如此设计，这在之后的模拟实现也会涉及。

            参考代码：

    1. void test6()
    2. {
    3. 	// reserve
    4. 	vector<int> v1;
    5. 	v1.reserve(10);
    6. 	cout << v1.capacity() << endl;
    7.  
    8. 	// resize
    9. 	vector<int> v2;
    10. 	v2.resize(6, 2);  // 初始化6个数据，均为2
    11. 	for (auto e : v2)
    12. 	{
    13. 		cout << e << " ";
    14. 	}
    15. 	cout << endl;
    16. 	v2.resize(10, 1);  // 当申请空间比原本数据个数大，那么会将没填充的数据填为对应数据
    17. 	for (auto e : v2)
    18. 	{
    19. 		cout << e << " ";
    20. 	}
    21. 	cout << endl;
    22. 	v2.resize(2, 0);  // 如果比原本数据小，会发生截断，不会填充数据
    23. 	for (auto e : v2)
    24. 	{
    25. 		cout << e << " ";
    26. 	}
    27. 	cout << endl;
    28. }

     

            在了解一些基本并且熟练的时候，就可以对vector进行更加深入的模拟实现了：

    二、简单模拟实现vector 

            大致了解后，我们想要进一步深入理解vector的话，就要对其进行模拟实现。既然只是简单的去模拟实现，那么我们只需要实现一个大致框架即可：

    1.代码分析

    准备工作：

            我们首先可以将其实现代码放在一个命名空间内，这样就可以不用和std内官方的vector相互冲突。当然，此类可以定义在一个头文件内，比如叫做vector.h，这样方便其他程序进行调用此头文件。

            然后，此类是一个模板类，因为里面的存储的数据可不只有int一种，自然使用template来进行定义：

    1. namespace QiHai
    2. {
    3. 	// 类模板
    4. 	template<typename T>
    5. 	class vector
    6. 	{
    7.         //...
    8.     }
    9. //...
    10. }

     成员变量：

            首先看我们的私有成员。因为这是一个顺序结构，所以内存地址是连续的，也就是普通的在堆上申请的动态数组。结合std官方的实现，我们可以定义如下三个指针：（同时将指针重命名为迭代器类型）

    1. 	public:
    2. 		typedef T* iterator;  // 定义迭代器类型为iterator
    3. 		typedef const T* const_iterator;
    1. 	private:
    2. 		iterator _start;          // 存储数据的开始位置
    3. 		iterator _finish;         // 存储数据的最后一个位置的后一个位置
    4. 		iterator _end_of_storage; // 存储数据的空间最后一个地址

            三者在某一时候关系可以如图所示：

    插入成员变量变化演示： 

             那么此时你的内心是否存在一个疑惑：那么这些是如何进行控制的呢？其实也就是保证开空间和插入的时候控制其在对应的位置即可，这些后面均会实现，现在这里可以进行一个简单的演示：（假设第一次插入开8个空间）

    迭代器相关实现：

            和string的实现不一样，我们对外提供的接口也是迭代器，所以首先提供一些基本的迭代器接口：比如begin()、end()等。

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

     无参构造函数：

            然后就是最基本的构造函数也是最常用的构造函数。如上述演示一样，我们只需控制三个变量初始化为nullptr即可。

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

    迭代器区间构造函数：

            为了方便后序的拷贝构造函数方便调用，并且也是一种构造函数方式，即对传入的类似于地址使用（即*解应用就是数据），要使用模板函数，结构如下：（push_back还未写，下面会进行实现）--（传入的迭代器，就有点类似于迭代器遍历）

    1. 		template <class InputIterator>
    2. 		vector(InputIterator first, InputIterator last)
    3. 			:_start(nullptr)
    4. 			,_finish(nullptr)
    5. 			,_end_of_storage(nullptr)
    6. 		{
    7. 			while (first != last)
    8. 			{
    9. 				push_back(*first);
    10. 				++first;
    11. 			}
    12. 		}

    交换&拷贝构造：

            拷贝构造也分为现代写法和原始写法，原始写法就是重新建立一个空间，然后一一把传入的对象的数据拷贝到新空间上去，否则默认的拷贝构造实现的是浅拷贝（注意此深拷贝不能使用memcpy进行数据替换，因为当储存对象本身也是一个数组的时候，即内部存的同样也是地址，那么此时就会出现问题，这就是深度拷贝，后面也会具体讲，需要一个一个进行赋值）

            当然，除了原始写法，现代写法就高明的多， 会让一个具体的对象帮我们做事，然后将地址进行交换即可。这个对象也就是我们上面的迭代器区间构造，而地址交换就需要我们自己实现一个。

            交换函数很简单，只需要执行外部的交换函数将我们每一个变量所存的地址交换即可。

            （注意传入的参数必须是一个类型，vector可不是一个具体的类型，而是一个模板，所以需要哦~） 

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

            拷贝构造现代写法：

    1. 		vector(const vector& v)
    2. 			:_start(nullptr)
    3. 			, _finish(nullptr)
    4. 			, _end_of_storage(nullptr)
    5. 		{
    6. 			// 现代做法，请打工人
    7. 			vector tmp(v.begin(), v.end());  // 请到的打工人
    8. 			swap(tmp);  // 两者交换，它的就是我的了
    9. 		}

    析构函数：

            析构函数很简单，因为我们变量的申请的空间由堆而来（new/malloc），所以我们将头指针释放掉，然后将其所有变量置为空即可。

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

    数据个数和容量：

            为了统计当前数据个数以及容量大小，结合之前创建变量的介绍，这里可以轻松的解决：

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

    赋值重载：

            赋值重载和拷贝构造函数有点类似，只不过一个是新创建一个对象，而赋值是两个以及存在的对象让另一个的值拷贝给另一个。

            也有原始写法和现代写法，原始写法同样注意深度拷贝的问题，而现代写法就只需要让形参做工具人，因为此时传参就会发生拷贝构造，然后与其形参交换数据即可。同时注意返回对象的本身。

    1. 		vector& operator=(vector v)
    2. 		{
    3. 			swap(v);  // 把形参当做打工人
    4. 			return *this;
    5. 		}

    []重载：

            此重载也就是方便像数组一样的对下标进行访问，方便快捷。实际上也就是根据传入的下标，根据首元素地址加减获得，因为可以修改数据，那么就可传出引用，const对象加上const即可：

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

    开空间或者初始化reserve&resize:

            开空间是插入的基础。首先就需要存在空间才能进行插入操作，也才能真正的构造一个数组。如上面的动画演示一样，我们可以对这个函数传入n表示我们要开n个对应数据类型的空间。

            所谓开空间，也就是原来开的的一串地址空间不够了或者没有，然后需要开辟一个比原来大的空间供数据进行操作。既然是新的空间，那么数据就要进行搬家。数据搬家也就是要进行拷贝。在拷贝的同时我们要注意到数据类型不再是像string那样简单的char类型了，而是T。这个T可以是内置类型，当然也可以是vector。此时我们存储的数据本身里面也存储的有地址，所以如果只是单单的memcpy的话，只是表面上给存储vector开辟了新的空间，但是内部却还是和原来那个指向的同一空间。所以为了解决这个问题，我们只需一个一个赋值就可以解决这个更深层次的拷贝了。

    1. 		void reserve(size_t n)
    2. 		{
    3. 			if (n > capacity())
    4. 			{
    5. 				iterator new_start = new T[n];
    6. 				size_t len = size();
    7.  
    8. 				if (_start)  // 有可能是空数据进行
    9. 				{
    10. 					// 普通的进行内存拷贝的话，存在更深层次无法拷贝
    11. 					//memcpy(new_start, _start, sizeof(T) * capacity());
    12. 					// 深层次拷贝  一个一个进行拷贝 方便调用其赋值进行深拷贝
    13. 					for (size_t i = 0; i < len; i++)
    14. 						new_start[i] = _start[i];
    15. 					delete[] _start;
    16. 				}
    17.  
    18. 				_start = new_start;
    19. 				_finish = _start + len;
    20. 				_end_of_storage = _start + n;
    21. 			}
    22. 		}

            开空间并且初始化实际上分为两个步骤，一个进行开空间，另一个负责初始化数据。注意缺省参数是一个匿名构造，C++为了迎合自定义类型初始数据的问题，也给内置类型定义了一个匿名对象，所以使用匿名对象对内置类型同样适合。

    1. 		void resize(size_t n, const T& val = T())  // 缺省值给T的一个匿名对象 （C++为了迎合自定义类型，也给内置类型增加了无参构造）
    2. 		{
    3. 			// 1. n > capacity()
    4. 			if (n > capacity())
    5. 			{
    6. 				reserve(n);  // 扩容
    7. 			}
    8. 			for (size_t i = size(); i < n; i++)
    9. 				_start[i] = val;
    10.  
    11. 			_finish = _start + n;
    12. 		}

    front、back、empty：

            front获得头数据，back获得尾数据，只需要像数组那样访问即可，记得传出引用即可：

    1. 		T& front()
    2. 		{
    3. 			assert(size() > 0);
    4. 			return *(_start);
    5. 		}
    6.  
    7. 		T& back()
    8. 		{
    9. 			assert(size() > 0);
    10. 			return *(_finish - 1);
    11. 		}
    12.  
    13. 		bool empty()
    14. 		{
    15. 			return _start == _finish;
    16. 		}

    操作：插入、删除

            只有插入我们才能对数据进行管理。随机插入可以复用于尾插，随机删除同样可以。需要注意的是在挪动空间，原本传入的迭代器就可能出现失效的问题，那么我们只需控制insert返回插入后新数据所在的位置指针，删除数据的下一个数据位置指针即可。（插入空间满申请空间，然后进行移动，删除进行移动操作）--注意检查边界问题哦~

    1. 		// 随机插入
    2. 		iterator insert(iterator pos, const T& val)
    3. 		{
    4. 			assert(pos >= _start);
    5. 			assert(pos <= _finish);
    6. 			// 满了就需要扩容
    7. 			if (_finish == _end_of_storage)
    8. 			{
    9. 				size_t len = pos - _start;
    10. 				reserve(capacity() == 0 ? 4 : capacity() * 2); // 扩容后，原本地址会发生改变
    11. 				pos = _start + len;  // pos也发生变化
    12. 			}
    13. 			
    14. 			iterator temp = _finish - 1;
    15. 			while (temp >= pos)
    16. 			{
    17. 				*(temp + 1) = *temp;
    18. 				--temp;
    19. 			}
    20. 			*pos = val;
    21. 			++_finish;
    22.  
    23. 			return pos;  // 返回改变地址后的迭代器位置
    24. 		}
    25.  
    26. 		// 随机删除  返回删除位置的下一个位置的迭代器
    27. 		iterator erase(iterator pos)
    28. 		{
    29. 			assert(pos < _finish);
    30. 			assert(pos >= _start);
    31.  
    32. 			iterator temp = pos + 1;
    33. 			while (temp <= _finish)
    34. 			{
    35. 				*(temp - 1) = *(temp);
    36. 				++temp;
    37. 			}
    38.  
    39. 			_finish--;
    40.  
    41. 			return pos;
    42. 		}

            此时尾插尾删复用即可。

    2.综合代码：

            仅供参考，有误请大佬指正！

    1. // vector.h
    2. #pragma once
    3. #include
    4. #include
    5. #include
    6. #include
    7.  
    8. using namespace std;
    9.  
    10. // 模拟实现vector
    11.  
    12. namespace QiHai
    13. {
    14. 	// 类模板
    15. 	template<typename T>
    16. 	class vector
    17. 	{
    18. 	public:
    19. 		typedef T* iterator;  // 定义迭代器类型为iterator
    20. 		typedef const T* const_iterator;
    21.  
    22. 		// 迭代器
    23. 		iterator begin()
    24. 		{
    25. 			return _start;
    26. 		}
    27.  
    28. 		iterator end()
    29. 		{
    30. 			return _finish;
    31. 		}
    32.  
    33. 		const_iterator begin() const
    34. 		{
    35. 			return _start;
    36. 		}
    37.  
    38. 		const_iterator end() const
    39. 		{
    40. 			return _finish;
    41. 		}
    42.  
    43. 		// 类中交换函数
    44. 		void swap(vector& v)
    45. 		{
    46. 			::swap(_start, v._start);
    47. 			::swap(_finish, v._finish);
    48. 			::swap(_end_of_storage, v._end_of_storage);
    49. 		}
    50.  
    51. 		// 构造函数
    52. 		vector()
    53. 			:_start(nullptr)
    54. 			,_finish(nullptr)
    55. 			,_end_of_storage(nullptr)
    56. 		{}
    57.  
    58. 		// 迭代器区间进行初始化构造
    59. 		template <class InputIterator>
    60. 		vector(InputIterator first, InputIterator last)
    61. 			:_start(nullptr)
    62. 			,_finish(nullptr)
    63. 			,_end_of_storage(nullptr)
    64. 		{
    65. 			while (first != last)
    66. 			{
    67. 				push_back(*first);
    68. 				++first;
    69. 			}
    70. 		}
    71.  
    72. 		// 拷贝构造
    73. 		vector(const vector& v)
    74. 			:_start(nullptr)
    75. 			, _finish(nullptr)
    76. 			, _end_of_storage(nullptr)
    77. 		{
    78. 			// 现代做法，请打工人
    79. 			vector tmp(v.begin(), v.end());  // 请到的打工人
    80. 			swap(tmp);  // 两者交换，它的就是我的了
    81. 		}
    82.  
    83.  
    84. 		// 析构函数
    85. 		~vector()
    86. 		{
    87. 			delete[] _start;
    88. 			_start = _finish = _end_of_storage = nullptr;
    89. 		}
    90. 		
    91. 		// 数据个数
    92. 		size_t size() const
    93. 		{
    94. 			return _finish - _start;
    95. 		}
    96.  
    97. 		size_t capacity() const
    98. 		{
    99. 			return _end_of_storage - _start;
    100. 		}
    101.  
    102. 		// 重载
    103. 		// 赋值重载
    104. 		vector& operator=(vector v)
    105. 		{
    106. 			swap(v);  // 把形参当做打工人
    107. 			return *this;
    108. 		}
    109.  
    110. 		// []重载
    111. 		T& operator[](size_t n)
    112. 		{
    113. 			assert(n < size());
    114. 			return _start[n];
    115. 		}
    116.  
    117. 		const T& operator[](size_t n) const
    118. 		{
    119. 			assert(n < size());
    120. 			return _start[n];
    121. 		}
    122.  
    123. 		// 开空间  
    124. 		void reserve(size_t n)
    125. 		{
    126. 			if (n > capacity())
    127. 			{
    128. 				iterator new_start = new T[n];
    129. 				size_t len = size();
    130.  
    131. 				if (_start)  // 有可能是空数据进行
    132. 				{
    133. 					// 普通的进行内存拷贝的话，存在更深层次无法拷贝
    134. 					//memcpy(new_start, _start, sizeof(T) * capacity());
    135. 					// 深层次拷贝  一个一个进行拷贝 方便调用其赋值进行深拷贝
    136. 					for (size_t i = 0; i < len; i++)
    137. 						new_start[i] = _start[i];
    138. 					delete[] _start;
    139. 				}
    140.  
    141. 				_start = new_start;
    142. 				_finish = _start + len;
    143. 				_end_of_storage = _start + n;
    144. 			}
    145. 		}
    146.  
    147. 		// 开空间并且初始化
    148. 		void resize(size_t n, const T& val = T())  // 缺省值给T的一个匿名对象 （C++为了迎合自定义类型，也给内置类型增加了无参构造）
    149. 		{
    150. 			// 1. n > capacity()
    151. 			if (n > capacity())
    152. 			{
    153. 				reserve(n);  // 扩容
    154. 			}
    155. 			for (size_t i = size(); i < n; i++)
    156. 				_start[i] = val;
    157.  
    158. 			_finish = _start + n;
    159. 		}
    160.  
    161. 		T& front()
    162. 		{
    163. 			assert(size() > 0);
    164. 			return *(_start);
    165. 		}
    166.  
    167. 		T& back()
    168. 		{
    169. 			assert(size() > 0);
    170. 			return *(_finish - 1);
    171. 		}
    172.  
    173. 		bool empty()
    174. 		{
    175. 			return _start == _finish;
    176. 		}
    177.  
    178. 		void pop_back()
    179. 		{
    180. 			assert(_finish > _start);
    181. 			--_finish;
    182. 		}
    183.  
    184. 		// 操作
    185. 		// 尾插
    186. 		void push_back(const T& val)
    187. 		{
    188. 			// 直接复用insert()即可
    189. 			insert(end(), val);
    190. 		}
    191.  
    192. 		// 随机插入
    193. 		iterator insert(iterator pos, const T& val)
    194. 		{
    195. 			assert(pos >= _start);
    196. 			assert(pos <= _finish);
    197. 			// 满了就需要扩容
    198. 			if (_finish == _end_of_storage)
    199. 			{
    200. 				size_t len = pos - _start;
    201. 				reserve(capacity() == 0 ? 4 : capacity() * 2); // 扩容后，原本地址会发生改变
    202. 				pos = _start + len;  // pos也发生变化
    203. 			}
    204. 			
    205. 			iterator temp = _finish - 1;
    206. 			while (temp >= pos)
    207. 			{
    208. 				*(temp + 1) = *temp;
    209. 				--temp;
    210. 			}
    211. 			*pos = val;
    212. 			++_finish;
    213.  
    214. 			return pos;  // 返回改变地址后的迭代器位置
    215. 		}
    216.  
    217. 		// 随机删除  返回删除位置的下一个位置的迭代器
    218. 		iterator erase(iterator pos)
    219. 		{
    220. 			assert(pos < _finish);
    221. 			assert(pos >= _start);
    222.  
    223. 			iterator temp = pos + 1;
    224. 			while (temp <= _finish)
    225. 			{
    226. 				*(temp - 1) = *(temp);
    227. 				++temp;
    228. 			}
    229.  
    230. 			_finish--;
    231.  
    232. 			return pos;
    233. 		}
    234.  
    235. 	private:
    236. 		iterator _start;          // 存储数据的开始位置
    237. 		iterator _finish;         // 存储数据的最后一个位置的后一个位置
    238. 		iterator _end_of_storage; // 存储数据的空间最后一个地址
    239. 	};
    240. }

            谢谢观看~

  • 相关阅读:
    【GDB】用 python 扩展 gdb
    MyBatis-Plus（三、增删改查）
    Qt | windows Qt6.5.3安卓环境搭建成功版(保姆级教程)
    雅虎、领英接连退出中国，开发者：GitHub 也会受到影响吗？
    SpringBoot Web开发----简单功能分析
    安装chrome对应驱动
    开源与闭源：大模型发展的未来之路
    问题汇总20231117
    Anchor-free目标检测综述 -- Keypoint-based篇
    YOLOv5/YOLOv7损失函数改进：SlideLoss创新升级，结合IOU动态调整困难样本的困难程度，提升小目标、遮挡物性能
  • 原文地址：https://blog.csdn.net/weixin_61508423/article/details/126917530