正文 

当前位置： 首页 > 代码 > java教程

万字长文|stl算法总结

author author     2023-01-04     781

关键词：

本篇所有算法源码均已同步收录 GitHub 仓库，欢迎点个小⭐️：https://github.com/rongweihe/CPPNotes/tree/master/STL-source-code-notes​

大家好，我是小贺。

上一篇更新了 ​​STL 关联式容器源码​​，今天我们来学习下 STL 算法。

STL 算法博大精深，涵盖范围之广，其算法之大观，细节之深入，泛型思维之于字里行间，每每阅读都会有不同的收获。

STL 将很多常见的逻辑都封装为现成的算法，熟悉这些算法的使用和实现很多时候可以大大简化编程。

并且在需要的时候能够对 STL 进行扩展，将自定义的容器和算法融入到 STL 中。

侯捷大师在书中说到：深入源码之前，先观察每一个算法的表现和大观，是一个比较好的学习方式。

不多 BB，先上思维导图：

万字长文

回顾

STL 源码剖析系列：

​​5 千字长文+ 30 张图解 | 陪你手撕 STL 空间配置器源码​​

​​万字长文炸裂！手撕 STL 迭代器源码与 traits 编程技法​​

​​超硬核 | 2 万字+20 图带你手撕 STL 序列式容器源码​​

​​硬核来袭  | 2 万字 + 10 图带你手撕 STL 关联式容器源码​​

基本算法

在 STL 标准规格中，并没有区分基本算法或复杂算法，然而 SGI 却把常用的一些算法定义于 <stl_algobase.h>之中，其它算法定义于 <stl_algo.h>中。

常见的基本算法有 equal、fill、fill_n、iter_swap、lexicographical_compare、max、min、mismatch、swap、copy、copy_backward 等。

质变算法和非质变算法

所有的 STL 算法归根到底，都可以分为两类。

所谓“质变算法”是指作用在由迭代器[first,last]所标示出来的区间，上运算过程中会更改区间内的元素内容：

比如拷贝(copy)、互换(swap)、替换(replace)、填写(fill)、删除(remove)、排列组合(permutation)、分割(partition)。随机重排(random shuffling)、排序(sort)等算法，都属于这一类。

而非质变算法是指在运算过程中不会更改区间内的元素内容。比如查找(find)，匹配(search)、计数（count）、遍历(for_each)、比较(equal_mismatch)、寻找极值(max,min)等算法。

输入参数

所有泛型算法的前两个参数都是一对迭代器，通过称为 first，last 用来标示算法的操作区间。

每一个 STL 算法的声明，都表现出它所需要的最低程度的迭代器类型。

比如 find() 需要一个 inputiterator ，这是它的最低要求，但同时也可以接受更高类型的迭代器。

如 Forwarditerator、Bidirectionaliterator 或 RandomAcessIterator。

因为，前者都可以看做是一个 inputiterator，而如果你给 find() 传入一个 Outputiterator，会导致错误。

将无效的迭代器传给某个算法，虽然是一种错误，但不保证能够在编译器期间就被捕捉出来。

因为所谓“迭代器类型”并不是真实的型别，它们只是function template的一种型别参数。

许多 STL 算法不仅支持一个版本，往往第一个版本算法会采用默认的行为，另一个版本会提供额外的参数，接受一个仿函数，以便采取其它的策略。

例如 unique() 默认情况下会使用 equality 操作符来比较两个相邻元素，但如果这些元素的型别并没有提供，那么便可以传递一个自定义的函数（或者叫仿函数）。

知道了这一点，对于想要深入研究源码的小伙伴们会更好理解一些。

算法的泛型化

将一个表述完整的算法转化为程序代码，是一个合格程序员的基本功。

如何将算法独立于其所处理的数据结构之外，不受数据的牵绊，使得设计的算法在即将处理的未知的数据结构上（也许是 array，也许是 vector，也许是 list，也许是 deque）上，正确地实现所有操作呢？

这就需要进一步思考：关键在于只要把操作对象的型别加以抽象化，把操作对象的标示法和区间目标的移动行为抽象化，整个算法也就在一个抽象层面上工作了。

