📌vector的模拟实现
😊本文为小碗里原创,CSDN首发
📅发布时间:2022/3/20
🙌欢迎大家👍点赞?收藏?加关注
?本文大约2200词左右
🙏笔者水平有限,如有错误,还望告诉笔者,万分感谢!
🚩有什么问题也可在评论区一起交流哦!
📣前言
在熟悉了vector的使用后,让我们来模拟一下vector的实现吧!
(声明:标准库中vector的实现比较复杂,本文旨在加深对vector使用的理解,若按照标准库的标准模拟实现,要牵扯其他的知识,不利于我们学习vector)
🎨模拟实现
一.主干结构
namespace V
{
//类模板
template<class T>
class vector
{
//迭代器(指针是一个天然的随机迭代器)
//关于迭代器,之后我们会详谈
typedef T* iterator;
public:
//...
private:
//迭代器可看作一个指针,但也有区别
iterator _start;//起始位置
iterator _finish;//最后一个元素下一位置
iterator _end_of_Storage;//最大容量位置下一位
};
}
这里是用迭代器去控制vector的,我们知道vector可看作一个可控大小的顺序表,对于顺序表的实现,我们知道有三个参数,一个是指向数组的指针a,一个是数组的大小size,还有一个是数组的容量capacity.所以对于vector来说,我们可以对比着顺序表来看.其实这三个迭代器就类似于顺序表中的三个参数.start指向内存空间起始位置,finish指向最后一个元素的下一位,end_of_storage指向最大容量位置下一位.
二.成员函数
🚀取容量 capacity()
size_t capacity() const
{
return _end_of_Storage - _start;
}
🚀取大小 size()
size_t size() const
{
return _finish - _start;
}
🚀swap
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_Storage, v._end_of_Storage);
}
🚀构造函数(1)
vector()
:_start(nullptr), _finish(nullptr), _end_of_Storage(nullptr)
{}
🚀析构函数
~vector()
{
//_start != nullptr
if (_start)
{
delete[] _start;
_start = _finish = _end_of_Storage = nullptr;
}
}
🚀拷贝构造函数
Traditional
vector(const vector<T>& v)
{
_start = new T[v.capacity()];
_finish = _start + v.size();
_end_of_Storage = _start + v.capacity();
memcpy(_start, v._start, v.size()*sizeof(T));
}
Modern
vector(const vector<T>& v)
:_start(nullptr), _finish(nullptr), _end_of_Storage(nullptr)
{
//调用构造函数
vector<T> tmp(v.begin(), v.end());
//自己实现的swap效率高,若用库里的swap(v1,v2),会有3次深拷贝
swap(v);
}
这里需要说明的是,对于vector拷贝构造函数的现代写法的思想与之前string的拷贝构造函数的现代写法思想一致,就是希望定义一个临时对象,其调用构造函数来开辟一块空间,但是对于vector来说,它在这里就不能用一开始写的构造函数了.
对于该使用需求,vector还有一种构造函数,它是通过一个迭代器区间初始化.
🚀构造函数(2)
//对于InputIterator的取名不能随意改,这是规范
//一个类模板的成员函数,也可以是一个函数模板
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr), _finish(nullptr), _end_of_Storage(nullptr)
{
while (first != last)
{
//尾插,下文给出
push_back(*first);
first++;
}
}
🚀尾插 push_back
void push_back(const T& x)
{
if (_finish == _end_of_Storage)
{
//增容
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
_finish++;
}
🚀增容 reserve
对于增容reserve函数,这里有一个易错点,以下是错误代码,大家能看出哪儿错了吗?
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
memcpy(tmp, _start, sizeof(T)*size());
delete[] _start;
}
_start = tmp;
_finish = _start + size();
_end_of_Storage = _start + n;
}
}
让我们揭晓答案~~
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
memcpy(tmp, _start, sizeof(T)*size());
delete[] _start;
}
_start = tmp;
//size()函数内部的实现是_finish-_start
//原空间被释放后,_start指向新开辟的空间的起始位置,而_finish还是指向原来的空间位置
//故在求size()时答案错误
_finish = _start + size();
_end_of_Storage = _start + n;
}
}
不难发现,问题就出在求size()的时候start的位置更新了,要解决这个问题就是要保持start和finish的相对位置,或是保存一份size(),所以这里就有两种解决方法:
//写法一:
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
//内存拷贝(字节序拷贝)
memcpy(tmp, _start, sizeof(T)*size());
delete[] _start;
}
//求得size()后再更新_start
_finish = tmp + size();
_start = tmp;
_end_of_Storage = _start + n;
}
}
//写法二:
void reserve(size_t n)
{
if (n > capacity())
{
//保存一份size
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
memcpy(tmp, _start, sizeof(T)*sz);
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_Storage = _start + n;
}
}
🚀重置大小 resize()
//缺省值是一个匿名对象,调用了它自己的构造函数
void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);//增容
}
while (_finish != _start + n)
{
*_finish = val;
_finish++;
}
}
}
对于resize()的实现,我相信大家都看得懂,但是大家可能会有一个疑惑:
🔎这里使用了匿名对象传缺省值,匿名对象的生命周期不是只在当前行吗?
🔎val是T()的引用,那该行结束,T()生命周期结束,val不也应该失效吗?
🔎那为什么程序没有出错?
🔎如果T是像int,double这样的内置类型,它们也有自己的构造函数?
为了不影响本文的篇幅和结构,关于匿名对象生命周期的问题,我在下面链接所指的文章中有详细的解释,感兴趣的老铁可以点击链接,前去查看~~
🚀赋值运算符重载 operator=
vector<T>& operator=(const vector<T> v)//v是实参的拷贝构造出来的临时对象
{ //函数调用完自动调用析构函数销毁
swap(v);
return *this;
}
🚀插入 insert
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start&&pos <= _finish);
if (_finish == _end_of_Storage)
{
//保存pos位置,防止增容后pos位置失效
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;//更新pos位置
}
iterator end = _finish;
while (end != pos)
{
*end = *(end - 1);
end--;
}
*pos = x;
_finish++;
return pos;
}
对于插入操作,要注意的就是增容带来的迭代器失效问题!
不仅如此,我们发现insert还返回了插入的位置,原因是insert的pos实参到形参是传值,如果增容了,函数里的pos更新了,但是外面的pos没有更新,为了不让外面的pos迭代器失效,insert支持了返回更新后的pos.
🚀尾删 pop_back
void pop_back()
{
assert(_finish > _start);
_finish--;
}
🚀删除 erase
iterator erase(iterator pos)
{
assert(pos >= _start&&pos < _finish);
iterator cur = pos + 1;
while (cur < _finish)
{
*(cur - 1) = *cur;
cur++;
}
_finish--;
return pos;//更新pos位置
}
三.完整代码
#include<iostream>
#include<assert.h>
using namespace std;
namespace V
{
template<class T>
class vector
{
typedef T* iterator;
public:
size_t capacity() const
{
return _end_of_Storage - _start;
}
size_t size() const
{
return _finish - _start;
}
vector()
:_start(nullptr), _finish(nullptr), _end_of_Storage(nullptr)
{}
~vector()
{
//_start != nullptr
if (_start)
{
delete[] _start;
_start = _finish = _end_of_Storage = nullptr;
}
}
//Modern写法
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::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(v);
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr), _finish(nullptr), _end_of_Storage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}
void push_back(const T& x)
{
if (_finish == _end_of_Storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
_finish++;
}
//写法一:
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
memcpy(tmp, _start, sizeof(T)*size());
delete[] _start;
}
//求得size()后再更新_start
_finish = tmp + size();
_start = tmp;
_end_of_Storage = _start + n;
}
}
//写法二:
void reserve(size_t n)
{
if (n > capacity())
{
//保存一份size
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
memcpy(tmp, _start, sizeof(T)*sz);
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_Storage = _start + n;
}
}
//缺省值是一个匿名对象,调用了它自己的构造函数
void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);//增容
}
while (_finish != _start + n)
{
*_finish = val;
_finish++;
}
}
}
vector<T>& operator=(const vector<T> v)
{
swap(v);
return *this;
}
void pop_back()
{
assert(_finish > _start);
_finish--;
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start&&pos <= _finish);
if (_finish == _end_of_Storage)
{
//保存pos位置,防止增容后pos位置失效
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;//更新pos位置
}
iterator end = _finish;
while (end != pos)
{
*end = *(end - 1);
end--;
}
*pos = x;
_finish++;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start&&pos < _finish);
iterator cur = pos + 1;
while (cur < _finish)
{
*(cur - 1) = *cur;
cur++;
}
_finish--;
return pos;//更新pos位置
}
private:
iterator _start;
iterator _finish;
iterator _end_of_Storage;
};
}
🎶代码练习
大家可以将下面代码拷贝到编译器上,自己写一写,练习一下!
#include<iostream>
#include<assert.h>
using namespace std;
namespace V
{
template<class T>
class vector
{
typedef T* iterator;
public:
//取容量
size_t capacity() const
//取大小
size_t size() const
//构造函数
vector()
//析构函数
~vector()
//拷贝构造函数
vector(const vector<T>& v)
//迭代器实现构造函数
template<class InputIterator>
vector(InputIterator first, InputIterator last)
//尾插
void push_back(const T& x)
//增容(两种写法)
void reserve(size_t n)
//重置大小
void resize(size_t n, const T& val = T())
//赋值运算符重载
vector<T>& operator=(const vector<T> v)
//pos位置插入数据
iterator insert(iterator pos, const T& x)
//删除pos位置元素
iterator erase(iterator pos)
private:
iterator _start;
iterator _finish;
iterator _end_of_Storage;
};
}
文章到这就结束了,大家有什么问题欢迎在评论区讨论,博主一定及时回复!觉得文章写的不错的老铁也可以点赞收藏加关注,后续还会有更多的好文分享哦!