OI代码实用技巧
这里只有一些冷门技巧。
随机数生成器
为了随机数质量和通用性，推荐使用mt19937。
关于效率：mt19937 生成的随机数O2下比 rand 快，但是非O2慢于rand。
uniform_int_distribution 生成 \([a, b]\) 的随机数
uniform_real_distribution 生成 \([a,b)\) 的随机数
const int ADDR = 1;
mt19937 rd = mt19937(种子)
int rr(int l, int r){
uniform_int_distribution<int> d(l, r);
return d(rd);
}
实用算法
增强代码可读性和通用性，有时候可以减少代码量
求前缀和，要求前两个参数满足输入迭代器，第三个参数满足输出迭代器，op是二元运算
partial_sum(first, last, first)
partial_sum(first, last, first, op)
求差分
adjacent_difference(first, last, first)
adjacent_difference(first, last, first, op)
求距离
hypot(x, y)
求点 \((x, y)\) 到坐标原点的欧式距离
将二元组排序，访问销毁对象是未定义行为
minmax(x, y)
返回值为 pair<const T&, const T&>
求最值，可以传入自定义比较函数
保证比较次数不会超过\(\frac{2}{3}(N−1)\)次
min_element(first, last)
max_element(first, last)
min_max_element(first, last)
求最值，可以传入初始化列表和自定义函数
min(list)
max(list)
归并排序，可以传入自定义比较函数
对\([first1, last1)\), \([first2, last2)\)
\([first, mid)\), \([mid, last)\) 进行归并排序
merge(first1, last1, first2, last2, first3)
inplace_merge(first, mid, last)
划分范围 \([first, last)\) 中的元素，将满足要求的元素放在前面，返回第二组元素的首指针
partion(first, last, p)
stable_partion(first, last, p)
计数，返回满足要求的个数
count(first, last, value)
count_if(first, last, p)
部分排序
约 \((last-first)log(middle-first)\) 次比较
保证 \([first, mid)\) 有序，且为序列中最小元素
partial_sort(first, mid, last)
找到第 \(n\) 小
保证 \([first, nth)\) 比 nth 小，\([nth, last)\) 比 nth 大
保证 nth 是 如果 \([first, last)\) 排好序之后出现的元素
nth_element(first, nth, last)
选转
n_first 成为新序列的首个元素，n_first - 1 成为新序列的最后一个元素
rotate(first, nth, last)
绑定函数参数
bind()
实用继承
struct base{
...
}
struct son : base{
}
注意，子类访问父类函数需要加上父类作用域
base :: f()
一个很好的例子：带 size 数组 （静态vector）
template<typename T, int N>
struct mvector : array<T, N>{
int cur = 0;
void push_back(const T& x){
array<T, N> ::operator[](cur) = x;
++cur;
}
void pop_back(){
--cur;
}
bool empty(){
return cur == 0;
}
int size(){
return cur;
}
auto end(){
return array<T, N>::begin() + cur;
}
};
好处：可以使用范围 for 循环
实用流
stringstream（严格快于sscanf / sprintf）
格式化字符串，同 用法cin , cout
实用容器
array<T, N>
这个容器挺好用的，不会退化。美中不足是为了保证这个平凡类型牺牲了构造函数，只能作为聚合类型进行聚合初始化
basic_string<T>
虽然被一些人吹过头了，但还是挺好用的。
常数略大于vector，好在有很多好用的函数。
实用语言特性
lambda 表达式
std::function<> f;