这个过程就叫做算法的泛型化，简称泛化。

比如在 STL 源码剖析这本书里举了一个 find 的例子，如果一步步改成 template + 迭代器的形式，来说明了泛化的含义。

下面我们就来看看 STL 那些牛批的算法，限于篇幅，算法的代码没有贴出。

具体源码细节可以去开头的 GitHub 仓库里研究，还有注释哦。​

构成

头文件

功能

​​<algorithm>​​

算法函数

​​<numeric>​​

数值算法

​​<functional>​​

函数对象/仿函数

分类

No.

分类

说明


1

非质变算法

Non-modifying sequence operations

不直接修改容器内容的算法

2

质变算法

Modifying sequence operations

可以修改容器内容的算法

3

排序算法

Sorting/Partitions/Binary search/

对序列排序、合并、搜索算法操作

4

数值算法

Merge/Heap/Min/max

对容器内容进行数值计算

填充

函数

作用

​​fill(beg,end,val)​​

将值​​val​​​赋给[​​beg​​​,​​end​​)范围内的所有元素

​​fill_n(beg,n,val)​​

将值​​val​​​赋给[​​beg​​​,​​beg+n​​)范围内的所有元素

​​generate(beg,end,func)​​

连续调用函数​​func​​​填充[​​beg​​​,​​end​​)范围内的所有元素

​​generate_n(beg,n,func)​​

连续调用函数​​func​​​填充[​​beg​​​,​​beg+n​​)范围内的所有元素

  • ​​fill()​​​/​​fill_n()​​用于填充相同值，​​generate()​​/​​generate_n()​​用于填充不同值。

遍历/变换

函数

作用

​​for_each(beg,end,func)​​

将[​​beg​​​,​​end​​​)范围内所有元素依次调用函数​​func​​​，返回​​func​​。不修改序列中的元素

​​transform(beg,end,res,func)​​

将[​​beg​​​,​​end​​​)范围内所有元素依次调用函数​​func​​​，结果放入​​res​​中

​​transform(beg2,end1,beg2,res,binary)​​

将[​​beg​​​,​​end​​​)范围内所有元素与[​​beg2​​​,​​beg2+end-beg​​​)中所有元素依次调用函数​​binnary​​​，结果放入​​res​​中

最大最小

函数

作用

​​max(a,b)​​

返回两个元素中较大一个

​​max(a,b,cmp)​​

使用自定义比较操作​​cmp​​,返回两个元素中较大一个

​​max_element(beg,end)​​

返回一个​​ForwardIterator​​​，指出[​​beg​​​,​​end​​)中最大的元素

​​max_element(beg,end,cmp)​​

使用自定义比较操作​​cmp​​​,返回一个​​ForwardIterator​​​，指出[​​beg​​​,​​end​​)中最大的元素

​​min(a,b)​​

返回两个元素中较小一个

​​min(a,b,cmp)​​

使用自定义比较操作​​cmp​​,返回两个元素中较小一个

​​min_element(beg,end)​​

返回一个​​ForwardIterator​​​，指出[​​beg​​​,​​end​​)中最小的元素

​​min_element(beg,end,cmp)​​

使用自定义比较操作​​cmp​​​,返回一个​​ForwardIterator​​​，指出[​​beg​​​,​​end​​)中最小的元素

排序算法(12个)：元素排序策略

函数

作用

​​sort(beg,end)​​

默认升序重新排列元素

​​sort(beg,end,comp)​​

使用函数​​comp​​​代替比较操作符执行​​sort()​​

​​partition(beg,end,pred)​​

元素重新排序，使用​​pred​​​函数，把结果为​​true​​​的元素放在结果为​​false​​的元素之前

​​stable_sort(beg,end)​​

与​​sort()​​类似，保留相等元素之间的顺序关系

​​stable_sort(beg,end,pred)​​

使用函数​​pred​​​代替比较操作符执行​​stable_sort()​​

​​stable_partition(beg,end)​​

与​​partition()​​类似，保留容器中的相对顺序

​​stable_partition(beg,end,pred)​​

使用函数​​pred​​​代替比较操作符执行​​stable_partition()​​

