总言

  主要讲述vector的模拟实现。

文章目录

• 总言
• 1、基本框架搭建：成员变量
• 2、对构造函数、析构函数
• 3、增删查改、空间扩容
• • 3.1、vector::push_back、vector::pop_back
  • 3.2、vector::reserve、vector::capacity、vector::size
  • 3.3、operator[ ]
  • 3.4、遍历：迭代器(begin、end)、范围for
  • 3.5、vector::insert、vector::erase 迭代器失效
  • • 3.5.1、vector::insert
    • 3.5.2、迭代器失效
    • 3.5.3、vector::erase
    • 3.5.5、细节问题：不同编译器下的迭代器失效
  • 3.6、vector::resize
  • 3.7、vector::front、vector::back
• 4、拷贝构造与赋值：vector的深拷贝问题
• • 4.1、深浅拷贝说明
  • 4.2、vector拷贝构造演示
  • • 4.2.1、写法一：自己开辟空间，自己拷贝数据
    • 4.2.2、写法二：复用
    • 4.2.3、使用迭代器区间构造构造函数
    • 4.2.4、写法三：复用4.2.3、vector:: swap
    • 4.2.5、构造函数：n个val值
  • 4.3、vector赋值：operator=
  • 4.4、二维数组下深浅拷贝问题

1、基本框架搭建：成员变量

  同string类模拟实现一致，此处为了解决命名冲突问题，我们使用添加命名空间myvector的方式来处理。

#pragma once
namespace myvector
{templateclass vector{typedef T* iterator;//将模板T*命名为迭代器iteratorpublic:private:iterator _start;//起始iterator _finish;//结束iterator _end_of_storage;//容量空间};
}

  由于后续涉及到迭代器问题，若将typedef T* iterator;定义成私有，则无法在类外很好的使用。此处修改如下：

#pragma once
namespace myvector
{templateclass vector{public:typedef T* iterator;//将模板T*命名为迭代器iteratortypedef const T* const_iterator;private:iterator _start;//起始iterator _finish;//结束iterator _end_of_storage;//容量空间};
}

2、对构造函数、析构函数

  1）、构造函数
  对构造函数，我们之前学习时看到其中有内存池的相关内容，此处由于我们暂时没学习它，故对vector的模拟实现中我们不使用它。

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

  
  2）、析构函数

		~vector()//析构函数{delete[] _start;//null出来的空间是连续一块的，以_start为起始点。注意delete的使用方式_start = _finish = _end_of_storage = nullptr;}

3、增删查改、空间扩容

3.1、vector::push_back、vector::pop_back

  1）、库函数中声明回顾

  2）、push_back模拟实现

