【C++模拟实现】vector的模拟实现

【C++模拟实现】vector的模拟实现

---

作者：爱写代码的刚子

时间：2023.9.1

前言：模拟实现系列好久没更了，前来补更。

vector模拟实现的标准代码

namespace test
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin(){return _start;}const_iterator cend() const{return _finish;}vector():_start(nullptr),_finish(nullptr),_endOfStorage(nullptr){}vector(int n, const T& value = T()){resize(n,value);}template<class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr),_finish(nullptr),_endOfStorage(nullptr){//存疑，是否要reservewhile(first!=last){push_back(*first);++first;}}vector(const vector<T>& v)//这里是引用:_start(nullptr),_finish(nullptr),_endOfStorage(nullptr){reserve(v.capacity());for(auto e:v){push_back(e);}}vector<T>& operator= (vector<T> v){swap(v);return *this;}~vector(){delete[] _start;_start = nullptr;_finish = nullptr;_endOfStorage = nullptr;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}void reserve(size_t n){if(n>capacity()) {iterator tmp = new T[n];//拷贝数据(手动)int sz = size();if(_start) {for (int i = 0; i < sz; i++) {tmp[i] = _start[i];}delete[] _start;//一定要记得}_start = tmp;_finish = _start + sz;_endOfStorage = _start + n;}}void resize(size_t n, const T& value = T()){if(n<capacity()){_finish=_start + n;}else{reserve(n);while(_finish!=_start+n){*_finish=value;++_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];}void push_back(const T& x){insert(end(),x);}void pop_back(){erase(--end());//注意是--end(),end()指向的是数据的下一个位置}void swap(vector<T>& v){std::swap(v._start,_start);std::swap(v._finish,_finish);std::swap(v._endOfStorage,_endOfStorage);}iterator insert(iterator pos, const T& x){assert(pos>=_start&&pos<=_finish);if(_finish==_endOfStorage){size_t len = pos - _start;size_t newcapacity = capacity()==0?4:capacity()*2;reserve(newcapacity);pos = _start + len;}iterator end = _finish - 1;while(end>=pos){*(end+1) = *end;--end;//--end不是++end()}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos>=_start&&pos<=_finish);iterator it=pos+1;while(it!=_finish){*(it-1)=*it;++it;}--_finish;return pos;}private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾iterator _endOfStorage; // 指向存储容量的尾};
}

vector模拟实现中的要点

insert和erase会涉及到迭代器失效的问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了 封装，比如:vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的 空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃（即如果继续使用已经失效的迭代器，程序可能会崩溃）。

有关迭代器失效的几种做法

• 对于vector可能会导致其迭代器失效的操作有:

  1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如:resize、reserve、insert、assign、 push_back等。

     出错原因:以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉， 而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。

     解决方式:在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新赋值即可。

  2. 指定位置元素的删除操作–erase

     erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是:如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。(但Linux下g++可能不一样，因为迭代器使用了原生指针，没有像vs一样进行封装)

​

**迭代器失效解决办法:在使用前，对迭代器重新赋值即可。 **

涉及到底层空间改变时，需要考虑重置迭代器

vector深度剖析

关于模版template< class InputIterator >

为什么不使用自己之前定义的iterator？

• 若使用iterator做迭代器，会导致初始化的迭代器区间[first,last)只能是vector的迭代器
• 重新声明迭代器，迭代器区间[first,last)可以是任意容器的迭代器

使用memcpy拷贝问题

为什么在reserve接口中不能直接使用memcpy进行拷贝？

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2. 如果拷贝的是自定义类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，memcpy的拷贝实际是浅拷贝。

所以在模版模拟实现中慎用memcpy！！！

结论:如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

---

【附】：范围for是C++11的