目录
前言：
vector类是STL(标准模板库)中的八大容器之一，而STL属于C++标准库的一部分，所以可以直接使用vector。他的作用类似于数组，是用一段连续的空间来存储元素，因此可以支持下标访问各个元素，其中元素的类型可以是int、char...类型以及自定义类型，所以vector类实际上是一个类模板。但是vector类对空间内存的管理比数组更加严格，且使用起来较数组更简便，因为vector是一个类很多功能都已封装完成，可以直接提供用户使用。
一、vector的模拟实现
1、vector的组成结构
vector类是由三个成员指针变量构成的，可以把这三个成员命名为：_start、_finish、_end_of_storage。
1、其中_start的作用类似于数组名，表示首元素地址，因此是用_start来开辟空间的。
2、而_finish指向最后一个元素的下一个位置。他的作用是减去_start可以得到当前空间的元素个数。（通过指针-指针得到整数的方式）
3、_end_of_storage指向整个空间的末尾处的下一个位置。他的作用是减去_start可以得到空间容量。
具体示意图如下：
2、vector尾插数据
有了上面的成员介绍就可以写一个简单的尾插函数，代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include<assert.h>
namespace ZH
{
template<class T>
class vector
{
public:
typedef T* iterator;
vector()//构造函数
{}
size_t size()const//得到元素个数
{
return _finish - _start;
}
size_t capacity()const//得到空间大小
{
return _end_of_storage - _start;
}
void reserve(size_t n)//扩容函数
{
if (n > capacity())
{
T* temp = new T[n];
size_t poi = _finish-_start;//先把_start和_finish之间的距离记录下来
if (_start != nullptr)
{
memcpy(temp, _start, sizeof(T) * size());//拷贝数据
delete[] _start;
}
_start = temp;//更新_start的指向
_finish = _start + poi;
_end_of_storage = _start + n;
}
}
void push_back(const T& val)
{
if (_finish == _end_of_storage)//相等说明当前容量不够
{
reserve(capacity()==0?4:capacity() * 2);//扩容
}
*_finish = val;//尾插
_finish++;
}
T& operator[](size_t i)//解引用运算符重载
{
assert(i < size());//检查越界
return _start[i];
}
private:
iterator _start = nullptr;//缺省值赋予空
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
int main()
{
//实例化对象v1
ZH::vector<int> v1;
//尾插五个数
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
for (size_t i = 0; i < v1.size(); i++)
{
cout << v1[i] << endl;
}
return 0;
}运行结果：
上述代码需要注意的是：扩容时采用的是异地扩容，因此要注意_start值的变化对_start与_finish之间距离的影响。如下图：
2.1 析构函数
因为是_start申请的空间，因此只需要delete _start即可。
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}3、迭代器实现
vector的迭代器可以看作是一个指针，迭代器实际上就是通过两个成员函数返回的指针实现的，这两个成员函数分别是begin（）和end（），一个返回首元素地址，一个返回末尾元素的下一个地址。然后用一个指针来接收他们的返回值，我们只需要把这个指针封装成迭代器的写法即可。
迭代器实现代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include<assert.h>
namespace ZH
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector()//构造函数
{}
size_t size()const//得到元素个数
{
return _finish - _start;
}
size_t capacity()const//得到空间大小
{
return _end_of_storage - _start;
}
void reserve(size_t n)//扩容函数
{
if (n > capacity())
{
T* temp = new T[n];
size_t poi = _finish - _start;//先把_start和_finish之间的距离记录下来
if (_start != nullptr)
{
memcpy(temp, _start, sizeof(T) * size());//拷贝数据
delete[] _start;
}
_start = temp;//更新_start的指向
_finish = _start + poi;
_end_of_storage = _start + n;
}
}
void push_back(const T& val)
{
if (_finish == _end_of_storage)//相等说明当前容量不够
{
reserve(capacity() == 0 ? 4 : capacity() * 2);//扩容
}
*_finish = val;//尾插
_finish++;
}
//普通版本迭代器函数
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
//const版本迭代器的函数
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}
private:
iterator _start = nullptr;//缺省值赋予空
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
int main()
{
//实例化对象v1
ZH::vector<int> v1;
//尾插五个数
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
//普通迭代器
ZH::vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
(*it)++;
cout << *it << " ";
it++;
}
cout << endl;
//const版本的迭代器
ZH::vector<int>::const_iterator cit = v1.begin();
while (cit != v1.end())
{
//(*cit)++;//const版本迭代器不能通过迭代器修改对象中的内容
cout << *cit << " ";
cit++;
}
return 0;
}运行结果：
4、resize
void resize(size_t n, const T& t = T())
//n表示期望的元素个数
//t表示补齐元素的值resize的作用是控制元素个数的多少，如果n大于当前元素的总数，则会在后面补齐元素，并且补齐元素的值为t，如果n大于该对象的容量，则会自动扩容。当n小于当前元素的总数，则该对象内的有效元素个数为n个（注意resize不会进行缩容）。
模拟实现resize：
#include<iostream>
using namespace std;
#include<assert.h>
namespace ZH
{
template<class T>
class vector
{
public:
typedef T* iterator;
vector()//构造函数
{}
size_t size()const//得到元素个数
{
return _finish - _start;
}
size_t capacity()const//得到空间大小
{
return _end_of_storage - _start;
}
void reserve(size_t n)//扩容函数
{
if (n > capacity())
{
T* temp = new T[n];
size_t poi = _finish - _start;//先把_start和_finish之间的距离记录下来
if (_start != nullptr)
{
memcpy(temp, _start, sizeof(T) * size());//拷贝数据
delete[] _start;
}
_start = temp;//更新_start的指向
_finish = _start + poi;
_end_of_storage = _start + n;
}
}
void push_back(const T& val)
{
if (_finish == _end_of_storage)//相等说明当前容量不够
{
reserve(capacity() == 0 ? 4 : capacity() * 2);//扩容
}
*_finish = val;//尾插
_finish++;
}
void resize(size_t n, const T& t = T())//匿名对象具有常属性
{
if (n < size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
reserve(n);
while (_finish != _start + n)
{
*_finish = t;
_finish++;
}
}
}
//普通版本迭代器函数
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
private:
iterator _start = nullptr;//缺省值赋予空
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
int main()
{
//实例化对象v1
ZH::vector<int> v1;
//尾插五个数
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.resize(8);//验证n大于元素总数
ZH::vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
v1.resize(3);//验证n小于元素总数
it = v1.begin();
while (it != v1.end())
{
cout << *it << " ";
it++;
}
return 0;
}运行结果：
5、删除数据
vector类可以看作是一个数组，数组的删除数据有尾删和指定位置删除，尾删就很简单了，直接让_finish--即可，因为打印数据时不会打印_finish的位置，当指针_finish指向最后一个元素，表示最后一个元素不打印，则达到了间接尾插。
而指定位置删除就稍微复杂些，比如删除第一个元素，那么要让后面的元素整体往前移到一位，最后再让_finish--，这样挪动数据的消耗是很大的。
指定位置删除数据代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include<assert.h>
namespace ZH
{
template<class T>
class vector
{
public:
typedef T* iterator;
vector()//构造函数
{}
size_t size()const//得到元素个数
{
return _finish - _start;
}
size_t capacity()const//得到空间大小
{
return _end_of_storage - _start;
}
void reserve(size_t n)//扩容函数
{
if (n > capacity())
{
T* temp = new T[n];
size_t poi = _finish - _start;//先把_start和_finish之间的距离记录下来
if (_start != nullptr)
{
memcpy(temp, _start, sizeof(T) * size());//拷贝数据
delete[] _start;
}
_start = temp;//更新_start的指向
_finish = _start + poi;
_end_of_storage = _start + n;
}
}
void push_back(const T& val)
{
if (_finish == _end_of_storage)//相等说明当前容量不够
{
reserve(capacity() == 0 ? 4 : capacity() * 2);//扩容
}
*_finish = val;//尾插
_finish++;
}
iterator erase(iterator pos)//指定位置删除,并返回当下位置
{
//检查pos是否合格
assert(pos >= _start);
assert(pos < _finish);
iterator start = pos;
while (start!=_finish-1)
{
*start = *(start + 1);//挪动数据
start++;
}
_finish--;
return pos;
}
//普通版本迭代器函数
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
private:
iterator _start = nullptr;//缺省值赋予空
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
int main()
{
//实例化对象v1
ZH::vector<int> v1;
//尾插五个数
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
//删除
ZH::vector<int>::iterator it = v1.begin()+1;//删除第二个元素
v1.erase(it);//使用完it后，正常来说it是会失效的
v1.erase(it);//删除第二个元素后，后面的元素往前挪动，则it指向的是第三个元素
v1.erase(v1.end() - 1);//删除最后一个元素
it = v1.begin();//it失效了需要重新赋值
while (it != v1.end())
{
cout << *it << " ";
it++;
}
return 0;
}运行结果：
5.1 迭代器失效
一般而言，用一个迭代器进行erase后，该迭代器会发生失效，原因就是会出现以下情况：
因此经过erase之后的迭代器会认为是失效的，即不能继续使用该迭代器。
6、指定位置插入数据
指定位置插入数据就是将该位置之后的所有数据往后面挪一位，然后直接把要插入的数据放到该位置即可。（注意扩容问题）
插入代码如下：
#include<iostream>
using namespace std;
#include<assert.h>
namespace ZH
{
template<class T>
class vector
{
public:
typedef T* iterator;
vector()//构造函数
{}
size_t size()const//得到元素个数
{
return _finish - _start;
}
size_t capacity()const//得到空间大小
{
return _end_of_storage - _start;
}
void reserve(size_t n)//扩容函数
{
if (n > capacity())
{
T* temp = new T[n];
size_t poi = _finish - _start;//先把_start和_finish之间的距离记录下来
if (_start != nullptr)
{
memcpy(temp, _start, sizeof(T) * size());//拷贝数据
delete[] _start;
}
_start = temp;//更新_start的指向
_finish = _start + poi;
_end_of_storage = _start + n;
}
}
void push_back(const T& val)
{
if (_finish == _end_of_storage)//相等说明当前容量不够
{
reserve(capacity() == 0 ? 4 : capacity() * 2);//扩容
}
*_finish = val;//尾插
_finish++;
}
void Insert(iterator pos, const T& val)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)//相等说明当前容量不够
{
size_t len = pos - _start;//记录pos与_start之间的距离
reserve(capacity() == 0 ? 4 : capacity() * 2);//扩容
pos = _start + len;//依靠len更新pos的新位置
}
iterator end = _finish-1;
while (end>=pos)
{
*(end+1) = *end;
end--;
}
*pos = val;
_finish++;
}
//普通版本迭代器函数
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
private:
iterator _start = nullptr;//缺省值赋予空
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
int main()
{
//实例化对象v1
ZH::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.Insert(v1.begin()+2, 30);
ZH::vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
return 0;
}运行结果：
扩容导致的问题如下图：
6.1 迭代器失效
用一个迭代器进行插入后，该迭代器也会失效，原因是虽然Insert函数里面的pos进行了位置的更新，但是形参的改变不影响实参，外面的pos实质上还是指向原来空间的位置，此时的pos就处于野指针行为，因此不能进行对其进行使用了。
7、迭代器构造和resize构造
vector类的构造方式除了上面的默认构造还有迭代器构造和resize构造，即实例化对象就能让该对象中拥有数据。
两种构造方式代码如下：
#include<iostream>
using namespace std;
#include<assert.h>
namespace ZH
{
template<class T>
class vector
{
public:
typedef T* iterator;
vector()//构造函数
{}
vector(size_t n, const T& t = T())//resize构造
{
resize(n, t);
}
template<class Inputinteraor>
vector(Inputinteraor left, Inputinteraor right)//迭代器构造
{
size_t sz = right - left;
reserve(sz);
while (left != right)
{
push_back(*left);
left++;
}
}
void push_back(const T& val)
{
if (_finish == _end_of_storage)
reserve(capacity() == 0 ? 4 : capacity() * 2);
*_finish = val;
_finish++;
}
void resize(size_t n, const T& t = T())//匿名对象具有常属性
{
if (n < size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
reserve(n);
while (_finish != _start + n)
{
*_finish = t;
_finish++;
}
}
}
size_t size()const//得到元素个数
{
return _finish - _start;
}
size_t capacity()const//得到空间大小
{
return _end_of_storage - _start;
}
void reserve(size_t n)//扩容函数
{
if (n > capacity())
{
T* temp = new T[n];
size_t poi = _finish - _start;//先把_start和_finish之间的距离记录下来
if (_start != nullptr)
{
memcpy(temp, _start, sizeof(T) * size());//拷贝数据
delete[] _start;
}
_start = temp;//更新_start的指向
_finish = _start + poi;
_end_of_storage = _start + n;
}
}
//普通版本迭代器函数
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
private:
iterator _start = nullptr;//缺省值赋予空
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
int main()
{
ZH::vector<int> v1(10u, 6);//resize构造
ZH::vector<int> v2(v1.begin(),v1.end());//迭代器构造
ZH::vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
ZH::vector<int>::iterator it2 = v2.begin();
while (it2 != v2.end())
{
cout << *it2 << " ";
it2++;
}
cout << endl;
return 0;
}运行结果：
8、深浅拷贝
若我们自己不写拷贝构造则系统会自动生成一个拷贝构造，但是系统自动生成的拷贝构造只能完成浅拷贝，即一些成员变量的值拷贝，但是这里的vector涉及到空间的开辟，因此不能用浅拷贝完成vector类型的拷贝，原因如下图：
我们所期望的是v2指向一块属于自己的空间，如下图：
但是即便是v2有一块属于自己的空间也不是完全解决了问题，因为vector的类型可以是自定义类型，这时候如果当vector的类型是string类型，那么vector中的每个元素都是string类型，则每个元素自己内部又会新开辟一块空间，这时候就是深拷贝的问题了。
示意图如下：
我们所期望的是每个自定义元素也指向一块属于该元素的空间：
因此当把v1里的元素拷贝给到v2的新空间时，元素之间的拷贝必须也是深拷贝，双重深拷贝代码如下：
#include<iostream>
using namespace std;
#include<assert.h>
namespace ZH
{
template<class T>
class vector
{
public:
typedef T* iterator;
vector()//构造函数
{}
void push_back(const T& val)
{
if (_finish == _end_of_storage)
reserve(capacity() == 0 ? 4 : capacity() * 2);
*_finish = val;
_finish++;
}
size_t size()const//得到元素个数
{
return _finish - _start;
}
size_t capacity()const//得到空间大小
{
return _end_of_storage - _start;
}
void reserve(size_t n)//扩容函数
{
if (n > capacity())
{
T* temp = new T[n];
size_t poi = _finish - _start;//先把_start和_finish之间的距离记录下来
if (_start != nullptr)
{
memcpy(temp, _start, sizeof(T) * size());//拷贝数据
delete[] _start;
}
_start = temp;//更新_start的指向
_finish = _start + poi;
_end_of_storage = _start + n;
}
}
vector(const vector<T>& val)//深拷贝构造
{
_start = new T[val.capacity()];
for (size_t i = 0; i < val.size(); i++)
{
//会调用string的运算符重载，而sting的运算符重载本身就是深拷贝
_start[i] = val._start[i];
}
_finish = _start + val.size();
_end_of_storage = _start + val.capacity();
}
~vector()//析构函数
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
//普通版本迭代器函数
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
private:
iterator _start = nullptr;//缺省值赋予空
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
int main()
{
ZH::vector<string> v1;
v1.push_back("hello");
v1.push_back("hello");
ZH::vector<string> v2 = v1;//双重深拷贝构造
//打印v2的值
ZH::vector<string>::iterator it = v2.begin();
while (it != v2.end())
{
cout << *it << " ";
it++;
}
cout << endl;
return 0;
}运行结果：
这里值得注意的是代码可以正常运行，意味着析构的时候没有出问题，即没有出现同一块空间被析构两次的情况。
结语：
以上就是关于vector的模拟实现，通过模拟实现可以帮助我们更深层次的了解vector类，vector类实质上就是一个动态的数组，只不过用起来更加便捷。最后希望本文可以给你带来更多的收获，如果本文对你起到了帮助，希望可以动动小指头帮忙点赞👍+关注😎+收藏👌！如果有遗漏或者有误的地方欢迎大家在评论区补充，谢谢大家！！
![[PyTorch][chapter 9][李宏毅深度学习][Why Deep]](https://img-blog.csdnimg.cn/direct/44aa7070aaed431fa4794e5acb0d9af2.png)
