倍（物理核心数量）才算理想加速比。 加速曲线 • funcA 用了 2 核就饱和。 • funcB 用了 4 核才饱和。 • funcC 用了 6 核才饱和。 • 结论：要想利用全部 CPU 核心，避免 mem-bound ，需要 func 里有足够的计算 量。 • 当核心数量越多， CPU 计算能力越强，相 对之下来不及从内存读写数据，从而越容 易 mem-bound 。 1 2 4 • 因此，数据小到装的进二级缓存，则最大带 宽就取决于二级缓存的带宽。稍微大一点则 只能装到三级缓存，就取决于三级缓存的带 宽。三级缓存也装不下，那就取决于主内存 的带宽了。 • 结论：要避免 mem-bound ，数据量尽量足 够小，如果能装的进缓存就高效了。 L2: 256 KB L3: 12 MB 缓存的工作机制：读 • 缓存中存储的数据结构： • struct CacheEntry 64 字节都被读取到缓存了，但实际只用到了其中 4 字节，之 后又没用到剩下的 60 字节，导致浪费了 94% 的带宽。 • 虽说连续、顺序访问是最理想的，然而在使用哈希表等数据结构中，不 可避免的会通过哈希函数得到随机的地址来访问，且 Value 类型可能小 于 64 字节，浪费部分带宽。怎么办？ 解决：按 64 字节分块地随机访问 • 解决方法就是，把数据按 64 字节大小分块。随

. . . . . . . . . . . . . . . . . . . . . 54 3.3 数字编码 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4 字符编码 * . . . . . . . . . . . . . . . . . . . . . . . . . 的是选读章节，内容相对困难。如果你的时间有限，可以先跳过。 ‧ 重要专有名词及其英文翻译会用「」 括号标注，例如「数组 array」 。建议记住它们，以便阅读文献。 ‧ 专有名词和有特指含义的词句会使用“引号” 标注，以避免歧义。 ‧ 重要名词、重点内容和总结性语句会 加粗，这类文字值得特别关注。 ‧ 当涉及编程语言之间不一致的名词时，本书均以 Python 为准，例如使用 None 来表示“空”。 ‧ 本书部分 源，对比不同算法之间的效率。 复杂度是个数学概念，对于初学者可能比较抽象，学习难度相对较高。从这个角度看，复杂度分析可能不太 适合作为最先介绍的内容。然而，当我们讨论某个数据结构或算法的特点时，难以避免要分析其运行速度和 空间使用情况。 综上所述，建议你在深入学习数据结构与算法之前，先对复杂度分析建立初步的了解，以便能够完成简单算 法的复杂度分析。 2.2 迭代与递归 在算法中，重复执行

. . . . . . . . . . . . . . . . . . . . . 52 3.3 数字编码 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.4 字符编码 * . . . . . . . . . . . . . . . . . . . . . . . . . hello‑algo.com 4 0.2.1 行文风格约定 ‧ 标题后标注 * 的是选读章节，内容相对困难。如果你的时间有限，建议可以先跳过。 ‧ 专有名词和有特指含义的词句会使用“双引号” 标注，以避免歧义。 ‧ 重要专有名词及其英文翻译会用「」 括号标注，例如「数组 array」 。建议记住它们，以便阅读文献。 ‧ 加粗的文字 表示重点内容或总结性语句，这类文字值得特别关注。 ‧ 当涉及到编程语言之间不一致的名词时，本书均以 源，对比不同算法之间的效率。 复杂度是个数学概念，对于初学者可能比较抽象，学习难度相对较高。从这个角度看，复杂度分析可能不太 适合作为最先介绍的内容。然而，当我们讨论某个数据结构或算法的特点时，难以避免要分析其运行速度和 空间使用情况。 综上所述，建议你在深入学习数据结构与算法之前，先对复杂度分析建立初步的了解，以便能够完成简单算 法的复杂度分析。 2.2 迭代与递归 在数据结构与算法中

