c++修炼之路之vector模拟实现

前言：

一：在STL的开源代码中的vector的实现

二：模拟实现

1.数据成员+size()+capacity()

2.resize+reserve

3.构造函数+析构函数+赋值重载

4.迭代器+[]

5.push_back+insert+erase+迭代器失效问题

三：测试用例和全部代码

接下来的日子会顺顺利利，万事胜意，生活明朗-----------林辞忧

前言：

在了解标准库中的vector之后，对于模拟实现vecor的各接口函数常常是面试时的重难点，在模拟实现vector的过程中主要有迭代器失效的问题，在模拟实现的vectro中是使用三指针来模拟实现vector的，接下来我们就开始介绍vector的模拟实现

一：在STL的开源代码中的vector的实现

对于vector的模拟实现和string的完全不同，vector采用的是三指针来模拟实现

使用的是start,finish,endofstorage三个指针，在看源代码时如果不懂这三个指针的指向位置的话，则可以先看size和capacity的实现来猜测，则

finish-start=size 有效数据的大小

endofstorage-start=capacity 容量

二：模拟实现

1.数据成员+size()+capacity()

typedef T*  iterator;private:iterator _start=nullptr;iterator _finish=nullptr;iterator _endofstorage=nullptr;size_t size()const
{return _finish - _start;
}
size_t capacity()const
{return _endofstorage - _start;
}

2.resize+reserve

对于在reserve的操作中会出现一些问题，首先是如果T是自定义类型的话，不能使用浅拷贝，得使用深拷贝，在操作过程中注意_finish的大小，如果不注意的话，_finish是不改变的，导致没有扩容，访问数据的话会直接越界访问报错

void reserve(size_t n)//开空间
{if (n > capacity()){T* tmp = new T[n];//开空间size_t sz = size();if (_start){//问题1：// memcpy是按字节来拷贝的，完成的是浅拷贝，如果T是string的话//浅拷贝会直接出错的，应该是实现为深拷贝//memcpy(tmp, _start, sizeof(T) * size());//拷贝数据for (int i = 0; i < sz; i++){tmp[i] = _start[i];}delete[]_start;//释放旧空间}//改变指向_start = tmp;//_finish = _start + size();//问题2：这样写的话，size()=_finish-_start   =>  _finish=_finish;// 还是原先的_finish没有改变（扩容）在访问数据时就会出错_finish = _start + sz;_endofstorage = _start + n;}
}
void resize(size_t n, const T& val = T())//匿名对象具有常行，加const修饰
{if (n <= size())//删除数据{_finish = _start + n;}else{reserve(n);while (_finish<_start+n){*_finish = val;++_finish;}}
}

3.构造函数+析构函数+赋值重载

注意尤其是拷贝构造，如果T是自定义类型的话，我们不写编译器自动生成的完成的是浅拷贝，浅拷贝就会发生问题的，所以得自己实现深拷贝

vector()//无参构造
{}//使用一段迭代器区间来构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);++first;}
}vector(size_t n, const T&val=T())//n个val构造   //缺省值给匿名对象
{reserve(n);//开空间for (int i = 0; i < n; i++){push_back(val);}
}//处理vector<int> v1(10,0)这种的，如果不重载的话，会自动匹配到迭代器区间构造
vector(int n, const T& val = T())//n个val构造   //缺省值给匿名对象
{reserve(n);//开空间for (int i = 0; i < n; i++){push_back(val);}
}//拷贝构造 vector<int> v2(v1)
vector(const vector<T>& v)
{reserve(v.capacity());//开空间//最好进行深拷贝for (auto& c : v){push_back(c);}
}void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}
//赋值重载 v1=v2;
vector<int>& operator=(vector<int> v)
{swap(v);return *this;
}~vector()
{delete[] _start;_start = _finish = _endofstorage = nullptr;
}

4.迭代器+[]

迭代器有着普通迭代器和const成员使用的const迭代器，有了迭代器就支持范围for来遍历数据

对于下标+[]一样，也有const对象遍历时使用的

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;
}
T &operator[](size_t pos)
{assert(pos < size());return *(_start + pos);
}const T& operator[](size_t pos)const
{assert(pos < size());return *(_start + pos);
}

5.push_back+insert+erase+迭代器失效问题

迭代器失效就是迭代器底层对应指针指向的空间被销毁了，而使用一块已经被释放的空间，程序会崩溃，引起迭代器失效的这些操作主要是与扩容有关的操作

对于insert插入数据要扩容时，由于之前的pos在扩容之前的数组中。在扩容后原数组被释放，pos还在原数组中，就会变为野指针，在扩容后的数组中没有pos指针，在insert操作时就报错，解决办法就是重新赋值

对于erase也是如此会有迭代器失效的问题，

这里使用的是传值传参，形参的改变不影响实参，底层空间是不改变的，如果没有返回值的话，pos就会失效的，下次使用vs就会直接报错的，解决办法就是传值返回

void push_back(const T& val)
{if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = val;++_finish;//insert(end(), val);复用
}
void insert(iterator pos,const T& val)//在pos位置插入val
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){//问题3：需要注意在开空间后pos位置还在原数组，此时delete原数组后，pos变成野指针//解决办法：先保存下来与_start的距离，在开空间之后在_start+距离即是pos的位置size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}//挪动数据iterator end = _finish;while (end > pos){*end = *(end - 1);--end;}*pos = val;++_finish;
}
iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);// vs2019进行强制检查，erase以后认为it失效了，不能访问，访问就报错//解决办法：使用返回值iterator end = pos + 1;while (end < _finish){*(end - 1) = *end;++end;}--_finish;return pos;
}