罗剑锋的 C++ 实战笔记
罗剑锋
前奇虎 360 技术专家,Nginx/OpenResty 开源项目贡献者
34779 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 32 讲
结束语 (1讲)
罗剑锋的 C++ 实战笔记
15
15
1.0x
00:00/00:00
登录|注册

13 | 五花八门的算法:不要再手写for循环了

你好,我是 Chrono。
上节课我提到了计算机界的经典公式“算法 + 数据结构 = 程序”,公式里的“数据结构”就是 C++ 里的容器,容器我们已经学过了,今天就来学习下公式里的“算法”。
虽然算法是 STL(标准库前身)的三大要件之一(容器、算法、迭代器),也是 C++ 标准库里一个非常重要的部分,但它却没有像容器那样被大众广泛接受。
从我观察到的情况来看,很多人都会在代码里普遍应用 vector、set、map,但几乎从来不用任何算法,聊起算法这个话题,也是“一问三不知”,这的确是一个比较奇怪的现象。而且,很多语言对算法也不太“上心”。
但是,在 C++ 里,算法的地位非常高,甚至有一个专门的“算法库”。早期,它是泛型编程的示范和应用,而在 C++ 引入 lambda 表达式后,它又成了函数式编程的具体实践,所以,学习掌握算法能够很好地训练你的编程思维,帮你开辟出面向对象之外的新天地

认识算法

从纯理论上来说,算法就是一系列定义明确的操作步骤,并且会在有限次运算后得到结果。
计算机科学里有很多种算法,像排序算法、查找算法、遍历算法、加密算法,等等。但是在 C++ 里,算法的含义就要狭窄很多了。
C++ 里的算法,指的是工作在容器上的一些泛型函数,会对容器内的元素实施的各种操作。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《罗剑锋的 C++ 实战笔记》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(24)

  • 最新
  • 精选
  • 屈肖东
    学习C++最蛋疼的地方之一,就是总要去确定哪些内容是C++11以及之后才具有的,哪些是C++11之前就有的,像我们公司,根本不支持C++11,C++11再牛逼也没用。只能在学习C++的时候刻意的去记C++11才有的功能,然后在开发时不去使用。这一点比C差太多了,C几乎完全不会考虑版本问题,因为最常用的C标准是C99和C89,现在系统自带的GCC基本不可能不支持。

    作者回复: C++的问题就是标准更新的太迟缓了,C++11/14的普及依然任重道远,好在现在很多开源库都开始要求至少C++11了,侧面上也在推进标准更新。

    2
    15
  • Zivon
    for_each是不是无法返回pos,在需要得到元素位置的情况不太合适?

    作者回复: 可以利用lambda表达式的闭包特性,用[&var]传出值。

    6
  • Luca
    回答一下第一个问题,不知是否正确:for_each循环不能完全代替for循环,比如在for循环中可以使用break跳出,而在for_each中在语法层面是没有跳出的,如果要跳出的话,可能需要借助异常机制了。 当然,应用for_each的函数式设计思想,也不应出现需要跳出循环的情况。 请老师与大家指正!

    作者回复: 在lambda表达式里可以用return,这样就可以结束循环,实现类似break的效果。

    5
    6
  • l c
    是从Java/Python转的c++,之前对c++其实是抱有一些成见的,大概就是难学难写,很古板很“笨重”。但是越学越发现c++是一个非常全能的语言,有一种什么都给你了随便你干什么的感觉,而且随着协议不断在更新这些工具。 觉得c++远没有到过时的时候,依然有它的活力啊。

    作者回复: 自由的哲学思想贯彻于C++始终,真的是感觉非常好,自由不受约束。

    4
  • EncodedStar
    用c++很多年了,确实会遇到手写类似标准库的函数,手写完之后才发现标准库有同样功能高效的函数,简直让人感觉是闭门造车,哭笑不得。 既然老师文章都提到以后尽量用for_each,我也觉得就可以替代for,以后尽量用老师教的,还有就是小技巧很实用!

    作者回复: 有时间多看看标准库文档,还有参考书,就可以少造些轮子,让自己也轻松一点。

    2
    4
  • EncodedStar
    这个标题成功吸引了我。

    作者回复: 希望大家都能多用算法,少写for。

    4
  • flying
    老师,对于多层map有没有好的解决方案: 比如: typedef std::map<sd::string, std::map<std::string, std::map<string, Info>> Firm2Cus2CommInfo; 然后对这个三级map中的Info进行操作,同时还会用到第一级、第二级的key。 感觉用for_each不太好实现。 用map的原因是,方便查询,通过key就能获取到结果。 但是用for的话,就是好多层for,看着难受。 老师有没有好的解决方法呢?

    作者回复: 这个实际上是数据结构的问题了,比如像json,就只能是这样的多层Key-Value,如果想要简化,就要从需求、设计等更前面的地方入手,而不是纠结于C++的容器、算法。

    3
  • 怪兽
    老师,在实践中遇到的2个问题: 1. 一个线程中,每间隔几秒调用sort,对vector中的元素进行排序。其他N个线程依据某种条件,从该vector容器中取出元素。对着这样的操作,vector容器作为公共资源需要上锁吗?也就是说sort是只读算法吗? 2. set/map中的lower_bound和upper_bound成员函数,也都是二分查找法吗?它们和find成员函数的查找效率哪个更高,或者哪个更好?

    作者回复: 1.sort不是只读算法,这种多线程操作容器,要线程安全就必须要加锁。 2.它们都是二分查找,效率一样,但效果是不同的。find返回的是否找到,lower_bound和upper_bound返回的是上下界。

    3
  • KevinJ
    C++17 允许并行策略 但是gcc9下需要引进intel TBB。也可以使用gnu自带的并行算法库拓展 但是必须开启fopenmp。但是在gcc11下就不用了 直接开启C++20标准然后include execution就好。

    作者回复: 最新的C++编译器能省很多事情。

    1
  • Stephen
    1.感觉for_each不能够完全替代for循环,就像if-else,break,continue这些for_each没法用. 2.根据自己的需求选择合适的算法: 排序中: 只是找出前几名的,选择partial_sort;而如果选出第一名和最后一名采用minmax_element;对于list容器,使用成员函数sort;有序容器map,set已经排好序了,直接迭代就可. 查找中: 需要先排好序的: 二分查找binary_search只能够告知元素是否存在;真正好用的还是lower_bound和upper_bound分别是返回该值的下界位置和上界位置(后一个位置); 有序的set/map,提供等价的成员函数find/lower_bound/upper_bound. 不需要排序的: find,search

    作者回复: 总结的很好,for_each算法顾名思义,就是专门为遍历容器所设计的,所以如果有一些特殊需求就不太合适了。 不过如果在for_each里用return,可以近似实现break的效果。

    2
    1
收起评论
显示
设置
留言
24
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部