c++ & STL の 神奇用法

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

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

例子：

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

时间复杂度：Θ(n).

minmax_element(begin, end)

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

时间复杂度 Θ(n).

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

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

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

iota(begin, end, value)

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

时间复杂度为 Θ(n).

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

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

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

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

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

时间复杂度：Θ(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)

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

这些函数的时间复杂度均为 Θ(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).

时间复杂度为 Θ(n).

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

时间复杂度为 Θ(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)) 中.

时间复杂度为 Θ(n).

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

时空复杂度均为 Θ(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;