线性数据结构和 STL
vector 容器 (container)
定义及头文件引入
- 定义：一个可变长数组
- 头文件：
#include <vector>
常用变量定义及函数解析
end()：尾后迭代器。push_back(x)：在末端插入元素x（自动扩容）。- 构造函数
- 一个参数：建立长度为
n的数组：vector<int> a(n); - 两个参数：建立长度为
n，每个元素的值均为x的数组：vector<int> a(n, x); - 应用：构造一个
n * m的二维vector嵌套：vector<vector<int>> a(n, vector<int>(m)); - 注意：局部变量
vector元素自动初始化为 \(0\)，不需要手动清空
- 一个参数：建立长度为
lower_bound(a.begin(), a.end(), x)在vector a中找到第一个大于等于x的数。（序列必须有序！！）- 注意：如果没有找到，那么返回的是尾后迭代器。不可直接访问。
upper_bound(a.begin(), a.end(), x)在vector a中找到第一个大于x的数。（序列必须有序！！）- 注意：如果没有找到，那么返回的是尾后迭代器。不可直接访问。
- 迭代器类型：随机访问迭代器
random access iterator- 特点，可以随意加减，如
*(it - 1)*(it + 4)
- 特点，可以随意加减，如
遍历
第一种
vector<int> a;
for (int i = 0; i < a.size(); i ++) {
cout << a[i] << " ";
}
cout << endl;
第二种 (for range) （相当于使用 auto it）
vector<int> a;
for (auto i: a) {
cout << i << " ";
i = 4; // i 只是值，不会影响 vector
}
cout << endl;
第三种 (完全等价于第二种) (for range)
vector<int> a;
for (auto it = a.begin(); it != a.end(); it ++) {
auto i = *it;
cout << i << " ";
}
cout << endl;
使用 auto 进行读入
vector<int> a(n);
for (auto &i: a) { // 中间的 & 很重要！
cin >> i; // i 为引用，会影响 vector
}
解释
因为第三种完全等价于第二种，所以在第二种中，如果对 i 进行操作，是不会影响到 vector 容器的。换言之，第二种中的 i 代表的是元素的值，而不是引用。
写 auto &i: a，则会对值进行修改，因为此时 i 变为了引用。
注意：编译器选项中添加 -std=c++14，不能编译则使用 -std=c++11，才可以使用 for range。
priority_queue 优先队列（二叉堆）
- 注意：没有
for range语法！ - 大根堆
priority_queue<int> Q - 小根堆
priority_queue<int, vector<int>, greater<int>> Qgreater<int>需要#include <functional>
- 如需存储结构体则需要运算符重载（必须定义小于号！）
- 大根堆重载小于号
- 小根堆重载小于号（一般不采用本方法）
- 小根堆直接把大根堆的运算符重载中所有符号取反（√）
set 容器
- 维护某个元素是否存在
- 查询大于等于/大于它的所有数字
- 维护本质不同的元素有几个
成员函数
set<int> s;
s.count(x)查询x是否在s中出现。s.erase(x)把x从s中删除（如果存在）。lower_bound和upper_bound基本同vector- 迭代器类型：双向访问迭代器
bidirectional access iterator- 只可以进行
++，--操作
- 只可以进行
- 在
set找到最后一个小于x的数：*(--s.lower_bound(4)) - 找到最大的元素：
*--s.end()
multiset 容器
- 基本同
set - 如果使用
erase(x)则会删除所有值等于x的元素 - 如果想要只删除一个则使用
erase(find(x))
bitset 容器
bitset<100> bs定义一个长度为100的bitset，命名为bs（长度填在尖括号中，必须为常量）。- 定义时可以加入构造函数，填入字符串
#include <bitset>
string s = "100101";
bitset<10> bs(s);
algorithm 库中的常用函数
min(a, b)取最小值max(a, b)取最大值next_permutation(a, a + n)数组的下一个排列unique去重，返回第一个重复元素的地址reverse翻转