		void push_back(const T& x){//涉及扩容检查if (_finish == _end_of_storage){reserve(capacity() == 0?4:capacity() * 2);}//尾插数据*_finish = x;_finish++;}

  为什么需要使用引用和const修饰？
  因为这里使用的是T模板参数，我们传入的值可能是内置类型，也可能是自定义类型，如果是后者，则传值传参代价很大。
  
  3）、pop_back模拟实现

		void pop_back(){assert(_finish > _start);_finish--;}

3.2、vector::reserve、vector::capacity、vector::size

  1）、库函数中声明回顾

  2）、模拟实现

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

		void reserve(size_t n){if (n > capacity())//满足该条件才进行扩容{size_t sz = size();//因为后续重新确定指向关系时需要知道size值T* tmp = new T[n];if (_start)//说明原先空间有数据，{memcpy(tmp, _start, sizeof(T) * sz);//需要挪动delete[] _start;//释放旧空间}//重新确定指向关系_start = tmp;_finish = _start + sz;//_finish = _start + size();//如果是在这里获取size值，则在原先空间有数据的情况下，_start已经被delete_end_of_storage = _start + n;}}

3.3、operator[ ]

  1）、库函数中声明回顾

  2）、模拟实现

		T& operator[](size_t pos)//加&是为了支持可读可写{assert(pos < size());//检查下标是否非法return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}

3.4、遍历：迭代器(begin、end)、范围for

  1）、普通迭代器

		//vector的迭代器就是原生指针iterator begin(){return _start;}iterator end(){return _finish;}

  
  
  2）、const修饰的迭代器
  为什么需要？
  存在如下的情况:const vector& v，所创建的vector对象被const修饰，如果直接使用vector::iterator it = v.begin();，则属于权限放大。

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

	void Func(const vector& v){vector::const_iterator it = v.begin();while (it != v.end()){//*it = 10;//errorcout << *it << " ";++it;}cout << endl;for (auto e : v)//此处若使用范围for，const对象会调用对应的const迭代器{cout << e << " ";}cout << endl;}

  
  3）、为什么说范围for是傻瓜式替换？
  只要我们仿照库中使用对应字符begin、end，则访问for就能起效。相应的，如果我们使用了Begin、End等其它字母，则在我们模拟的vector中范围for失效。
  
  

3.5、vector::insert、vector::erase 迭代器失效

3.5.1、vector::insert

  1）、库函数中声明回顾

  2）、insert模拟实现1.0

		void insert(iterator pos, const T& val){assert(pos <= _finish && pos >= _start);//扩容检查if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}//数据挪动iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}//插入val值*pos = val;++_finish;}

  
  
  3）、insert涉及扩容时迭代器失效问题
  问题：

  
  原因解释：

  
  
  4）、insert模拟实现2.0

  解决方案： 若扩容，则要顺带更新pos指向位置

//保存二者指针差距
size_t len = pos - _start;
//扩容后更新pos指向
pos = len + _start;

void insert(iterator pos, const T& val){assert(pos <= _finish && pos >= _start);//扩容检查if (_finish == _end_of_storage){//保存二者指针差距size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);//扩容后更新pos指向pos = len + _start;}//数据挪动iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}//插入val值*pos = val;++_finish;}

3.5.2、迭代器失效

  1）、问题引入与现象分析
  接上一阶段代码，分析下述情形：
  一开始我们使用find找到了p位置，然后在p位置前插入一次，现在我们变为p位置前连续插入多次。问：是否能成功？

		//使用算法中的findauto p = find(v.begin(), v.end(), 3);if (p != v.end())//找到了{v.insert(p, 30);//1、插入一个30cout << *p << endl;//2、再次来到p的位置v.insert(p, 40);//3、我们p位置前插入一个40，问:是否能成功？}

  现象如下：

  
  可能出现疑问如下：我们在3.5.1中解决了insert中pos位置更新的问题，为什么此处p仍旧不起效？
  这里我们需要思考上述写的insert函数中，形参pos和实参p之间的关系。可知晓的是，在insert函数中，它们是值传递，故形参改变不影响实参。

		void insert(iterator pos, const T& val){assert(pos <= _finish && pos >= _start);//扩容检查if (_finish == _end_of_storage){//保存二者指针差距size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);//扩容后更新pos指向pos = len + _start;}//数据挪动iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}//插入val值*pos = val;++_finish;}

  
  
  2）、解决方案
  ①一个相对比较适合的方法是，在此类情况中，最好别再p位置失效后再去访问p。
  
  
  ②有人可能提出，我们在insert中为pos加上一个引用，即传引用返回，这样不就解决了？void insert(iterator& pos, const T& val)

		void insert(iterator& pos, const T& val){assert(pos <= _finish && pos >= _start);//扩容检查if (_finish == _end_of_storage){//保存二者指针差距size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);//扩容后更新pos指向pos = len + _start;}//数据挪动iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}//插入val值*pos = val;++_finish;}

  事实上这样做，针对insert而言确实可以解决问题，但同样会面临新的问题。
  第一，这样的模拟实现与库中不匹配，库中直接使用iterator pos；
  第二，这样做会带来新的问题，如下：

v.insert(v.begin(), 1);

  此段代码无法编译通过。因为begin模拟实现时，我们使用的是iterator传值返回，中间会生成一份临时变量，具有常性，后续insert处权限放大。
    Ⅰ、若为insert加上const，那么又无法解决修改问题。
    Ⅱ、而如果将begin也写为传引用返回，iterator& begin()，这样会使得begin具有修改能力，反而增添麻烦。

		iterator begin(){return _start;}

  
  
  3）、思考：上述值传递中，p一定存在迭代器失效问题吗？
  回答：同3.5.2中所讲，在涉及扩容问题时，p才存在失效。
  演示：如下述，假如我们一开始插入5个数值，容量空间足够的情况下，此处不存在p失效问题。

  
  
  4）、insert为push_back提供复用

		void push_back(const T& x){insert(end(), x);}

  5）、insert模拟实现3.0：案例演示
  案例要求： 在所有的偶数前插入该偶数的二倍值。

  代码演示+现象分析：
  我们以上述insert2.0版本为例进行演示，顺带再来回顾一下迭代器失效问题。

	void test_vector5(){std::vector v;v.reserve(10);v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//v.push_back(5);//在所有偶数前插入该偶数的2倍auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){v.insert(it, *it * 2);}++it;}}

  上述代码我们直接运行则程序崩溃无输出结果，调试后发现如下：it始终指向2的位置。这就是迭代器失效的另一种模式：因为数据挪动，导致外部指针指向错乱。
  ps: 迭代器失效的第一种模式：函数内扩容，导致野指针。

  
  为了解决上述问题，也一并解决insert中扩容后外部迭代器失效问题，一个方案如下：
    Ⅰ、对insert函数，模仿库中带上iterator返回值；
    Ⅱ、对原先的二倍插入循环，需要更新it指向的新位置，旨在解决扩容后外部迭代器失效问题。

		iterator insert(iterator pos, const T& val){assert(pos <= _finish && pos >= _start);//扩容检查if (_finish == _end_of_storage){//保存二者指针差距size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);//扩容后更新pos指向pos = len + _start;}//数据挪动iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}//插入val值*pos = val;++_finish;return pos;}

	void test_vector5(){std::vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//v.push_back(5);//在所有偶数前插入该偶数的2倍auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){it=v.insert(it, *it * 2);++it;}++it;}for (auto e : v){cout << e << " ";}cout << endl;}

  演示结果：

3.5.3、vector::erase

  1）、erase模拟实现1.0

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

  
  2）、erase是否会导致迭代器失效？
  ①主要看编译器如何实现erase函数，不排除有些编译器以时间换空间进行缩容：
  

			if (size() < capacity()/2){// 缩容 -- 以时间换空间}

  
  
  ②其它案例演示：删除vector中的偶数
  使用代码如下：

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

void test_vector4(){vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//v.push_back(5);for (auto e : v){cout << e << " ";}cout << endl;//删除所有偶数auto it = v.begin();while (it != v.end()){if(*it % 2 == 0){v.erase(it);}++it;}for (auto e : v){cout << e << " ";}cout << endl;}

  现象如下：

  
  
  
  
  3）、erase模拟实现2.0

		iterator erase(iterator pos){assert(pos < _finish && pos >= _start);iterator end = pos + 1;while (end < _finish){*(end - 1) = *end;++end;}--_finish;//if (size() < capacity()/2)//{//	// 缩容 -- 以时间换空间//}return pos;}

  基于2.0版本的erase我们再来修改上述 2) 中的题目：

void test_vector4(){vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//v.push_back(5);for (auto e : v){cout << e << " ";}cout << endl;//删除所有偶数auto it = v.begin();while (it != v.end()){if(*it % 2 == 0){it=v.erase(it);}else {++it;}}for (auto e : v){cout << e << " ";}cout << endl;}

3.5.5、细节问题：不同编译器下的迭代器失效

  需要注意的是，上述我们对迭代器失效的问题演示，其结果是未定义的，因为针对不同平台其STL底层实现并不一致。
  即，STL只是一个规范，其细节如何实现不做要求。
  VS：PJ版。
  g++：SGI版。
  
  

3.6、vector::resize

  1）、库函数中声明回顾

  
  2）、模拟实现
  根据上述可知，resize面临三种情况：
    Ⅰ、当n>capacity：扩容+使用val初始化；
    Ⅱ、当size：使用val初始化；
    Ⅲ、当n：删除多余数据
  
  模拟实现如下：

		void resize(size_t n, const T& val=T()){if (n > capacity()){reserve(n);}if (n > size())//两种情况：n>capacity、size//只需要初始化即可while (_finish < _start + n){push_back(val);++_finish;}}else{_finish = _start + n;}}

	void test_vector11(){//resize常用场景：在生成对象后开辟空间vectorv;v.resize(5);//验证默认缺省值for (auto e : v){cout << e << " ";}cout << endl;v.resize(10, 2);for (auto e : v){cout << e << " ";}cout << endl;}

	void test_vector11(){vector v1;v1.reserve(10);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.resize(8,8);//由大到小，而值只有5个，会添3个值for (auto e : v1){cout << e << " ";}cout << endl;}

T& front(){assert(size() > 0);return *_start;}T& back(){assert(size() > 0);return *（_finish - 1）;}

	private:iterator _start;//起始iterator _finish;//结束iterator _end_of_storage;//容量空间

		vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);vector v2(v);for (auto e : v2){cout << e << " ";}cout << endl;

		vector(const vector& v){_start = new T[v.size()];//此处也可以开辟v.capacity()大小的空间，各有各的优缺点memcpy(_start, v._start, sizeof(T)*v.size());//照搬数据_finish = _start + v.size();_end_of_storage = _start + v.size();//此处this._finish的大小根据上述我们开辟空间时的选择而变动}

	vector(const vector& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(v.size());for (const auto& e : v){push_back(e);//this.push_back()}}

		template vector(InputIterator first, InputIterator last){while (first != last){push_bakc(*first);++first;}}

	void test_vector7(){string str("hello world");vector v(str.begin(), str.end());//使用迭代器区间构造for (auto e : v){cout << e << " ";}cout << endl;}

		//使用迭代区间的构造函数：含类模板template vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first != last){push_back(*first);++first;}}

		void swap(vector& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v.__end_of_storage);}

		vector(const vector& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){vector tmp(v.begin(), v.end());swap(tmp);}

	vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}}

	void test_vector9(){int i=11;int j = int();int k(10);cout << "i:" << i << endl;cout << "j:" << j << endl;cout << "k:" << k << endl;}

	void test_vector10(){vectorv1(10);//验证默认缺省值for (auto e : v1){cout << e << " ";}cout << endl;vectorv2(5);for (auto e : v2){cout << e << " ";}cout << endl;}

		vectorv1(10,1);//验证默认缺省值for (auto e : v1){cout << e << " ";}cout << endl;

		//赋值v1=v2vector& operator=(vector v){swap(v);return *this;}

class Solution {
public:vector> generate(int numRows) {vector> vv;//定义一个vector>类型的数据vv.resize(numRows);//第一次开辟空间：numRows，表示总行数(整体大小)for(size_t i=0;ivv[i].resize(i+1,0);//第二次开辟空间，表示初始化杨辉三角的每行大小vv[i].front()=vv[i].back()=1;//杨辉三vv.size()角每行首尾数据为1//vv[i].resize(i+1,1);//上述代码也可以合并为一行实现}for(size_t i=2;ifor(size_t j=1;jvv[i][j]=vv[i-1][j-1]+vv[i-1][j];}}return vv;}
};

vector> ret = Solution().generate(5);

vector(const vector& v)//拷贝构造传统写法{_start = new T[v.size()];//此处也可以开辟v.capacity()大小的空间，各有各的优缺点//memcpy(_start, v._start, sizeof(T)*v.size());//照搬数据for (size_t i = 0; i < sz; i++)//照搬数据{_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.size();//此处this._finish的大小根据上述我们开辟空间时的选择而变动}

void reserve(size_t n){if (n > capacity())//满足该条件才进行扩容{size_t sz = size();//因为后续重新确定指向关系时需要知道size值T* tmp = new T[n];if (_start)//说明原先空间有数据，{//memcpy(tmp, _start, sizeof(T) * sz);//需要挪动for (size_t i = 0; i < sz; i++)//需要挪动{tmp[i] = _start[i];//*(tmp + i) = *(_start + i);}delete[] _start;//释放旧空间}//重新确定指向关系_start = tmp;_finish = _start + sz;//_finish = _start + size();//如果是在这里获取size值，则在原先空间有数据的情况下，_start已经被delete_end_of_storage = _start + n;}}