. . . . . . . . . . . . . . . . . . . . 39 3.3. 数字编码 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.4. 字符编码 * . . . . . . . . . . . . . . . . . . . . . . . . . Array」 。请务必记住这些名词，包括英文翻译，以 便后续阅读文献时使用。 ‧ 加粗的文字 表示重点内容或总结性语句，这类文字值得特别关注。 ‧ 专有名词和有特指含义的词句会使用“双引号” 标注，以避免歧义。 ‧ 涉及到编程语言之间不一致的名词，本书均以 Python 为准，例如使用 None 来表示“空”。 ‧ 本书部分放弃了编程语言的注释规范，以换取更加紧凑的内容排版。注释主要分为三种类型：标题注 我们能够对比不同算法之间的效率。 复杂度是个数学概念，对于初学者可能比较抽象，学习难度相对较高。从这个角度看，复杂度分析可能不太 适合作为第一章的内容。然而，当我们讨论某个数据结构或算法的特点时，我们难以避免要分析其运行速度 和空间使用情况。因此，在深入学习数据结构与算法之前，建议读者先对复杂度建立初步的了解，并能够完 成简单案例的复杂度分析。 2.2. 时间复杂度 2.2.1. 统计算法运行时间

. . . . . . . . . . . . . . . . . . . . . 54 3.3 数字编码 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4 字符编码 * . . . . . . . . . . . . . . . . . . . . . . . . . PDF 版）或添加下划线（网页版），例如数组（array）。建议记住它们， 以便阅读文献。 ‧ 重点内容和总结性语句会 加粗，这类文字值得特别关注。 ‧ 有特指含义的词句会使用“引号”标注，以避免歧义。 ‧ 当涉及编程语言之间不一致的名词时，本书均以 Python 为准，例如使用 None 来表示“空”。 ‧ 本书部分放弃了编程语言的注释规范，以换取更加紧凑的内容排版。注释主要分为三种类型：标题注 源，对比不同算法之间的效率。 复杂度是个数学概念，对于初学者可能比较抽象，学习难度相对较高。从这个角度看，复杂度分析可能不太 适合作为最先介绍的内容。然而，当我们讨论某个数据结构或算法的特点时，难以避免要分析其运行速度和 空间使用情况。 综上所述，建议你在深入学习数据结构与算法之前，先对复杂度分析建立初步的了解，以便能够完成简单算 法的复杂度分析。 2.2 迭代与递归 在算法中，重复执行

find/replace/substr…… • string 可以通过 s.c_str() 重新转换回古板的 const char * 。 • string 在离开作用域时自动释放内存 (RAII) ，不用手动 free 。 C++ 字符串和 C 字符串的不同 • C 语言字符串是单独一个 char *ptr ，自动以 ‘ \0’ 结尾。 • C++ 字符串是 string 类，其成员有两个： char • 而且即使搞错了也能正常编译通过（一些高级的编译器会 给出警告），但是运行结果不对，或者还有可能崩溃。 泛型的 iostream 应运而生 • 得益于 C++ 的重载技术， cout 不用你手动指定类型，他 会自动识别参数的类型，帮你调用相应的格式化函数。 c_str 和 data 的区别 • s.c_str() 保证返回的是以 0 结尾的字符串首地址指针，总长度为 s.size() std::string 定义很多个不同的 + 重载，每个针对不同的数字类 型（ int 、 float 、 double ）排列组合，但是这样没有可扩展性，而且影响编 译速度。 • 所以 cpp 说，你必须手动把 42 先转换为字符串，然后再和已有的字符串相 加： • “you have ” + std::to_string(42) + “ yuan” std::to_string 数字转字符串 •

. . . . . . . . . . . . . . . . . . . . . 54 3.3 数字编码 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4 字符编码 * . . . . . . . . . . . . . . . . . . . . . . . . . PDF 版）或添加下划线（网页版），例如数组（array）。建议记住它们， 以便阅读文献。 ‧ 重点内容和总结性语句会 加粗，这类文字值得特别关注。 ‧ 有特指含义的词句会使用“引号”标注，以避免歧义。 ‧ 当涉及编程语言之间不一致的名词时，本书均以 Python 为准，例如使用 None 来表示“空”。 ‧ 本书部分放弃了编程语言的注释规范，以换取更加紧凑的内容排版。注释主要分为三种类型：标题注 源，对比不同算法之间的效率。 复杂度是个数学概念，对于初学者可能比较抽象，学习难度相对较高。从这个角度看，复杂度分析可能不太 适合作为最先介绍的内容。然而，当我们讨论某个数据结构或算法的特点时，难以避免要分析其运行速度和 空间使用情况。 综上所述，建议你在深入学习数据结构与算法之前，先对复杂度分析建立初步的了解，以便能够完成简单算 法的复杂度分析。 2.2 迭代与递归 在算法中，重复执行

