C++初阶：STL详解（五）——vector的模拟实现
✨✨小新课堂开课了，欢迎欢迎~✨✨
🎈🎈养成好习惯，先赞后看哦~🎈🎈
所属专栏：C++：由浅入深篇
小新的主页：编程版小新-CSDN博客
前言：
我们前面已经了解了vecto的特性和常见接口的使用，今天就来了解一下vector的底层。vector和string又非常的相似，所有今天要介绍的底层大家也会处理的得心应手，在实现的时候又会用到我们前面说的迭代器失效的问题，也可以简单回忆一下。
C++初阶：STL详解（三）——vector的介绍和使用-CSDN博客
C++初阶：STL详解（四）——vector迭代器失效问题-CSDN博客
vector各函数接口总览
namespace fu
{
//模拟实现vector
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//默认成员函数
vector(); //无参的构造函数1
vector(size_t n, const T& val = T()); //构造函数2
template<class InputIterator>
vector(InputIterator first, InputIterator last); //构造函数3
vector(const vector<T>& v); //拷贝构造函数
vector<T>& operator=(const vector<T> v); //赋值运算符重载函数
~vector(); //析构函数
//迭代器相关函数
iterator begin();
iterator end();
const_iterator begin()const;
const_iterator end()const;
//容量和大小相关函数
size_t size()const;
size_t capacity()const;
void reserve(size_t n);
void resize(size_t n, const T& val = T());
bool empty()const;
//修改容器内容相关函数
void push_back(const T& x);
void pop_back();
iterator insert(iterator pos, const T& x);
iterator erase(iterator pos);
void swap(vector<T>& v);
//访问容器相关函数
T& operator[](size_t i);
const T& operator[](size_t i)const;
private:
iterator _start; //指向容器的头
iterator _finish; //指向有效数据的尾
iterator _endofstorage; //指向容器的尾
};
}注意：为了与标准库里的vector产生命名冲突，在模拟实现时要放到我们自己的命名空间中去。
成员变量简介
默认成员函数
构造函数1
我们第一个介绍的是一个无参的构造函数，只需对成员变量进行简单的初始化即可，这里我们都初始化为空指针。
// 无参的构造函数
vector()
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
}构造函数2
第二种构造方式，我们可以用一个迭代器区间区去构造。至于这里为什么会使用函数模版，是因为我们也不知道要接送的迭代器类型是什么，可能是string类型，可能就是某个vector迭代器区间。之后我们在将该迭代器区间的数据一个个尾插即可。
template<class InputIterator> //模板函数
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
//将迭代器区间在[first,last)的数据一个个尾插到容器当中
while (first != last)
{
push_back(*first);
first++;
}
}构造函数3
第三种构造方式，我们可以用n个val进行初始化。我们可先利用reserve这个接口提前开好空间，避免多次扩容使得效率低下，之后在用push_back这个接口尾插即可。
//用n个val进行构造
vector(size_t n, const T& val=T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}好了看到这里，我们已经认识了这三种构造方式，但是这里还有一些小瑕疵。
fu::vector<int> v1(5, 8);你猜这个v1会调用哪种构造函数，是构造函数2，是构造函数3。编译器会优先选择与构造函数2匹配，但是构造函数2内对first进行了解引用，但是整形(int）不能解引用，就会报错。
解决方式就是我们需要几个与构造函数2类似的重载函数。
vector(int n, const T& val=T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(long n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}拷贝构造
和string类似，vector的拷贝拷贝也涉及深拷贝问题，这里我们也提供两种方式。
传统写法：
先开辟一块与该容器大小相同的空间，然后将该容器当中的数据一个个拷贝过来即可，最后更新_finish和_endofstorage的值即可。
//拷贝构造函数
//传统写法
vector(const vector<T>& v)
{
//开辟一个足够大小的空间
_start = new T[v.size()];
//将数据插入到容器中
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v[i];
}
//更新信息
_finish = _start + v.size();//当前容器有效数据的个数
_endofstorage = _start + v.capacity();//当前容器的容量大小
}现代写法：
现代写法和传统写法的思路是一样的，只是现代写法用了范围for（自动迭代，自动取数据，自动判断结束）。
//现代写法
vector(const vector<T>& v)
{
//开辟一个足够大小的空间
reserve(v.capacity());
//将数据插入到容器中
for (auto ch : v)
{
push_back(ch);
}
//更新信息
_finish = _start + v.size();//当前容器有效数据的个数
_endofstorage = _start + v.capacity();//当前容器的容量大小
}赋值运算符重载
vector的赋值运算符重载也涉及深拷贝问题，这里还是提供两种方式。
传统写法：
首先先判断是否自己给自己赋值，自我赋值没必要，开辟一个足够的空间，将容器中的数据一个个拷贝过来，释放旧空间，指向新空间，最后更新成员变量的信息即可。
//赋值运算符重载函数
//传统写法
vector<T>& operator=(const vector<T>& v)
{
//自己给自己赋值不需要改变
if (this != v)
{
//开辟一个足够大小的空间
T tmp = new T[v.capacity()];
//将原来的数据拷贝给容器
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v[i];
}
//释放旧空间
delete[] _start;
//指向新空间
_start = tmp;
_finish = _start + v.size();//当前容器有效元素的个数
_endofstorage = _start + v.capacity();//当前容器容量的大小
return *this;//可重复赋值
}
}现代写法：
赋值运算符重载的现代写法十分精巧，首先在右值传参时并没有使用引用传参，传值传参调用vector的拷贝构造函数，然后将这个拷贝构造出来的容器v与左值进行交换，此时就相当于完成了赋值操作，而容器v会在该函数调用结束时自动析构。
//现代写法
vector<T>& operator=(const vector<T> v)
{
//交换
swap(v);
return *this;//可重复赋值
}析构函数
首先要判断容器是否为空，避免对空指针进行解引用，不过不为空，就先释放原来空间，再将成员变量置空即可。
//析构函数
~vector()
{
if (_start)
{
delete[] _start;
_start = nullptr;
_finish = nullptr;
_endofstorage = nullptr;
}
}迭代器相关的函数
begin和end
//迭代器相关函数
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}vector当中的begin函数返回容器的首地址，end函数返回容器当中有效数据的下一个数据的地址。
容量和大小相关函数
size和capacity
指针相减即可。
size_t size()const
{
return _finish-_start;
}
size_t capacity()const
{
return _endofstorage-_start;
}reserve和resize
resize函数改变容器中的有效元素个数，reserse函数改变容器的容量。
reserve规则：
1、当所给值大于当前容器的capacity时，将capacity扩大到该值。
2、当所给值小于当前容器的capacity时，什么也不做，不会缩容。
void reserve(size_t n)
{
//检查是否需要扩容
if (n > capacity())
{
//记录当前容器的大小
size_t sz = size();
//开辟一个足够大小的空间
T* tmp = new T[n];
//将先前数据拷贝给新容器
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
//释放旧空间
delete[] _start;
//指向新空间
_start = tmp;
_finish = _start + sz;//当前容器有效元素个数
_endofstorage = _start + n;//当前容器的容量大小
}
} resize规则：
1、当所给值大于容当前容器的size时，将size扩大到该值，扩大的元素为第二个所给值，若未给出，则int型默认为0，char型默认是'\0'。
2、当所给值小于容器当前的size时，将size缩小到该值。
void resize(size_t n, const T& val = T())
{
//当n小于size
if (n < size())
{
_finish = _start + n;
}
else//大于size
{
//检查是否需要扩容
if (n > capacity())
{
//提前开够足够的空间
reserve(n);
//填充数据
while (_finish != _start+n)
{
*_finish = val;
_finish++;
}
}
}
}empty
当_start 和_finish指向的位置相同的时候代表容器为空。
bool empty()const
{
return _start == _finish;
}修改容器内容相关函数
push_back
在进行插入的前的第一步都是先判断空间是否够用，有需要就扩容，之后我们就将数据插入到_finish的位置，在++_finish即可。
// 尾插数据
void push_back(const T & x)
{
if (_finish == _endofstorage) //判断是否需要增容
{
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); //将容量扩大为原来的两倍
reserve(newcapacity); //增容
}
*_finish = x; //尾插数据
_finish++; //_finish指针后移
}pop_back
在容器不为空的情况下。直接将_finish指向的位置往前挪动即可。
void pop_back()
{
assert(!empty());
_finish--;
}
insert
在插入操作前，不变的第一步还是检查是否需要扩容。在实现扩容操作的时候，可能一不小心就会犯让迭代器失效的问题，这里我们记录扩容前pos与_start的相对位置就是方便在扩容后能找到pos位置，这里也就避开了我们之前举例的迭代器失效问题的一个常见场景。该场景的迭代器失效就是由扩容引起的。之后我们就只需要挪动数据，再在pos位置插入即可，记得要++_finish哦，因为这里又多一个数据。insert返回插入元素的位置。
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
//检查是否需要扩容
if (_finish == _endofstorage)
{
size_t len = pos - _start;//记录相对位置，避免迭代器失效问题
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;//找到扩容后pos的位置
}
//将pos及其后面的元素往后移，移出位置，给要插入的元素
iterator end = _finish;
while (end>=pos+1)
{
*end = *(end - 1);
end--;
}
*pos = x;//插入
_finish++;//往后移
return pos;
}erase
在删除数据前要判断容器是否为空，空的容器还怎么删除呢。这里所说的删除其实就是挪动覆盖，记得要--_finish哦，因为这里少了一个数据。erase返回被删除位置的下一个位置的迭代器。
iterator erase(iterator pos)
{
assert(!empty());
iterator it = pos + 1;
//挪动覆盖数据
while (it != _finish)
{
*(it - 1) = *it;
it++;
}
_finish--;//少了一个数据，往前移
return pos;//返回被删除位置的下一个位置的迭代器
}swap
我们直接使用库里面的交换函数即可。
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}访问容器相关函数
operator[]
vector也支持下标+[]对容器进行访问，我们这里实现了可读可写和只读的接口。检查下标的合法性后，返回对应的数据即可。
//访问容器相关函数
T& operator[](size_t i)
{
assert(i < size()); //检测下标的合法性
return _start[i]; //返回对应数据
}
const T& operator[](size_t i)const
{
assert(i < size()); //检测下标的合法性
return _start[i]; //返回对应数据
}总结：
vector的模拟实现到这里也结束了，和string非常的相似，所以也很好理解，我们在学习了string和vector之后，就要进入到list的学习，也是有很多想通性，list的特性决定了它的模拟实现和vector有所不同，之后我们一起来看吧。
感谢各位大佬的观看，创作不易，还请各位大佬支持~