vector的模拟实现

vector框架

template <class T>class vector {public:T _start;//(1)T _finsih;//(2)T _endofstorge;//(3)
};


  $(1)$指向当前空间的第一个元素。
  $(2)$指向当前空间存储的最后一个元素的下一个位置。
  $(3)$指向当前空间的末尾。

默认构造函数

vector()//默认构造函数:_start(nullptr),//(1)_finish(nullptr),//(2)_endofstorge(nullptr)//(3){}


  $(1)(2)(3)$因为一开始没有分配空间&＃xff0c;所以三个指针都置为空。

有参构造函数

template<class InputIterator>vector(InputIterator first, InputIterator last)//(1):_start(nullptr),_finish(nullptr),_endofstorge(nullptr){while (first !&＃61; last){push_back(*first);//(2)first&＃43;&＃43;;}}


  $(1)$使用一个迭代器区间进行初始化。
  $(2)$复用push_back。

为什么这里要将这个这个函数设置为函数模板呢&＃xff1f;
并且将模板参数的名字取为InputIterator。

迭代器其实也有其分类&＃xff1a;

1.Input_iterator 2.Output_iterator 这两个没有实际对应的类型
3.forward_iterator (单向迭代器)如&＃xff1a; map&＃xff0c;unordered_map 迭代器只能&＃43;&＃43;
4.Bidirectional_iterator (双向迭代器) 能够&＃43;&＃43;和-- 如list
5.Randoaccess_iterator (随机迭代器) 能够访问任意位置 如&＃xff1a;vector

上面是父类&＃xff0c;下面是子类&＃xff0c;子类包含了父类的功能。除此之外迭代器都具有解引用这类功能

迭代器的分类有什么作用呢&＃xff1f;
我们查看下算法库中的sort&＃xff0c;

sort要求传入随机迭代器&＃xff0c;这时传入双向迭代器&＃xff0c;单向迭代器就不满足要求了&＃xff0c;如list就不支持sort算法。

又如reverse

其迭代器的类型为双向迭代器&＃xff0c;但是也可以传入随机迭代器&＃xff0c;因为随机迭代器具有双向迭代器的全部功能。

总结&＃xff1a;迭代器的分类其实是一种引导的功能&＃xff0c;告诉你该算法可以使用哪些迭代器&＃xff0c;哪些不能用。

size

