目录
一、vector的模拟实现
1、vector的组成结构
2、vector尾插数据
2.1 析构函数
3、迭代器实现
4、resize
5、删除数据
5.1 迭代器失效
6、指定位置插入数据
6.1 迭代器失效
7、迭代器构造和resize构造
8、深浅拷贝
结语:
前言:
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类实质上就是一个动态的数组,只不过用起来更加便捷。最后希望本文可以给你带来更多的收获,如果本文对你起到了帮助,希望可以动动小指头帮忙点赞👍+关注😎+收藏👌!如果有遗漏或者有误的地方欢迎大家在评论区补充,谢谢大家!!