片头
嗨~小伙伴们，今天我们来一起学习关于C++的vector类的模拟实现，准备好了吗？咱们开始咯~
一、基本框架
namespace bit {template<class T>class vector {public:typedef T* iterator;typedef const T* const_iterator;// 针对const修饰的迭代器private:iterator _start; //指向数据块的开始iterator _finish; //指向有效数据的结尾iterator _end_of_storage; //指向存储容量的结尾};
}我们定义了一个模板类，这里的vector三个成员均为迭代器，而Vector的迭代器是一个原生指针，我们这里为其定义别名iterator
私有成员：
iterator _start; //指向数据块的开始iterator _finish; //指向有效数据的结尾iterator _end_of_storage;//指向存储容量的结尾这些成员变量用于管理vector内部的动态数组
（1）_start：这是一个指针，指向分配给vector的内存区域的开始。这是数组的第一个元素。
（2）_finish：这个指针指向数组中最后一个实际存在的元素的下一个位置。这意味着它指向结束后的第一个元素，它用来表示存储在vector中的实际元素的结束。
（3）_end_of_storage：这个指针指向分配给vector的内存块的末尾。这不是最后一个有效元素的位置，而是整个内存块的结束位置，在这之后可能会有额外的未初始化空间，预留以实现当vector增长时无需重新分配整个数组
二、相关函数
（1）size();
获取有效元素的个数
//获取有效元素的个数 size_t size() {return _finish - _start;}size_t size() const {return _finish - _start;}（2）capacity();
获取容量的大小
//获取容量的大小 size_t capacity() {return _end_of_storage - _start;}size_t capacity() const {return _end_of_storage - _start;}（3）reserve(size_t n);
如果容量不足，就开辟空间
有同学肯定会说，那还不简单~ ，下面我们来示范错误代码：
//如果当前容量不足,就开辟空间 void reserve(size_t n) {//n大于实际的容量,那么开辟新空间if (n > capacity()) {T* temp = new T[n];//重新申请一块新空间,能够存放n个有效数据memcpy(temp, _start, sizeof(T) * size());//将原来的数据拷贝到temp中delete[] _start;//释放旧空间_start = temp; //将新空间的地址赋给_start}_finish = _start + size();//更新_finish_end_of_storage = _start + n;//更新_end_of_storage}但是这里有一个很大的问题：原来的_start的地址被销毁了，temp赋值给_start，_start指向新的空间，但是_finish还是旧的_finish，而size()函数需要用_finish-_start，所以此时的size()是无效的。
怎么解决这个问题呢？我们可以先用一个变量oldsize把原来的size()保存，后面_finish直接使用oldsize即可。
改进代码（仍不完善）：
//不完善的代码 void reserve(size_t n) { size_t oldsize = size();//使用oldsize变量将原来的size()保存if (n > capacity()) {T* temp = new T[n];memcpy(temp, _start, sizeof(T) * size());delete[] _start;_start = temp;}_finish = _start + oldsize;//直接使用oldsize_end_of_storage = _start + n;}我们知道，只有当传递过来的n大于capacity()时，才需要扩容；并且，只有当旧空间有值的时候，才需要拷贝到新空间中，否则不做处理。因此，还可以进行优化：
//优化版本 void reserve(size_t n) { if (n > capacity()){size_t oldsize = size();//使用oldsize变量将原来的size()保存T* temp = new T[n];if (_start) //当_start存在的时候,进行拷贝{memcpy(temp, _start, sizeof(T) * size());delete[] _start;}_start = temp;_finish = _start + oldsize;//直接使用oldsize_end_of_storage = _start + n;}}（4）push_back(const T& val);
从容器尾部插入一个元素
//尾插void push_back(const T& val) {if (_finish == _end_of_storage) //如果_finish和_end_of_storage重合,那么需要扩容{size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();//更新newCapacityreserve(newCapacity);//将newCapacity传递给reserve函数}*_finish = val;//如果不需要扩容,直接插入到_finish的位置即可++_finish; //_finish更新}此外,push_back函数还可以进行优化：
//尾插void push_back(const T& val) {//if (_finish == _end_of_storage) //如果_finish和_end_of_storage重合,那么需要扩容//{// size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();//更新newCapacity// reserve(newCapacity);//将newCapacity传递给reserve函数//}//*_finish = val;//如果不需要扩容,直接插入到_finish的位置即可//++_finish; //_finish更新insert(end(), val);//在end()位置,插入val}（5）T& operator[](size_t i);
使用operator[]访问当前下标的元素
//operator[]T& operator[](size_t i) {assert(i < size());//严格空值i的取值范围return _start[i]; //返回当前下标的元素}注意，使用assert函数时，必须包含头文件#include<assert.h>
写了这么多函数了，让我们来测试一下：
注意：所有的成员变量，成员函数声明和定义都是放在vector.h中的，只有测试代码放在test.cpp里面。
.h中我们使用到了cout和endl，虽然.h文件中没有包含#include<iostream>和using namespace std，但是并没有报错，为什么呢？因为.h文件不会被编译，在预处理阶段，.h文件就会在.cpp文件里面展开。
可以这么说，编译和链接的时候，没有.h这一个概念，.h已经在.cpp中展开了，只有test.cpp了。在test.cpp里面，我们把.h的内容都拷贝过来，编译器会向上查找。查找到了#include<iostream>和命名空间，因此，不会报错。
不过，必须要把#include<iostream>和using namespace std;写在#include"vector.h"的上面哦~因为编译器只会向上查找。如果在"vector.h"的上面没有找到这2个，会报错。
（6）vector();构造函数
空值初始化：
//构造函数vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}我们也可以直接利用缺省值来完成
//构造函数vector(){}private:iterator _start = nullptr; //指向数据块的开始iterator _finish = nullptr; //指向有效数据的结尾iterator _end_of_storage = nullptr;//指向存储容量的结尾（7）~vector()析构函数
//析构函数~vector() {delete[] _start;_start = _finish = _end_of_storage = nullptr;}（8）iterator begin();
//迭代器iterator begin() {return _start;}const_iterator begin() const {return _start;}（9）iterator end();
//迭代器iterator end() {return _finish;}const_iterator end() const {return _finish;}我们测试一下：
（10）pop_back();
从容器尾部删除一个数据
//尾删void pop_back() {assert(size() > 0);//保证有效元素个数必须大于0--_finish; //_finish更新}（11）iterator insert(iterator pos,const T& x);
在pos位置插入一个元素x
可能有小伙伴觉得，太简单了，咱们先来示范一个错误代码：
//在pos位置插入元素x
//错误代码void insert(iterator pos, const T& val) {assert(pos >= _start);assert(pos <= _finish);//检查是否需要扩容if (_finish == _end_of_storage) {size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newCapacity);}iterator end = _finish - 1;//end位置在最后一个元素的位置while (end >= pos) //如果end>=pos,那么需要移动元素{*(end + 1) = *end; //将当前元素移动到下一个位置--end; //end继续往前遍历,最后一次: *(pos+1) = *(pos)}*pos = val; //在pos处插入元素val++_finish; //更新_finish}我们运行一下：
这是因为，在insert函数里面，如果_finish == _end_of_storage，那么就会调用reserve函数去扩容。原来的空间被释放，取而代之的是新的空间。
但是pos位置仍然在原来的空间里面，一起被释放掉了，并且没有在新的空间标记出来。因此，我们需要定义一个变量len，来保存pos在原来空间的位置，再把pos标记到新的空间里面。
//不完善版本
//在pos位置插入元素xvoid insert(iterator pos, const T& val) {assert(pos >= _start);assert(pos <= _finish);//检查是否需要扩容if (_finish == _end_of_storage) {size_t len = pos - _start; //保存原来的pos位置size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newCapacity);pos = _start + len; //在新的空间中标记pos位置}iterator end = _finish - 1;while (end >= pos) {*(end + 1) = *end; --end; }*pos = val; ++_finish; }现在测试一下：
我们还可以利用#include<algorithm>库里面提供的find函数，找到值对应的pos位置进行插入数据。
int x;cin >> x;//没有x就不插入,有x的前面插入vector<int>::iterator it = find(v1.begin(), v1.end(), x);if (it != v1.end()) {//insert以后,it这个实参会不会失效？会！//迭代器失效的建议是：不要使用失效的迭代器v1.insert(it, 200);}for (auto e : v1) {cout << e << " ";}cout << endl;
insert以后，pos这个位置会失效，因此，我们不要去使用失效的迭代器。如果一定要访问，那么必须赋值更新一下这个失效的迭代器。
我们还可以进一步优化，返回新插入位置的迭代器（返回pos位置）：
//在pos位置插入元素xiterator insert(iterator pos, const T& val) {assert(pos >= _start);assert(pos <= _finish);//检查是否需要扩容if (_finish == _end_of_storage) {size_t len = pos - _start;//保存原来的pos位置size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newCapacity);pos = _start + len; //在新的空间中标记pos位置}iterator end = _finish - 1;while (end >= pos) {*(end + 1) = *end; //将当前元素移动到下一个位置--end; //end继续往前遍历,最后一次: *(pos+1) = *(pos)}*pos = val; ++_finish; return pos; //返回pos位置}（12）iterator erase(iterator pos);
删除pos位置的数据并返回被删除元素的下一个位置
有的小伙伴说，这还不简单~
//删除pos位置的元素
//不完善void erase(iterator pos) {assert(pos >= _start);//严格控制pos的取值范围assert(pos < _finish);iterator it = pos + 1;//it的初始位置在pos的下一个位置while (it != _finish) //如果it走到_finish，循环结束{*(it - 1) = *it; //后一个元素将前一个覆盖++it; //更新it}--_finish; //_finish更新}但是，请注意，执行完删除操作后，pos迭代器是会失效的
我们可以先调用std库里面的erase函数试一试：
所以，调用erase函数后，it会失效。可能会缩容，也可能删除的是最后一个元素的位置。
那么，如果我一定要访问it，std库里面的erase函数是提供了一个返回值，返回的就是被删除元素的下一个位置。
因此，代码可以这样修改：
那么，如果我恰好删除的是最后一个元素“5”呢？我们可以对其进行检查，如果是删除最后一个元素，我们可以不进行访问。因为删除了最后一个元素后，返回的就是end()
void test3() {std::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);int x;cin >> x;std::vector<int>::iterator it1 = find(v1.begin(), v1.end(), x);if (it1 != v1.end()) {it1 = v1.erase(it1);if(it1 != v1.end())//如果删除的是最后一个元素,那么就不访问了cout << *it1 << endl;}}小练习：删除vector容器里面的偶数
//删除pos位置的元素iterator erase(iterator pos) {assert(pos >= _start);//严格控制pos的取值范围assert(pos < _finish);iterator it = pos + 1;//it的初始位置在pos的下一个位置while (it != _finish) //如果it走到_finish，循环结束{*(it - 1) = *it; //后一个元素将前一个覆盖++it; //更新it}--_finish; //_finish更新return pos;}void test4() {//定义vector容器,往里面添加数据vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);vector<int>::iterator it1 = v1.begin();while (it1 != v1.end()) {if (*it1 % 2 == 0) {it1 = v1.erase(it1);//使用erase函数时,返回删除数据的下一个位置}else {++it1;}}for (auto e : v1) {cout << e << " ";}cout << endl;}运行结果如下：
1 3 5
（13）vector(size_t n,const T& value = T())
用n个value元素构造vector
vector(size_t n, const T& val = T()) {reserve(n);for (size_t i = 0; i < n; i++) {push_back(val);}}const T& value = T() 是使用了一个默认参数和引用的函数参数声明。
（1）= T() 这部分声明了默认值，如果在调用函数时没有提供这个参数，就会使用它。= T() 创建了 T 类型的一个临时对象，这是通过类型的默认构造函数完成的。这意味着如果没有提供具体的 value 值时，构造函数将使用 T 类型默认构造出的一个新对象作为默认值。
例如，如果 T 是 int，那么T() 就是 0 。
如果 T 是某个类类型，并且该类有一个无参数的构造函数，那么 T() 就会调用这个默认构造函数来创建一个新对象。
因此，这个参数声明使得构造函数可以具有灵活性：你既可以用特定的初始值来构造 vector，也可以不提供初始值，让 vector 用类型 T 的默认值来填充
（14）vector(InputIterator first,InputIterator last)
template<class InputIterator>vector(InputIterator first, InputIterator last) {while (first != last) {push_back(*first);++first;}}这个函数是 vector 类的一个范围构造函数（range constructor），它允许你根据一对迭代器 first 和 last 来构造一个新的 vector 对象。这个构造函数遍历从 first 开始一直到 last 结束的序列，并将每个元素添加到新构造的 vector 中。
下面是详细的说明：
（1）template<class InputIterator> 这一行表述了模板参数 InputIterator ，它是一种迭代器类型，用于表示输入序列中的位置。它可以是指针或者支持 ++ （前置递增）和 * （解引用）操作的任何类型的迭代器
（2）vector(InputIterator first,InputIterator last) 这是构造函数的声明，它接受2个参数，first 和 last ，代表输入序列的开始和结束迭代器。序列不包括迭代器 last 指向的元素。序列由 [first，last) 间的元素组成，是一个左闭右开的区间
函数体内的代码逻辑如下：
（1）while（first != last）循环，将一直执行，直到 first 迭代器等于 last 迭代器，这表示已经到达了输入序列的末尾。
（2）push_back(*first) 在循环体内部调用，这个函数应该是 vector 类中的成员函数，它会添加解引用迭代器 first 指向当前元素到 vector 的末尾
（3）++first ，迭代器 first 递增以便在下一次迭代中指向序列中的下一个元素
这个构造函数可以用来构造一个 vector ，使其包含现存容器（如另一个 vector、list 、array）中某个子序列的元素，或者任何由迭代器定义的元素序列。
注意：除了这2个函数，我们模拟实现时需要手动增加一个函数：
vector(int n, const T& val = T()) {reserve(n);for (size_t i = 0; i < n; i++) {push_back(val);}理论来说，提供了 vector(size_t n,const T& value = T()) 之后，vector(int n,const T& value = T())就不需要提供了。
但是，对于 vector<int> v(10,5); 编译器在编译时，认为T已经被实例化为int，而 10 和 5 编译器会默认其为 int 类型而不会走 vector(size_t n,const T& value = T()) 这个构造方法。
最终选择的是： vector(InputIterator first，InputIterator last) 因为编译器觉得区间构造2个参数类型一致，因此编译器就会将InputIterator实例化为 int，但是10 和 5 根本不是一个区间，编译器就报错了。故需要增加该构造方法。
（15）vector(const vector& v)
拷贝构造函数实现，只需要分配好空间对元素依次尾插即可
//拷贝构造函数vector(const vector<T>& v) {reserve(v.capacity());for (auto& e : v) {push_back(e);}}（16）void resize(size_t n,const T& val = T())
void resize(size_t n, const T& val = T()) {if (n > size()) {reserve(n);//插入while (_finish < _start + n) {*_finish = val;++_finish;}}else {//删除_finish = _start + n;}}（1）若resize传入的n大于capacity，进行扩容并用val来填满新位置
（2）若n大于有效元素个数并小于capacity，不进行扩容，用val填满空位置
（3）若n小于有效元素个数，进行删除操作
片尾
今天，我们学习了vector类的模拟实现，希望看完这篇文章能对友友们有所帮助！！！
求点赞收藏加关注！！！
谢谢大家！！！
