一、vector的介绍及使用
1、vector的介绍
https://cplusplus.com/reference/vector/vector/
- vector 是表示可变大小数组的序列容器。
- 就像数组一样，vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对 vector 的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
- 本质讲，vector 使用动态分配数组来存储它的元素。当新元素插入的时候，这个数组需要被重新分配大小，为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector 并不会每次都重新分配大小。
- vector 分配空间策略：vector 会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
- 因此，vector 占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
- 与其它动态序列容器相比（deque, list and forward_list），vector 在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起 list 和 forward_list 统一的迭代器和引用更好。
2、vector的使用
（1）vector的定义
https://cplusplus.com/reference/vector/vector/vector/
- default(1)
这里给的是一个缺省值，目前只要看到 alloc 就可以直接忽略它，它是 STL 六大组件中的空间配置器。
- fill(2)
value_type 是第一个模板参数，它是一个 ‘\0’ 。
- range(3)
这里的迭代器还是一个函数模板，也就是说这里的迭代器不一定是 vector 的迭代器。
// vector的构造 int TestV1() { // constructors used in the same order as described above: vector<int> first; // empty vector of ints vector<int> second(4, 100); // 4 ints with value 100 vector<int> third(second.begin(), second.end()); // iterating through second vector<int> fourth(third); // a copy of third // 迭代器构造函数也可以使用数组来进行构造，传的区间是左闭右开 // 因为指向数组空间的指针是天然的迭代器 int myints[] = {16, 2, 77, 29}; vector<int> fifth (arr, arr + 4 ); //vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int)); cout << "The contents of fifth are:"; for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it) { cout << ' ' << *it; } cout << '\n'; return 0; }
（2）vector iterator 的使用
// vector的迭代器 void PrintVecotr(const vector<int>& v) { // const对象使用const迭代器进行遍历打印 vector<int>::const_iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; } void TestV2() { // 使用push_back插入4个数据 vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); // 使用迭代器进行遍历打印 vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; // 使用迭代器进行修改 it = v.begin(); while (it != v.end()) { *it *= 2; ++it; } // 使用反向迭代器进行遍历再打印 // vector<int>::reverse_iterator rit = v.rbegin(); auto rit = v.rbegin(); while (rit != v.rend()) { cout << *rit << " "; ++rit; } cout << endl; PrintVector(v); }
（3） vector 空间增长问题
cplusplus.com/reference/vector/vector/reserve/
cplusplus.com/reference/vector/vector/resize/
- reserve 只负责开辟空间，如果确定知道需要用多少空间，reserve 可以缓解 vector 增容的代价缺陷问题。
- resize 在开空间的同时还会进行初始化，影响 size 。
void test() { vector<int> v; v.reserve(10); // 有效元素个数size=0，只是开了空间capacity=10 /* error for (size_t i = 0; i < 10; i++) { v[i] = i; // 违规访问 } */ // 正确做法 for (size_t i = 0; i < 10; i++) { v.push_back(i); } }
如果不断往 vector 中尾插数据，容器会随着数据的增多而发生扩容，通过验证发现：VS 下 capacity 是按 1.5 倍增长的，G++ 是按 2 倍增长的。这个问题经常会考察，不要固化的认为，vector 增容都是 2 倍，具体增长多少是根据具体的需求定义的。VS 是 PJ 版本 STL，G++ 是 SGI 版本 STL。
// vector的resize和reserve // reisze(size_t n, const T& data = T()) // 将有效元素个数设置为n个，如果时增多时，增多的元素使用data进行填充 // 注意：resize在增多元素个数时可能会扩容 void TestV3() { vector<int> v; // set some initial content: for (int i = 1; i < 10; i++) v.push_back(i); v.resize(5); v.resize(8, 100); v.resize(12); cout << "v contains:"; for (size_t i = 0; i < v.size(); i++) cout << ' ' << v[i]; cout << '\n'; }
// 测试vector的默认扩容机制 // VS：按照1.5倍方式扩容 // Linux：按照2倍方式扩容 void TestVectorExpand() { size_t sz; vector<int> 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'; } } }
VS2019：
g++运行结果：linux下使用的STL基本是按照2倍方式扩容 making foo grow: capacity changed: 1 capacity changed: 2 capacity changed: 4 capacity changed: 8 capacity changed: 16 capacity changed: 32 capacity changed: 64 capacity changed: 128
（4）vector 增删查改
迭代器 的主要作用：让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector 的迭代器就是原生态指针 T* 。
因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃（即如果继续使用已经失效的迭代器，程序可能会崩溃）。
⚪对于 vector 可能会导致其迭代器失效的操作有：
a. 会引起其底层空间改变的操作，都有可能是迭代器失效。
比如：resize、reserve、insert、assign、push_back 等。
两种导致迭代器失效的操作：
// 指定位置之前插入元素操作–insert void TestV4() { // 迭代器失效问题 -- 类似野指针问题 vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); vector<int>::iterator pos = find(v.begin(), v.end(), 2); if (pos != v.end()) { v.insert(pos, 20); // 在pos之前插入20 /* * 如果想要继续通过迭代器操作vector中的元素，需要给pos重新赋值 * 即 pos = v.insert(pos, 20); // 函数返回指向新插入元素的迭代器 */ } // 在insert之后，pos迭代器位置就失效了，不能再去访问了--insert时增容导致的 //cout << *pos << endl; //*pos = 200; }
运行结果：
- VS2019 下验证，程序崩溃。
- Linux 下验证，虽然没有崩溃（和具体实现、增容机制以及检查机制有关），但也认为失效了。
void TestV5() { // 迭代器失效问题 -- 类似野指针问题 vector<int> v; v.reserve(5); // 提前开好空间，防止后续插入元素时发生扩容 v.push_back(1); v.push_back(2); v.push_back(3); vector<int>::iterator pos = find(v.begin(), v.end(), 2); // 在2之前插入20,如果没有则不插入 if (pos != v.end()) { v.insert(pos, 20); // 在pos之前插入20 /* * 如果想要继续通过迭代器操作vector中的元素，需要给pos重新赋值 * 即 pos = v.insert(pos, 20); // 函数返回指向新插入元素的迭代器 */ } // 在insert时空间足够，没有增容，但我们依旧认为pos迭代器位置失效了，不能再去访问了 // 这里的失效是指pos位置的意义变了，pos不再指向原来的值 //cout << *pos << endl; //*pos = 200; }
运行结果：
- VS2019 下验证，程序崩溃（VS 会进行检查）。
- Linux 下验证，虽然没有崩溃（和具体实现、检查机制有关），但也认为失效了。
【总结】
指定位置之前插入元素操作（insert）导致迭代器失效的两种场景：
- insert 插入元素时增容，pos 还指向已被释放的空间（非法空间），所以 pos 位置迭代器失效。
- insert 插入元素时没有增容，但 pos 位置意义变了，不再指向原来的值，所以 pos 位置迭代器失效。
vector 插入元素过程中可能会发生扩容，挪动数据，因此当前迭代器和后面所有元素的迭代器都失效。失效后，我们都不要去访问 pos 位置，否则可能出现各种意外情况。
b. 指定位置元素的删除操作 -- erase
// 任意位置插入：insert和erase，以及查找find void TestV6() { // 使用列表方式初始化，C++11新语法 vector<int> v{ 1, 2, 3 }; vector<int>::iterator pos = find(v.begin(), v.end(), 2); if (pos != v.end()) { v.erase(pos); // 删除pos位置的数据 /* * 如果想要继续通过迭代器操作vector中的元素，需要给pos重新赋值 * 即 pos = v.erase(pos); // 返回指向被删除元素下一个w的迭代器 */ } // 在erase之后，pos迭代器位置就失效了，不能再去访问了 // 这里的失效是指pos位置的意义变了，pos不再指向原来的值 //cout << *pos << endl; //*pos = 200; }
运行结果：
- VS2019 下验证，程序崩溃（VS 会进行检查）。
- Linux 下验证，虽然没有崩溃（和具体实现、检查机制有关），但也认为失效了。
分析：
对于 erase，我们在 erase 后也可能会失效，失效的原因有两种：
- insert 会扩容，那么 erase 也会缩容（比如有 200 个容量的空间、200 个有效数据，在删除后，只剩下 70 个有效数据，然后想把容量给缩容至一半【开 100 个容量的空间，把旧空间内容拷贝后释放，pos 就是野指针了】)
- erase 删除 pos 位置元素后，pos 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但 pos 位置的意义变了；如果 pos 刚好是最后一个元素，删完之后 pos 刚好是 end 的位置，而 end 位置是没有元素的，那么 pos 也是失效了。
这两种方式有是有可能的，STL 并没有对它们进行规定，但是不管缩容与否，都认为它们失效了，因为意义已经变了。并且在 VS 下做了非常严格的检查（pos 仅仅是意义改变了，并没有野指针，都不能进行访问），而在 G++ 下没有问题。
注意：find 不是 vector 自身提供的方法，是 STL 提供的算法，如果要查找只能使用STL提供的全局find。若找到，返回指向该元素的迭代器，若没有找到，返回 last （开区间）。
// 传迭代器区间 [first, last) 和要查找的元素 template <class InputIterator, class T> InputIterator find (InputIterator first, InputIterator last, const T& val); { while (first!=last) { if (*first==val) return first; ++first; } return last; }
【总结】
vector 插入或删除元素会导致当前迭代器和后面所有元素的迭代器失效。
迭代器失效解决办法：在使用前，对迭代器重新赋值即可。
如果想要继续通过迭代器操作 vector 中的元素，需要给 pos 重新赋值
【补充】
operator[] + index 和 C++11 中 vector 的新式 for+auto 的遍历。
vector 使用这两种遍历方式是比较便捷的。
void TestV7() { vector<int> v{1, 2, 3, 4}; v[0] = 10; // 通过[]读写第0个位置 cout << v[0] << endl; // 1、使用for+[]下标方式遍历 for (size_t i = 0; i < v.size(); ++i) { cout << v[i] << " "; } cout << endl; vector<int> swapv; swapv.swap(v); // 使用swap函数将原先的vector v与一个新的空vector swapv进行交换 cout << "v data:"; // 在输出v的数据时，可以看到原先的v已经变为空，不再包含任何元素 for (size_t i = 0; i < v.size(); ++i) { cout << v[i] << " "; } cout << endl; // 2、使用迭代器遍历 cout << "swapv data:"; auto it = swapv.begin(); while (it != swapv.end()) { cout << *it << " "; ++it; } // 3、使用范围for遍历 for (auto x : v) { cout << x << " "; } cout << endl; }
operator[] 和 at 的区别是什么？
它们之间的主要区别在于对边界检查的处理方式：
- operator[] 使用下标访问运算符 [] 可以直接通过索引来获取元素，不进行边界检查。如果使用下标访问一个越界的索引，会导致未定义行为。这种方式比较高效，适用于已经进行了边界检查或者明确知道索引是有效的情况。
- at() 函数也用于通过索引来获取元素，但它会进行边界检查。如果传入的索引超过了有效的范围，at() 函数会抛出 std::out_of_range 异常。这种方式更安全，建议在需要进行边界检查或者对索引的有效性不确定时使用。
【总结】
operator[] 执行更快但不进行边界检查，而 at() 相对安全但速度稍慢，因为它会进行边界检查并抛出异常。
对于失效，有对应的机制来处理：比如 insert 是有一个返回值的，它返回一个迭代器指向新插入的那个元素，也就是说你想去访问那个指向的新插入的元素就可以 pos 接收 insert 的返回值。同理， erase 也是相同的，它返回被删除数据的下一个数据的位置。
【C++】Vector -- 详解（下）https://developer.aliyun.com/article/1514679?spm=a2c6h.13148508.setting.26.4b904f0ejdbHoA
