✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨文章所属专栏：c++篇–CSDN博客
文章目录
- 前言
- 一.`vector`类的默认成员函数
- 二.`vector`类的访问和迭代器相关函数
- 三.`vector`类的容量相关函数
- 四.`vector`类的修改相关函数
- 五.迭代器失效问题
- 六.完整代码文件
前言
在C++的世界中，标准模板库（STL）的vector容器因其灵活性和效率而广受欢迎。vector以其动态数组的形式，提供了快速访问和插入元素的能力，是许多程序员的得力工具。然而，当我们深入探究其内部机制时，会发现实现一个高效、健壮的vector并非易事。在这篇博客中，我们将一起踏上模拟实现vector的旅程。我们将从零开始，一步步构建一个属于我们自己的vector类。我们将探索vector的内部结构，理解其内存管理策略，并实现其核心功能，如push_back、pop_back、insert和erase等操作。
本次模拟实现需要用到两个文件：
test.cpp测试文件用来进行测试检验
vector.h头文件用来声明和定义
一.vector类的默认成员函数
整体框架
和之前模拟实现string一样，为了和库里面的std::vector进行区分，要定义一个命名空间用来封装我们自己模拟实现的vector，整体框架如下：
namespace Myvector{
template<class T>
class vector{
public:
typedef T* iterator;
//成员函数
private:
//成员变量
iterator _start;
iterator _finish;
iterator _endofstorage;
};
}
实现原理：
-
和
string类不同的是，vector是模版类，vector中不仅可以存储内置类型的数据，对于我们自己设置的自定义类型数据也可以存储，因此需要使用模版。 -
用typedef 关键字重定义T类型，因为vector中不管是成员变量还是之后需要用到的迭代器都是T类型（就是指针类型），所以直接重定义为迭代器类型名iterator。
-
_start指针指向的是数组的首元素位置，_finish指针指向的是数组最后一个元素的下一个位置，而_endofstorage指针指向的是数组空间最后的位置。
-
如图所示：
构造函数
vector类中用多种构造函数的重载，这里我们主要实现三种常用的构造函数：
-
无参构造函数：
代码实现：
vector() :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { cout<<"vector()"<<endl; } -
带参构造函数：
1.代码实现：
vector(int n, const T& val = T()) :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { resize(n, val); }2.实现原理：
-
n表示指定数量大小需要存储多少个元素，val表示需要存储的数据
-
T()是匿名对象缺省值，如果T是自定义类型会调用对应的构造函数创建匿名对象，而c++对内置类型进行了升级，也可以使用构造函数初始化，比如：
int i=0; int j=int(); int k=int(1); -
直接调用resize()函数（该函数在后面讲解），对空数组开辟空间的同时，将数据val填充到新的空间。
-
-
迭代器区间构造函数：
1.代码实现：
template<class inputiterator> vector(inputiterator first,inputiterator last) :_start(nullptr) ,_finish(nullptr) ,_endofstorage(nullptr) { while(first!=last) { push_back(*first); first++; } }2.实现原理：
-
这里使用函数模版是因为对于迭代器的类型我们并不确定，可能是一个数组，也可能是string类型的迭代器所以这里使用函数模版来代替具体的类型，调用函数时，编译器会根据具体的类型来推演具体的函数。
-
_first表示迭代器的起始位置，_last表示迭代器的终止位置。
-
调用push_back()函数直接将需要存储的数据插入到vector对象中。
-
如图所示：
-
析构函数
析构函数比较简单，如果_start指针不为空指针，表示有空间需要释放，直接调用delete函数释放空间，再将三个指针置为空即可，没有什么需要注意的地方，这里直接展示代码实现：
~vector()
{
cout<<"~vector()"<<endl;
if(_start)
{
delete[] _start;
_start=_finish=_endofstorage=nullptr;
}
}
拷贝构造函数
-
代码实现：
vector(const vector<T>& v) { _start=new T[v.capacity()]; for(size_t i=0;i<v.size();i++) { _start[i]=v._start[i]; } _finish=_start+v.size(); _endofstorage=_start+v.capacity(); } -
实现原理：
-
拷贝构造是用一个已经存在的对象拷贝创建一个新的对象，所以首先是调用new函数开辟新的空间，空间大小是被拷贝对象容量。
-
接下来就是拷贝数据，这里和模拟实现stirng类不同的是，string类可以使用memcpy函数直接拷贝所有数据，而vector类这里有所不同，如果vector数组中存储的是string类型的对象，直接使用memcpy会完成浅拷贝，而string类型是自定义类型，拷贝数据需要完成深拷贝，否则会产生一系列错误（具体可以看string模拟实现那篇文章，有详细的讲解深拷贝），所以这里需要一个一个拷贝数据，实现拷贝构造。
-
拷贝完数据后，_finish指针指向最后一个元素的位置，_endofstorage指针指向数组空间最后的位置。
-
如图所示：
-
赋值运算符重载函数
-
代码实现：
//现代写法 void Swap(vector<T>& v) { swap(_start,v._start); swap(_finish,v._finish); swap(_endofstorage,v._endofstorage); } //赋值运算符重载函数 vector<T>& operator=(vector<T> v) { Swap(v); return *this; } -
实现原理：
- 赋值拷贝是用一个已经存在的对象赋值给另一个已经存在的对象。
- 使用现代写法直接交换两个对象的三个指针，让他们分别指向另一个空间
测试
测试代码：
void test1()
{
//指定数量和数值构造v1对象
Myvector::vector<int> v1(10,1);
for(auto e:v1){
cout<<e<<" ";
}
cout<<endl;
//用区间进行构造v2对象
int array[]={1,2,3,4,5};
Myvector::vector<int> v2(array,array+5);
for(auto e:v2){
cout<<e<<" ";
}
cout<<endl;
//用v2对象拷贝构造v3对象
Myvector::vector<int> v3(v2);
for(auto e:v3){
cout<<e<<" ";
}
cout<<endl;
//构造空对象v4，并将对象v1赋值给v4
Myvector::vector<int> v4=v1;
for(auto e:v4){
cout<<e<<" ";
}
cout<<endl;
}
测试结果：
二.vector类的访问和迭代器相关函数
访问函数
访问函数operator[]:
-
代码实现：
//普通对象访问函数 T& operator[](size_t pos) { assert(pos<size()); return _start[pos]; } //const对象访问函数 const T& operator[](size_t pos)const { assert(pos<size()); return _start[pos]; } -
实现原理：
- 断言判断pos位置是否符合范围。
- 符合范围后直接返回数组中对应位置元素即可
迭代器函数
vector类的迭代器模拟实现较为简单，begin()函数直接返回_start指针，end()函数直接返回_finish指针即可。
类型定义：
//普通对象迭代器类型
typedef T* iterator;
//const对象迭代器类型
typedef const T* const_iterator;
begin()函数:
-
代码实现：
iterator begin(){ return _start; } const_iterator begin()const { return _start; }
end()函数：
-
代码实现：
iterator end(){ return _finish; } const_iterator end()const { return _finish; }
测试
测试代码：
void test2()
{
Myvector::vector<int> v(5,100);
//下标+[]方式访问遍历
for(size_t i=0;i<v.size();i++){
cout<<v[i]<<" ";
}
cout<<endl;
//迭代器遍历
Myvector::vector<int>::iterator it=v.begin();
while(it!=v.end()){
cout<<*it<<" ";
it++;
}
cout<<endl;
}
测试结果：
三.vector类的容量相关函数
容量大小函数
size()函数：
-
代码实现：
size_t size()const { return _finish-_start; } -
实现原理：
_finsih指针指向的是数组做后一个元素，直接减去_start指针，就是数组实际存储的元素个数
capacity()函数：
-
代码实现：
size_t capacity()const { return _endofstorage-_start; } -
实现原理：
_endofstorage指针指向的是数组空间最后的位置，直接减去_start指针，就是整个数组的容量
扩容函数
reserve()函数：
-
代码实现：
void reserve(size_t n){ if(n>capacity()){ //先保存 size_t sz=size(); //开新空间 iterator tmp=new T[n]; //判断是否需要拷贝数据 if(_start){ for(size_t i=0;i<sz;i++){ tmp[i]=_start[i]; } delete[] _start; } //更改指针，指向新的空间 _start=tmp; _finish=_start+sz; _endofstorage=_start+n; } } -
实现原理：
- 首先判断需要扩容的大小n是否大于原数组的容量，如果大于就进行扩容，小于则保持不变。
- 扩容时，开辟新的空间，空间大小为参数n，设置一个新的指针tmp指向新的空间。
- 开辟新空间后判断原数组的_start指针是否为空，如果为空，表示原数组是空，不需要拷贝数据，不为空则需要进行拷贝数据。这里的拷贝数据和拷贝构造函数那里一样，如果T是自定义类型时，直接使用memcpy函数会完成数据的浅拷贝，而自定义类型必须是深拷贝，所以这里也需要一个一个的拷贝每个数据元素。拷贝完后释放原来的数组空间。
- _start指针指向新的空间，_finish指针加上最开始保存的size(),如果没有保存，直接调用size()函数，会发生错误，因为原空间中的_start指针已经指向新的空间。_endofstorage指针加上新的容量大小n
resize()函数：
-
代码实现：
void resize(size_t n,const T& val=T()){ if(n<size()){ _finish=_start+n; } else{ reserve(n); while(_finish!=_start+n){ *_finish=val; _finish++; } } } -
实现原理：
- 如果n小于原数组的大小则发生截断。
- 如果n大于原数组的大小进行扩容，扩容直接调用reserve()函数，扩容后，从_finish指针当前位置开始遍历，将val数据填充到新空间中，同时更改_finish指针的位置，指向新的位置。
- 图片：
测试
测试代码：
void test3()
{
//创建对象v,依次插入5个字符串"vector"
Myvector::vector<string> v;
for(size_t i=0;i<5;i++){
v.push_back("vector");
}
//输出当前的大小和容量并遍历打印
cout<<v.size()<<" "<<v.capacity()<<endl;
for(auto e:v){
cout<<e<<" ";
}
cout<<endl;
//调用reserve()函数扩容到8
v.reserve(10);
//输出当前的大小和容量
cout<<v.size()<<" "<<v.capacity()<<endl;
//调用resize()函数扩容到10,并将新空间中插入字符串"string"
//输出当前的大小和容量并遍历打印
v.resize(12,"string");
cout<<v.size()<<" "<<v.capacity()<<endl;
for(auto e:v){
cout<<e<<" ";
}
cout<<endl;
//调用resize()函数缩容到4，发生截断
//输出当前的大小和容量并遍历打印
v.resize(6);
cout<<v.size()<<" "<<v.capacity()<<endl;
for(auto e:v){
cout<<e<<" ";
}
cout<<endl;
}
测试结果：
四.vector类的修改相关函数
插入函数
insert()函数：
-
代码实现：
iterator insert(iterator pos,const T& x){ assert(pos>=_start&&pos<=_finish); if(_finish==_endofstorage){ size_t len=pos-_start; size_t newcapacity=capacity()==0?4:2*capacity(); reverse(newcapacity); pos=_start+len; } iterator end=_finish-1; while(end>=pos){ *(end+1)=*end; end--; } *pos=x; _finish++; return pos; } -
实现原理：
- 首先断言判断pos指针是否符合范围，pos指针指向的位置需要在_start指针和_finish指针中间
- 然后判断是否需要扩容，扩容前需要先计算并保存pos指针到_start指针的大小，然后调用reserve()函数进行扩容，扩容后从新更改pos指针，让它指向新空间中的位置（这里是涉及到迭代器失效问题，在本文的后面会重点讲解）
- 扩容后就是开始移动数据，将pos位置后面的数据都往后移动一位，具体过程看代码实现
- 移动数据后，将需要插入的数据插入到pos位置，然后_finish指针后移一位，最后返回pos指针，相当于返回当前插入的位置。
push_back()函数：
-
代码实现：
void push_back(const T& x){ insert(end(),x); } -
实现原理：
直接调用insert()函数，相当于在数组的最后位置也就是end()位置插入数据。
删除函数
erase()函数：
-
代码实现：
iterator erase(iterator pos){ assert(pos>=_start&&pos<=_finish); iterator it=pos+1; while(it!=_finish){ *(it-1)=*it; it++; } _finish--; return pos; } -
实现原理：
- 首先断言判断pos指针是否符合范围，pos指针指向的位置需要在_start指针和_finish指针中间
- 然后设置一个新的指针it用来遍历数组，将pos位置后面的数据依次往前移动一位
- _finish–，表示删除一个元素，最后返回pos指针，相当于返回当前删除的位置。
pop_back()函数：
-
代码实现：
void pop_back(){ erase(end()--); } -
实现原理：
直接调用erase()函数，相当于删除数组最后一个位置的元素，也就是end()前一个位置
测试
测试代码：
void test4()
{
//创建对象v,依次插入5个字符串"vector"
Myvector::vector<string> v;
for(size_t i=0;i<5;i++){
v.push_back("vector");
}
for(auto e:v){
cout<<e<<" ";
}
cout<<endl;
v.insert(v.begin()+2,"string");
for(auto e:v){
cout<<e<<" ";
}
cout<<endl;
v.erase(v.begin()+4);
for(auto e:v){
cout<<e<<" ";
}
cout<<endl;
}
测试结果：
五.迭代器失效问题
在C++的vector中，迭代器失效是一个需要注意的重要问题。迭代器失效主要发生在vector的底层空间发生改变的情况下，这通常是由于vector的扩容或者指定位置的元素插入或者删除操作引起的。
迭代器失效的原因
-
扩容操作：
- 当vector需要增加元素，而当前分配的空间不足以容纳新元素时，vector会进行扩容。扩容通常涉及分配一个新的、更大的数组，并将原数组中的元素复制到新数组中。
- 由于底层空间的改变，之前获取的迭代器将不再指向vector中的有效元素，因此迭代器会失效。
这就是为什么在insert函数中，扩容前需要先计算pos位置指针到_start指针的大小，扩容后再从新更新pos指针，因为扩容导致底层空间的改变，之前获取的迭代器pos指针没有指向新空间对应的位置。
-
指定位置的插入和删除：
-
在vector的指定位置插入元素时，如果插入位置不是vector的末尾，且插入后导致vector需要扩容，那么迭代器会失效。
vector<int> v={1,2,3,4,5}; vector<int>::iterator it=v.begin()+3; //在3之前插入100 //插入前迭代器it指向3 it=insert(it,100); //插入后迭代器it不再指向3,而是插入的100 //v:1,2,100,3,4,5 -
删除vector中指定位置的元素时，虽然不会总是导致扩容，但删除操作会使得被删除元素之后的元素向前移动一个位置。如果删除的是最后一个元素，那么指向该元素的迭代器在删除后会变为指向end()的迭代器，而end()迭代器并不指向有效元素，因此也可以认为迭代器失效。
vector<int> v={1,2,3,4,5}; vector<int>::iterator it=v.begin()+2; //删除前迭代器it指向2 it=erase(it); //删除后迭代器it指向3，因为2已经被删除 //v:1,3,4,5 vector<int>::iteraot rit=v.begin()+4; //删除前迭代器rit指向5 rit=erase(rit); //删除后rit指向的是end()迭代器，此时迭代器rit失效
-
避免迭代器失效的方法
- 对于扩容引起的失效：在调用可能导致扩容的函数（如push_back、insert等）后，应重新获取迭代器。
- 对于插入和删除引起的失效：使用insert函数时，应接收其返回的迭代器作为新的有效迭代器；在使用erase函数删除元素后，同样应接收其返回的迭代器作为继续遍历的起点。
示例代码分析
以下是一个简单的示例，展示了在vector中插入元素后迭代器失效的情况：
void test5() {
Myvector::vector<int> vec;
vec.push_back(0);
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
vec.push_back(4);
Myvector::vector<int>::iterator it = vec.begin();
while (it != vec.end()) {
if (*it % 2 == 0) {
vec.insert(it, 5); // 在迭代器it指向的位置插入元素5
++it; // 由于insert可能改变底层空间，需要重新更新迭代器
}
++it;
}
for(auto e:vec){
cout<<e<<" ";
}
cout<<endl;
}
在上面的代码中，如果在insert操作后没有重新更新迭代器it，那么it可能会指向一个已经失效的位置，从而导致未定义的行为。
总结
在使用vector的迭代器时，需要注意扩容和指定位置插入/删除操作可能导致的迭代器失效问题。为了避免这些问题，应在这些操作后重新获取迭代器。同时，在编写涉及vector迭代器的代码时，应谨慎处理迭代器的有效性，以避免程序崩溃或未定义行为的发生。
六.完整代码文件
vector.h文件
#include<iostream>
#include<string>
#include<algorithm>
#include<assert.h>
using namespace std;
namespace Myvector
{
template<class T>
class vector
{
public:
typedef T* 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;
}
//只要是构造函数一定要用初始化列表给成员变量初始化，自定义类型用初始化列表初始化，内置类型可以在声明中给缺省值
//普通构造函数
vector()
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
cout<<"vector()"<<endl;
}
//n个val的构造函数
vector(size_t n, const T& val = T())
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
resize(n, val);
}
vector(int n, const T& val = T())
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
resize(n, val);
}
template<class inputiterator>
vector(inputiterator first,inputiterator last)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
while(first!=last)
{
push_back(*first);
first++;
}
}
//析构函数
~vector()
{
cout<<"~vector()"<<endl;
if(_start)
{
delete[] _start;
_start=_finish=_endofstorage=nullptr;
}
}
//拷贝构造函数
vector(const vector<T>& v)
{
_start=new T[v.capacity()];
for(size_t i=0;i<v.size();i++)
{
_start[i]=v._start[i];
}
_finish=_start+v.size();
_endofstorage=_start+v.capacity();
}
void Swap(vector<T>& v)
{
swap(_start,v._start);
swap(_finish,v._finish);
swap(_endofstorage,v._endofstorage);
}
//赋值运算符重载函数
vector<T>& operator=(vector<T> v)
{
Swap(v);
return *this;
}
size_t size()const
{
return _finish-_start;
}
size_t capacity()const
{
return _endofstorage-_start;
}
T& operator[](size_t pos)
{
assert(pos<size());
return _start[pos];
}
const T& operator[](size_t pos)const
{
assert(pos<size());
return _start[pos];
}
void reserve(size_t n)
{
if(n>capacity())
{
size_t sz=size();
T* tmp=new T[n];
if(_start){
//这里拷贝数据时，如果T是自定义类型，比如sring，直接使用memcpy会是浅拷贝，所以要用赋值深拷贝
for(size_t i=0;i<sz;i++)
{
tmp[i]=_start[i];
}
delete[] _start;
}
_start=tmp;
_finish=_start+sz;
_endofstorage=_start+n;
}
}
//T()是匿名对象缺省值，如果T是自定义类型会调用对应的构造函数创建匿名对象
//c++对内置类型进行了升级，也可以使用构造函数初始化
//int i=0; int j=int(); int k=int(1);
void resize(size_t n,const T& val=T())
{
if(n<size())
{
_finish=_start+n;
}
else
{
reserve(n);
while(_finish!=_start+n)
{
*_finish=val;
_finish++;
}
}
}
void push_back(const T& x)
{
/*if(_finish==_endofstorage){
size_t newcpacity=capacity()==0?4:2*capacity();
reserve(newcpacity);
}
*_finish=x;
_finish++;*/
insert(end(),x);
}
iterator insert(iterator pos,const T& x)
{
assert(pos >= _start && pos <= _finish);
//先记录pos的位置，防止扩容后迭代器失效
if(_finish==_endofstorage)
{
size_t len=pos-_start;
size_t newcapacity=capacity()==0?4:2*capacity();
reserve(newcapacity);
pos=_start+len;
}
//扩容后，更新pos的位置，让po指向新的空间中的位置
iterator end=_finish-1;
while(end>=pos)
{
*(end+1)=*end;
end--;
}
*pos=x;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos>=_start&&pos<=_finish);
iterator it=pos+1;
while(it!=_finish)
{
*(it-1)=*it;
it++;
}
_finish--;
return pos;
}
void pop_back()
{
erase(end()-1);
}
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
}
test.cpp文件
#include"vector.h"
void test1()
{
//指定数量和数值构造v1对象
Myvector::vector<int> v1(10,1);
for(auto e:v1){
cout<<e<<" ";
}
cout<<endl;
//用区间进行构造v2对象
int array[]={1,2,3,4,5};
Myvector::vector<int> v2(array,array+5);
for(auto e:v2){
cout<<e<<" ";
}
cout<<endl;
//用v2对象拷贝构造v3对象
Myvector::vector<int> v3(v2);
for(auto e:v3){
cout<<e<<" ";
}
cout<<endl;
//构造空对象v4，并将对象v1赋值给v4
Myvector::vector<int> v4=v1;
for(auto e:v4){
cout<<e<<" ";
}
cout<<endl;
}
void test2()
{
Myvector::vector<int> v(5,100);
//下标+[]方式访问遍历
for(size_t i=0;i<v.size();i++){
cout<<v[i]<<" ";
}
cout<<endl;
//迭代器遍历
Myvector::vector<int>::iterator it=v.begin();
while(it!=v.end()){
cout<<*it<<" ";
it++;
}
cout<<endl;
}
void test3()
{
//创建对象v,依次插入5个字符串"vector"
Myvector::vector<string> v;
for(size_t i=0;i<5;i++){
v.push_back("vector");
}
//输出当前的大小和容量并遍历打印
cout<<v.size()<<" "<<v.capacity()<<endl;
for(auto e:v){
cout<<e<<" ";
}
cout<<endl;
//调用reserve()函数扩容到8
v.reserve(10);
//输出当前的大小和容量
cout<<v.size()<<" "<<v.capacity()<<endl;
//调用resize()函数扩容到10,并将新空间中插入字符串"string"
//输出当前的大小和容量并遍历打印
v.resize(12,"string");
cout<<v.size()<<" "<<v.capacity()<<endl;
for(auto e:v){
cout<<e<<" ";
}
cout<<endl;
//调用resize()函数缩容到4，发生截断
//输出当前的大小和容量并遍历打印
v.resize(6);
cout<<v.size()<<" "<<v.capacity()<<endl;
for(auto e:v){
cout<<e<<" ";
}
cout<<endl;
}
void test4()
{
//创建对象v,依次插入5个字符串"vector"
Myvector::vector<string> v;
for(size_t i=0;i<5;i++){
v.push_back("vector");
}
for(auto e:v){
cout<<e<<" ";
}
cout<<endl;
v.insert(v.begin()+2,"string");
for(auto e:v){
cout<<e<<" ";
}
cout<<endl;
v.erase(v.begin()+4);
for(auto e:v){
cout<<e<<" ";
}
cout<<endl;
}
void test5() {
Myvector::vector<int> vec;
vec.push_back(0);
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
vec.push_back(4);
Myvector::vector<int>::iterator it = vec.begin();
while (it != vec.end()) {
if (*it % 2 == 0) {
vec.insert(it, 5); // 在迭代器it指向的位置插入元素5
++it; // 由于insert可能改变底层空间，需要重新更新迭代器
}
++it;
}
for(auto e:vec){
cout<<e<<" ";
}
cout<<endl;
}
int main()
{
//test1();
//test2();
//test3();
//test4();
test5();
return 0;
}
以上就是关于如何模拟实现vector类的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！