int size() const{return _finish - _start;//(1)}


  $(1)$_finish指向当前空间存储元素的最后一个元素的下一个位置&＃xff0c;所以直接减去_start就能得到当前空间存储了多少个数据。

capacity

int capacity() const{return _endofstorge - _start;}


内置数据类型的构造函数

在C&＃43;&＃43;中自定义类型具有构造函数&＃xff0c;为了兼容&＃xff0c;内置类型也具有构造函数&＃xff0c;如int的构造函数int()。

const修饰的匿名对象

匿名对象的生命周期为当前行&＃xff0c;出了该行以后即被回收。
但是如果const修饰以后呢&＃xff1f;
结论&＃xff1a;const修饰的匿名对象生命周期得到延长&＃xff0c;直至函数执行完毕
证明&＃xff1a;通过调试模式&＃xff0c; 当执行到23行时&＃xff0c;仍然没有执行person的析构函数&＃xff0c;main函数运行完才执行析构。

reserve

void reserve(int newcapacity)//这里capacity是存储的个数&＃xff0c;不是字节数{T *tmp &＃61; new T[newcapacity];int sz &＃61; size();//(1)if (_start){//memcpy(tmp, _start, sizeof(T)*newcapacity);//(2)for (int i &＃61; 0; i < sz; i&＃43;&＃43;)tmp[i] &＃61; _start[i];//(3)}delete[]_start;//(4)_start &＃61; tmp;//(5)_finish &＃61; _start &＃43; sz;//(6)_endofstorge &＃61; _start &＃43; newcapacity;//(7)}


  $(1)$需要提前记录下旧空间存储数据的个数&＃xff0c;用于后面更新_finish。关于为什么要提前记录。这里我们画图理解。
因为后面更新_finish需要_finish距离_start的距离&＃xff0c;但是因为先更新的_start,导致后面通过size()函数获得的数据个数是错误的&＃xff0c;就无法得到_finish正确的位置

  $(2)$这里不能使用memcpy&＃xff0c;如果单纯的对两个string进行拷贝&＃xff0c;会导致两个string类的_str指针指向的空间一致&＃xff0c;这会导致浅拷贝。在释放空间的时候会造成错误。

  $(3)$浅拷贝引发的问题使用深拷贝进行解决&＃xff0c;对vector的每个数据都进行赋值拷贝。
  $(4)$释放原空间。
  $(5)(6)(7)$分别更新_start,_finish,_endofstorage。

resize

void resize(int newcapacity, const T &x &＃61; T())//(1){if (newcapacity > capacity())//(2){reserve(newcapacity);while (_finish!&＃61;_endofstorge){*_finish &＃61; x;_finish&＃43;&＃43;;}}else if (capacity() >&＃61; newcapacity)//(3){_finish &＃61; _start &＃43; newcapacity;}}


  $(1)$因为resize会对扩容的部门进行初始化&＃xff0c;而vector存储的数据类型有很多种&＃xff0c;因此使用默认的构造函数作为初始化的默认值。
这里的T& x&＃61;T();牵扯到自定义类型有点不好理解&＃xff0c;我们进行画图理解。
假设要创建一个三行三列的二维vector

  $(2)$扩容的空间大于原空间&＃xff0c;将多余的空间进行初始化。
  $(3)$扩容的空间小于原空间&＃xff0c;更新_finish就好

迭代器

typedef T* iterator;typedef const T* const_iterator;


  $(1)$普通版本

iterator begin(){return _start;//(1)}iterator end(){return _finish;//(2)}


  $(1)$返回第一个元素。
  $(2)$返回最后一个元素的下一个位置。

  $(1)$const版本

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


&＃xff1a;

拷贝构造函数传统写法

vector(const vector<T> &v){_start &＃61; new T[v.capacity()];//(1)_finish &＃61; _start &＃43; v.size();//(2)_endofstorge &＃61; _start &＃43; v.capacity();//(3)//memcpy(_start, v._start, sizeof(T)*v.size());碰到string这种自定义类型的时候浅拷贝导致同一块空间被析构两次。//(4)for (int i &＃61; 0; i < v.size(); i&＃43;&＃43;)//(5)_start[i] &＃61; v._start[i];}


  $(1)$申请新空间。
  $(2)(3)$更新_finish和_endofstorage。
  $(4)$这里不能使用memcpy&＃xff0c;和reserver一样&＃xff0c;当vector存储的数据类型是自定义类型string的时候&＃xff0c;这里就是一个浅拷贝&＃xff0c;而每个对象出来作用域就会被析构&＃xff0c;就会导致堆区内存重复释放。
  $(5)$浅拷贝的问题需要通过深拷贝进行解决。

拷贝构造函数现代写法

void swap(vector<T>&v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorge, v._endofstorge);}vector(const vector<T>&v):_start(nullptr),//(1)_finish(nullptr),//(2)_endofstorge(nullptr)//(3){vector<T> tmp(v.begin(),v.end());//(4)swap(tmp);//(5)}


  $(1)(2)(3)$因为一开始指向的空间是随机值&＃xff0c;这样在释放空间的时候会导致非法访问&＃xff0c;所以需要置空。
  $(4)$复用有参构造函数
  $(5)$直接进行空间交换就好&＃xff0c;tmp是个临时对象&＃xff0c;出了函数作用域会被析构&＃xff0c;空间会被释放。

find

iterator find(iterator first,iterator last,T val ){while (first!&＃61;last){if (*first &＃61;&＃61; val)//(1)return first;first&＃43;&＃43;;}return last;//(2)}

  $(1)$找到了就返回该元素的迭代器位置
  $(2)$没找到返回末尾迭代器

insert迭代器失效

在了解什么是迭代器失效之前&＃xff0c;我们先看一下vector中insert的模拟实现。
我们知道&＃xff0c;插入数据的时候需要扩容。并且需要从插入位置开始挪动数据。
原因正是出在这&＃xff0c;扩容以后_start,_finish,_endofstorage都指向了新空间的位置。但是pos指向的还是原空间&＃xff0c;但是原空间已经被释放&＃xff0c;这时pos就是一个野指针。挪动数据的时候就会失败。

void insert(iterator pos,T val){if (_finish &＃61;&＃61; _endofstorge)//这里扩容会导致迭代器失效{reserve(capacity() &＃61;&＃61; 0 ? 4 : capacity() * 2);}iterator right &＃61; _finish;iterator left &＃61; pos;//因为增容,pos原来指向的空间会被释放&＃xff0c;所以需要计算出新的pos的位置while (left < right){(*right) &＃61; *(right - 1);right--;}*pos &＃61; val;_finish&＃43;&＃43;;}


解决代码如下&＃xff1a;

void insert(iterator pos,T val){if (_finish &＃61;&＃61; _endofstorge)//这里扩容会导致迭代器失效{int sz &＃61; pos - _start;//(1)reserve(capacity() &＃61;&＃61; 0 ? 4 : capacity() * 2);pos &＃61; _start &＃43; sz;//&＃xff08;2&＃xff09;}iterator right &＃61; _finish;iterator left &＃61; pos;//因为增容,pos原来指向的空间会被释放&＃xff0c;所以需要计算出新的pos的位置while (left < right){(*right) &＃61; *(right - 1);right--;}*pos &＃61; val;_finish&＃43;&＃43;;}


加上(1)和(2)代码以后就可以正常插入数据了。
  $(1)$提前计算pos的位置
  $(2)$扩容完成后更新pos

这时候insert在插入数据的时候迭代器不会失效了&＃xff0c;但是还有一种场景迭代器失效的场景存在&＃xff1a;
如果我想打印插入的数据呢&＃xff1f;这时候实参传递的it迭代器会不会失效呢&＃xff1f;
答案是会的&＃xff0c;在前面我们只是对pos迭代器进行了矫正&＃xff0c;但是传参过程是一个值传参&＃xff0c;形参的改变不会影响实参。也就是说it还是指向旧空间。
解决办法&＃xff1a;返回值进行接收&＃xff0c;it接收insert函数返回pos更新以后的位置。

void test10()//测试insert{vector<int> v1;v1.push_back(10);v1.push_back(20);v1.push_back(30);v1.push_back(40);auto it&＃61;v1.find(v1.begin(), v1.end(), 30);if (it !&＃61; v1.end()){v1.insert(it, 50);//(1)cout << *it << endl;}}


  $(1)$外部迭代器仍然是失效的
正确代码&＃xff1a;

iterator insert(iterator pos,T val){if (_finish &＃61;&＃61; _endofstorge)//这里扩容会导致迭代器失效{int sz &＃61; pos - _start;reserve(capacity() &＃61;&＃61; 0 ? 4 : capacity() * 2);pos &＃61; _start &＃43; sz;}iterator right &＃61; _finish;iterator left &＃61; pos;//因为增容,pos原来指向的空间会被释放&＃xff0c;所以需要计算出新的pos的位置while (left < right){(*right) &＃61; *(right - 1);right--;}*pos &＃61; val;_finish&＃43;&＃43;;return pos;}

void test10()//测试insert{vector<int> v1;v1.push_back(10);v1.push_back(20);v1.push_back(30);v1.push_back(40);auto it&＃61;v1.find(v1.begin(), v1.end(), 30);if (it !&＃61; v1.end()){it&＃61;v1.insert(it, 50);//(1)cout << *it << endl;}}


  $(1)$接收pos更新以后位置的迭代器

erase

iterator erase(iterator pos){//删除pos位置的数据iterator left &＃61; pos;iterator right &＃61; _finish;while (left<right)//(1){(*left) &＃61; *(left &＃43; 1);left&＃43;&＃43;;}_finish--;return pos;}


  $(1)$挪动数据。
  $(1)$别忘了 更新_finish的位置。

总结&＃xff1a;
1.拷贝构造传统写法和reseve一定要注意使用&＃xff0c;避开浅拷贝带来的问题。
2.insert带来的迭代器失效也需要认真画图思考一下。
3.在模拟实现的时候&＃xff0c;迭代器&＃xff0c;模板参数T&＃xff0c;typdef以后很容易让人搞乱&＃xff0c;大家可以多想一想&＃xff0c;并可以根据下图进行思考。