-D 选项：指定配置变量（又称缓存变量） • 可见 CMake 项目的构建分为两步： • 第一步是 cmake -B build ，称为配置阶段（ configure ），这时只检测环境并生成构建规则 • 会在 build 目录下生成本地构建系统能识别的项目文件（ Makefile 或是 .sln ） • 第二步是 cmake --build build ，称为构建阶段（ build ），这时才实际调用编译器来编译代码 Linux 的 make ， Windows 的 MSBuild ），从而让构建规则可以只写一份，跨平 台使用。 • 过去的软件（例如 TBB ）要跨平台，只好 Makefile 的构建规则写一份， MSBuild 也写一份 。 • 现在只需要写一次 CMakeLists.txt ，他会视不同的操作系统，生成不同构建系统的规则文件。 • 那个和操作系统绑定的构建系统（ make 、 MSBuild MSBuild ）称为本地构建系统（ native buildsystem ）。 • 负责从 CMakeLists.txt 生成本地构建系统构建规则文件的，称为生成器（ generator ）。 -G 选项：指定要用的生成器 • Linux 系统上的 CMake 默认用是 Unix Makefiles 生成器； Windows 系统默认是 Visual Studio 2019 生成器； MacOS

表格，其中每个单元格都可以存储 1 byte 的数据，在算法运 行时，所有数据都被存储在这些单元格中。 系统通过「内存地址 Memory Location」来访问目标内存位置的数据。计算机根据特定规则给表格中每个 单元格编号，保证每块内存空间都有独立的内存地址。自此，程序便通过这些地址，访问内存中的数据。 Figure 3‑2. 内存条、内存空间、内存地址 内存资源是设计数据结构与算法的重 ) 添加元素 ?(?) ?(1) 删除元素 ?(?) ?(1) 59 5. 栈与队列 5.1. 栈 「栈 Stack」是一种遵循「先入后出 first in, last out」数据操作规则的线性数据结构。我们可以将栈类比为放 在桌面上的一摞盘子，如果需要拿出底部的盘子，则需要先将上面的盘子依次取出。 “盘子”是一种形象比喻，我们将盘子替换为任意一种元素（例如整数、字符、对象等），就得到了栈数据结 得到了栈数据结 构。 我们将这一摞元素的顶部称为「栈顶」，将底部称为「栈底」，将把元素添加到栈顶的操作称为「入栈」，将删除 栈顶元素的操作称为「出栈」。 Figure 5‑1. 栈的先入后出规则 5.1.1. 栈常用操作 栈的常用操作见下表（方法命名以 Java 为例）。 方法 描述 时间复杂度 push() 元素入栈（添加至栈顶） ?(1) pop() 栈顶元素出栈 ?(1)

为什么需要构建系统（ Makefile ） • 文件越来越多时，一个个调用 g++ 编译链接会变得很麻烦。 • 于是，发明了 make 这个程序，你只需写出不同文件之间的依赖关系，和生成各文件的规则。 • > make a.out • 敲下这个命令，就可以构建出 a.out 这个可执行文件了。 • 和直接用一个脚本写出完整的构建过程相比， make 指明依赖关系的好处： 1. 当更新了 hello.o ，而不需要把 main.o 也重新编译一遍。 2. 能够自动并行地发起对 hello.cpp 和 main.cpp 的编译，加快编译速度（ make -j ）。 3. 用通配符批量生成构建规则，避免针对每个 .cpp 和 .o 重复写 g++ 命令（ %.o: %.cpp ）。 • 但坏处也很明显： 1. make 在 Unix 类系统上是通用的，但在 Windows 则不然。 2 2. 需要准确地指明每个项目之间的依赖关系，有头文件时特别头疼。 3. make 的语法非常简单，不像 shell 或 python 可以做很多判断等。 4. 不同的编译器有不同的 flag 规则，为 g++ 准备的参数可能对 MSVC 不适用。 构建系统的构建系统（ CMake ） • 为了解决 make 的以上问题，跨平台的 CMake 应运而生！ • make 在 Unix 类系统上是通用的，但在

