C++程序设计:原理与实践(进阶篇)16.1 标准库算法
摘要
Programming: Principles and Practice Using C++, Second Edition
算法和映射
理论上,实践是简单的。
——Trygve Reenskaug
本章将完成我们对STL基本思想的介绍以及对STL所提供工具的纵览。在本章中,我们主要关注算法。我们的主要目的是给你介绍一些最有用的算法,它们能够节省你大量时间,即使达不到以月计,也能达到以天计。每个算法都将通过其使用示例和支持的编程技术来介绍。本章的另一个目的是提供足够的工具,令你在需要标准库和其他库之外的特性时有能力自己编写优雅高效的算法。另外,本章还将介绍三种容器:map、set和unordered_map。
16.1 标准库算法
标准库大约提供了80种有用的算法。所有算法都至少在某些场景下对某些人是有用的;我们将在本章着重介绍其中一些对很多人通常都有用的算法以及一些对某些人极为有用的算法:
挑选的标准算法
r = f?ind(b,e,v) r指向[b:e)中v首次出现的位置
r = f?ind_if(b,e,p) r指向[b:e)中令p(x)为true的第一个元素x
x = count(b,e,v) x为v在[b:e)中出现的次数
x = count_if(b,e,p) x为[b:e)中满足p(x)为true的元素的个数
sort(b,e) 用<运算符对[b:e)排序
sort(b,e,p) 用谓词p对[b:e)排序
copy(b,e,b2) 将[b:e)拷贝至[b2:b2+(e-b));b2之后应有足够的空间用于存储元素
unique_copy(b,e,b2) 将[b:e)拷贝至[b2:b2+(e-b));不拷贝相邻的重复元素
merge(b,e,b2,e2,r) 将有序序列[b2:e2)和[b:e)合并,并放入[r:r+(e-b)+(e2-b2))之中
r = equal_range(b,e,v) r是有序范围[b:e)的一个子序列,且其中所有元素值均为v,本质上是通过二分搜索查找v
equal(b,e,b2) [b:e)和[b2:b2+(e-b))的所有元素对应相等?
x = accumulate(b,e,i) x是将i与[b:e]中所有元素进行累加的结果
x = accumulate(b,e,i,op) 与accumulate类似,但用op进行“求和”运算
x = inner_product(b,e,b2,i) x是[b:e)与[b2:b2+(e-b))的内积
x = inner_product(b,e,b2,i,op,op2) 与inner_product类似,但用op和op2取代内积的+和*
默认情况下,相等比较用==进行,而序则是基于<(小于)的。标准库算法可在<algorithm>找到。如果想获得更多信息,请参考附录C.5和16.2~16.5节中列出的资源。这些算法接受一个或几个序列。一个输入序列由一对迭代器定义,一个输出序列由一个指向首元素的迭代器定义。通常,一种算法可以由一个或多个操作参数化,这些操作可以定义为函数对象或函数。这些算法通常会通过返回输入序列尾来报告“失败”。例如,如果f?ind(b,e,v)未找到v,则返回e。
相关文章
- 容器部署和无服务器部署那些事儿
- 分享五个使用 JSON 相关方法的小技巧
- 不会吧,你还在赤裸裸的使用Printf?
- 在你的 Linux 终端中玩经典的贪吃蛇游戏
- 安装 Ubuntu 22.10 后要做的十件事
- 代码注释的艺术,优秀代码真的不需要注释吗?
- 完全使用Linux替换Windows之后,我觉得自己非常愚蠢
- 鸿蒙开发工具 DevEco Studio 3.0 体验与项目介绍
- 使用 VirtualBox 安装 Linux 虚拟机
- 如何在 Ubuntu 服务器 22.04 上设置静态 IP 地址
- 在 git 中提交后,如何撤销?
- 一文看得 Linux 性能分析
- Ubuntu Budgie 22.10 的新变化
- 苹果 macOS Monterey 12.6.1 / Big Sur 11.7.1 累积更新发布:解决三个问题
- 谷歌 Chrome 浏览器 107“内置搜索”和恐龙小游戏适配支持苹果 iOS 16 锁屏小组件
- 微软 Windows 11 21H2 Build 22000.1165(KB5018483)预览版发布(附更新内容大全)
- 微软 Windows 11 22H2 Build 22621.755(KB5018496)预览版发布(附更新内容大全)
- 开发人员不喜欢低代码和无代码的八个理由
- git 协同工作,怎样重命名、删除分支和查找分支的创建者呢?
- 如何删除远程 git 分支