vector类模拟实现（c++）（学习笔记）

学习笔记）"/>

vector类模拟实现（c++）（学习笔记）

vector

• 构造函数
• 析构函数
• []
• push_back
• • size()
  • capacity()
  • reserve()
  • push_back()
• 迭代器实现
• • 非const和const版本
• pop_back()
• resize()
• insert()***重点
• erase()***重点
• 再谈构造函数！
• 拷贝构造函数****（重点）
• =运算符重载***（重点）

基本框架：

namespace xty
{template<class T>class vector {public:typedef T* iterator;/////...///private:iterator _strat;  //起始位置iterator _finish;  //最后一个元素的下一个地址iterator _end_of_storage;  //容量的最后一个元素};
}

vector的大致形状如下：黄色代表每天满的地方。

构造函数

使用初始化列表实现一个简单的无参构造函数。

		//无参构造函数vector():_finish(nullptr),_start(nullptr),_end_of_storage(nullptr){}

析构函数

记住要带[]即可。

		~vector(){delete[] _start; //用带括号的_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;}

[]

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

push_back

size()

		size_t size() const{return _finish - _start;}

capacity()

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

reserve()

因为push_back涉及到扩容函数，需要实现reserve()。

如下示例：

		void  reserve(size_t n){if (n > capacity()){T* tem = new T[n];if (_start){memcpy(tem, _start, sizeof(T)*size()); //拷贝过去delete[] _start;}_start = tem;_finish = _start + size();   //error_end_of_storage = _start + n;}}

问题1：_finish赋值出错，出bug了，是因为size()函数，调用了空指针，导致报错。
改正：
因为delete之后，原数据就被清空了，所以可以提前保存一下size()的大小。

		void  reserve(size_t n){if (n > capacity()){T* tem = new T[n];const size_t sz = size();  //提前保存szif (_start){memcpy(tem, _start, sizeof(T)*size()); //拷贝过去delete[] _start;}_start = tem;_finish = _start + sz;  //使用sz赋值_end_of_storage = _start + n;}}

push_back()

逻辑比较简单，在vector的尾部添加一个val，就需要一些前置函数。

		//尾插void push_back(const T& val){//满了扩容if (_finish  == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}//插入数据*_finish = val;_finish++;}

迭代器实现

该逻辑也比较简单，注意实现const的版本。

非const和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;}

pop_back()

尾删。

bool empty(){return _start == _finish;}//尾删void pop_back(){assert(!empty());_finish--;}

resize()

和string逻辑差不多。

		void resize(size_t n, const T& val = T()){//一样大，直接返回if (n == size())   {return;}if (n<size())   //小于直接修改_finish{while (n != size()){--_finish; }}else{if (n > capacity())   //大于容量先扩容{reserve(n);}while (n != size()){push_back(val);}}}

优化：该函数多次调用push_back()使用while，效率低。

		void resize(size_t n, const T& val = T()){if (n == size()){return;}if (n < size()){ _finish = _start + n;  //直接移动_finish}else{if (n > capacity()){reserve(n);}while (_finish != _start + n)  //使用指针操作，减少调用{*_finish = val;_finish++;}}}

insert()***重点

传入迭代器的位置，插入一个元素。

		void insert(iterator pos ,const T& val){//检测pos位置是否合法assert(pos >= _start);assert(pos <= _finish);// 满了需要扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}//从后往前移动iterator end = _finish;while (end > pos){*end = *(end - 1);end--;}*pos = val;   //在该位置赋值_finish++;}

算法问题1：会造成迭代器失效，迭代器失效，实际就是迭代器底层对应指针所指[空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。
该程序正常来说没有问题，当出现扩容的时候，reserve（）会删除原来的空间，去申请新的空间，因此会导致pos指向的那段空间被释放掉，pos变成野指针。

改正：记录插入的相对位置，扩容后根据相对位置更新pos的值。

		void insert(iterator pos, const T& val){//检测pos位置是否合法assert(pos >= _start);assert(pos <= _finish);// 满了需要扩容if (_finish == _end_of_storage){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 = val;   //在该位置赋值_finish++;}

算法问题2：执行insert后，如果扩容，pos位置已经改变了，而函数外面的pos因为是值传递，并没有修改，同样导致了野指针的问题。（迭代器再一次失效！）
解决办法：

1. pos传引用可以吗？
   不可以。如下图：如果传入v.begin()，会报错。因为begin()是传值返回，传值返回有一个临时变量，而临时变量具有常性，不能被修改，insert里面就不能修改了！
   
2. 通过返回值解决可以吗？
   可以，我们可以利用insert返回值的特性，来更新pos防止失效！
   如下图：这样就解决问题了。

最终版本：

		iterator insert(iterator pos, const T& val){//检测pos位置是否合法assert(pos >= _start);assert(pos <= _finish);// 满了需要扩容if (_finish == _end_of_storage){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 = val;   //在该位置赋值_finish++;return pos;}

总结：使用insert后，我们默认迭代器失效！因为我们不知道何时执行扩容操作，因此需要重新对pos赋值，防止这类情况发生！

erase()***重点

指定位置执行删除操作。

		void erase(iterator pos){assert(pos >= _start);assert(pos < _finish);auto end = pos + 1;while (end < _finish){//后给前，从前往后*(end - 1) = *end;end++;}_finish--;}

问题1：erase会导致迭代器失效？
==会导致！==如果删除最后一个位置，最后一个位置就变成了空位置，导致pos也指向了不该指向的位置。因此，erase()执行过后，应该重新给pos赋值再使用！

最终版本：添加返回值。

		iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);auto end = pos + 1;while (end < _finish){//后给前，从前往后*(end - 1) = *end;end++;}_finish--;return pos;}

---

最后给大家一个例子自己感受：
该例子在VS2019会报错

#include <iostream>
using namespace std;
#include <vector>
int main()
{vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it;}return 0;
}
int main()
{vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)it = v.erase(it);else++it;}return 0;
}

再谈构造函数！

这次实现一个可以规定数量和内容的构造函数。

//正常实现vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);size_t len = n;while (n--){push_back(val);}}//构造函数由迭代器实现template<class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first != last){push_back(*first);++first;}}

当我们满心欢喜的实现好这两个构造函数后，想要测试一下。结果报错了。
输入： vector vx(10,5);

这是为什么呢？因为10，5都被编译器认为是int类型，而编译器在函数重载时，会自动调用最合适的，而它认为第二个函数更适合自己()，因此解引用的时候产生非法间接寻址！

因此我们需要再次实现一个int型的函数重载！

		vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);size_t len = n;while (len--){push_back(val);}}

---

迭代器构造还支持以下方法：

	int a[] = { 1, 2, 3 };vector<int> v4(a, a + 3);for (auto e : v4){std::cout << e << " ";}std::cout << std::endl;
}

拷贝构造函数****（重点）

如果我们不自己实现拷贝构造函数，编译器就会默认生成一个，但是编译器默认生成的是浅拷贝，不可以。

//拷贝构造vector(const vector<T>& v){//扩容reserve(v.capacity());memcpy(_start, v._start, sizeof(T) * v.size());_finish = _start + v.size();}

现在我们写完这个函数的拷贝构造之后，看看是否有问题：

提前告诉大家，这个程序会崩溃，因为memcpy()实现的是浅拷贝，他仅仅会拷贝v3的首尾指针，并不会开一个新的空间去存储相应的字符串。所以，程序结束时，调用析构函数，会连续析构两次！

**解决办法：**不适用memcpy()自己实现深拷贝，使用‘=’即可实现，因为string赋值操作就是深拷贝，string的赋值，就会先开空间，再拷贝！

//拷贝构造vector(const vector<T>& v){//扩容reserve(v.capacity());//memcpy(_start, v._start, sizeof(T) * v.size());for (size_t i = 0; i <v.size(); i++){_start[i] = v._start[i];   //变成string对象的拷贝}_finish = _start + v.size();}

但是reverse()也会产生这个浅拷贝的问题，因此将reserve也应该改成深拷贝。

		void  reserve(size_t n){if (n > capacity()){T* tem = new T[n];const size_t sz = size();  //提前保存szif (_start){//memcpy(tem, _start, sizeof(T)*size()); //拷贝过去for (size_t i = 0; i < size(); i++){tem[i] = _start[i];}delete[] _start;}_start = tem;_finish = _start + sz;  //使用sz赋值_end_of_storage = _start + n;}}

这样vector的问题就解决了。但是vector<vector<int>>还有问题！！！请看赋值重载的部分。

=运算符重载***（重点）

这里暴露了一个问题，就是虽然外面的vector是深拷贝，但是里面的vector是浅拷贝，是由于没有写vector的赋值重载，再补充一个赋值重载即可！

		vector<T>& operator=(vector<T> v){swap(v);return *this;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}

运算符重载和拷贝构造这里写的不太详细，后续还会补充！