前言
大家好呀！欢迎来到我的C++系列学习笔记！~上一篇是有关STL标准模板库的string的理解到深入，传送门在这里哦：【C++】从使用string类到模拟实现string类_柒海啦的博客-CSDN博客_c++引入string
vector同样是STL里的一个容器，其功能就是存放任意数据的一个动态数组。这篇文章我会从会用vector的容器开始，理解到最后的模拟实现vector的基本框架，以便达到我们对此容器的一个熟练操作的目的。
目录
一、熟练使用vector
因为是STL，所以里面的容器操作还是熟悉的操作，我们只需要明白其容器的大致框架，然后具体的对这些进行模拟实现即可，所以我们针对这些框架去熟练使用vector。
1.大致框架
vector的理解流程大致如上图所示。首先自然了解其构造函数，明确内部所拥有的成员变量，其次也要明确析构。
然后容量来说就是对整个空间进行申请或者初始化操作了，运算符重载要么就是方便使用，要么就是重载一些比较常用且重要的（比如赋值重载）。操作就是一个动态线性表一般的操作，随机插入，随机删除，尾插，尾删.......
接下来我会用具体代码来对对应的模块进行演示，帮助我们一起理解vector这个容器。
比较好的C++文档在这里：https://cplusplus.com/reference/vector/vector/
2.代码演示
构造函数：
空数组、几个相同的数构造、拷贝构造、迭代器构造。
参考代码：
void test1()
{
vector<int> v1; // 空
vector<int> v2(6, 6); // 初始化6个6
vector<int> v3(v2); // 或者 vector<int> v3 = v2 // 拷贝构造
vector<int> v4(v3.begin(), v3.end()); // 迭代器构造
} 
可以发现v1 v2 v3 v4对象均构造成功，v2对应的就是构造6个6，v3就是拷贝构造，v4用了两个迭代器进行构造。（一般线性顺序表的迭代器的底层实际上就是指针）
既然构造成功了，那么我们就需要对其进行操作了。
插入、遍历操作：
首先，可以简单的看一下我们耳熟能详的push_back:(push_back实际上底层也就是调用的insert())。
同样的，在vector里面也支持[]运算符重载，所以我们就可以通过下标的方式去遍历vector，自然同样存在size()是统计当前数据的个数的。
参考代码：
void test2()
{
// 插入 遍历
vector<int> v1(6, 1);
v1.push_back(2); // 尾插
// 利用下标去遍历数据
for (size_t i = 0; i < v1.size(); ++i)
{
cout << v1[i] << " ";
}
cout << endl;
} 
上述取出数据我们使用的是[]重载，实际上，我们取出数据的方式有很多种，这里介绍两种：一个取出头的数据front()，一个取出尾的数据back()。
插入数据的话自然也就是有insert之类的函数：
当然，和插入对应的就是删除了，erase()即随机删除：
也存在尾删pop_back()：
需要注意的是，上述传入的参数并不是size_t或者int的下标，而是迭代器iterator哦~
提到迭代器自然就不会忘记end(),begin(),rend(),rbegin()...... 并且实际上此迭代器的实现底层也就是简单的指针，且类型应该是：std::vector<T>::iterator
那么我们可以利用其进行遍历--同时就可以使用范围for，然后进行一些基本的随机插入删除等操作：
void test3()
{
// 插入遍历
// 迭代器及其迭代器遍历：
vector<int> v(3, 2);
vector<int>::iterator it = v.begin();
while (it != v.end()) // end为最后的元素的下一个
{
cout << *it << " "; // 像指针一样的进行访问
++(*it); // 同样的可以进行修改
++it;
}
cout << endl;
// 支持迭代器，也就支持范围for
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
v[0] = 1;
v[2] = 0;
// 打印头尾，不用[]重载
cout << "头：" << v.front() << endl;
cout << "尾：" << v.back() << endl;
// 随机插入 先寻找
it = find(v.begin(), v.end(), 3);
// 在3前插入 2
v.insert(it, 2);
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
// 随机删除
//v.erase(it); // 在把此位置删除 直接这样会出现失效的问题，所以必须重新寻找或者接收insert的返回值
it = find(v.begin(), v.end(), 2);
v.erase(it);
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
}
这里提到了迭代器失效的情况，那么这个是什么情况呢？
迭代器失效：
所谓迭代器失效，也就是在进行insert或者erase，即移动空间的时候，就可能会产生当前位置地址被释放掉，转移到其他地方去了，那么此时地址也就是野指针了，这就是迭代器失效。
void test4()
{
vector<int> v(2, 2);
auto it = v.begin(); // 头结点值地址
printf("%p\n", it);
v.erase(it);
//验证it是否失效
printf("%p\n", it);
printf("%p\n", v.begin());
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
}
此时可以发现三者的地址完全不一样，说明发生了变化，也就是所谓的迭代器失效了。
其实，在不同的平台下，编译器对此迭代器失效的方法也存在不一样的地方：
比如，我们测试程序12345，对此数组中的偶数进行删除：在linuxg++和Windows下的vs2022分别进行测试：
void test5()
{
// 迭代器遍历随机删除
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
vector<int>::iterator it = v.begin();
// 迭代器失效
while (it != v.end())
{
if (*it % 2 == 0)
{
// 偶数删除
v.erase(it);
}
++it;
}
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
}
vs2022 直接崩溃
Linux下的g++却没有。
上述情况也就说明了：
VS下和Linux下可能会不一样：STL只是一个规范-->不同的平台下面实现是不同的。
VS下对迭代器会进行强制检查，如果原本指向的数据被清除了，下次在对此处指向（存在数据，不是野指针），但是会检查报错
Linux下：12345没有问题（删去偶数，不正确使用）1235
-- 数据排列的偶然性（最后一个不是偶数，没有连续的偶数）
但是当我们遍历插入或者删除的时候就会产生很多不便，那么insert以及erase要如何处理才能优化好呢？对返回值进行操作：
insert返回的就是新插入的那个元素位置的迭代器，而erase返回的就是被删除元素的下一个元素的迭代器。
知晓这些之后，我们就可以稍微修改一下上面的代码，使其能在Windows平台下也能够跑起来：
while (it != v.end())
{
if (*it % 2 == 0)
{
// 偶数删除
it = v.erase(it);
}
else
++it;
}
此时就能够在Windows平台上跑了。
容量
跟string这个类类似，实际上在STL内基本都有这个扩容以及初始化的reserve和resize，用法都基本一致，一个就是一开始申请多大空间，另一个就是申请的同时也初始化多少数据。
其实我们发现resize默认给的是value_type(),其实有的时候存储的数据并不是内置类型，而是自定义类型，所以就会如此设计，这在之后的模拟实现也会涉及。
参考代码：
void test6()
{
// reserve
vector<int> v1;
v1.reserve(10);
cout << v1.capacity() << endl;
// resize
vector<int> v2;
v2.resize(6, 2); // 初始化6个数据，均为2
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
v2.resize(10, 1); // 当申请空间比原本数据个数大，那么会将没填充的数据填为对应数据
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
v2.resize(2, 0); // 如果比原本数据小，会发生截断，不会填充数据
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
} 
在了解一些基本并且熟练的时候，就可以对vector进行更加深入的模拟实现了：
二、简单模拟实现vector
大致了解后，我们想要进一步深入理解vector的话，就要对其进行模拟实现。既然只是简单的去模拟实现，那么我们只需要实现一个大致框架即可：
1.代码分析
准备工作：
我们首先可以将其实现代码放在一个命名空间内，这样就可以不用和std内官方的vector相互冲突。当然，此类可以定义在一个头文件内，比如叫做vector.h，这样方便其他程序进行调用此头文件。
然后，此类是一个模板类，因为里面的存储的数据可不只有int一种，自然使用template<class T>来进行定义：
namespace QiHai
{
// 类模板
template<typename T>
class vector
{
//...
}
//...
}成员变量：
首先看我们的私有成员。因为这是一个顺序结构，所以内存地址是连续的，也就是普通的在堆上申请的动态数组。结合std官方的实现，我们可以定义如下三个指针：（同时将指针重命名为迭代器类型）
public:
typedef T* iterator; // 定义迭代器类型为iterator
typedef const T* const_iterator; private:
iterator _start; // 存储数据的开始位置
iterator _finish; // 存储数据的最后一个位置的后一个位置
iterator _end_of_storage; // 存储数据的空间最后一个地址三者在某一时候关系可以如图所示：
插入成员变量变化演示：
那么此时你的内心是否存在一个疑惑：那么这些是如何进行控制的呢？其实也就是保证开空间和插入的时候控制其在对应的位置即可，这些后面均会实现，现在这里可以进行一个简单的演示：（假设第一次插入开8个空间）
迭代器相关实现：
和string的实现不一样，我们对外提供的接口也是迭代器，所以首先提供一些基本的迭代器接口：比如begin()、end()等。
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}无参构造函数：
然后就是最基本的构造函数也是最常用的构造函数。如上述演示一样，我们只需控制三个变量初始化为nullptr即可。
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{}迭代器区间构造函数：
为了方便后序的拷贝构造函数方便调用，并且也是一种构造函数方式，即对传入的类似于地址使用（即*解应用就是数据），要使用模板函数，结构如下：（push_back还未写，下面会进行实现）--（传入的迭代器，就有点类似于迭代器遍历）
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}交换&拷贝构造：
拷贝构造也分为现代写法和原始写法，原始写法就是重新建立一个空间，然后一一把传入的对象的数据拷贝到新空间上去，否则默认的拷贝构造实现的是浅拷贝（注意此深拷贝不能使用memcpy进行数据替换，因为当储存对象本身也是一个数组的时候，即内部存的同样也是地址，那么此时就会出现问题，这就是深度拷贝，后面也会具体讲，需要一个一个进行赋值）
当然，除了原始写法，现代写法就高明的多， 会让一个具体的对象帮我们做事，然后将地址进行交换即可。这个对象也就是我们上面的迭代器区间构造，而地址交换就需要我们自己实现一个。
交换函数很简单，只需要执行外部的交换函数将我们每一个变量所存的地址交换即可。
（注意传入的参数必须是一个类型，vector可不是一个具体的类型，而是一个模板，所以需要<T>哦~）
void swap(vector<T>& v)
{
::swap(_start, v._start);
::swap(_finish, v._finish);
::swap(_end_of_storage, v._end_of_storage);
}拷贝构造现代写法：
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
// 现代做法，请打工人
vector<T> tmp(v.begin(), v.end()); // 请到的打工人
swap(tmp); // 两者交换，它的就是我的了
}析构函数：
析构函数很简单，因为我们变量的申请的空间由堆而来（new/malloc），所以我们将头指针释放掉，然后将其所有变量置为空即可。
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}数据个数和容量：
为了统计当前数据个数以及容量大小，结合之前创建变量的介绍，这里可以轻松的解决：
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}赋值重载：
赋值重载和拷贝构造函数有点类似，只不过一个是新创建一个对象，而赋值是两个以及存在的对象让另一个的值拷贝给另一个。
也有原始写法和现代写法，原始写法同样注意深度拷贝的问题，而现代写法就只需要让形参做工具人，因为此时传参就会发生拷贝构造，然后与其形参交换数据即可。同时注意返回对象的本身。
vector<T>& operator=(vector<T> v)
{
swap(v); // 把形参当做打工人
return *this;
}[]重载：
此重载也就是方便像数组一样的对下标进行访问，方便快捷。实际上也就是根据传入的下标，根据首元素地址加减获得，因为可以修改数据，那么就可传出引用，const对象加上const即可：
T& operator[](size_t n)
{
assert(n < size());
return _start[n];
}
const T& operator[](size_t n) const
{
assert(n < size());
return _start[n];
}开空间或者初始化reserve&resize:
开空间是插入的基础。首先就需要存在空间才能进行插入操作，也才能真正的构造一个数组。如上面的动画演示一样，我们可以对这个函数传入n表示我们要开n个对应数据类型的空间。
所谓开空间，也就是原来开的的一串地址空间不够了或者没有，然后需要开辟一个比原来大的空间供数据进行操作。既然是新的空间，那么数据就要进行搬家。数据搬家也就是要进行拷贝。在拷贝的同时我们要注意到数据类型不再是像string那样简单的char类型了，而是T。这个T可以是内置类型，当然也可以是vector<int>。此时我们存储的数据本身里面也存储的有地址，所以如果只是单单的memcpy的话，只是表面上给存储vector<int>开辟了新的空间，但是内部却还是和原来那个指向的同一空间。所以为了解决这个问题，我们只需一个一个赋值就可以解决这个更深层次的拷贝了。
void reserve(size_t n)
{
if (n > capacity())
{
iterator new_start = new T[n];
size_t len = size();
if (_start) // 有可能是空数据进行
{
// 普通的进行内存拷贝的话，存在更深层次无法拷贝
//memcpy(new_start, _start, sizeof(T) * capacity());
// 深层次拷贝 一个一个进行拷贝 方便调用其赋值进行深拷贝
for (size_t i = 0; i < len; i++)
new_start[i] = _start[i];
delete[] _start;
}
_start = new_start;
_finish = _start + len;
_end_of_storage = _start + n;
}
}开空间并且初始化实际上分为两个步骤，一个进行开空间，另一个负责初始化数据。注意缺省参数是一个匿名构造，C++为了迎合自定义类型初始数据的问题，也给内置类型定义了一个匿名对象，所以使用匿名对象对内置类型同样适合。
void resize(size_t n, const T& val = T()) // 缺省值给T的一个匿名对象 （C++为了迎合自定义类型，也给内置类型增加了无参构造）
{
// 1. n > capacity()
if (n > capacity())
{
reserve(n); // 扩容
}
for (size_t i = size(); i < n; i++)
_start[i] = val;
_finish = _start + n;
}front、back、empty：
front获得头数据，back获得尾数据，只需要像数组那样访问即可，记得传出引用即可：
T& front()
{
assert(size() > 0);
return *(_start);
}
T& back()
{
assert(size() > 0);
return *(_finish - 1);
}
bool empty()
{
return _start == _finish;
}操作：插入、删除
只有插入我们才能对数据进行管理。随机插入可以复用于尾插，随机删除同样可以。需要注意的是在挪动空间，原本传入的迭代器就可能出现失效的问题，那么我们只需控制insert返回插入后新数据所在的位置指针，删除数据的下一个数据位置指针即可。（插入空间满申请空间，然后进行移动，删除进行移动操作）--注意检查边界问题哦~
// 随机插入
iterator insert(iterator pos, const T& val)
{
assert(pos >= _start);
assert(pos <= _finish);
// 满了就需要扩容
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2); // 扩容后，原本地址会发生改变
pos = _start + len; // pos也发生变化
}
iterator temp = _finish - 1;
while (temp >= pos)
{
*(temp + 1) = *temp;
--temp;
}
*pos = val;
++_finish;
return pos; // 返回改变地址后的迭代器位置
}
// 随机删除 返回删除位置的下一个位置的迭代器
iterator erase(iterator pos)
{
assert(pos < _finish);
assert(pos >= _start);
iterator temp = pos + 1;
while (temp <= _finish)
{
*(temp - 1) = *(temp);
++temp;
}
_finish--;
return pos;
}此时尾插尾删复用即可。
2.综合代码：
仅供参考，有误请大佬指正！
// vector.h
#pragma once
#include<iostream>
#include<vector>
#include<string.h>
#include<assert.h>
using namespace std;
// 模拟实现vector
namespace QiHai
{
// 类模板
template<typename T>
class vector
{
public:
typedef T* iterator; // 定义迭代器类型为iterator
typedef const T* const_iterator;
// 迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
// 类中交换函数
void swap(vector<T>& v)
{
::swap(_start, v._start);
::swap(_finish, v._finish);
::swap(_end_of_storage, v._end_of_storage);
}
// 构造函数
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{}
// 迭代器区间进行初始化构造
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
// 拷贝构造
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
// 现代做法，请打工人
vector<T> tmp(v.begin(), v.end()); // 请到的打工人
swap(tmp); // 两者交换，它的就是我的了
}
// 析构函数
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
// 数据个数
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
// 重载
// 赋值重载
vector<T>& operator=(vector<T> v)
{
swap(v); // 把形参当做打工人
return *this;
}
// []重载
T& operator[](size_t n)
{
assert(n < size());
return _start[n];
}
const T& operator[](size_t n) const
{
assert(n < size());
return _start[n];
}
// 开空间
void reserve(size_t n)
{
if (n > capacity())
{
iterator new_start = new T[n];
size_t len = size();
if (_start) // 有可能是空数据进行
{
// 普通的进行内存拷贝的话，存在更深层次无法拷贝
//memcpy(new_start, _start, sizeof(T) * capacity());
// 深层次拷贝 一个一个进行拷贝 方便调用其赋值进行深拷贝
for (size_t i = 0; i < len; i++)
new_start[i] = _start[i];
delete[] _start;
}
_start = new_start;
_finish = _start + len;
_end_of_storage = _start + n;
}
}
// 开空间并且初始化
void resize(size_t n, const T& val = T()) // 缺省值给T的一个匿名对象 （C++为了迎合自定义类型，也给内置类型增加了无参构造）
{
// 1. n > capacity()
if (n > capacity())
{
reserve(n); // 扩容
}
for (size_t i = size(); i < n; i++)
_start[i] = val;
_finish = _start + n;
}
T& front()
{
assert(size() > 0);
return *(_start);
}
T& back()
{
assert(size() > 0);
return *(_finish - 1);
}
bool empty()
{
return _start == _finish;
}
void pop_back()
{
assert(_finish > _start);
--_finish;
}
// 操作
// 尾插
void push_back(const T& val)
{
// 直接复用insert()即可
insert(end(), val);
}
// 随机插入
iterator insert(iterator pos, const T& val)
{
assert(pos >= _start);
assert(pos <= _finish);
// 满了就需要扩容
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2); // 扩容后，原本地址会发生改变
pos = _start + len; // pos也发生变化
}
iterator temp = _finish - 1;
while (temp >= pos)
{
*(temp + 1) = *temp;
--temp;
}
*pos = val;
++_finish;
return pos; // 返回改变地址后的迭代器位置
}
// 随机删除 返回删除位置的下一个位置的迭代器
iterator erase(iterator pos)
{
assert(pos < _finish);
assert(pos >= _start);
iterator temp = pos + 1;
while (temp <= _finish)
{
*(temp - 1) = *(temp);
++temp;
}
_finish--;
return pos;
}
private:
iterator _start; // 存储数据的开始位置
iterator _finish; // 存储数据的最后一个位置的后一个位置
iterator _end_of_storage; // 存储数据的空间最后一个地址
};
}谢谢观看~