本章博客是对vector的介绍，有需要借鉴即可。
vector详情链接：LINK
1.vector介绍
vector的嵌套定义
vector支持嵌套自定义类型使用，即一个vector里面每个元素也可以嵌套进另一个vector…当然也可以是其他类型
eg1:vector < string >
eg2:vector<vector>
具体来说，以示例2来举例，编译器先根据模板开辟出一个vector< int >，之后再根据这个vector< int >开一个vector<vector< int >>出来。
vector调用[][]与二维数组[][]的底层区别
在语法上，我们可以定义一个vector<vector< int >>和一个二维数组，如下：
#include<vector> vector<vector<int>> vv; int arr[5][10]; //调用： vv[i][j]; arr[i][j];
那这两个调用方式有什么区别呢？
- 在语法上看，形式是一致的
- 在底层实现上，是不一致的
- 二维数组是解引用指针来做到访问的
- vector则是连续调用两个[]重载函数来实现访问的
可以通过做下面题目来进行体会：
//参考题解： class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> ret; //开空间 ret.resize(numRows); for(size_t i = 0; i < numRows; i++) { ret[i].resize(i+1); } //给值 for(size_t i = 0; i < ret.size(); i++) { for(size_t j = 0; j <= i; j++) { if(j == 0 || j == i) { ret[i][j] = 1; } else { ret[i][j] = ret[i-1][j] + ret[i-1][j-1]; } } } return ret; } };
2.vector模拟
2.1vector模拟代码
从一些开源的vector源文件中可以了解到，vector是由迭代器进行维护的。所以下面整体的模拟实现逻辑是用到了三个简化的迭代器指针来对vector进行维护。
#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<assert.h> using namespace std; namespace bit { template<typename T> class vector { private: typedef T* iterator; typedef const T* const_iterator; iterator _start; iterator _finish; iterator _endofstorage; public: //构造函数 //无参 vector() :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) {} //拷贝构造 // v2(v1) vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { reserve(v.capacity()); for (auto& e : v) { push_back(e); } } //迭代器构造函数 template<typename InputIterator> vector(InputIterator first, InputIterator last)//会根据传进来的参数自动推导类型,至于为什么不用T，因为写T一定是得传与类对象一致的参数，但是这样另改一个参数可以传其他的参数 { while (first != last) { push_back(*first); first++; } } //用n个值初始化，构造函数 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); } } //C++11新语法 // vector<int> v1 = { 1,2,3,4,5,6,7,8,9,10 }; vector(initializer_list<T> il) { reserve(il.size()); for (auto& e : il) { push_back(e); } } //赋值运算符重载 // v1 = v3 void swap(vector<T>& v) { std::swap(this->_start, v._start); std::swap(this->_finish, v._finish); std::swap(this->_endofstorage, v._endofstorage); } vector<T>& operator=(vector<T> v) { swap(v); return *this; } //析构函数 ~vector() { delete[] _start; _start = _finish = _endofstorage = nullptr; } //迭代器 iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } bool empty() { return _finish == _start; } //size与capacity const size_t size() const { return _finish - _start; } const size_t capacity() const { return _endofstorage - _start; } //resize void resize(size_t n, const T& val = T())//内置类型有默认构造 { if (n > capacity()) { //扩容 reserve(n); //填入数据 while (_finish < _start + n) { *_finish = val; _finish++; } } else { //对其他视而不见 _finish = _start + n; } } //开空间 void reserve(size_t n) { if (n > capacity()) { size_t old_size = size(); //申请一块新空间 iterator temp = new T[n]; //把值原来的值拷贝过去 //memcpy(temp, _start, sizeof(T) * size());//深拷贝大坑，如果里面仍然是一个需要深拷贝的类型的话，那么这个地方就会指向同一块空间，到时候析构就直接崩溃。 for (size_t i = 0; i < old_size; i++) { temp[i] = _start[i];//这样就可以调用类对象的拷贝构造，而对应的类对象的拷贝构造是用深拷贝去做的。 } //销毁原来的空间 delete[] _start; //把新空间赋给类 _start = temp; _finish = temp + old_size;//但是注意，这个size已经不是我们需要的size了，所以要在之前处理一下 _endofstorage = temp + n; } } //尾插 void push_back(const T& val) { insert(_finish, val);//直接复用insert } //任意插入 void insert(iterator pos, const T& val) { //断言 assert(pos <= _finish && pos >= _start); //扩容 if (_finish == _endofstorage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : 2 * capacity()); // 如果扩容了要更新pos --> 迭代器失效！！！其实也可以在下面直接去更新pos指针 pos = _start + len; } //移动数据 iterator it = _finish - 1;//这个时候指向的是最后一个有效元素 while (it >= pos) { *(it + 1) = *it; --it; } //插入数据 *pos = val; //更新一下finish指针 _finish++; } //删除 //任意删除 iterator erase(iterator pos) { //断言 assert(pos < _finish && pos >= _start); //移动数据 iterator it = pos + 1; while (it < _finish) { *(it - 1) = *it; it++; } _finish--; return pos; } //尾删 void pop_back() { assert(!empty()); --_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); } }; } int main() { //bit::vector<int> v; /*v.insert(v.begin(), 5); v.insert(v.begin(), 4); v.insert(v.begin(), 3); v.insert(v.begin(), 2); v.insert(v.begin(), 1);*/ //bit::vector<int> v2; //v2 = v; //std::string str("123456"); /*bit::vector<int> v(10, 3);*/ /*bit::vector<int> v = { 1,2,3,4,5,6 }; for (size_t i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl;*/ bit::vector<string> vs; vs.push_back("hello"); vs.push_back("hello"); vs.push_back("hello"); vs.push_back("hello"); vs.push_back("hello"); vs.push_back("hello"); vs.push_back("hello"); for (size_t i = 0; i < vs.size(); i++) { cout << vs[i] << " "; } cout << endl; //8：外面的迭代器有可能会因为扩容的缘故而失效，每次使用前应该再次更新迭代器而不是直接进行使用之前使用过的。 //9：erase也有可能会因为迭代器问题失效而崩溃 return 0; }
2.2reserve扩容的细节
细节一：迭代器失效问题
错误代码示例：
//开空间 void reserve(size_t n) { if (n > capacity()) { //申请一块新空间 iterator temp = new T[n]; //把值原来的值拷贝过去 //memcpy(temp, _start, sizeof(T) * size());//深拷贝大坑，如果里面仍然是一个需要深拷贝的类型的话，那么这个地方就会指向同一块空间，到时候析构就直接崩溃。 for (size_t i = 0; i < old_size; i++) { temp[i] = _start[i];//这样就可以调用类对象的拷贝构造，而对应的类对象的拷贝构造是用深拷贝去做的。 } //销毁原来的空间 delete[] _start; //把新空间赋给类 _start = temp; _finish = temp + size();//但是注意，这个size已经不是我们需要的size了，所以要在之前处理一下 _endofstorage = temp + n; } }
问题：这个主要是_finish看着是更新了，但是并没有更新的缘故，因为_finish更新的结果是错误的，这个_finish是之前空间的地址，所以这个地方是个坑。
那该怎么处理呢？
改正：算相对位置，在释放完原空间之后再根据相对位置old_size来推算_finish的指向。
改正代码示例：
//开空间 void reserve(size_t n) { if (n > capacity()) { size_t old_size = size(); //申请一块新空间 iterator temp = new T[n]; //把值原来的值拷贝过去 //memcpy(temp, _start, sizeof(T) * size());//深拷贝大坑，如果里面仍然是一个需要深拷贝的类型的话，那么这个地方就会指向同一块空间，到时候析构就直接崩溃。 for (size_t i = 0; i < old_size; i++) { temp[i] = _start[i];//这样就可以调用类对象的拷贝构造，而对应的类对象的拷贝构造是用深拷贝去做的。 } //销毁原来的空间 delete[] _start; //把新空间赋给类 _start = temp; _finish = temp + old_size;//但是注意，这个size已经不是我们需要的size了，所以要在之前处理一下 _endofstorage = temp + n; } }
细节二：reserve的深层浅层拷贝问题
错误代码示例：
//开空间 void reserve(size_t n) { if (n > capacity()) { size_t old_size = size(); //申请一块新空间 iterator temp = new T[n]; //把值原来的值拷贝过去 memcpy(temp, _start, sizeof(T) * size());//深拷贝大坑，如果里面仍然是一个需要深拷贝的类型的话，那么这个地方就会指向同一块空间，到时候析构就直接崩溃。 //销毁原来的空间 delete[] _start; //把新空间赋给类 _start = temp; _finish = temp + old_size;//但是注意，这个size已经不是我们需要的size了，所以要在之前处理一下 _endofstorage = temp + n; } }
问题：这个问题主要是memcpy是进行按照字节进行浅层拷贝的一个库函数，如果拷贝的内容需要深层拷贝，用memcpy会直接崩溃，崩溃的原因在于两次析构同一块地址。
改正：出错的原因在于memcpy的浅拷贝问题，我们可以调用需要拷贝类的对应深层拷贝构造去处理。下面就是去调用对应的赋值函数，其赋值函数的实现逻辑是用深层拷贝实现的。
改正代码：
//开空间 void reserve(size_t n) { if (n > capacity()) { size_t old_size = size(); //申请一块新空间 iterator temp = new T[n]; //把值原来的值拷贝过去 //memcpy(temp, _start, sizeof(T) * size());//深拷贝大坑，如果里面仍然是一个需要深拷贝的类型的话，那么这个地方就会指向同一块空间，到时候析构就直接崩溃。 for (size_t i = 0; i < old_size; i++) { temp[i] = _start[i];//这样就可以调用类对象的拷贝构造，而对应的类对象的拷贝构造是用深拷贝去做的。 } //销毁原来的空间 delete[] _start; //把新空间赋给类 _start = temp; _finish = temp + old_size;//但是注意，这个size已经不是我们需要的size了，所以要在之前处理一下 _endofstorage = temp + n; } }
2.3insert函数细节
问题：这个insert有一个点值得注意，就是在扩容之后，他就会重新开空间进行拷贝嘛，但是insert中要记得及时更新pos指针，不然这个pos指针还是指向原位置。
错误代码示例：
改正：这个简单，扩容之后及时更新一下pos指针就行了。
改正代码示例：
2.4构造函数细节
上面实现的那一堆构造函数其实有个坑
问题：当存在一个构造模板和一个构造函数时候，可能会出现编译器调用不符合我们期望的问题。
比如：vector v1(10, 1);这个地方关键是因为vector v1(10, 1)函数模板和函数构造都可以匹配，只不过说模板更好一些而已
错误示例：
改正：参考库源码的实现，直接对第二个函数进行int重载就行了。
改正示例：下面第三个函数就是直接重载实现的。
//迭代器构造函数 template<typename InputIterator> vector(InputIterator first, InputIterator last)//会根据传进来的参数自动推导类型,至于为什么不用T，因为写T一定是得传与类对象一致的参数，但是这样另改一个参数可以传其他的参数 { while (first != last) { push_back(*first); first++; } } //用n个值初始化，构造函数 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); } }
\
思考：这个第一个构造函数为什么实现为模板的形式呢？
这个地方主要是为了兼容其他容器的迭代器。
比如：
string str("abcd"); vector<int> v3(str.begin(), str.end()); print_vector(v3);
2.5CPP11构造函数解释
从上面那一堆构造代码中，我们可以发现这样一个构造函数代码：
//C++11新语法 // vector<int> v1 = { 1,2,3,4,5,6,7,8,9,10 }; vector(initializer_list<T> il) { reserve(il.size()); for (auto& e : il) { push_back(e); } }
解释：这个主要是为了实现CPP11的一个新语法，这个语法可以实现花括号整体构造的效果，vector库中是新实现了一个类进行实现的，当然我模拟实现的这个也是直接调用的库中实现的一个类。
具体用法如下：
底层：实际底层上，这个玩意就是通过两个指针进行维护的，一个指向花括号的第一个元素，第二个指针指向最后一个元素，因为空间上是连续进行存储的，所以说可以用迭代器挨个遍历就行了。
2.6单参数的构造函数支持隐式类型转换
比如下面：
解释：
一般来说，我们如果push进vector一个字符串，需要大概两个动作，一是把“”字符串先构造出一个string对象，然后再将其拷贝构造到push_back函数中作为形参。
但是呢，这个时候因为单参数构造函数支持隐式类型转换的缘故，所以直接把“”字符串隐式转换为string，然后直接进行调用构造函数。
这个隐式类型转换大大方便了我们写代码，这里简单一提。
2.7迭代器失效问题
我们模拟实现的整个victor底层都是用三个迭代器进行维护的，一旦迭代器出问题，那就很可能会挂。
结论1：外面的迭代器有可能会因为扩容的缘故而失效，每次使用前应该再次更新迭代器而不是直接进行使用之前使用过的。
比如说：
解释：这里的失效原因就是扩容时候新开了一块空间，虽然里面的迭代器及时进行更新了，但是外面的迭代器it没有及时进行更新，还摁着旧空间进行访问，自然会出问题了。
结论2：erase也有可能会因为迭代器问题失效而崩溃
比如说下面有例子：让你删除偶数并且打印出来
通过上面例子可以发现，三组例子出现了三个不同的结果。
原因：这个问题本质上就是迭代器失效问题。
怎么办改正呢？
改正：库函数给出了答案。每次删除元素之后返回最新的迭代器即可。
所以然后我们可以修改一下我们的模拟erase()的代码：
iterator erase(iterator pos) { //断言 assert(pos < _finish && pos >= _start); //移动数据 iterator it = pos + 1; while (it < _finish) { *(it - 1) = *it; it++; } _finish--; return pos; }
下次调用完erase之后更新一下调用的迭代器指针就行了哈。
3.总结
其实有一定基础的话写得出victor的简化模拟还可以凑合一下的，不过其中的一些细节需要把握一下。
EOF
