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)

random_shuffle 自 C++14 起被弃用,C++17 起被移除。

在 C++11 以及更新的标准中,您可以使用 shuffle 函数代替原来的 random_shuffle。使用方法为 shuffle(v.begin(), v.end(), rng)(最后一个参数传入的是使用的随机数生成器,一般情况使用以真随机数生成器 random_device 播种的梅森旋转伪随机数生成器 mt19937)。

  • 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)

在一般的数组里,这两个函数的时间复杂度均为 ,但在 set 等关联式容器中,直接调用 lower_bound(s.begin(),s.end(),val) 的时间复杂度是 的。

set 等关联式容器中已经封装了 lower_bound 等函数(像 s.lower_bound(val) 这样),这样调用的时间复杂度是 的。

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

使用样例

  • 使用 lower_boundupper_bound 查找有序数组 中小于 ,等于 ,大于 元素的分界线。
  • 使用 partial_sum 求解 中元素的前缀和,并存储于 中。
  • 使用 sortunique 查找数组 小的值(注意:重复出现的值仅算一次,因此本题不是求解第 小的元素)。例题:Luogu P1138 第 k 小整数

贡献者:@Imple@Menci@Xeonacid@opsiff@mgt@SBOfGaySchool@chentingyu.20@Shuhao@Jacob@ouuan@Ir1d

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组