​​partial_sort(beg,mid,end)​​

部分排序，被排序元素个数放到[beg,end)内

​​partial_sort(beg,mid,end,comp)​​

使用函数​​comp​​​代替比较操作符执行​​partial_sort()​​

​​partial_sort_copy(beg1,end1,beg2,end2)​​

与​​partial_sort()​​类似，只是将[beg1,end1)排序的序列复制到[beg2,end2)

​​partial_sort_copy(beg1,end1,beg2,end2,comp)​​

使用函数​​comp​​​代替比较操作符执行​​partial_sort_copy()​​

​​nth_element(beg,nth,end)​​

单个元素序列重新排序，使所有小于第​​n​​个元素的元素都出现在它前面，而大于它的都出现在后面

​​nth_element(beg,nth,end,comp)​​

使用函数​​comp​​​代替比较操作符执行​​nth_element()​​

反转/旋转

函数

作用

​​reverse(beg,end)​​

元素重新反序排序

​​reverse_copy(beg,end,res)​​

与​​reverse()​​​类似，结果写入​​res​​

​​rotate(beg,mid,end)​​

元素移到容器末尾，由​​mid​​成为容器第一个元素

​​rotate_copy(beg,mid,end,res)​​

与​​rotate()​​​类似，结果写入​​res​​

随机

函数

作用

​​random_shuffle(beg,end)​​

元素随机调整次序

​​random_shuffle(beg,end,gen)​​

使用函数​​gen​​​代替随机生成函数执行​​random_shuffle()​​

查找算法(13个)：判断容器中是否包含某个值

统计

函数

作用

​​count(beg,end,val)​​

利用​​==​​​操作符，对[​​beg​​​,​​end​​​)的元素与​​val​​进行比较，返回相等元素个数

​​count_if(beg,end,pred)​​

使用函数​​pred​​​代替​​==​​​操作符执行​​count()​​

查找

函数

作用

​​find(beg,end,val)​​