表格，其中每个单元格都可以存储 1 byte 的数据，在算法运 行时，所有数据都被存储在这些单元格中。 系统通过「内存地址 Memory Location」来访问目标内存位置的数据。计算机根据特定规则给表格中每个 单元格编号，保证每块内存空间都有独立的内存地址。自此，程序便通过这些地址，访问内存中的数据。 Figure 3‑2. 内存条、内存空间、内存地址 内存资源是设计数据结构与算法的重 ) 添加元素 ?(?) ?(1) 删除元素 ?(?) ?(1) 59 5. 栈与队列 5.1. 栈 「栈 Stack」是一种遵循「先入后出 first in, last out」数据操作规则的线性数据结构。我们可以将栈类比为放 在桌面上的一摞盘子，如果需要拿出底部的盘子，则需要先将上面的盘子依次取出。 “盘子”是一种形象比喻，我们将盘子替换为任意一种元素（例如整数、字符、对象等），就得到了栈数据结 得到了栈数据结 构。 我们将这一摞元素的顶部称为「栈顶」，将底部称为「栈底」，将把元素添加到栈顶的操作称为「入栈」，将删除 栈顶元素的操作称为「出栈」。 Figure 5‑1. 栈的先入后出规则 5.1.1. 栈常用操作 栈的常用操作见下表，方法名需根据编程语言来确定，此处我们以常见的 push , pop , peek 为例。 方法 描述 时间复杂度 push() 元素入栈（添加至栈顶）

表格，其中每个单元格都可以存储 1 byte 的数据，在 算法运行时，所有数据都被存储在这些单元格中。 系统通过「内存地址 Memory Location」来访问目标内存位置的数据。计算机根据特定规则为表格中的每 个单元格分配编号，确保每个内存空间都有唯一的内存地址。有了这些地址，程序便可以访问内存中的数 据。 Figure 3‑2. 内存条、内存空间、内存地址 内存是所有程序的共享资源 来表示一个字符，根据字符的复杂性而变。ASCII 字符只需要 1 个字节，拉丁字母和希腊字母需要 2 个字节， 常用的中文字符需要 3 个字节，其他的一些生僻字符需要 4 个字节。 UTF‑8 的编码规则并不复杂，分为两种情况： ‧ 对于长度为 1 字节的字符，将最高位设置为 0 、其余 7 位设置为 Unicode 码点。值得注意的是，ASCII 字符在 Unicode 字符集中占据了前 128 ? 位设置为 1 比较容易理解，可以向系统指出字符的 长度为 ? 。那么，为什么要将其余所有字节的高 2 位都设置为 10 呢？实际上，这个 10 能够起到校验符的作 用，因为在 UTF‑8 编码规则下，不可能有字符的最高两位是 10 。这是因为长度为 1 字节的字符的最高一位 是 0 。假设系统从一个错误的字节开始解析文本，字节头部的 10 能够帮助系统快速的判断出异常。 Figure 3‑8

unsigned long 类型 • 32ULL 是 unsigned long long 类型 • 小写也是可以的： • 32ull 也是 unsigned long long 类型 字面常量的特殊规则：如果 int 表示不下，则自动选择较大的类型 标准化的类型： stdint.h • 而实际上，尽管主流操作系统上 int 都是 32 位的， C 语言标准并没有规定 int 就是 32 位 的。 short ，根据补码的规则仍是 - 128 。 实验：不同大小之间的整数互转 • 例如 char 类型的 127 是 011111111 • 强制转换为 short 后是 00000000 011111111 • 可见符号位还是被完全填充到了 short 的前一个字节 ，这次因为符号位是 0 ，所以 short 的高位也全部 填满了 0 ，对值没有影响，根据补码的规则仍是 127 。 • 例如 char 类型的 -128 是 10000000 • 强制转换为 short 后是 00000000 10000000 • 可见 short 的前一个字节被填满了 0 ，根据补码的 规则他是一个正数 128 。 实验：自动类型提升（ type promotion ） • 一个较小类型的 short 和较大类型的 int 相加会得到什么类型？会得到 int 类型。 • 结论：小类型和大类型做数学运算（

一块内存空间。我们可以将内存想象成一个巨大的 Excel 表格，其中每个单元格都可以存储一定大小的数据， 在算法运行时，所有数据都被存储在这些单元格中。 系统通过内存地址来访问目标位置的数据。如图 3‑2 所示，计算机根据特定规则为表格中的每个单元格分配 编号，确保每个内存空间都有唯一的内存地址。有了这些地址，程序便可以访问内存中的数据。 图 3‑2 内存条、内存空间、内存地址 内存是所有程序的共享资源，当某块内存被某 来表示一个字符，根据字符的复杂性而变。ASCII 字符只需要 1 个字节，拉丁字母和希腊字母需要 2 个字节， 常用的中文字符需要 3 个字节，其他的一些生僻字符需要 4 个字节。 UTF‑8 的编码规则并不复杂，分为以下两种情况。 ‧ 对于长度为 1 字节的字符，将最高位设置为 0、其余 7 位设置为 Unicode 码点。值得注意的是，ASCII 字符在 Unicode 字符集中占据了前 128 10 呢？实际上，这个 10 能够起到校验符的作用。假设系统从 一个错误的字节开始解析文本，字节头部的 10 能够帮助系统快速的判断出异常。 之所以将 10 当作校验符，是因为在 UTF‑8 编码规则下，不可能有字符的最高两位是 10 。这个结论可以用 反证法来证明：假设一个字符的最高两位是 10 ，说明该字符的长度为 1 ，对应 ASCII 码。而 ASCII 码的最 高位应该是 0 ，与假设矛盾。

