1. 简介

STL 提供了大约 100100 个实现算法的模版函数，基本都包含在 <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) 范围内进行分类，找出序列中第 nn 大的元素，使其左边均为小于它的数，右边均为大于它的数。

  • 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)：求前缀和。设源容器为 xx，目标容器为 yy，则有 y[i]=x[0]+x[1]+⋯+x[i]y[i] = x[0] + x[1] + \cdots + x[i]。