C++vector模拟实现

vector官方库实现的是一个模板类，因此我们也写个模板类。
在前面模拟实现过string类，string和vector都是动态增长的数组，有点类似。

vector把这个三个成员变量都换成了指针。

template<class T>
class Vector
{
public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start;iterator _finish;iterator _endofstorage;
};

1.构造函数

	//第一种无参构造Vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}

	//第二种构造Vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){//扩容if (_finish == _endofstorage){//因为这里没有size,capacity所以自己写个size，capacityint newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}while (n--){push_back(val);}}void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];//_start不为nullptr再拷贝if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_finish = _start + size();_endofstorage = _start + n;}}size_t size() const{//指针减指针等于元素个数return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}void push_back(const T& val = T()){//扩容if (_finish == _endofstorage){//因为这里没有size,capacity所以自己写个size，capacityint newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish = val;++_finish;}

写完一段代码先测试测试，看看有没有错误。

这里的_finish报错了，调试一下找原因。如果不能确定到底是哪里错误，就一段一段屏蔽代码，这里我们最终确定是扩容出现了问题。

我们开辟空间之后，_finish还指向nullptr，也就是根本没有更新_finish的位置。

	void reserve(size_t n){if (n > capacity()){//记录_finish的相对位置int Oldsize = size();T* tmp = new T[n];//_start不为nullptr再拷贝if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;//对_finish特殊处理。//_finish=_start+_finish-_start导致的错误。//_finish = _start + size();_finish = _start + Oldsize;_endofstorage = _start + n;}}

这样写，也防止了_start本身有空间，然后异地扩容，_finish位置不对的情况。

这里的reserve内部memcpy还有一个浅拷贝的问题，等最后说到这个成员函数再具体谈。

	//第三种扩容template <class InputIterator>Vector(InputIterator first, InputIterator last):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){while (first != last){push_back(*first);++first;}}iterator begin() const{return _start;}iterator end() const{return _finish;}

注意看图片的对比，右边没有屏蔽第二种构造函数，竟然报错了。

把1换成字符‘c’就不报错了。

其原因是因为10，1都是int类型，走的是模板参数的构造。
不是走的Vector(size_t n, const T& val = T())，因为int转换成size_t涉及算术转换。
而Vector(InputIterator first, InputIterator last) 这里都是同一类型，所以编译器会选择模板。
这里和库的解决方法一样，在加一个Vector(int n, const T& val = T())。
这样由于由现成的，编译器就不再会走模板了。

Vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){//扩容if (_finish == _endofstorage){//因为这里没有size,capacity所以自己写个size，capacityint newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}while (n--){push_back(val);}}

2.拷贝构造

在string模拟实现，拷贝构造实现了现代写法，是比较方便的，我们这里就继续用起来。

void swap(Vector<T> x){//这里调用的是库里面swap,关于这里可以看看string类模拟实现std::swap(_start, x._start);std::swap(_finish, x._finish);std::swap(_endofstorage, x._endofstorage);}Vector(const Vector<T>& val):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){Vector<T> tmp(val.begin(), val.end());//这里调用的是自己写的swap，如果直接用库里面的就会调用构造和拷贝构造。swap(tmp);}

3.析构+赋值运算符重载

	~Vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}//赋值运算符重载现代写法//v1=v2//v1=v1  虽然这里没有判断，但是很少有人会自己给自己赋值//即使赋值了，也是使用了一次拷贝构造Vector<T>& operator=(Vector<T> val){swap(val);return *this;}

4.iterator

	iterator begin() const{return _start;}const_iterator begin() const{return _start;}iterator end() const{return _finish;}const_iterator end() const{return _finish;}

5.modifiers

5.1push_back

void push_back(const T& val = T()){//扩容if (_finish == _endofstorage){//因为这里没有size,capacity所以自己写个size，capacityint newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish = val;++_finish;}

5.2pop_back

	void pop_push(){assert(!empty());--_finish;}

5.3empty

	bool empty(){return _start == _finish;}

5.4insert

	void insert(iterator pos, const T& val){assert(pos >= _start);assert(pos < _finish);//扩容if (_finish == _endofstorage){int newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}iterator begin = end();while (begin > pos){*begin = *(begin - 1);--begin;}*pos = val;++_finish;}

这样写就没有问题了吗？
测试一下看看。

发现和我们预想的结果不一样，分析一下，找原因

请问pos，在扩容之后应该在哪里呢？

这里是迭代器失效：野指针问题。
扩容导致，插入pos位置还是原空间的位置。
解决方法：
更新pos的位置。

	void insert(iterator pos, const T& val){assert(pos >= _start);assert(pos < _finish);//扩容if (_finish == _endofstorage){//记录pos的相对位置size_t n = pos - _start;int newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);//更新pospos = _start + n;}iterator begin = end();while (begin > pos){*begin = *(begin - 1);--begin;}*pos = val;++_finish;}

5.5erase

	void erase(iterator pos){assert(pos >= _start)assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;}

在来测试一下。

发现自己实现的vector没报错，库里面的vector，删除it位置，然后再读it位置，就报错了。这是也是因为迭代器失效问题。

再看看linux环境下同样代码是上面情况。


linux环境下读it位置可以再次读，说明这个位置没有失效。

那么erase删除位置到底失效不失效呢？

erase删除it位置，失效不失效，由编译器自己决定。

再看这样一种情况。

两个平台出现不一样的结果，为了代码能够再不同平台都能正常运行。所以，

erase，删除it位置元素，统一认为it失效了。it就不能再读写访问了，更新it才能继续访问，所以erase返回被删元素的下一个位置

更新了lt位置，就不会报错了。

正确写法。

	iterator erase(iterator pos){assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;}

5.6swap

	void swap(Vector<T>& x){std::swap(_start, x._start);std::swap(_finish, x._finish);std::swap(_endofstorage, x._endofstorage);}

6.Capacity

6.1size

	size_t size() const{//指针减指针等于元素个数return _finish - _start;}

6.2capacity

	size_t capacity() const{return _endofstorage - _start;}

6.3reserve

void reserve(size_t n){if (n > capacity()){//记录_finish的相对位置int Oldsize = size();T* tmp = new T[n];//_start不为nullptr再拷贝if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;//对_finish特殊处理。//_finish=_start+_finish-_start导致的错误。//_finish = _start + size();_finish = _start + Oldsize;_endofstorage = _start + n;}}

6.4resize

resize有三种情况；
n<size()；删除元素
size()<n<capacity()；插入元素
n>capacity()；扩容+插入元素

void resize(size_t n, const T& val=T()){if (n > size()){//这里在reserve已经判断过了是否扩容reserve(n);//插入数据while (_finish < _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}

6.5empty

	bool empty(){return _start == _finish;}

7.Element access

7.1operator[]

	T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}

7.2at

T& at(size_t pos){assert(pos < size());return _start[pos];}const T& at(size_t pos) const{assert(pos < size());return _start[pos];}

剩下接口比较简单，这里就不再模拟实现了。

8.在谈reserve

在谈reserve之前，做一道LeetCode的题
118. 杨辉三角

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv;vv.resize(numRows);for(int i=0;i<vv.size();++i){vv[i].resize(i+1);//放数据for(int j=0;j<vv[i].size();++j){if(j == 0 || j ==  vv[i].size()-1){vv[i][j]=1;}else{vv[i][j]=vv[i-1][j-1]+vv[i-1][j];}}}return vv;}
};

注意这道题，vector < T > ,T是自定义类型，不是内置类型；我们用自己写的vector来跑一下类似的代码，看看有没有什么问题。

void test_Vector4()
{Vector<Vector<int>> vv;Vector<int> v(5, 1);vv.push_back(v);vv.push_back(v);vv.push_back(v);vv.push_back(v);vv.push_back(v);for (size_t i = 0; i < vv.size(); ++i){for (size_t j = 0; j < vv[i].size(); ++j){cout << vv[i][j] << " ";}cout << endl;}}

为什么会有随机值的出现呢？
画图分析。

原因在于，reserve中memcpy拷贝的时候是浅拷贝，delete[ ] _start会把原有空间给释放掉了，所以出现随机值问题，

解决方法：浅拷贝换成深拷贝。

void reserve(size_t n){if (n > capacity()){//记录_finish的相对位置int Oldsize = size();T* tmp = new T[n];//_start不为nullptr再拷贝if (_start){//浅拷贝//memcpy(tmp, _start, sizeof(T) * size());//深拷贝for (size_t i = 0; i < Oldsize; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;//对_finish特殊处理。//_finish=_start+_finish-_start导致的错误。//_finish = _start + size();_finish = _start + Oldsize;_endofstorage = _start + n;}}

自此关于vector类模拟实现结束了。里面有很多值得多多思考的东西，希望能给你带来一份收获，喜欢的小伙伴，点赞，评论，收藏+关注！下篇博文再见！