STL 算法

STL 提供了大约 100 个实现算法的模版函数，基本都包含在 <algorithm> 之中，还有一部分包含在 <numeric> 和 <functional>。完备的函数列表请 参见参考手册，排序相关的可以参考

排序内容的对应页面。

• find：顺序查找。find(v.begin(), v.end(), value)，其中 value 为需要查找的值。
• find_end：逆序查找。find_end(v.begin(), v.end(), value)。
• reverse：翻转数组、字符串。reverse(v.begin(), v.end()) 或 reverse(a + begin, a + end)。
• unique：去除容器中相邻的重复元素。unique(ForwardIterator first, ForwardIterator last)，返回值为指向 去重后 容器结尾的迭代器，原容器大小不变。与 sort 结合使用可以实现完整容器去重。
• random_shuffle：随机地打乱数组。random_shuffle(v.begin(), v.end()) 或 random_shuffle(v + begin, v + end)。

• sort：排序。sort(v.begin(), v.end(), cmp) 或 sort(a + begin, a + end, cmp)，其中 end 是排序的数组最后一个元素的后一位，cmp 为自定义的比较函数。
• stable_sort：稳定排序，用法同 sort()。
• nth_element：按指定范围进行分类，即找出序列中第 大的元素，使其左边均为小于它的数，右边均为大于它的数。nth_element(v.begin(), v.begin() + mid, v.end(), cmp) 或 nth_element(a + begin, a + begin + mid, a + end, cmp)。
• binary_search：二分查找。binary_search(v.begin(), v.end(), value)，其中 value 为需要查找的值。
• merge：将两个（已排序的）序列 有序合并 到第三个序列的 插入迭代器 上。merge(v1.begin(), v1.end(), v2.begin(), v2.end() ,back_inserter(v3))。
• inplace_merge：将两个（已按小于运算符排序的）：[first,middle), [middle,last) 范围 原地合并为一个有序序列。inplace_merge(v.begin(), v.begin() + middle, v.end())。
• lower_bound：在一个有序序列中进行二分查找，返回指向第一个 大于等于 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。lower_bound(v.begin(),v.end(),x)。
• upper_bound：在一个有序序列中进行二分查找，返回指向第一个 大于 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。upper_bound(v.begin(),v.end(),x)。

• next_permutation：将当前排列更改为 全排列中的下一个排列。如果当前排列已经是 全排列中的最后一个排列（元素完全从大到小排列），函数返回 false 并将排列更改为 全排列中的第一个排列（元素完全从小到大排列）；否则，函数返回 true。next_permutation(v.begin(), v.end()) 或 next_permutation(v + begin, v + end)。
• partial_sum：求前缀和。设源容器为 ，目标容器为 ，则令 。partial_sum(src.begin(), src.end(), back_inserter(dst))。

使用样例

• 使用 next_permutation 生成 到 的全排列。例题：Luogu P1706 全排列问题

• 使用 lower_bound 与 upper_bound 查找有序数组 中小于 ，等于 ，大于 元素的分界线。

• 使用 partial_sum 求解 中元素的前缀和，并存储于 中。

• 使用 lower_bound 查找有序数组 中最接近 的元素。例题：UVA10487 Closest Sums

• 使用 sort 与 unique 查找数组 中 第 小的值（注意：重复出现的值仅算一次，因此本题不是求解第 小的元素）。例题：Luogu P1138 第 k 小整数