《从 C++98 到 C++20，寻觅甜甜的语法糖们》
这篇文章对《从 C++98 到 C++20，寻觅甜甜的语法糖们》稍有改动
-
find(bg,ed,val)
-
返回指向第一个等于 \(val\) 的元素的指针。
-
时间复杂度 \(O(n)\)。
-
后文所有序列操作的函数，都以 \(n\) 代指 \(ed−bg\)。
-
-
fill(bg,ed,val)
-
将 \(bg \sim ed\) 之间的所有元素赋值为 \(val\)。
-
复杂度为 \(O(n)\)，常数略大于
memset。 -
在
val = 0x3f时常数与memset相同。（存疑） -
常用于弥补
memset无法赋值的问题，如赋值一个数组为 \(1\)。
-
-
max_element/min_element(bg,ed)
-
返回指向 \(bg \sim ed\) 中最大/最小的元素的指针。
-
时间复杂度 \(O(n)\)。
-
第三个参数可传入比较函数。
-
求数组最大值就可以直接写：
*max_element(a+1,a+n+1)
-
-
nth_element(bg,md,ed)：
-
将 \(bg \sim ed\) 中的内容重新分配顺序，\(\le\) md 的元素在 \(bg \sim md\)，\(\ge\) md 的元素都在 \(md \sim ed\)。
-
时间复杂度 \(O(n)\)，需要 \(O(n)\) 的额外空间。
-
第四个参数为比较函数，若不传则默认
less<>()。 -
常用于线性求序列中的第 \(k\) 大，常用于实现替罪羊树。
-
-
stable_sort(bg,ed)
-
对 \(bg \sim ed\) 进行 稳定 排序。
-
时间复杂度 \(O(n log n)\)，要 \(O(n)\) 的额外空间。
-
当空间不足时使用 \(O(n log_2 n)\) 的双调排序。
-
-
next_permutation(bg,ed)
-
将 \(bg \sim ed\) 更改为下一个排列，并返回 \(1\)。
-
若 \(bg \sim ed\) 已经是最后一个排列，那么返回 \(0\)。
-
下一个排列的定义为字典序严格大于当前排列的下一个排列。
-
时间复杂度 \(O(n)\)。
-
事实上 \(bg \sim ed\) 不一定要是排列，可以存在相同元素。
-
常用于枚举全排列：
do{ // ... }while(next_permutation(p,p+n));prev_permutation(bg,ed)可以求出上一个排列。
-
-
merge(bg1,ed1,bg2,ed2,bg3)
-
\(bg1 \sim ed1\) 和 \(bg2 \sim ed2\) 是两个有序序列，对其进行归并并存入
bg3。 -
不能够原地归并，若要原地归并请使用
inplace_merge。 -
时间复杂度 \(O(ed1−bg1+ed2−bg2)\)。
-
可以传入第六参数作为比较函数。
-
-
inplace_merge(bg,md,ed)
-
将 \(bg \sim md\) 和 \(md \sim ed\) 归并排序，并存入
bg。 -
时间复杂度 \(O(n)\)，需要 \(O(n)\) 的额外空间。
-
当空间不足时使用 \(O(n log n)\) 的原地排序。
-
常数较小，可能比手写的还快。
-
可以传入第四个参数作为比较函数。
-
常用于
CDQ分治等分治算法，非常好用。
-
-
count(bg,ed,val)
- 返回 \(bg \sim ed\) 中等于 \(val\) 的元素的个数。
时间复杂度 \(O(n)\)。
-
count_if(bg,ed,func)
-
返回 \(bg \sim ed\) 中使得函数
func返回值为 \(\true\) 的元素的个数。 -
时间复杂度 \(O(n \times f)\)，\(f\) 为
func的复杂度。 -
常用的
func有：islower/isupper/isdigit等。
-
-
replace(bg,ed,val1,val2)
-
将 \(bg \sim ed\) 中所有等于 \(val1\) 的元素替换为 \(val2\)。
-
时间复杂度 \(O(n)\)。
-
-
for_each(bg,ed,func)
-
对 \(bg \sim ed\) 中所有元素执行函数
func。 -
时间复杂度 \(O(n \times f)\)。
-
其实没啥用，就是能压行。
-
-
accumulate(bg,ed,val)
-
将 \(bg \sim ed\) 中的所有所有元素与初始值 \(val\) 相加，返回这个和。
-
时间复杂度 \(O(n)\)。
-
可以传入第四个参数作为加法。
-
可以用于求序列和，但注意，该函数返回值与 \(val\) 类型一致，意味着你要注意
long long的问题：
accumulate(bg,ed,0);//返回值是 int，可能溢出 accumulate(bg,ed,0ll);//返回值是 long long -
-
fabs(x)
-
返回 \(∣x∣\)。
-
注意，对浮点运算请都使用
fabs而不是abs，因为有可能你调用的是abs(int)。
-
-
ceil(x)
-
返回 \(⌈x⌉\)
-
其返回值依旧是浮点类型，输出时注意格式。
-
-
floor(x)
-
返回 \(⌊x⌋\)
-
其返回值依旧是浮点类型，输出时注意格式。
-
-
shuffle(bg,ed,gen)
-
打乱 \(bg \sim ed\) 的顺序，
gen是一个随机数生成器（mt19937）。 -
时间复杂度 \(O(n)\)。
-
C++11 之后请尽量使用
shuffle而不是random_shuffle。
-
-
is_sorted(bg,ed)
-
判断 \(bg \sim ed\) 是否升序排序。
-
时间复杂度 \(O(n)\)。
-
-
minmax(a,b)
-
返回一个
pair<>，其first为 \(\min(a,b)\)，second为 \(\max(a,b)\)。 -
时间复杂度 \(O(1)\)。
-
常用于无向图存边的去重问题。
-
-
exp2(x)
- 返回 \(2^x\)。
-
log2(x)
- 返回 \(log_2(x)\)
-
hypot(x,y)
-
返回 \(\sqrt {x^2 + y^2}\)
-
常用于求两点之间的距离，非常方便。
-
-
hypot(x,y,z)
-
返回 \(\sqrt {x^2 + y^2 + z^2}\)
-
复杂度 O(1)。
-
常用来求三维中两点距离。
-
-
mt19937
-
一个类型，作为随机数生成器。
-
其构造函数应传入一个数字作为随机种子，使用时用法和 \(rand\) 相同。
-
生成
unsigned int范围内的随机数。
mt19937 gen(123456); //123456 为随机种子 int x = gen()%10000; //x will in [0,10000] uint32_t y = gen(); //normally y will in [0,2^32]- 随机种子通常为时间相关，下面的非常常用，建议背过
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());//chrono 在头文件 <chrono> 中 -
-
uniform_int_distribution
(L,R) - 随机数发生器，每次调用时传入一个
mt19937，返回一个 \(L \sim R\) 之间的整数，类型为 \(T\)，若 \(T\) 为空则默认为int。
- 随机数发生器，每次调用时传入一个
-
uniform_real_distribution
(L,R) - 随机数发生器，每次调用时传入一个
mt19937，返回一个 \(L \sim R\) 之间的实数，类型为 \(T\)，若 \(T\) 为空则默认为double。
- 随机数发生器，每次调用时传入一个
-
gcd(x,y) 或 lcm(x,y)
-
返回 \(\gcd(|x|,|y|)\) 或 \(\operatorname {lcm}(|x|,|y|)\) 的值。
-
复杂度对数级别的。
-
保证了返回值的符号是正。
-
\(\operatorname {lcm}\) 的实现是先除后乘。
-
-
popcount(x)
-
返回无符号整形 \(x\) 在二进制下 \(1\) 的个数。
-
时间复杂度有说 \(O( \log \log x)\) 的，也有说 \(O(1)\) 的，一定比手写的快。
-
使用
__builtin_popcount实现，但会检查传入的参数是否为无符号整形。
-
countl_zero(x);//从最高位起连续的 0 的数量
countr_zero(x);//从最低位起连续的 0 的数量
countl_one(x);//从最高位起连续的 1 的数量
countr_one(x);//从最低位起连续的 1 的数量
-
bit_width(x)
-
当 \(x = 0\) 时返回 \(0\)，否则返回 \(1+⌊log2(x)⌋\)。
-
即二进制下 \(x\) 的位数。
-
复杂度 \(O(1)\)。
-
-
bit_floor(x)/bit_ceil(x)
-
返回不超过 \(x\) 的最大的 \(2\) 的整次幂 / 不小于 \(x\) 的最小的 \(2\) 的整次幂。
-
复杂度 \(O(1)\)。
-
-
has_single_bit(x)
-
返回 \(x\) 是否为 \(2\) 的整次幂，相当于
popcount(x)==1。 -
复杂度 \(O(1)\)。
-
-
numbers 库
头文件 <numbers>，命名空间 std::numbers 中提供了大量的数学常数：
| 代码表示 | 数学表示 |
|---|---|
| e_v | \(e\) |
| log2e_v | \(log_{2}e\) |
| pi_v | \(\pi\) |
| log10e_v | \(log_{10}e\) |
| inv_pi_v | \(\frac{1}{\pi}\) |
| inv_sqrtpi_v | \(\frac{1}{\sqrt{\pi}}\) |
| ln2_v | \(\operatorname{ln}2\) |
| ln10_v | \(\operatorname{ln}10\) |
| sqrt2_v | \(\sqrt{2}\) |
| sqrt3_v | \(\sqrt{3}\) |
| inv_sqrt3_v | \(\frac{1}{\sqrt{3}}\) |
| egamma_v | 欧拉-马斯克若尼常数 \(γ\) |
| phi_v | 黄金比 \(ϕ= \frac{\sqrt5+1}{2}\)（注意这里是加号！！！） |
- 这些都是类模板，调用时请填入类型：
int main(){
std::cout<<std::fixed<<std::setprecision(9)<<std::numbers::pi_v<double><<'\n';
}
去掉末尾的 _v 后直接就是一个常量：
cout<<numbers::e<<'\n';