【C++】C++ STL探索:Vector使用与背后底层逻辑（一）https://developer.aliyun.com/article/1617341
2.10 resize(重点常用)
//重点实现resize void resize(size_t n, const T& val = T()) { //缩容 if (n <= size()) { //类似截断 _finish = _start + n; } else { //提前扩容 //大于capacity才起作用 reserve(n); while (_finish < _start + n) { *_finish = val; _finish++; } } }
具体说明:虽然没有reserve这么多坑，但是有几个知识点值得我们注意。
2.10.1 const T& val = T()解释
- 对于T可能是内置类型或自定义类型，对于自定义类型不能通过简单常量作为缺省值，所以选择了T()调用构造函数作为缺省值最合适。
- 对于内置类型不是说没有构造函数这一说法吗？好的，内置类型被迫升级下。内置类型也有了自己的构造函数和析构函数(平常一般不使用)，int就是0（char也是整型 ASCII码）、double就是0.0、指针就是空指针。
- 因为缺省值怎么给都不合理，只能用自身的构造(匿名对象实例化)
2.11 单或多参数构造支持隐式类型转化
string str="1111";//构造+拷贝构造-->优化 直接构造 const string& str1="1111";//构造临时对象，引用的是临时对象 vector<string>v; v.push_back(str); v.push_back(string("2222")); v.push_back("33333");
隐式类型+优化的情况:
vector<int> v1={1,2,3,4,5}; vector<int> v2({1,2,3,4,5}) //直接构造
2.12 insert
2.12.1 insert使用
void insert(iterator pos, const T& val) { assert(_start <= pos); assert(pos <= _finish); //考虑是否需要扩容 //说明空间已经满了 if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } //开始移动数据 iterator it = _finish - 1; while (it >= pos) { *(it + 1) = *it; it--; } *pos = val; _finish++; }
具体说明：使用迭代器去模拟实现insert比起string模拟实现，在 while (it >= pos)没有pos为0的坑。涉及到开辟或销毁空间时，都有可能涉及到迭代器失效，对此都需要考虑到位。
2.13 扩容前迭代器失效
void test_vector() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); v1.push_back(6); v1.push_back(7); v1.push_back(8); print_vector(v1); vector<int>::iterator it = v1.begin() + 3; v1.insert(it, 40); print_vector(v1); cout << *it << endl; }
问题:在进行insert操作后，迭代器it就会失效。
思考:在扩容接口中，不是解决迭代器失效的问题了吗？
具体说明：
在调用insert接口是it传参pos位置，而形参是实参的一份临时拷贝，那么需要传引用解决。一波未平一波又起，如果传引用
v2.insert(v2.begin(),11.11)，这里v2.begin()返回的是临时变量，不能通过引用来接收。没有给出解决办法，调用insert接口出现扩容操作，迭代器会失效，不要去使用
2.14 erase
2.14.1 erase使用
//迭代器实现erase iterator erase(iterator pos) { assert(_start <= pos); //删除不到_finish这个位置 assert(pos < _finish); iterator it = pos+1; //it=pos+1=_finish就是最后一个位置 while (it <= _finish) { *(it - 1) = *(it); it++; } _finish--; return pos; }
2.14.2 验证迭代器失效
接下来我将给出三个场景:都是关于删除偶数
第一个场景:没啥问题
vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); vector<int>::iterator it = v1.begin(); while (it != v1.end()) { if (*it % 2 == 0) { v1.erase(it); } ++it; }
第二个场景:少删除
vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(4); v1.push_back(5); vector<int>::iterator it = v1.begin(); while (it != v1.end()) { if (*it % 2 == 0) { v1.erase(it); } ++it; }
第三个场景:迭代器失效
vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); v1.push_back(4);
关于上面出现的问题分析:
- 在erase的逻辑是通移动数据覆盖不需要的数据，达到删除的效果。逻辑上会跳过一个值，移动++可能会导致错过了一些值。
- 如果it++操作跳过end()，it就会一路向北，错过了判断条件
解决措施:
vector<int>::iterator it = v1.begin(); while (it != v1.end()) { if (*it % 2 == 0) { v1.erase(it); } else { it++; } } print_vector(v1);
2.14.3缩容导致迭代器失效
上面解决措施在Linux下还可以，但是在Vs下就不行了。由于因为Vs下的iterator没有使用原生指针实现，是自定义类型的迭代器，内部会进行强制类型检查。
对于erase不同编译器迭代器是不同的，erase也可能会缩容。erase迭代器的解决方案有两个：迭代器失效以后不要直接使用，如果要使用按照规则重新更新后使用。
vector<int>::iterator it = v1.begin(); while (it != v1.end()) { if (*it % 2 == 0) { it=v1.erase(it); } else { it++; } }
这样子就可以适应不同的版本，缩容以后。迭代器还是但会删除原生的下一个迭代器。
2.15 push_back
void push_back(const T& val ) { insert(end(), val); }
2.16 pop_back
void pop_back() { /*assert(!empty()); --_finish;*/ erase(end()-1); }
2.17 pop_back
void pop_back() { /*assert(!empty()); --_finish;*/ erase(end()-1); }
2.18 empty 判断空
bool empty() { return _start == _finish; }
2.19 print_vector 打印数据
为了实现适用于不同类型的打印，这里需要涉及一个函数模板
void print_vector(const vector<T>& v) { //下标加[] for (size_t i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; //迭代器 vector<T>::const_iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; //范围for for (auto e : v) { cout << e << " "; } cout << endl;、 }
不足之处：在三种遍历方式，使用迭代器遍历会出现报错。
问题在于: vector,这里类模板没有实例化，对于内嵌类型，那么不敢进去取，里面的东西也有没有实例化。编译器无法识别const_iterator是静态变量还是内中类,选择报错。
vector类模板没有完成实例化，对于内嵌类型const_iterator不敢进去取，对于内部是否实例。编译器无法编译器无法识别const_iterator是静态变量还是内中类。编译器选择报错。
解决措施:编译器规定typename告诉后面后面是一个类型，不是静态成员变量(先通过编译，之后再给你实例化)。在编译阶段才知道类型，如果需要一个类型接收，可以使用auto自动识别类型。
typename vector<T>::const_iterator it = v.begin(); auto it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl;
【C++】C++ STL探索:Vector使用与背后底层逻辑（三）https://developer.aliyun.com/article/1617343
