STL用法详解

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]