低头赶路，敬事如仪
目录
1、模拟vector
1.1底层结构
1.2构造析构
1.3尾插扩容
1.4迭代器
1.5增删查改
1.6模拟中的注意事项
2、vector模拟补充
2.1迭代器区间构造问题
2.2memcpy深浅拷贝问题
2.3动态二维数组的模拟及遍历
1、模拟vector
想要模拟实现自己的vector，得知其所以然！
分析一下STL源码里的vector底层成员变量
可以看到是三个迭代器类型成员变量，迭代器类型是什么呢？
经过typedef的底层指针，而T类型是模版类的参数。
大致框架如图：
1.1底层结构
根据我们刚才所查看的源码，我们要使用三个迭代器，要使用迭代器，我们可以使用指针进行模拟。
namespace xc{//设置成模板 兼容各种参数 但是不能分离编译否则链接错误template<class T>class vector{public:typedef T* iterator;private:iterator _start = nullptr;//指向容器开始iterator _finish = nullptr;//指向有效数据下一个位置iterator _end_of_storage = nullptr;//指向空间容量的下一个位置};}写出三个迭代器（指针）后，我们可以接着实现构造函数：需要初始化三个迭代器，所以我们给予初始值nullptr。然后进行开辟空间。
1.2构造析构
实现常用的构造析构以及赋值重载
/*vector(){}*///C++11 强制生成默认构造vector() = default;//优先匹配构造函数，防止非法的间接寻址问题vector(size_t n, const T& val = T()){reserve(n);for (size_t i=0; i < n; i++){push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (int i=0; i < n; i++){push_back(val);}}vector(long long n, const T&val = T()){reserve(n);for (long long i=0; i < n; i++){push_back(val);}}//类模板的成员函数还可以继续是函数模板template<class InputIterator> //写成模板是为了兼容所有容器vector(InputIterator first, InputIterator last){while(first != last){push_back(*first);++first;}}// v1(v)vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}void clear(){_finish = _start;} v1=v//vector<T>& operator=(const vector<T>&v)//{//if (this != &v)//{//clear();//reserve(v.size());//for (auto& e : v)//{//push_back(e);//}//}//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);}//现代写法 V1=vvector<T>& operator=(const vector<T> v){swap(v);return *this;}~vector(){if (_start){delete[]_start;_start = _finish = _end_of_storage = nullptr;}}1.3尾插扩容
想要实现尾插的操作，根据之前的经验，可以知道需要复用一些常用的简单接口（size() capacity() reserve() 等）
size_t size()const { return _finish - _start; }size_t capacity()const { return _end_of_storage - _start; }bool empty()const { _start == _finish; }//void reserve(size_t n)//{//if (n > capacity())//{//T* tmp = new T[n];//memcpy(tmp, _start, sizeof(T));//delete[]_start;//_start = tmp;//_finish = _start + size();//这是错误的 _start 已经是扩容后的 start了 而size调用的是 finish - start////解决方法 可以先更新 finish 或者记录一下 size的值//_end_of_storage = _start + n;//}//}void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, size()*sizeof(T));delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}}void reseize(size_t n, T val = T())//内置类型也具有的构造析构等函数行为 但是并没有概念{if (n < size()){_finih = _start + n;}else{reserve(n);while (_finsh < _start+n){*_finish++ = val;}}}void push_back(const T& x){//扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish++ = x;}注意：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。
1.4迭代器
所需要实现的迭代器其实很简单，对指针 typedef 即可
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; }实现了简单的迭代器，我们可以测试一下 迭代器遍历和范围for遍历
void test_vector1(){vector<int> v;v.push_back(1);v.push_back(1);v.push_back(1);v.push_back(1);vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << ' ';++it;}cout << endl;for (auto e : v){cout << e << ' ';}cout << endl;}
这里我们为了后续方便封装一个打印函数
template<class T>void print_vector(const vector<T>& v){vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << ' ';++it;}cout << endl;}可是这居然报错
为什么呢？没有实例化的类模板里面取东西，编译器是分不清 const_iterator 是静态成员变量还是类型的，在前面加一个 typename 显示告诉编译器是类型即可
template<class T>void print_vector(const vector<T>& v){typename vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << ' ';++it;}cout << endl;}1.5增删查改
void insert(iterator pos, const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}iterator end = _finish;while (pos < end){*end = *(end - 1);--end;}*pos = x;++_finish;}看起来没什么问题，但是存在着迭代器失效的风险
pos仍指向原来的空间！记录相对位置，修正一下pos即可
void insert(iterator pos, const T& x){if (_finish == _end_of_storage){size_t len = pos - _start;//记录相对位置reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish;while (pos < end){*end = *(end - 1);--end;}*pos = x;++_finish;}值得注意的是STL里的 insert有返回值！
这是为什么呢？还是防止迭代器失效的一种措施。
void test_vector2(){vector<int>v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);print_vector(v);/*v.insert(v.begin() + 1, 10);print_vector(v);*/int x;cin >> x;// x==2auto pos = find(v.begin(), v.end(), x);//没找到返回 last 左闭右开区间if (pos != v.end()){v.insert(pos, 40);//pos 可以理解为下标位置 也可以理解为原来位置数据前面插入一个数据print_vector(v);(*pos) *= 10;//期望将x乘以10 但是是插入的40*10 并没有指向原来的数据//归为迭代器失效一类}print_vector(v);}
如果这里还发生了扩容呢？？就是将push的5给删掉
这是什么鬼？我们不是已经修正了pos的位置吗？显然这里的p已经失效了！形参是无法改变实参的，我们修正了pos，但是影响不了p
传const 引用过去影响实参。但不是常量引用的话 ，下面代码会报错！
因为函数调用返回的参数是临时变量，且临时变量具有常性。
而事实上加了const引用里面的pos就无法修正了！我们的思路错了，STL的操作是加一个返回值 （返回的是新插入数据的下标）
iterator insert(iterator pos, const T& x){assert(pos <= _finish && pos >= _start);if (_finish == _end_of_storage){size_t len = pos - _start;//记录相对位置reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish;while (pos < end){*end = *(end - 1);--end;}*pos = x;++_finish;return pos;}
所以 insert后不能再访问find 的 p 想要访问得更新！
增删查改：
iterator insert(iterator pos, const T& x){assert(pos <= _finish && pos >= _start);if (_finish == _end_of_storage){size_t len = pos - _start;//记录相对位置reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish;while (pos < end){*end = *(end - 1);--end;}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos < _finish && pos >= _start);iterator it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;return pos;}size_t find(T val = T()){for (auto it = _start; it < _finish; it++){if (*it == val){return it - _start;}}return -1;}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i)const{assert(i < size());return _start[i];}void pop_back(){assert(!empty());--_finish;}1.6模拟中的注意事项
规定：类模板在没有实例化时，迭代器无法读取！编译器不能区分这里const_iterator是类型还是静态成员变量。要想解决：第一可以在前面加上typename用来证明这里是类型；第二用auto，让编译器判断为类型
内置类型是没有构造函数的概念，但为了兼容模板（T val = T( ) ），可以被视为具有默认构造函数的行为 void reseize(size_t n, T val = T())//内置类型具有的构造析构等函数行为，并没有对应概念{if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish < _start+n){*_finish++ = val;}}}
//类里面可以用类名替代类型（特殊化）//vector & operator=(vector v)vector<T>& operator= (vector<T> v){ swap(v); return *this;}//类模板的成员函数还可以继续是函数模板template<class InputIterator> //写成模板是为了兼容所有容器vector(InputIterator first, InputIterator last){while(first != last){push_back(*first);++first;}}2、vector模拟补充
2.1迭代器区间构造问题
//C++11 强制生成默认构造vector() = default;vector(size_t n, const T& val = T()){reserve(n);for (size_t i; i < n; i++){push_back(val);}}//类模板的成员函数还可以继续是函数模板template<class InputIterator> //写成模板是为了兼容所有容器vector(InputIterator first, InputIterator last){while(first != last){push_back(*first);++first;}}这个是对迭代器区间进行的构造函数，思路很简单，把迭代器区间的数据依次尾插就可以了（这里之所以另外使用一个新的模版，而不是使用vector类的模版，是为了兼容其他容器类型）。这样就可以通过一个现有的类型来构造容器。
但是出乎意料的是出现了一个问题： C2100 非法的间接寻址 （编译层面的问题） 。非法的间接寻址的造成原因有很多：
为什么报错在迭代器构造呢？因为编译器会寻找最合适的函数，但是这里与我们期望所违背！！
为了解决编译器选择的问题，可以多枚举几个构造函数：
vector(size_t n, const T& val = T()){reserve(n);for (size_t i=0; i < n; i++){push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (int i=0; i < n; i++){push_back(val);}}vector(long long n, const T&val = T()){reserve(n);for (long long i=0; i < n; i++){push_back(val);}}这样可以做到优先匹配vector(int n,T val = T());，我们的问题也就解决了。
2.2memcpy深浅拷贝问题
我们测试一下自定义类型的vector（这里以string为例）：
void vector_test6() {vector<string> v1;v1.push_back("11111");v1.push_back("22222");v1.push_back("33333");v1.push_back("44444"); //再次插入扩容v1.push_back("55555");print_vector(v1);}
程序崩溃了
分析：
<1> memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
<2> 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。
结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃
解决方法：
void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];//memcpy(tmp, _start, size()*sizeof(T));//浅拷贝for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];//自定义类型的话 也是会调用自定义类型的赋值重载}delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}}2.3动态二维数组的模拟及遍历
结构框架图：
//二维数组vector<int>v(3, 1);vector<vector<int>>vv(5, v);vv[2][1] = 2;//与上述等价 vv.operator[](2).operator[](1) = 2;for (size_t i = 0; i < vv.size(); i++){for (size_t j = 0; j < vv[i].size(); j++){cout << vv[i][j] << ' ';}cout << endl;}cout << endl;for (auto it = vv.begin(); it != vv.end(); it++){for (auto jt = (*it).begin(); jt != (*it).end(); jt++){cout << *jt << ' ';}cout << endl;}cout << endl;auto it1 = vv.begin();/*auto it2 = (*it1).begin();*/while (it1 != vv.end()){auto it2 = (*it1).begin();//更新it2 指针在堆上分配，所以可以看见内存不是连续分配的while (it2 != (*it1).end()){cout << *it2 << ' ';it2++;}cout << endl;it1++;}cout << endl;for (auto row : vv){for (auto column : row){cout << column << ' ';}cout << endl;}cout << endl;应用：杨辉三角
// 以杨慧三角的前n行为例：假设n为5void test2vector(size_t n){// 使用vector定义二维数组vv，vv中的每个元素都是vector<int>vector<vector<int>> vv(n);// 将二维数组每一行中的vecotr<int>中的元素全部设置为1for (size_t i = 0; i < n; ++i)vv[i].resize(i + 1, 1);// 给杨慧三角出第一列和对角线的所有元素赋值for (int i = 2; i < n; ++i){for (int j = 1; j < i; ++j){vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];}}}构造一个vv动态二维数组，vv中总共有n个元素，每个元素 都是vector类型的，每行没有包含任何元素，n为5时如下所示：
