C++初阶：适合新手的手撕vector（模拟实现vector）

上次讲了常用的接口：C++初阶：容器（Containers）vector常用接口详解
今天就来进行模拟实现啦

1.基本结构与文件规划

• vector.h头文件：包含类的全部(函数的声明与定义)
• test.cpp源文件：进行调用test函数，测试和完善功能

基本结构，先看一下源码：

namespace MyVector
{template <class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//先定义好迭代器//各种函数private:iterator _start;iterator _finish;iterator _endOfStorage;};
}

• _start：指向动态数组的起始位置的指针，即第一个元素的位置。
• _finish：指向动态数组中最后一个元素之后的位置的指针。在这个实现中，_finish 指针始终指向当前元素范围的末尾，也就是下一个要插入元素的位置。
• _endOfStorage：指向动态数组分配的内存空间的末尾之后的位置的指针。在这个实现中，_endOfStorage 指针指向当前分配的内存空间的末尾，当需要扩充容量时，会通过比较 _finish 和 _endOfStorage 的位置来判断是否需要重新分配更大的内存空间

2.空参构造函数（constructor)

		vector():_start(nullptr), _finish(nullptr), _endOfStorage(nullptr)//直接使用初始化列表{}

都初始化为空指针

#3.迭代器（iterator）(begin(),end())

		iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}

进行const的重载