Excel 表格，其中每个单元格都可以存储一定大 小的数据。 第 3 章 数据结构 hello‑algo.com 53 系统通过内存地址来访问目标位置的数据。如图 3‑2 所示，计算机根据特定规则为表格中的每个单元格分配 编号，确保每个内存空间都有唯一的内存地址。有了这些地址，程序便可以访问内存中的数据。 图 3‑2 内存条、内存空间、内存地址 � 值得说明的是，将内存比作 Excel 字符只需 1 字节，拉丁字母和希腊字母需要 2 字节，常用 第 3 章 数据结构 hello‑algo.com 62 的中文字符需要 3 字节，其他的一些生僻字符需要 4 字节。 UTF‑8 的编码规则并不复杂，分为以下两种情况。 ‧ 对于长度为 1 字节的字符，将最高位设置为 0 ，其余 7 位设置为 Unicode 码点。值得注意的是，ASCII 字符在 Unicode 字符集中占据了前 128 10 呢？实际上，这个 10 能够起到校验符的作用。假设系统从 一个错误的字节开始解析文本，字节头部的 10 能够帮助系统快速判断出异常。 之所以将 10 当作校验符，是因为在 UTF‑8 编码规则下，不可能有字符的最高两位是 10 。这个结论可以用 反证法来证明：假设一个字符的最高两位是 10 ，说明该字符的长度为 1 ，对应 ASCII 码。而 ASCII 码的最 高位应该是 0 ，与假设矛盾。

Excel 表格，其中每个单元格都可以存储一定大 小的数据。 第 3 章 数据结构 hello‑algo.com 53 系统通过内存地址来访问目标位置的数据。如图 3‑2 所示，计算机根据特定规则为表格中的每个单元格分配 编号，确保每个内存空间都有唯一的内存地址。有了这些地址，程序便可以访问内存中的数据。 图 3‑2 内存条、内存空间、内存地址 Tip 值得说明的是，将内存比作 Excel 字符只需 1 字节，拉丁字母和希腊字母需要 2 字节，常用 第 3 章 数据结构 hello‑algo.com 62 的中文字符需要 3 字节，其他的一些生僻字符需要 4 字节。 UTF‑8 的编码规则并不复杂，分为以下两种情况。 ‧ 对于长度为 1 字节的字符，将最高位设置为 0 ，其余 7 位设置为 Unicode 码点。值得注意的是，ASCII 字符在 Unicode 字符集中占据了前 128 10 呢？实际上，这个 10 能够起到校验符的作用。假设系统从 一个错误的字节开始解析文本，字节头部的 10 能够帮助系统快速判断出异常。 之所以将 10 当作校验符，是因为在 UTF‑8 编码规则下，不可能有字符的最高两位是 10 。这个结论可以用 反证法来证明：假设一个字符的最高两位是 10 ，说明该字符的长度为 1 ，对应 ASCII 码。而 ASCII 码的最 高位应该是 0 ，与假设矛盾。

的。这样的场景其实有很多很多，所以匿名函数几乎是现代编程语言的标配。 基础 Lambda 表达式的基本语法如下： [捕获列表](参数列表) mutable(可选) 异常属性 -> 返回类型 { // 函数体 } 上面的语法规则除了 [捕获列表] 内的东西外，其他部分都很好理解，只是一般函数的函数名被略 去，返回值使用了一个 -> 的形式进行（我们在上一节前面的尾返回类型已经提到过这种写法了）。 所谓捕获列表，其实可以理解为参数的一种类型，Lambda pass(l) 而言，l 是一个左值，为什么 会成功传递给 pass(T&&) 呢？ 这是基于引用坍缩规则的：在传统 C++ 中，我们不能够对一个引用类型继续进行引用，但 C++ 由 于右值引用的出现而放宽了这一做法，从而产生了引用坍缩规则，允许我们对引用进行引用，既能左引 用，又能右引用。但是却遵循如下规则： 函数形参类型 实参参数类型 推导后函数形参类型 T& 左引用 T& T& 右引用 T& 则用于检查类型推导是否正确，在 std::forward 的第二个实现中检查了接收到的值确实是一个左值，进 而体现了坍缩规则。 当 std::forward 接受左值时，_Tp 被推导为左值，所以返回值为左值；而当其接受右值时，_Tp 被 推导为右值引用，则基于坍缩规则，返回值便成为了 && + && 的右值。可见 std::forward 的原理在于 巧妙的利用了模板类型推导中产生的差异。