的发展，使得这门古老而又新颖的语言更加充满活力。 目标读者 1. 本书假定读者已经熟悉了传统 C++ ，至少在阅读传统 C++ 代码上不具备任何困难。换句话说， 那些长期使用传统 C++ 进行编码的人、渴望在短时间内迅速了解现代 C++ 特性的人非常适合 阅读本书； 2. 本书一定程度上介绍了一些现代 C++ 的黑魔法，但这些魔法毕竟有限，不适合希望进阶学习现代 C++ 的读者，本书的定位系现代 1.1 被弃用的特性 在学习现代 C++ 之前，我们先了解一下从 C++11 开始，被弃用的主要特性： 注意：弃用并非彻底不能用，只是用于暗示程序员这些特性将从未来的标准中消失，应该尽 量避免使用。但是，已弃用的特性依然是标准库的一部分，并且出于兼容性的考虑，大部分 特性其实会『永久』保留。 • 不再允许字符串字面值常量赋值给一个 char *。如果需要用字符串字面值常量赋值和初始化一个 从现在开始，你的脑子里应该树立『C++ 不是 C 的一个超集』这个观念（而且从一开始就不是， 后面的进一步阅读的参考文献中给出了 C++98 和 C99 之间的区别）。在编写 C++ 时，也应该尽可能 的避免使用诸如 void* 之类的程序风格。而在不得不使用 C 时，应该注意使用 extern "C" 这种特性， 将 C 语言的代码与 C++ 代码进行分离编译，再统一链接这种做法，例如： // foo

令解码和指令缓存的压力等原因，出现加速超过 4 倍的情况。 第 1 章：化简 编译器优化：代数化简 编译器优化：常量折叠 编译器优化：举个例子 编译器优化：我毕竟不是万能的 结论：尽量避免代码复杂化，避免使用会造 成 new/delete 的容器。 简单的代码，比什么优化手段都强。 造成 new/delete 的容器：我是说，内存分配在堆上的容器 • 存储在堆上（妨碍优化）： • vector 的函数体定义，就会自动内联 内联与否和 inline 没关系，内联与否只取决于是否在同文件，且函数体够小 要性能的，定义在头文件声明为 static 即可，没必要加 inline 的 static 纯粹是为了避免多个 .cpp 引用同一个头文件造成冲突，并不是必须 static 才内 联 如果你不确定某修改是否能提升性能，那你最好实际测一下，不要脑内模拟 inline 在现代 C++ 中有其他含义，但和内联没有关系，他是一个迷惑性的名字 持的指令。老师的电脑支持 AVX 指令集，所 以他用了。不过注意这样编译出的程序，可能 放到别人不支持 AVX 的电脑上没法运行。 数组清零：自动调用标准库的 memset memcpy 同理，不必为了高效，手动改 写成对 memcpy/memset 的调用，影响 可读性。编译器会自动分析你是在做拷贝 或是清零，并优化成对标准库这俩的调用 。 从 0 到 1024 填充： SIMD 加速 paddd ：四个

C++ 有哪些面向对象思想？ C++ 思想：封装 比如要表达一个数组，需要：起始地址指针 v ，数组大小 nv 将多个逻辑上相关的变量包装成一个类 因此 C++ 的 vector 将他俩打包起来，避免程序员犯错 封装：不变性 比如当我要设置数组大小为 4 时，不能只 nv = 4 还要重新分配数组内存，从而修改数组起始地址 v 常遇到：当需要修改一个成员时，其他也成员需要被修改，否则出错 还包括了用于销毁的解构函数（ destructor ） 离开 {} 作用域自动释放 手动释放 RAII ：避免犯错误 与 Java ， Python 等垃圾回收语言不同， C++ 的 解构函数是显式的，离开作用域自动销毁，毫不含 糊（有好处也有坏处，对高性能计算而言利大于 弊） 如果没有解构函数，则每个带有返回的分 支都要手动释放所有之前的资源 : RAII ：异常安全（ exception-safe 自定义构造函数：无参数（使用初始化表达式） 为什么需要初始化表达式？ 1. 假如类成员为 const 和引用 2. 假如类成员没有无参构造函数 3. 避免重复初始化，更高效 自定义构造函数：多个参数 自定义构造函数：单个参数 自定义构造函数：单个参数（陷阱） 自定义构造函数：单个参数（避免陷阱） 避免陷阱体现在哪里？ • 加了 explicit 表示必须用 () 强制转换。 • 否则 show(80) 也能编译通过！