4.基本函数（size(),capacity(),resize(),reserve())

		void reserve(size_t n){if (n > capacity()){int old_size = size();//保存一下长度，方便后续给_finish移到新的位置T* tmp = new T[n];if (_start != nullptr)//vector里存东西了{for (size_t i = 0; i < size(); ++i){tmp[i] = _start[i];//_start本质是指针}}delete[] _start;_start = tmp;_finish = _start + old_size;_endOfStorage = _start + n;}}void resize(size_t n, const T& x = T()){if (n > size()){reserve(n);//<capacity 的话，也没有进行处理while (_finish != _start + n){*_finish = x;++_finish; }}else{_finish = _start + n;//小于长度时，直接移动finish}}size_t size(){return _finish - _start;}size_t capacity(){return _endOfStorage - _start;}

1. reserve 函数：

• reserve 函数用于保留至少能容纳 n 个元素的内存空间。如果当前的容量小于 n，则会分配新的内存空间，并将原来的元素复制到新的内存空间中。
• 首先，它会创建一个新的大小为 n 的临时数组 tmp，然后将原始数组中的元素复制到临时数组中。
• 接着，释放原始数组的内存空间，将 _start 指针指向新分配的内存空间，同时更新 _finish 和 _endOfStorage 的位置。

2. resize 函数：

• resize 函数用于改变数组的大小，使其包含 n 个元素，并使用值 x 进行初始化。
• 如果 n 大于当前的大小，它会调用 reserve 函数以确保数组有足够的容量，然后将数组的大小增加到 n，并使用值 x 进行初始化。
• 如果 n 小于当前的大小，它会直接将 _finish 指针移动到新的位置，从而改变数组的大小。

3. size 函数：

• size 函数用于返回数组中元素的个数，即 _finish 和 _start 之间的距离。

4. capacity 函数：

• capacity 函数用于返回数组的容量，即 _endOfStorage 和 _start 之间的距离

怎么来理解：const T& x = T()

实现给出各种类型的默认值，在这里为了妥协，其实内置类型也有构造函数在 C++ 中。内置类型（如 int、float、double 等）也有默认构造函数。默认构造函数对于内置类型来说，其实就是不带参数的构造函数，它会将变量初始化为默认值

1. T() 表示创建一个类型 T 的临时对象，并进行值初始化。这里假设 T 是一个类或者结构体，那么这个语句会调用 T 的默认构造函数来创建一个临时对象。
2. const T& x 表示创建一个类型为 T 的常量引用 x。这里的引用是 T 类型的引用，而且是常量引用，意味着 x 引用的对象是不可修改的。
3. const T& x = T() 将这个临时对象绑定到常量引用 x 上。这样做的好处是可以避免不必要的拷贝，同时也可以确保 x 引用的对象是不可修改的。

使用如下来测试

	void test1(){vector<int> v;for (auto e : v){cout << e << " ";}cout << endl;v.resize(10);for (auto e : v){cout << e << " ";}cout << endl;v.resize(5);for (auto e : v){cout << e << " ";}cout << endl;}

4.增删改查(push_back,pop_back,insert,erase)

		void push_back(const T& x){if (_finish == _endOfStorage){int newcapacity = capacity() == 0 ? 2 : 2 * capacity();reserve(newcapacity);}*_finish = x;_finish++;}void pop_back(){assert(size() > 0);--_finish;}iterator insert(iterator pos, const T& x)//在pos前插入{assert(pos < _finish&& pos >= _start);if (_finish == _endOfStorage){size_t site = pos - _start;int newcapacity = capacity() == 0 ? 2 : 2 * (capacity());reserve(newcapacity);pos = _start + site;//pos到新空间的位置上}iterator end = _finish - 1;while (end >= pos)//开始整体向后退{*(end + 1) = *end;end--;}*pos = x;++_finish;return pos;}iterator erase(iterator pos)//删pos处{assert(pos < _finish&& pos >= _start);assert(size() > 0);//开始向前移动iterator start = pos + 1;while (start < _finish){*(start - 1) = *start;start++;}_finish--;return pos;//返回删除的位置}

使用test2函数看功能是否正常

void test2(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);//尾插3个for (auto e : v){cout << e << " ";}cout << endl;v.pop_back();//尾删一个for (auto e : v){cout << e << " ";}cout << endl;v.insert(v.begin(), 0);//头插一个0for (auto e : v){cout << e << " ";}cout << endl;v.erase(v.begin());//头删for (auto e : v){cout << e << " ";}cout << endl;}

5.在实现Insert和erase时迭代器失效问题

当使用迭代器遍历容器时，如果在遍历的过程中对容器进行了结构性的修改（例如插入、删除元素，重新分配内存等操作），可能会导致迭代器失效。迭代器失效意味着该迭代器不再指向有效的元素或容器的结尾，因此继续使用失效的迭代器可能会导致未定义行为。

迭代器失效的原因主要有以下几种：

1. 插入操作：当在容器中插入元素时，可能会导致容器内部的元素发生移动或重新分配内存，这会导致原先的迭代器失效。因为插入元素后，原先的迭代器可能不再指向正确的位置。
2. 删除操作：当在容器中删除元素时，可能会导致容器内部的元素发生移动，也会导致原先的迭代器失效。因为删除元素后，原先的迭代器可能指向了一个已经被删除的元素，或者指向了不正确的位置。
3. 重新分配内存（扩容时）：某些容器在元素数量达到一定阈值时会进行内存的重新分配，这会导致原先的迭代器失效。因为重新分配内存后，原先的迭代器可能指向了无效的内存地址。
4. 容器的清空：当对容器进行清空操作时，所有的元素都被移除，迭代器也会失效。

迭代器失效可以大致分为两类：

1. 结构性变化导致的失效：这类失效包括扩容时申请了新空间、插入或删除元素导致元素位置改变等情况。在这种情况下，原先的迭代器可能会指向已经被移动或者删除的元素，或者指向了新分配的内存空间，导致迭代器失效。
2. 数据变化导致的失效：这类失效包括使用了 memmove、std::copy 等函数对容器内部元素进行移动或复制的情况。这些函数可能会导致容器内部的元素发生移动，导致原先的迭代器指向的位置发生变化，从而导致迭代器失效。

	void test3(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (auto e : v){cout << e << " ";}cout << endl;//删除偶数vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0){it=v.erase(it);//这里不能只是v.erase(it); 删除后}else{it++;}}for (auto e : v){cout << e << " ";}cout << endl;}

在使用 erase 函数删除元素后，erase 函数会返回指向被删除元素之后的元素的迭代器，而不是原先被删除元素的迭代器。如果使用 v.erase(it);，则会导致 it 迭代器失效，因为它指向的元素已经被删除，而 it 没有更新。因此，为了确保迭代器的有效性，需要将返回的迭代器赋值给 it，以便在下一次循环中继续使用正确的迭代器。

6.重载[]

		T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}

7. 完善构造函数

7.1vector (size_type n, const value_type& val = value_type());

		vector(size_t n, const T& val= T()){resize(n, val);}vector(int n, const T& val = T())//适用于  vector<int> v(5,1){resize(n, val);}

7.2利用迭代器进行构造

		template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}

为什么使用模版：

因为可能使用其他类型的迭代器来进行初始化

7.3拷贝构造

		vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_endOfStorage(nullptr)//先利用初始化列表进行初始化{reserve(v.capacity());for (const auto& e : v){push_back(e);}}

8.重载=

		void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}

注意这里的参数不是常量引用，而是按值传递的。这是因为在赋值操作符中我们会调用 swap 函数，按值传递可以保证传入的参数会被复制一份，避免对原对象的修改。在函数体内，我们调用了 swap 函数，将当前对象和传入的对象进行内容交换，然后返回 *this，即当前对象的引用。

9.析构函数

		~vector(){delete[] _start;_start = _finish = _endOfStorage = nullptr;}

好啦，今天就到这里啦，感谢大家支持！！！