利用​​==​​​操作符，对[​​beg​

万字长文|2023届推荐算法岗面经总结！

大家好，我是对白。转眼间2023届春招实习已接近尾声，由于疫情影响，今年找个大厂实习确实很难，今天就给大家分享一位23届同学找算法岗实习的总结，最终拿下抖音APP、快手主站和美团优选的推荐算法岗offer，希望能帮助到... 查看详情

收藏|五万字长文总结c/c++(代码片段)

...程序员链接：https://github.com/huihut/interview这是一篇五万字的C/C++知识点总结，长文预警。能滑到留 查看详情

jdbc万字长文总结回炉重造(代码片段)

JDBC-万字长文总结1.概述1.1什么是JDBC1.2JDBCAPI1.3JDBC可以做什么1.4JDBC程序编写步骤2.演示完整步骤2.1引入JDBC驱动程序2.2加载并注册驱动2.2.1Class.forName()2.2.2服务提供者框架2.3获取数据库链接2.4操作或访问数据库2.4.1Statement2.4.2ResultSet2.... 查看详情

leetcode0707.设计链表：c++小详解，万字小长文：分别借助和不借助stl解决(代码片段)

【LetMeFly】707.设计链表：C++小详解，万字小长文：分别借助和不借助STL解决力扣题目链接：https://leetcode.cn/problems/design-linked-list/设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有... 查看详情

万字长文，整理到吐血！linux最全命令总结

关注我，每天分享软件测试技术干货、面试经验，想要领取测试资料、进入软件测试学习交流群的可以直接加群644956177~~这篇文章主要向大家介绍Linux命令本身总结,主要内容包括基础应用、实用技巧、原理机制等方面࿰... 查看详情

四万字长文总结多线程，一篇就够了！(代码片段)

多线程目录多线程1.认识线程及线程的创建<1>.线程的概念<2>.线程的特性<3>.线程的创建方式(1)继承Thread类(2)实现Runnable接口(3)实现Callable接口2.线程的常用方法<1>构造方法和属性的获取方法<2>常用方法(1)run()... 查看详情

四万字长文总结多线程，一篇就够了！(代码片段)

多线程目录多线程1.认识线程及线程的创建<1>.线程的概念<2>.线程的特性<3>.线程的创建方式(1)继承Thread类(2)实现Runnable接口(3)实现Callable接口2.线程的常用方法<1>构造方法和属性的获取方法<2>常用方法(1)run()... 查看详情

java万字长文基础知识总结（下）-王者笔记《收藏版》(代码片段)

上一篇Java基础知识学习总结之（上）   下一篇Java集合容器篇面试题 （上）                                          目录三、计算机原理和操作系统 内存、CPU、硬盘？ Linux基本命令... 查看详情

史上最强vue总结~万字长文---面试开发全靠它了

vue框架篇vue的优点轻量级框架：只关注视图层，是一个构建数据的视图集合，大小只有几十kb；简单易学：国人开发，中文文档，不存在语言障碍，易于理解和学习；双向数据绑定：保留了angular的特点，在数据操作方面更为简单... 查看详情

java万字长文基础知识总结（下）-王者笔记《收藏版》(代码片段)

上一篇Java基础知识学习总结之（上）                                             目录三、计算机原理和操作系统 内存、CPU、硬盘？ Linux基本命令线程和进程的区别？四、数据库基础关系... 查看详情

万字长文总结《计算机网络http协议》强烈推荐，建议收藏

1.HTTP协议概述：1.HTTP（HyperTextTransferProtocol，超文本传输协）的协议2.HTTP是无连接，无状态，工作在应用层的协议无连接理解为：http协议本身是没有维护连接信息的，http的数据会交给网络协议栈传... 查看详情

干货总结！kafka面试大全（万字长文，37张图，28个知识点）(代码片段)

关注并标星 Kafka面试的连环问题，保证你看完后，对Kafka有了更深层次的了解。全文总结的题目之间的关联性很强，本文将通过问答+图解的形式由浅入深帮助大家进一步学习和理解Kafka分布式流式处理平台。全文总计负责保... 查看详情

❤️万字长文总结❤️一篇学会redis高可用✔集群✔搭建详细教程(代码片段)

大家好，我是Lex喜欢欺负超人那个Lex擅长领域：python开发、网络安全渗透、Windows域控Exchange架构今日重点：今天总结一下Redis集群高可用的搭建流程【惊喜推荐+优质资源见文末，建议收藏！！！】建... 查看详情

❤️万字长文总结❤️一篇学会redis高可用✔集群✔搭建详细教程(代码片段)

大家好，我是Lex喜欢欺负超人那个Lex擅长领域：python开发、网络安全渗透、Windows域控Exchange架构今日重点：今天总结一下Redis集群高可用的搭建流程【惊喜推荐+优质资源见文末，建议收藏！！！】建... 查看详情

万字长文不学算法你也应该知道的算法知识(代码片段)

文末有投票哦~~前言兄弟，想一起学习算法吗？想一起变强吗？想毕业的时候在算法方面吊打面试官吗？想成为刷题狂人吗？快来联系我，一起互相监督，一起征服力扣~~我的伙伴，刷题四天王（... 查看详情

万字长文不学算法你也应该知道的算法知识(代码片段)

文末有投票哦~~前言兄弟，想一起学习算法吗？想一起变强吗？想毕业的时候在算法方面吊打面试官吗？想成为刷题狂人吗？快来联系我，一起互相监督，一起征服力扣~~我的伙伴，刷题四天王（... 查看详情

预训练模型需要知道的知识点总结，万字长文带你深入学习（建议收藏）

前言：如何在有限数据下训练高效的深度学习模型？利用深度学习自动学习特征已经逐步取代了人工构建特征和统计方法。但其中一个关键问题是需要大量的数据，否则会因为参数过多过拟合。以下是我为大家准备的几个精品专... 查看详情

❤c站最全python库总结丨标准库+高级库（万字长文，建议收藏）(代码片段)

作者：不吃西红柿简介：CSDN博客专家、蓝桥签约作者、大数据&Python领域优质创作者。梦想还是要有的，万一别人问呢？文章如果能击中你，求点赞、求收藏、求评论上一篇，《C站最全Python标准库总结... 查看详情