1. 简介

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

2. 常用函数

• find(InputIterator first, InputIterator last, const T& val)：顺序查找 [first, last) 中第一个等于 val 值对应的 Iterator。如果没找到 val 值，则返回 Iterator last。

• reverse(BidirectionalIterator first, BidirectionalIterator last)：翻转 [first, last) 中的元素。

• unique(ForwardIterator first, ForwardIterator last)：去除容器中相邻的重复元素，返回值为指向去重后容器结尾的迭代器，原容器大小不变。unique 函数直接采用覆盖方法去重，故去重后容器的结尾后的元素并不是剩余的重复元素。

• sort(RandomAccessIterator first, RandomAccessIterator last)：对 [first, last) 范围内的元素进行升序排序。非稳定排序！

• stable_sort(RandomAccessIterator first, RandomAccessIterator last)：对 [first, last) 范围内的元素进行升序排序。稳定排序！

• nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)：在 [first, last) 范围内进行分类，找出序列中第 $n$ 大的元素，使其左边均为小于它的数，右边均为大于它的数。

• binary_search(ForwardIterator first, ForwardIterator last, const T& val)：二分查找 [first, last) 中是否存在值 val，若是则返回 true，否则返回 false。

• merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)：将两个有序序列范围 [first1, last1) 和 [first2, last2) 合并到第三个序列的插入迭代器上。

• inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last)：将一个序列中的两个有序范围 [first, middle) 和 [middle, last) 原地合并为一个有序序列。

• lower_bound(ForwardIterator first, ForwardIterator last, const T& val)：二分查找 [first, last) 中第一个大于等于 val 的元素，返回其对应的 Iterator。若没有找到，则返回 Iterator last。

• upper_bound(ForwardIterator first, ForwardIterator last, const T& val)：二分查找 [first, last) 中第一个大于 val 的元素，返回其对应的 Iterator。若没有找到，则返回 Iterator last。

• next_permutation(BidirectionalIterator first, BidirectionalIterator last)：将当前排列更改为全排列中的下一个排列。若当前排列已经是全排列中最后一个排列，函数返回 false 并将排列更改为全排列中的第一个排列；否则，函数返回 true。

• partial_sum(InputIterator first, InputIterator last, OutputIterator result)：求前缀和。设源容器为 $x$，目标容器为 $y$，则有 $y[i] = x[0] + x[1] + \cdots + x[i]$。