📌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 != nullptrif (_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()){//保存一份sizesize_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#includeusing 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 != nullptrif (_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()){//保存一份sizesize_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#includeusing 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;};}

文章到这就结束了,大家有什么问题欢迎在评论区讨论,博主一定及时回复!觉得文章写的不错的老铁也可以点赞收藏加关注,后续还会有更多的好文分享哦!