🍒1，vector的介绍
- vector是表示可变大小数组的序列容器。
- 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
- 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。
🍒2，vector的使用
vector学习时一定要学会查看文档：vector的文档介绍vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。
注意：使用vector要包含 < vector >
🐯2.1 vector的构造
我们先介绍使用两个重点的构造使用，其余两个在下一篇模拟实现的文章中会涉及。
代码演示：
void TestVector1() { //无参构造 vector<int> v1; //构造并用4个100初始化 vector<int> v2(4, 100); //拷贝构造 vector<int> v4(v3); //用迭代区间初始化 vector<int> v3(second.begin(),second.end()); }
🦁2.2 vector iterator 的使用
代码演示：
void TestVector2() { // 使用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); }
🌽2.3 vector 空间增长问题
代码演示1：
reisze(size_t n, const T& data = T())
将有效元素个数设置为n个，如果时增多时，增多的元素使用data进行填充。
注意：resize在增多元素个数时可能会扩容
void TestVector3() { vector<int> v; //插入一些数据 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'; }
代码演示2：
往vecotr中插入元素时，如果大概已经知道要存放多少个元素，可以通过reserve方法提前将容量设置好，避免边插入边扩容效率低。
void TestVectorExpandOP() { vector<int> 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'; } } }
注意：
- capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。
这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。- reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
- resize在开空间的同时还会进行初始化，影响size。
🍓2.4 vector 增删查改
注意：insert和erase会涉及迭代器失效问题，这个问题比较复杂，将在vector的模拟实现里介绍。
代码演示1：
// 尾插和尾删：push_back/pop_back void TestVector4() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); auto it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; v.pop_back(); v.pop_back(); it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; }
代码演示2：
注意find不是vector自身提供的方法，是STL提供的算法。
// 任意位置插入：insert和erase，以及查找find void test_vector4() { vector<int> v1; v1.push_back(1); v1.push_back(25); v1.push_back(12); for (auto e : v1) { cout << e << " "; } cout << endl; v1.insert(v1.begin(), 0);//头插 for (auto e : v1) { cout << e << " "; } cout << endl; v1.erase(v1.begin());//头删 for (auto e : v1) { cout << e << " "; } cout << endl; v1.insert(v1.begin() + 2, 50);//在中间位置插 for (auto e : v1) { cout << e << " "; } cout << endl; int x; cin >> x; //没有x就不插入，有x在它前面插入 //find是算法里的函数 vector<int>::iterator pos = find(v1.begin(), v1.end(), x); if (pos != v1.end()) { v1.insert(pos, 1000); } for (auto e : v1) { cout << e << " "; } cout << endl; }
🐯2.5 vector 访问及遍历
// operator[]+index 和 C++11中vector的新式for+auto的遍历 // vector使用这两种遍历方式是比较便捷的。 void TestVector6() { vector<int> v{ 1, 2, 3, 4 }; // 通过[]读写第0个位置。 v[0] = 10; cout << v[0] << endl; // 1. 使用for+[]方式遍历 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; }
🦊2.6 vector实例化string类的初始化形式
注意：
(1) 有名对象和匿名对象的使用形式的区别。
(2) 此时范围for的使用，最好加上const 和 &。
因为范围for的底层其实是迭代器，* it 赋值给e，而这里的*it是string类，每次赋值都是深拷贝，所以加引用可以避免多余的拷贝构造，const是因为不修改。
void TestVector7() { vector<string> v1;//此时v1指向的就是对象数组 //有名对象 string s1("张三"); v1.push_back(s1); //匿名对象 v1.push_back(string("李四")); //直接单参数隐式类型转换 v1.push_back("王五"); //对名字进行修改 v1[1] += "你好"; //加const & //范围for的底层其实是*it赋值给e //而这里的*it是string类，每次赋值都是深拷贝 for (const auto& e : v1) { cout << e << " "; } cout << endl; }
🌴2.7 sort算法的使用
sort不在vector中，在STL的算法库中，其底层是快速排序。
(1) sort算法默认排升序，它的参数需要传迭代器。
(2) 那如何控制升降序呢？根据sort的第二个重载，多了一个仿函数的参数。就是下面代码中的greater(降序)，less(升序)。其实这两个也是模板，再用这个模板进行实例化对象。并且又重载了operator() 运算符。
void TestVector8() { //sort算法的使用 vector<int> v1; v1.push_back(1); v1.push_back(25); v1.push_back(12); v1.push_back(9); v1.push_back(0); v1.push_back(40); //默认排升序 greater<int> gt1;//降序 > less<int> gt2;//升序 < //重载了operator() cout << gt1(3, 4) << endl;//0 cout << gt1.operator()(3, 4) << endl; //全部排序 //有名对象使用 //sort(v1.begin(), v1.end(),gt1); //匿名对象使用 sort(v1.begin(), v1.end(), greater<int>()); //去头去尾排 //sort(v1.begin() + 1, v1.end() - 1); //对前一半排序 //sort(v1.begin(), v1.begin() + v1.size() / 2); for (auto e : v1) { cout << e << " "; } cout << endl; }
🚀3，动态二维数组的理解
我们以杨辉三角这个题目为例：
代码实现如下：
class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> vv; vv.resize(numRows);//开出了numRows个vector类的空间 for(size_t i = 0;i < numRows ;i++ ) { vv[i].resize(i + 1, 0);//再开辟vector类里面的空间，初始化为0 //把每一行的第一个和最后一个初始化为1 vv[i][0] = vv[i][vv[i].size() - 1] = 1; } return vv; } };
我们需要理解一下函数的返回值 vector<vector< int >>，我们用它定义对象时 vector<vector< int >> vv(n);其实实例化出了两个类，第一个类把T实例化成了vector< int >，第二个类把T实例化成 int 。如下图，构造一个vv动态二维数组，vv中总共有n个元素，每个元素都是vector类型的，每行没有包含任何元素。
