一、前言本篇是 C 学习之路系列的第六期重点讲解 STL 中最重要的容器之一——vector。学习 STL 有三个境界能用、明理、能扩展。本篇文章将按照这个思路从 vector 的基本使用讲起逐步深入到迭代器失效问题、OJ 实战最后完成 vector 的深度剖析与模拟实现。二、vector 的介绍及使用2.1 vector 的介绍vector 是 C 标准模板库STL中一个非常重要的序列容器它底层是一段连续的内存空间支持随机访问可以动态扩容。vector 的详细文档可以参考官方文档。2.2 vector 的使用学习 vector 时一定要学会查看文档vector 在实际开发中非常重要。我们熟悉常见的接口即可下面列出需要重点掌握的接口。2.2.1 vector 的定义vector 的构造函数主要有以下几种构造函数声明接口说明vector()重点无参构造vector(size_type n, const value_type val value_type())构造并初始化 n 个 valvector(const vector x)重点拷贝构造vector(InputIterator first, InputIterator last)使用迭代器进行初始化构造vector 的构造代码演示#include iostream #include vector using namespace std; int main() { vectorint v1; // 无参构造 vectorint v2(10, 5); // 构造并初始化 10 个 5 vectorint v3(v2); // 拷贝构造 int arr[] {1, 2, 3, 4, 5}; vectorint v4(arr, arr 5); // 迭代器区间构造 return 0; }2.2.2 vector iterator 的使用迭代器的主要作用是让算法能够不用关心底层数据结构vector 的迭代器底层就是原生指针 T*。常用接口如下iterator 的使用接口说明begin end重点获取第一个数据位置的 iterator/const_iterator获取最后一个数据的下一个位置的 iterator/const_iteratorrbegin rend获取最后一个数据位置的 reverse_iterator获取第一个数据前一个位置的 reverse_iteratorvector 的迭代器使用代码演示#include iostream #include vector using namespace std; int main() { vectorint v{1, 2, 3, 4, 5}; // 正向迭代器遍历 vectorint::iterator it v.begin(); while (it ! v.end()) { cout *it ; it; } cout endl; // 反向迭代器遍历 vectorint::reverse_iterator rit v.rbegin(); while (rit ! v.rend()) { cout *rit ; rit; } cout endl; return 0; }2.2.3 vector 空间增长问题容量空间相关的接口如下容量空间接口说明size获取数据个数capacity获取容量大小empty判断是否为空resize重点改变 vector 的 sizereserve重点改变 vector 的 capacitycapacity 的代码在 VS 和 g 下分别运行会发现VS 下 capacity 是按 1.5 倍增长的g 是按 2 倍增长的。这个问题经常被考察不要固化地认为 vector 增容都是 2 倍具体增长多少是根据具体需求定义的。VS 是 PJ 版本 STLg 是 SGI 版本 STL。reserve 只负责开辟空间如果确定知道需要用多少空间reserve 可以缓解 vector 增容的代价缺陷问题。resize 在开空间的同时还会进行初始化影响 size。测试 vector 的默认扩容机制// 测试 vector 的默认扩容机制 void TestVectorExpand() { size_t sz; vectorint v; sz v.capacity(); cout making v grow:\n; for (int i 0; i 100; i) { v.push_back(i); if (sz ! v.capacity()) { sz v.capacity(); cout capacity changed: sz \n; } } }VS 运行结果1.5 倍扩容capacity changed: 1 capacity changed: 2 capacity changed: 3 capacity changed: 4 capacity changed: 6 capacity changed: 9 capacity changed: 13 capacity changed: 19 capacity changed: 28 capacity changed: 42 capacity changed: 63 capacity changed: 94 capacity changed: 141g 运行结果2 倍扩容capacity changed: 1 capacity changed: 2 capacity changed: 4 capacity changed: 8 capacity changed: 16 capacity changed: 32 capacity changed: 64 capacity changed: 128如果已经确定 vector 中要存储元素的大概个数可以提前将空间设置足够避免边插入边扩容导致效率低下的问题void TestVectorExpandOP() { vectorint v; size_t sz v.capacity(); v.reserve(100); // 提前将容量设置好可以避免一遍插入一遍扩容 cout making bar grow:\n; for (int i 0; i 100; i) { v.push_back(i); if (sz ! v.capacity()) { sz v.capacity(); cout capacity changed: sz \n; } } }2.2.4 vector 增删查改vector 增删查改相关的接口如下vector 增删查改接口说明push_back重点尾插pop_back重点尾删find查找注意这个是算法模块实现不是 vector 的成员接口insert在 position 之前插入 valerase删除 position 位置的数据swap交换两个 vector 的数据空间operator[]重点像数组一样访问vector 插入和删除操作代码演示#include iostream #include vector using namespace std; int main() { vectorint v{1, 2, 3, 4, 5}; v.push_back(6); // 尾插 v.pop_back(); // 尾删 v.insert(v.begin(), 0); // 在 begin 位置之前插入 0 v.erase(v.begin()); // 删除 begin 位置的数据 for (size_t i 0; i v.size(); i) cout v[i] ; cout endl; return 0; }2.3 vector 迭代器失效问题重点迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了封装比如 vector 的迭代器就是原生指针 T*。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃即如果继续使用已经失效的迭代器程序可能会崩溃。对于 vector 可能会导致其迭代器失效的操作有会引起其底层空间改变的操作都有可能是迭代器失效比如resize、reserve、insert、assign、push_back 等。指定位置元素的删除操作——erase。下面通过代码演示扩容导致的迭代器失效#include iostream using namespace std; #include vector int main() { vectorint v{1,2,3,4,5,6}; auto it v.begin(); // 将有效元素个数增加到100个多出的位置使用8填充操作期间底层会扩容 // v.resize(100, 8); // reserve的作用就是改变扩容大小但不改变有效元素个数操作期间可能会引起底层容量改变 // v.reserve(100); // 插入元素期间可能会引起扩容而导致原空间被释放 // v.insert(v.begin(), 0); // v.push_back(8); // 给vector重新赋值可能会引起底层容量改变 v.assign(100, 8); /* 出错原因以上操作都有可能会导致vector扩容也就是说vector底层原理旧空间被释放掉 而在打印时it还使用的是释放之间的旧空间在对it迭代器操作时实际操作的是一块已经被 释放的空间而引起代码运行时崩溃。 解决方式在以上操作完成之后如果想要继续通过迭代器操作vector中的元素只需给it重新赋值即可。 */ while(it ! v.end()) { cout *it ; it; } coutendl; return 0; }erase 删除 pos 位置元素后pos 位置之后的元素会往前搬移没有导致底层空间的改变理论上讲迭代器不应该会失效但是如果 pos 刚好是最后一个元素删完之后 pos 刚好是 end 的位置而 end 位置是没有元素的那么 pos 就失效了。因此删除 vector 中任意位置上元素时VS 就认为该位置迭代器失效了。以下代码的功能是删除 vector 中所有的偶数请问哪个代码是正确的为什么#include iostream using namespace std; #include vector int main() { vectorint v{ 1, 2, 3, 4 }; auto it v.begin(); while (it ! v.end()) { if (*it % 2 0) v.erase(it); it; } return 0; }上面这段代码是错误的。因为 erase 之后 it 已经失效再执行 it 会导致未定义行为甚至程序崩溃。正确的写法是使用 erase 的返回值重新给 it 赋值int main() { vectorint 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; }注意Linux 下g 编译器对迭代器失效的检测并不是非常严格处理也没有 VS 下极端。扩容之后迭代器已经失效了程序虽然可以运行但是运行结果已经不对了int main() { vectorint v{1,2,3,4,5}; for(size_t i 0; i v.size(); i) cout v[i] ; cout endl; auto it v.begin(); cout 扩容之前vector的容量为: v.capacity() endl; // 通过reserve将底层空间设置为100目的是为了让vector的迭代器失效 v.reserve(100); cout 扩容之后vector的容量为: v.capacity() endl; // 经过上述reserve之后it迭代器肯定会失效在vs下程序就直接崩溃了但是linux下不会 // 虽然可能运行但是输出的结果是不对的 while(it ! v.end()) { cout *it ; it; } cout endl; return 0; }程序输出1 2 3 4 5 扩容之前vector的容量为: 5 扩容之后vector的容量为: 100 0 2 3 4 5 409 1 2 3 4 5erase 删除任意位置代码后Linux 下迭代器并没有失效因为空间还是原来的空间后续元素往前搬移了it 的位置还是有效的#include vector #include algorithm int main() { vectorint v{1,2,3,4,5}; vectorint::iterator it find(v.begin(), v.end(), 3); v.erase(it); cout *it endl; while(it ! v.end()) { cout *it ; it; } cout endl; return 0; }程序可以正常运行并打印4 4 5从上述例子中可以看到SGI STL 中迭代器失效后代码并不一定会崩溃但是运行结果肯定不对如果 it 不在 begin 和 end 范围内肯定会崩溃的。erase 删除的迭代器如果是最后一个元素删除之后 it 已经超过 end此时迭代器是无效的it 导致程序崩溃int main() { vectorint v{1,2,3,4,5}; // vectorint v{1,2,3,4,5,6}; auto it v.begin(); while(it ! v.end()) { if(*it % 2 0) v.erase(it); it; } for(auto e : v) cout e ; cout endl; return 0; }使用第一组数据时程序可以运行1 3 5使用第二组数据时程序最终会崩溃Segmentation fault。与 vector 类似string 在插入 扩容操作 erase 之后迭代器也会失效#include string void TestString() { string s(hello); auto it s.begin(); // 放开之后代码会崩溃因为resize到20会string会进行扩容 // 扩容之后it指向之前旧空间已经被释放了该迭代器就失效了 // 后序打印时再访问it指向的空