STL vector
I.vector 的介绍及使用
0x00 vector 介绍
🔍 vector 文档介绍：vector - C++ Reference
1.vector是表示可变大小数组的序列容器，我们说vector像是数组，但又不像数组
为啥像数组：vector就像是数组一样，它也是采用连续存储空间来存储元素的，这也就意味着我们可以用下标访问vector元素，和数组一样高效。
为啥不像数组：vector的大小是可以动态改变的，而且它的大小会被容器自动处理
2.本质上来说，vector使用动态分配数组来存储它的元素。
当新元素插入时，为了增加存储空间，这个数组就需要被重新分配大小。具体做法是分配一个新的数组，然后将全部的元素转移到这个新的数组。就时间成本而言，vector的消耗过高，我们通常不会考虑每次插入新的元素就要重新分配一次数组空间。
3.vector空间分配策略：所以为了简化我们的操作，vector在动态分配上往往会分配额外的存储空间以适应可能的增长，因此容器的实际容量可能会大于严格容纳其元素所需的存储空间（即其大小)。
4.与其他动态序列容器（双端队列、列表和前向列表）相比，向量在访问其元素方面非常高效（与数组一样），并且在从其末尾添加或删除元素方面相对高效。对于涉及在非末尾位置插入或删除元素的操作，向量的性能比其他容器差，并且与列表和前向列表相比，其迭代器和引用的一致性较差。
0x01 初始化vector![]()
1.无参构造
vector<int> v1; // 无参构造，创建一个int类型的，空的vector对象2.构造并初始化：用 n 个 value 初始化：
vector<int> v2(10, 3); // 10个33.迭代器区间初始化：begin 👉 end
vector<int> v3(v2.begin(), v2.end());4.拷贝构造
vector<int> v4(v2);但是不乏有这种情况，我不要拷贝对象的头尾数据呢？即，不要它的 begin 和 end
vector<int> v3(++v2.begin(), --v2.end());综合
vector<int> arr1; //一个空数组 vector<int> arr2 {1, 2, 3, 4, 5}; //包含1、2、3、4、5五个变量 vector<int> arr3(4); //开辟4个空间，值默认为0 vector<int> arr4(5, 3); //5个值为3的数组 vector<int> arr5(arr4); //将arr4的所有值复制进去，和arr4一样 vector<int> arr6(arr4.begin(), arr4.end()); //将arr4的值从头开始到尾复制 vector<int> arr7(arr4.rbegin(), arr4.rend()); //将arr4的值从尾到头复制---------------------------------------------------------------------------------------------------------------------------------
对于迭代器区间初始化，它这里的 InputInerator 不一定是 vector Inerator。
它是一个模板，所以你传的是谁的迭代器，它就可以实例化出谁的迭代器
0x02 关于 vector 的析构、拷贝构造和赋值构造
至于析构函数，一般情况下我们不需要管，因为它会自动调用。
拷贝构造和赋值构造，vector 的拷贝构造和赋值其实就是深拷贝。
这些我们放在 vector 模拟实现的章节里详细探讨。
II.vector的遍历
0x00 push_back![]()
vector 不能用爽到飞起地 operator+=
string 能用 += 主要是 string 不仅可以尾插一个字符还可以追加一个字符串。
但是 vector 就只支持一个一个数据的插入和删除，push_back 和 pop_back。
vector.push_back(内容);0x01 下标+方括号遍历
vector 是连续的空间，又支持 operator[] 和 size() ，所以可以用下标+方括号遍历。
void vector_Traversal_test() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); // 遍历 for (size_t i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; }结果如下
当然也支持修改
void vector_Traversal_test() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); // 遍历 for (size_t i = 0; i < v.size(); i++) { v[i] += 1; // 令每个元素+1 cout << v[i] << " "; } cout << endl; }结果如下
0x02 访问vector（）的at（）
顺便再讲一下 at() ，它和 operator[] 一样，也是用来访问 vector 的，但是 at() 会进行边界检查
void test_vector4() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); cout << v.at(0) << endl; cout << v.at(3) << endl; }结果如下
需要注意的是！！！ operator会用断言assert检查是否越界，而at（）会抛出异常
void test_vector4() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); cout << v.at(5) << endl; // 故意越界看看 }结果如下
0x03 迭代器遍历vector
//迭代器：vector<int>::iterator for (vector<int>::iterator it = arr.begin(); it != arr.end(); it++) { cout << *it << endl; } //迭代器：vector<int>::reverse_iterator for (vector<int>::reverse_iterator it = arr.rbegin(); it != arr.rend(); it++) { cout << *it << endl; }0x04 范围for
vector支持迭代器，也就支持范围 for，这个我们在模拟实现 string 的时候已经验证过了。
范围 for 的本质就是编译器在编译时自动替换成迭代器，这里也一样。
void vector_Traversal_test() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); // 范围for for (auto e : v) { cout << e << " "; } cout << endl; for (auto& e : v) { e += 10; cout << e << " "; } cout << endl; }结果如下
Ⅲ. vector 空间
0x00 获取数据个数的 size()
和string里的一样，用来获取数据的元素个数
void test_vector2() { vector<int> v(6, 6); // 生成6个6 cout << v.size() << endl; }0x01 改变 vector 容量的 reserve()
void test_vector3() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.reserve(100); }结果如下
reserve 会扩容，但是不会影响数据个数。[capacity] 4 → [capacity]100
0x02 改变 vector 大小的 resize()
void test_vector4() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.resize(100); }string 的 resize 如果不指定 "填充值" ，默认给的是 \0
而 vector 的 resize 如果不指定，默认给的是其对应类型的缺省值作为 "填充值"
这里是 int 就是 0，如果是指针，对应的缺省值就是空指针。
注意注意！！！如果开的数据比之前小，还会删除数据
void test_vector4() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.resize(2); }结果如下
Ⅳ. vector 增删查改
0x00 pop_back（）尾删
void test_vector5() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); for (auto e : v) cout << e << " "; cout << endl; v.pop_back(); // 尾删：3 for (auto e : v) cout << e << " "; cout << endl; v.pop_back(); // 尾删：2 for (auto e : v) cout << e << " "; cout << endl; }结果如下
0x01 assign() 赋值
assign 可以把 vector 的内容覆盖掉。允许给一段区间覆盖，也可以给个value去覆盖。
void test_vector6() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.assign(10, 5); // 原来是1到4，现在改成10个5 }结果如下
0x02探讨：为什么vector不提供find接口
string、map、set 都有 find() 用，凭什么 vector 和 list 没有
其实，我们应该考虑的是 —— 为什么 string、map、set 能有 find 操作。
而 vector 之所以不提供 find ，是因为如果去查找元素效率就会是……
但其实我们也可以用，算法库algorithm里就有同样的find操作。
该find内部是从begin到end进行一次遍历，复杂度为O（n）
值得一提的是，在C++中，凡是使用迭代器区间，都是左闭右开的——（first，last].
再去思考 map、set 为什么有 find() 通过迭代器从头到尾遍历 map 与 set 时，
得到的结果是按 key 排序的结果，而不是插入时的顺序，所以这两个容器没有 push_back 操作。
其实，插入到 map 与 set 中的元素会被组织到一颗红黑树上，红黑树是一颗平衡二叉树，
平衡二叉树是一颗二叉排序树，对一颗二叉排序树的查找有点像二分查找，复杂度是 ，
由于 map 与 set 的数据结构能有更快的查找方法，所以在容器内提供了 find 方法。
0x03 insert () 插入
void test_vector7() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::iterator ret = find(v.begin(), v.end(), 3); if (ret != v.end()) { cout << "找到了" << endl; v.insert(ret, 30); // 在ret位置前面插入一个30 } for (auto e : v) cout << e << " "; cout << endl; }结果如下
用insert去头插：
void test_vector8() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); for (auto e : v) cout << e << " "; cout << endl; v.insert(v.begin(), -1); // 在起始位置插入一个-1 for (auto e : v) cout << e << " "; cout << endl; }结果如下
0x04 erase（）删除
使用erase（）的时候需要判断一下有没有要删除的元素：
void test_vector9() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); for (auto e : v) cout << e << " "; cout << endl; vector<int>::iterator pos = find(v.begin(), v.end(), 5); if (pos != v.end()) { // 判断pos是否存在 v.erase(pos); // 删除pos } for (auto e : v) cout << e << " "; cout << endl; }结果如下
怕的就是要删的目标不存在！比如我要删个 5，但是 vector 里只有 1，2，3，4 。
vector<int>::iterator pos = find(v.begin(), v.end(), 5); v.erase(pos);如果有了判断，就不会翻车了，如果待删目标不存在，就不会去走 erase() 。
因为pos如果找不到就会等于 end() 上的值，我们利用这一点进行 if 判断
vector<int>::iterator pos = find(v.begin(), v.end(), 5); if (pos != v.end()) { // 检查！ v.erase(pos); }0x05 clear（）清空数据
void test_vector10() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); printf("清空前："); for (auto e : v) cout << e << " "; cout << endl; v.clear(); printf("清空后："); for (auto e : v) cout << e << " "; cout << endl; }结果如下