c++ & STL の 神奇用法

min() 与 max() 的列表版本

普通的 min() 与 max() 只能得到两个数的最值，但是这个版本可以得到许多数的最值.

例子：

min({1, 2, 3, 4, 5});
max({5, 4, 3, 2, 1});

时间复杂度：$\Theta(n)$.

minmax_element(begin, end)

这个函数用于查询区间 $[begin,end)$ 的最大、最小值，返回一个 pair，first 最小，second 最大.

时间复杂度 $\Theta(n)$.

shuffle(begin, end, gen) & is_sorted(begin, end)

这个函数可以随机打乱数组，其中 gen 是一个随机数生成器（一般为 mt19937），begin 与 end 为首尾迭代器，时间复杂度 $\Theta(n)$.

is_sorted() 可以检查一个序列是否有序，时间复杂度为 $\Theta(n)$.

iota(begin, end, value)

将区间 $[begin, end)$ 赋值为 ${value, value + 1, value + 2}$ 等等.

时间复杂度为 $\Theta(n)$.

可以用来初始化并查集等.

prev_permutation(begin, end) & next_permutation(begin, end)

两个求排列的函数，一个求上一个排列，一个求下一个排列.

当然，“排列” 存在相同元素也是可以的.

如果已经是第一个 / 最后一个排列，返回 false，否则返回 true，并将区间 $[begin, end)$ 更改为上 / 下一个排列.

时间复杂度：$\Theta(n)$

count(begin, end, value) & count_if(begin, end, func) & replace(begin, end, value1, value2) & fill(begin, end, value) & copy(begin, end, begin2) & find(begin, end, value)

这六个函数都是区间赋值或检查类的.

这些函数的时间复杂度均为 $\Theta(n)$.

1. count(begin, end, value) 返回区间 $[begin, end)$ 中值为 $value$ 的个数.

2. count_if(begin, end, func) 对于区间 $[begin, end)$ 中的一个值 $x$，返回 func(x) 为 true 的个数。其中 func 应为一个返回值为 bool，有一个参数的函数指针，也可以 $lambda$ 函数.

3. replace(begin, end, value1, value2) 将区间 $[begin, end)$ 的所有等于 $value1$ 的数替换为 $value2$.

4. fill(begin, end, value) 将区间 $[begin,end)$ 全部设为 $value$，类似函数 memset.

5. copy(begin, end, begin2) 将区间 $[begin,end)$ 复制到区间 $[begin2,begin2+(end-begin))$.

6. find(begin, end, value) 线性查找区间 $[begin,end)$ 中为 $value$ 的数。对于有序区间，请使用 lower_bound() 或 upper_bound().

7. accumulate(begin, end, value) 返回区间 $[bgein, end)$ 中每一个元素加上初始值 $value$ 的总和，即 $sum(begin, end) + value(end - begin)$.

时间复杂度为 $\Theta(n)$.

accumulate(begin, end, value) 返回区间 $[bgein, end)$ 中每一个元素加上初始值 $value$ 的总和，即 $sum(begin, end) + value(end - begin)$.

时间复杂度为 $\Theta(n)$.

partial_sum(begin, end, begin2) & adjacent_difference(bg1,ed1,bg2)

1. partial_sum(begin, end, begin2) 将区间 $[begin,end)$ 的前缀和存储至 $[begin2, begin2+(end-begin))$ 中.

2. adjacent_difference(bg1,ed1,bg2) 将区间 $[begin,end)$ 的差分存储至 $[begin2, begin2+(end-begin))$ 中.

时间复杂度为 $\Theta(n)$.

inplace_merge(begin, mid, end) 对区间 $[begin, mid)$) 和区间 $[mid,end)$ 进行归并排序，并存入区间 $[begin, mid)$.

时空复杂度均为 $\Theta(n)$. 可以传入第四个参数作为比较.

function<>

function<R<T1, T2, ..., Tn> > f; 表示定义一个返回值类型为 $R$，形参为 $T1, T2, …, Tn$ 的名为 $f$ 的函数.

function<int<int, int> > func = [](int a, int b)->int{
    return a + b;
}

显然，我们做到了在 C++ 里像 JavaScript 一样使用 lambda 函数了！

在这个类型出来之前，我们一般使用 auto 关键字（我也喜欢这样使用）：

auto func = [](int a, int b)->int{
    return a + b;
}

同样地，function<> 也可以作为函数指针，如下例：

int a(int a, int b){
    return a + b;
}
function<int<int, int> > func = a;
//其等价于
int(func*)(int, int) a;