C++ STL，即 C++ Standard Template Library（标准模板库），它由三个重要部分组成：容器， 算法，迭代器
- 容器：
vector、deque、map、set等 - 算法：
sort、find、lower_bound等 - 迭代器：用来在容器和算法之间建立统一的访问接口
它们在算法竞赛中十分常见，建议熟练使用。
本篇我们介绍其中的容器。
容器，又叫数据结构，是经过C++高度封装的数据结构。
对于各类容器，只需简单了解原理，需要熟练掌握如何使用。
vector
vector是动态数组，大小可变，经常替代C中的传统数组。
（1）引入头文件
#include <vector>
// 或者使用万能头文件，包含大多数头文件
#include <bits/stdc++.h>（2）创建vector数组
vector<int> v; // 创建大小为零的整数数组v
vector<int> a(10); // 创建初始大小为10的整数数组, 初始值默认为0
int n = 100;
vector<bool> a(n); // 创建初始大小为100的布尔数组a
vector<int> b(n, -1) // 创建初始大小为100的数组b, 初始值都为-1
vector<double> c(n * 2, 3.14) // 创建初始大小为200的浮点数数组c, 初始值都为3.14
// 列表初始化
vector<int> v = {1, 2, 3, 4};（3）输入元素
1、未指定长度
如果vector数组数组定义的时候，没有指定长度，则只能使用push_back()函数输入。
a.push_back(val) ，向vector数组a中的尾部添加一个元素val。
vector<int> a;
for (int i = 0; i <= 5; ++ i) {
a.push_back(i);
}
// a = [0, 1, 2, 3, 4, 5]然后数组a就可以使用[]修改、读取元素，和普通数组一样，但是也不可以越界。
cout <<< a[0] << "\n"; // 输出：0
a[2] = 100; // 修改元素
for (int i = 0; i <= 5; ++ i) {
cout << a[i] << " ";
}
// 输出： 0 1 100 4 5
a[6] = 10; // 报错，数组越界2、指定长度
如果数组定义时指定了长度，那么就可以直接当做普通数组来用，也是不可以越界的。
vector<int> v(10); // 长度为10，初始值默认为0
for (int i = 0; i < 10; ++ i) {
cin >> v[i];
}（4） 遍历数组
1、直接遍历
vector<int> a = {1, 2, 3};知道数组长度
for (int i = 0; i < 3; ++ i) {
cout << a[i] << " ";
}
// 输出：1 2 3不知道数组长度
int n = a.size(); // 获取数组a的长度
for (int i = 0; i < n; ++ i) {
cout << a[i] << " ";
}
// 输出同上2、范围 for 循环
for (int val: a) {
cout << val << " ";
}
// 输出同上（5）相关函数（重要）
1、size()
a.size() 获取a的长度。
vector<int> a = {1, 2, 3, 4};
int n = a.size(); // n = 4
vector<int> b(100);
int sz = b.size(); // sz = 100;2、sort()
快速排序函数，平均时间复杂度O(nlogn)
(1) 头文件
#include<algorithm>
(2) 排序整个数组，默认升序排序
sort(a.begin(), a.end())
这里的a.begin()是a的迭代器，我们目前不需要知道是什么，只需要明白它表示a的开始位置，a.end() 表示a的最后一个元素的后一个位置。
vector<int> a = {4, 1, 3, 2};
// 排序a，范围为a.begin()到a.end()
sort(a.begin(), a.end());
// a = [1, 2, 3, 4](3) 排序数组的指定区间[l, r]（下标从1开始）
sort(a.begin() + l - 1, a.begin() + l + r - 1)
vector<int> a = {4, 1, 3, 2};
// 排序a，范围为[1, 3]
sort(a.begin() + 1 - 1, a.begin() + 1 + 3 - 1);
// 等同于：
sort(a.begin(), a.begin() + 3)
// a = [1, 3, 4, 2](4) 降序排序
sort(a.begin(), a.end(), greater<T>())
这里的T取决于数组a的类型
vector<int> a = {1, 2, 3, 4, 5};
sort(a.begin(), a.end(), greater<int>());
// a = [5, 4, 3, 2, 1]3、erase()
删除元素，时间复杂的：最好情况下O(1)，最坏O(n)，平均复杂度O(n)，除非数据量过小，或者是尾部删除，谨慎使用。
(1) 删除数组第k个元素
a.erase(a.begin() + k - 1)
vector<int> a = {1, 2, 3, 4};
a.erase(a.begin());
// a = [2, 3, 4]
a.erase(a.begin() + 1)
// a = [2, 4](2) 删除区间[l, r]的元素
a.erase(a.begin() + l - 1, a.begin() + l + r - 1)
vector<int> a = {1, 2, 3, 4};
int l = 1, r = 2;
a.erase(a.begin(), a.begin() + 2);
// a = [3, 4](3) 删除末尾元素 O(1)
a.erase(a.end())
vector<int> a = {1, 2, 3, 4};
a.erase(a.end());
// a = [1, 2, 3]4、resize()
手动扩容，扩大vector的容量
vector<int> a = {1, 2, 3};
a.resize(5);
// a = [1, 2, 3, 0, 0]string
string是C++的字符串类型，等同于C语言的char a[]（字符数组），但是各方面都完爆字符数组，建议赶紧丢弃字符数组，拥抱string。
（1）头文件
#include <string>
（2）初始化
string s; // 定义一个空字符串
string s = "Hello World!"; // 直接赋值（3） 输入输出
string s;
cin >> s;
cout << s;
string s = "hello";
cout << s << "\n";
// 输出： hello（4）修改
string s = "hello";
s[0] = 'Y';
cout << s << "\n";
// 输出：Yello
s += 'w';
cout << s << "\n";
// 输出：Yellow
string a = "hello";
string b = " world"; // 注意这里前面有一个空格
string c = a + b;
cout << c << "\n";
// 输出：hello world（5）相关函数
1、size() 、length()
获取字符串的长度，两个效果完全等同，一般习惯使用size(),和其他容器相契合。
string s = "hello";
int n = s.size(); // n = 5
int m = s.length(); // m = 52、stoi()
将字符串转化为int类型的数字，字符串必须全部是数字，不能出现非数字字符，也必须在int范围之内。
string s = "1230";
int a = stoi(s);
// a = 12303、erase()
(1)删除第k个字符
string s = "hello";
int k = 1;
s.erase(s.begin() + k - 1);
cout << s << '\n';
// 输出: ello(2)从下标x开始，删除后面的k个
string s = "hello world";
int x = 0, k = 6;
s.erase(x, k);
cout << s << "\n";
// 输出: world4、find()
查找子串str第一次出现的位置的下标，未找到则输出-1
string s = "woOK wowow";
int a = s.find("OK");
cout << a << "\n";
// 输出：2
