C++ 基础知识指南 - 洛谷保存站

C++ 是许多信息学竞赛选手最熟悉的编程语言。日常训练中，我们可能只用到循环、数组这些基础功能，但这位朝夕相处的"老朋友"，其实藏着更多值得探索的奥秘。

也许你曾见过题解中神奇的语法"黑科技"，也许你被未定义行为导致的"玄学问题"困扰过，也许你面对突如其来的编译错误百思不得其解...

掌握这些知识，不会让你在赛场多拿几分，但能让你更加了解这个朝夕相处的代码伙伴。它们或许能帮你理解那些精妙的语言特性，或许能让你接触更现代的编程思维，又或许，只是满足你对技术世界的好奇心。

这个专栏并不是“语法大师课”，而是一次共同探索的旅程。我也只是一个 C++ 初学者，尝试分享自己理解中的一些点滴。

我们将从基础出发，逐步走进 C++ 的深处。虽然我的理解有限，无法覆盖那些艰深的内容。无论如何，都希望这些分享能为你打开一扇窗，了解一些可能平时了解不到的小知识，让你对这门语言多一分理解，这便是这篇专栏的最大意义。

# 声明
本文的绝大部分内容为本人原创，由 DeepSeek、Qwen、ChatGPT 等 AI 提供核查（无 AI 生成内容）。

目前，洛谷绝大多数关于 C++ 语法的专栏都位于“科技·工程”分区，同时这些知识能够对读者的工程代码编程能力提供一些帮助，所以我选择投递到该分区。我自认为这篇专栏与该板块有足够的关联。

本文最近更新于 2025/07/21。

# 前置知识

在正式开始之前，先来了解一些相关的概念。

## 编程工具

### 编译器

编译器是一种软件，负责将源代码编译成可执行文件。可执行文件（例如 Windows 系统的 exe 文件）可以被操作系统直接执行。

GCC（GNU Compiler Collection）是算法竞赛中最常用的 C++ 编译器。

代码编辑器负责帮助程序员编写代码。从定义上讲，记事本就可以算作编辑器。编辑器不负责代码的运行。

Sublime Text、Visual Studio Code 等都是常见的代码编辑器。

### 集成开发环境

集成开发环境（IDE）是一种集成了多种功能的工具，通常包含代码编写、编译运行、调试等功能。现代的代码编辑器，通过插件通常也能实现类似 IDE 的功能。

### 调试器

调试器可以帮助开发人员调试代码，通常包含断点（在程序运行到某处时停止运行）、逐行调试、查看变量值、检查运行时错误位置等功能。

gdb 是一个常用的调试器，并且**在 NOI Linux 的考试环境下可用**。

## C++ 标准

C++ 语言一直在发布新的标准，从 2011 年开始，每 3 年都会发布一个新标准。

当前的 C++ 标准有：C++98（C++03）、C++11、C++14、C++17、C++20、C++23，下一个标准是 C++26。

其中 C++03 只是在 C++98 的基础上做了简单的修订，并没有大幅度的更改。

本文讲述的内容，如果没有标注，默认是 C++98 就存在的。由于内容繁多，这部分标注可能存在遗漏，但是我会尽力保证所有 C++17 及以后的特性都标注出来（即不能在 NOI 系列考试中使用的）。

## 编译器优化（O2 优化）

大多数的现代编译器都提供了优化选项。在代码不存在未定义行为的情况下，编译器优化选项可以保证程序行为正确，并且优化代码的运行速度。

常见的优化选项有 `-O0`（无优化）、`-O1`、`-O2`、`-O3`、`-Ofast` 等，优化效果通常是递增的。

很多情况下，一些简单的优化在开启优化选项 `-O2` 之后，都会被编译器自动完成（例如简单函数调用造成的开销，绝大多数情况下都会被内联）。

开启编译器优化后，可能让存在问题的代码行为变得奇怪，同时会影响调试器的使用。所以在调试时建议禁用优化。

**目前，在 CCF 组织的比赛中，均使用 C++14 标准，开启 O2 优化。**

# 基础语法

## 输入输出

```cpp
#include <iostream>
using namespace std;

int main() {
    cout << "Hello World!" << endl;
    return 0;
}
```

C++ 标准库中，主要有这几类输入输出方式：

-   C 风格的输入输出：`scanf`，`printf`，`getchar`，`putchar`，`puts` 等。
-   C++ iostream：`cin`，`cout` 等。
-   C++23 print：`print`，`println` 等。

在这些标准库提供的工具中，我最常用的是 iostream。它较为简单，并且可以保证类型安全，无需考虑占位符和实际类型的配套问题。而 C++23 的 print 尚未受到广泛支持。

iostream 采用重载的右移（有时又称“流输入”）和左移（“流输出”）运算符进行输入输出。代码如下：

```cpp
int x;
std::cin >> x;  // 输入
std::cout << x;  // 输出
```

`cout` 可以通过输出一些操纵符，来进行一定程度的格式化输出。大多数操纵符在头文件 `iomanip` 中定义。例如，如下代码可以保留 2 位小数输出：

```cpp
std::cout << std::fixed << std::setprecision(2) << 3.1415;  // 3.14
```

执行以上代码以后，接下来所有的浮点数输出都会维持这样的格式。

iostream 最大的问题可能就是它在默认情况下效率很低。**可以通过以下代码来加速**：

```cpp
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
```

这种方法通常叫做“关闭同步流”，可以大幅度提升 cin 和 cout 的速度。

第一行的原理是，默认情况下 C 风格的输入输出会维护一个缓冲区来加速（即内容不会立即输出到屏幕，而是存到缓冲区中，缓冲区满或者手动刷新再一次性输出）。而 iostream 为了和 C 兼容，会在每一次输入输出时都刷新缓冲区，导致额外开销。调用了 `ios::sync_with_stdio(false)` 之后就不会每次刷新了。

第二行的原理是，默认情况下 cin 会和 cout 互相绑定，在每次使用 cin 输入时都刷新 cout 的缓冲区。这样可以避免交替使用输入输出时的额外刷新开销。

由于 `endl` 会刷新缓冲区，使用 `'\n'` 而不是 `endl` 换行也会加速输出。

经过这样优化的 `cin` 和 `cout`，速度会略快于 `scanf` 和 `printf`。

**关闭同步流的情况下，iostream 和 C 风格输入输出不能混用**。否则可能会导致多次输出的结果乱序。

有些时候，一些题目会要求输入不定量的信息。这种输入之所以可行，是因为从控制台输入信息，本质上是从一个虚拟的文件 `stdin` 输入。文件是有边界的，读到文件结尾就会获得 EOF 信息（End Of File），无法继续读入。

`cin` 可以通过 `cin.good()`（返回 `true`/`false`）来判断是否处于正常状态。同时 `cin.eof()` 可以判断是否到达文件末尾，`cin.fail()` 和 `cin.bad()` 可以判断是否出现其他的问题，例如读入的整数超过类型上限，或者期望读入整数实际读到字母，将会使得 `cin.fail()` 返回 `true`。

如果 `cin.good()` 返回 `false`，此时将会拒绝接下来的读取操作（变量将会保持原值不被修改）。

在条件判断中，`cin` 对象可以隐式转换为布尔值，即 `cin.good()`。可以通过以下代码来持续读入整数直到文件末尾。在控制台中运行时，可以按下快捷键 Ctrl+Z（Windows）或者 Ctrl+D（Linux）并换行，来手动输入一个 EOF。

```cpp
int x;
while (cin >> x) {  // cin/cout 输入输出之后返回自己
    cout << x << ' ';
}
```

## 未定义行为和错误程序

接下来的代码中，将会涉及“未定义行为”及相关概念。可以参考 [cppreference](https://en.cppreference.com/w/cpp/language/ub.html) 页面。

C++ 的代码可能出现以下类型的错误：

-   **非良构**（ill-formed）。程序存在语法错误，或者可以诊断的语义错误。标准要求编译器对这种行为给出诊断信息，通常会导致编译错误。
-   非良构，但是不要求诊断（no diagnostic required）。有些情况下，程序存在语义错误，但是错误可能在链接时才能发现，或者进行诊断需要的代价过大。这类程序被执行，行为是未定义的。
-   **实现定义行为**（implementation-defined behavior）。程序在不同的实现中（包括编译器、标准库实现、运行时环境等），可能会有不同的行为。但是符合标准的实现需要在文档中说明每种行为的实际效果。
    -   例如，`long` 类型的大小是实现定义的。在常见的实现中，有些是 4 字节，有些是 8 字节。
-   **未指定行为**（unspecified behavior）。程序行为在不同的实现中有所不同，并且实现不需要说明这些行为的效果。
    -   例如，一些情况下的求值顺序，相同的字符串字面量是否指向不同地址。
    -   不应该依赖未指定行为。
-   **未定义行为**（undefined behavior，简称 ub）。程序的行为将不受任何限制。
    -   例如，数组的越界访问，有符号整数溢出，空指针解引用。
    -   实现无需对未定义行为进行诊断（因为有些只能在运行时被发现）。
    -   **未定义行为可能导致任何问题**，编译器也可以基于“程序不存在未定义行为”的假设进行优化。
    -   通常情况下，代码开启编译器优化前后行为不一致，就是由于存在未定义行为。

简单来讲，程序非良构通常会导致编译失败；未定义行为十分危险，必须避免；不应该依赖未指定行为；可以适当依赖实现定义行为。

以下是几个编译器依赖“不会出现未定义行为”，进行优化的例子：

```cpp
bool f(int x) {
    return x + 1 > x;  // 不溢出的情况下，整数 +1 一定大于自身
}
// 可能优化成：
bool f_(int x) {
    return true;
}
```

```cpp
int g(int *ptr) {
    int value = *ptr;  // 已经进行解引用，基于 UB 假设一定不是空指针
    if (ptr == nullptr) {
        return 0;
    } else {
        return value;
    }
}
// 可能优化成：
int g_(int *ptr) {
    return *ptr;
}
```

## 变量

```cpp
#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
    return 0;
}
```

C++ 的“变量”（Variable）是通过标识符引用的对象（Object），指向一个内存中的存储单元，持有的值可以改变。变量几乎是一切数值计算的基础。这个最简单的“两数和问题”中，我们就使用了变量进行计算。

### 变量名

变量名必须是一个合法的“标识符”（[Identifier](https://en.cppreference.com/w/cpp/language/identifiers.html)）。即有以下的要求：

-   首字符必须为英文字母 `A-Za-z` 或下划线 `_`，或其他具有 XID_Start 属性的 Unicode 字符。
-   其余字符必须为英文字母 `A-Za-z` 、数字 `0-9`或下划线 `_`，或其他具有 XID_Continue 属性的 Unicode 字符。

值得注意的是，自 C++11 起，绝大多数语言中的字母（例如中文汉字），甚至表情符号，都是合法的标识符（即上文提到的 Unicode 字符）。GCC 编译器对该功能支持较晚，在 GCC10 以上的版本才可以使用。

除此以外，用户定义的标识符（变量、函数、类型等）不能与[关键字](https://en.cppreference.com/w/cpp/keyword.html)完全相同。以双下划线开头（如 `__reserved`），或者单下划线紧跟大写字母开头（如 `_Reserved`），行为是未定义的。

### 变量作用域

变量的作用域主要分为局部作用域和命名空间作用域等。

在函数等花括号（`{}`）包裹的代码块中定义的变量，具有局部作用域。局部作用域的变量，自声明后开始可见，直到代码块结束。

在命名空间中声明的变量，具有命名空间作用域。这类变量自声明后开始，在命名空间内始终可见，或者通过命名空间名来访问（`ns::name`）。全局作用域可以看作一个特殊的命名空间作用域，它自声明后开始，在全局内始终可见。

不同作用域的同名变量存在“遮蔽”原则，**内层作用域的同名变量会隐藏外层作用域的变量**。

```cpp
#include <iostream>
int x = 0; // 全局变量
int main() {
    std::cout << x << '\n'; // 输出 0
    int x = 1; // 局部变量将会遮蔽全局的 x
    std::cout << x << '\n'; // 输出 1
    std::cout << ::x << '\n'; // 可以通过 ::x 强制指定全局作用域的 x，输出 0
    return 0;
}
```

可以根据以上代码理解这些原则。

类型、函数等的作用域规则，也和变量相同。

#### 命名空间

命名空间（namespace）是 C++ 中用来避免命名冲突的机制，不同命名空间内的变量可以重名。变量、函数、类型等，都可以通过命名空间来组织。

访问一个命名空间内的内容，需要使用作用域解析运算符 `::`。例如上文的 `std::cout` 就是在访问 `std` 命名空间的 `cout` 对象。

可以使用 `using` 语句，引入一个命名空间中的名字。使用 `using namespace` 引入所有名字。

```cpp
namespace A {
    int value;
    int test;
}

namespace B {
    int value;  // 不会发生重名
    int number;
    int example;
}

using A::test;  // 接下来使用 test 可以不指定命名空间
using namespace B;  // 同时引入 B::value, B::number, B::example
```

命名空间可以嵌套，使用 `std::ranges::sort` 这样的方式访问。可以用以下方式创建命名空间别名。

```cpp
namespace rg = std::ranges;
```

C++ 的所有标准库对象，都存在于 `std::` 命名空间中。C 标准库函数（如 `printf`）在全局和 `std` 命名空间中均存在，但是部分函数（尤其是 cmath 中的）会存在少量差异。所以在没有 `using namespace std;` 的情况下，**建议始终使用 `std::` 版本来保证安全**。

```cpp
#include <cmath>

auto main() -> int {
    long long x = -5;
    auto x1 = abs(x);  // int
    auto x2 = std::abs(x);  // long long
}
```

### 存储期

存储期（Storage duration）指定了一个对象的生命周期，即在何时被销毁并回收资源。变量的存储期由定义的方式决定。

C++ 有以下的几种存储期：

-   自动存储期。这是局部变量的默认存储期，会在离开自己的作用域后自动销毁。
-   静态存储期。这是命名空间作用域（包括全局作用域）变量的默认存储期，在程序结束后销毁。
-   动态存储期。通过 `new`、`malloc` 等方式在堆空间动态分配对象的属于动态存储期，需要通过配对的解分配函数来销毁。
-   线程存储期。对于多线程程序，这类对象对每一个线程都会有一个独立的值，生命周期与这个线程相同。

简单来讲，只需要记住以下规则：

-   自动存储期（局部变量），在离开作用域的时候（对应的右花括号）立即销毁，不占用更多内存。
-   静态存储期（全局/命名空间变量，或显式声明 static），在程序结束时统一销毁。
-   还有动态存储期、线程存储期，分别有各自的用途。
-   默认情况下下，自动存储期的变量大小有限（栈空间），但是竞赛场景通常会主动放开限制，不需要在意。

有对应的说明符可以指定存储期。

-   `auto`：**C++11 起含义改变**。此前表示自动存储期。
-   `register`：**在 C++14 起被弃用、C++17 起被移除**。此前用于请求编译器把这个值存储在寄存器中，这个请求可以被忽略。
-   `static`：静态存储期。
-   `thread_local`：线程存储期。
-   `extern`：用于声明一个变量（而不是定义），链接到一个外部的来源。

`mutable` 关键字在 cppreference 中被归类为存储说明符，但是实际不会影响存储期，所以不在此讲述。

尽管 `register` 关键字直到 C++17 才被移除，但是即使在更早的标准中，编译器通常也会忽略它。不要试图使用这个关键字优化性能，这不会有任何作用。

自动存储期的对象将会存储在“栈空间”中，栈空间的容量有限（通常为 8MB），所以定义一些较大的数组，或者递归层数过深，都可能会出现“爆栈”的问题。但是**大部分 OJ 和比赛环境**，包括 CCF 组织的比赛中，**允许程序使用无限的栈空间**（即与程序总体内存限制相等），这些情况下可以放心使用局部数组和递归（局部数组需要手动初始化，推荐直接使用值初始化形式 `int a[maxN]{}`）。

如果想要设置无限栈空间，可以通过如下方式：

-   对于 Windows 系统，编译选项（GCC 为例）添加 `-Wl,-stack=2147483647`。
-   对于 Linux 系统，运行程序前在终端执行 `ulimit -s unlimited`。

全局或命名空间作用域的静态变量，将会在调用主函数之前进行初始化。

可以在局部作用域中通过 `static` 关键字来定义一个静态变量，这个变量将仅会在第一次运行到定义处的时候进行一次初始化，接下来**每次使用都会保有一个相同的值**。可以结合以下代码理解。

```cpp
#include <iostream>

void f() {
    static int count = 0;
    count++;
    std::cout << count << ' ';
    // 静态变量的值不会被清除
}

int main() {
    f(); f(); f(); // 输出 1 2 3
    return 0;
}
```

### 变量初始化

定义一个变量的同时会进行初始化，赋予其一个初始值。C++ 的变量初始化规则十分复杂，接下来我们将会进行一些简单的讲解。

本章节中可能会涉及一些后续章节才出现的知识。如果出现了你不理解的内容，可以暂时忽略。

#### 核心规则概括

核心规则可以大致概括为：

-   零初始化：逐位赋值为 0，全局/静态变量自动执行。
-   默认初始化 `int x`：
    -   类类型（`string`、`set`、`vector` 等），调用默认构造函数。
    -   基本类型，**局部变量的值不确定**，全局/静态变量预先零初始化为 0。
    -   自定义结构体，如果没有提供默认值，默认初始化也是不安全的。
-   值初始化 `int x{}`：
    -   基本类型，初始化为 0。
    -   类类型，调用默认构造。
    -   通常是最安全的初始化方式。
-   直接初始化 `int x(5)`：
    -   直接调用匹配的构造函数。
-   复制初始化 `int x = 5`：
    -   实际行为通常与直接初始化一致。
    -   禁用 `explicit` 构造函数。
    -   经过编译器优化，不会有额外的复制。
-   列表初始化 `int x{5}`：
    -   优先匹配接受 `std::initializer_list` 的构造函数。
    -   禁止窄化转换。

#### 零初始化

零初始化（[Zero-Initialization](https://en.cppreference.com/w/cpp/language/zero_initialization.html)）是将对象逐位赋值为 0 的初始化方式。C++ 中没有专用的零初始化语法，但是其他初始化方式可能包含零初始化。

**所有具有静态存储期的变量**，将会在进行其他初始化之前，先进行一次零初始化。平时常见的结论“全局变量会自动赋值为 0”就是来自这条规则。

#### 默认初始化

默认初始化（[Default-Initialization](https://en.cppreference.com/w/cpp/language/default_initialization.html)）是在没有指定初始化器时的初始化方式。例如以下场景将会执行默认初始化：

```cpp
int x;
auto *ptr = new double;
```

另外，在类的构造函数中，没有在初始化列表中提及的成员，也会执行默认初始化。

```cpp
struct A {
    int data;
    A() {}
};
A p;  // p.data 将会执行默认初始化
```

对类型 `T` 进行默认初始化的效果如下：

-   如果 `T` 是类类型（Class Type，由 `class`、`struct` 或 `union` 关键字定义的类型），则调用默认构造函数（空参数列表），为对象提供初始值。
-   如果 `T` 是数组类型，对数组的每个元素进行默认初始化。
-   否则，**不额外执行初始化**。

**对象在未执行初始化的情况下，将会持有一个不确定的值**，直到这个值被替换。使用这个不确定的值进行任何求值操作，都是未定义行为。

但是由于静态存储期的对象会预先进行一次零初始化，所以这种写法对它们是安全的。

C++26 起规定，对于一个自动存储期的变量，并且没有被标识 `[[indeterminate]]`，将会有以下行为：

-   构成该对象存储的所有字节，填充一个错误值。这个错误值由实现定义，但是与程序状态无关。
-   如果使用错误值进行求值操作，则行为是错误行为（Erroneous Behavior）。错误行为仍然应该被视作不正确的结果，但是标准建议实现对错误行为进行诊断，而非像未定义行为一样假设不会存在并促进优化。

C++26 引入的错误填充值，往往会导致未初始化的对象拥有一个异常值（例如无效指针，或者绝对值很大的整数和浮点数），避免由于“不确定值”有时恰好符合期望，而产生偶发性的错误。

`const` 对象不允许默认初始化。

#### 值初始化

值初始化（[Value-Initialization](https://en.cppreference.com/w/cpp/language/value_initialization.html)）在使用空初始化器构造对象时执行，以下是几种常见的场景：

```cpp
int x{};
auto *ptr = new double();
std::cout << float() /*构造临时对象*/ << '\n';
char arr[100]{};
```

下文中用 `T` 代指对象类型。

有以下特例：

-   如果 `T` 是聚合类型（见下文“聚合初始化”），那么执行聚合初始化。但是这种情况下聚合初始化的行为与值初始化的效果是一致的。
-   如果 `T` 没有默认构造函数，但是有一个接收 `std::initializer_list` 的构造函数，那么执行列表初始化。

值初始化的效果如下：

-   如果 `T` 是类类型，那么：
    -   如果它的默认构造函数不是用户提供的（即自动生成），先执行零初始化。
    -   接下来，执行默认初始化。
-   否则，如果 `T` 是数组类型，值初始化每个元素。
-   否则，对象将会被零初始化。

值初始化在大多数情况下可以保证所有元素被正确初始化（一个反例为上文“默认初始化”章节的 `p.data`）。

#### 聚合初始化

聚合初始化（[Aggregate-Initialization](https://en.cppreference.com/w/cpp/language/aggregate_initialization.html)）是通过初始化列表来初始化聚合类型的过程。这是一种特殊的列表初始化。

##### 聚合类型

聚合类型（Aggregate）是以下类型之一：

-   数组类型
-   符合以下要求的类类型
    -   没有用户声明或继承的构造函数。（C++20 起，此前的要求类似，但是略有不同）
    -   没有私有（private）或受保护（protected）的非静态数据成员。
    -   没有虚基类（virtual），没有私有或受保护的基类。（C++17 起，此前要求没有任何基类）
    -   没有虚成员函数。
    -   C++11 及以前的版本，还要求没有默认成员初始化器（Default Member Initializers，即在声明成员的同时赋默认值）。

##### 指派初始化器

C++20 引入了指派初始化器（Designated Initializers），可以通过成员名称和目标值之间的键值对来进行聚合初始化。

```cpp
struct A { int a; double b; };
A a{.a = 5, .b = 9.0};  // 指派初始化器
```

##### 窄化转换

窄化转换是有潜在精度丢失的转换方式。目标类型不能存储源类型的所有值时，视为窄化转换（例如 `double` 到 `int`，`long long` 到 `int`）。

在标准禁止窄化转换的操作中，部分编译器可能实现为仅视为警告，不拒绝编译。

##### 初始化流程

聚合初始化可以分为显式初始化（explicit）和隐式初始化（implicit）。

首先，确定需要显式初始化的元素：

-   如果初始化列表是指派初始化器，则包含对应的所有成员。
-   否则，按照声明顺序包含最靠前的若干个元素。如果一个成员 `x` 也是聚合体，并且实际传入的值不是聚合体，将会进一步匹配 `x` 的全体成员，再对 `x` 进行聚合初始化，减少一层花括号嵌套。

```cpp
struct A { int x = 0, y = 0, z = 0; };
A arr[2] {0, 1, 2, 3, 4, 5};  // 相当于 {{0, 1, 2}, {3, 4, 5}}
```

如果 `T` 为联合体（union），包含超过一个显式初始化的元素，程序非良构；若是使用指派初始化器，则只能指定一个成员。

接下来，按照声明顺序初始化这些选中的元素。初始化每个成员时相当于使用复制初始化。

接下来，如果 `T` 不是联合体，每个未显式初始化的成员按照以下方式隐式初始化：

-   如果这个元素有默认成员初始化器，从初始化器初始化它。
-   否则，如果元素不是引用，从空的初始化列表对它进行拷贝初始化（多数情况下等价于值初始化）。
-   否则，程序非良构。

特别地，通过字符串字面量初始化一个字符数组，也属于聚合初始化。允许的字符类型有：`char`（或 `signed` 和 `unsigned` 变种）、`wchar_t`、`char16_t`（C++11 起）、`char32_t`（C++11 起）和 `char8_t`（C++20 起）。数组过长的部分将用 0 填充。

聚合初始化的过程中，不允许对参数进行窄化转换。

```cpp
char s[30]{"This is a C-style string."};
```

#### 列表初始化

通过花括号包裹的初始化列表初始化对象的方式，叫做列表初始化（[List-Initialization](https://en.cppreference.com/w/cpp/language/list_initialization.html)）。

```cpp
std::pair<int, int> p = {1, 2};
std::vector<int> v{0, 1, 2, 3};
```

类似以上方式的初始化，属于列表初始化。

上下两种方式，以语义上是否需要紧跟一次复制为分别，又称为“复制列表初始化”和“直接列表初始化”。例如，向函数参数传递一个初始化列表，或者将初始化列表作为返回值，都属于“复制列表初始化”。经过编译器优化，这种方式通常不会有额外的复制开销，

复制列表初始化，不会调用标记为 `explicit` 的构造函数。

列表初始化有以下的流程：

-   如果初始化列表是指派初始化器，执行聚合初始化。
-   如果 `T` 为聚合类型，并且初始化列表提供了一个同类型的对象，则从这个对象初始化。（依据自身类别进行复制初始化/直接初始化）
-   如果 `T` 为字符数组，且用花括号括起来一个对应的字符串字面量，则由这个字符串进行聚合初始化。
-   如果 `T` 为聚合类型，执行聚合初始化。
-   如果初始化列表为空，且 `T` 为存在默认构造函数的类类型，执行值初始化。
-   如果 `T` 为 `std::initializer_list` 的特化，逐个成员复制初始化。
-   如果 `T` 为类类型，考虑其构造函数：
    -   接受单个 `std::initializer_list` 参数的构造函数，优先调用。
    -   对于初始化列表中指定的参数执行重载决议，寻找最佳匹配的构造函数。
-   否则（`T` 不是类类型），并且初始化列表中只有一项，并且 `T` 不是引用，或者 `T` 是兼容的引用（同类型或是其基类），则从这个对象初始化，但是不允许窄化转换。
-   否则，如果 `T` 是不兼容的引用类型，将会通过复制列表初始化创建一个 `T` 所引用类型的临时量，然后引用绑定到这个临时对象。如果 `T` 是非 `const` 的左值引用，那么操作失败。
-   否则，如果初始化列表为空，执行值初始化。

初始化列表中，求值顺序是固定的从前到后。相对地，**函数调用的参数求值顺序是不固定的**。

##### std::initializer_list

`std::initializer_list` 可以存储若干个类型相同的对象。列表初始化中，将会优先使用接受 `std::initializer_list` 的构造函数。

例如，通过花括号初始化存在若干个初始元素的 `std::vector`，就是通过 `std::initializer_list`。

```cpp
std::vector<int> vec{0, 1, 2, 3, 4};
```

#### 复制初始化

复制初始化（[Copy-Initialization](https://en.cppreference.com/w/cpp/language/copy_initialization.html)）指从另一个对象初始化一个对象，在语义上应该发生复制。

```cpp
int x = y;
f(x);  // 函数调用时也是复制初始化
```

-   如果初始化器的类型为 `T`，调用 `T` 的构造函数。
-   初始化器类型与 `T` 无关，则尝试调用：
    -   初始化器类型的转换函数，转换为 `T` 或派生类。
    -   `T` 的构造函数，接受初始化器类型。
-   尝试应用标准转换。

复制初始化中，不会使用任何标记为 `explicit` 的构造函数。有些情况下的复制往往可以被编译器优化掉，转换成直接在目标位置构造对象。

C++17 起，标准强制要求进行复制消除，即初始化器为函数返回值这样的纯右值时，一定不会进行额外的复制。此前的编译器往往也会做这样的优化。

#### 直接初始化

直接初始化（[Direct-Initialization](https://en.cppreference.com/w/cpp/language/direct_initialization.html)）通过指定的参数调用构造函数，初始化对象。

```cpp
std::vector<int> vec(/*n:*/10, /*default:*/2);
```

直接初始化的效果如下：

-   如果 `T` 是数组类型：
    -   C++20 起，数组按照聚合初始化的方式进行初始化，但允许进行窄化转换，并且任何没有初始化器的元素将进行值初始化。
-   如果 `T` 是类类型：
    -   C++17 起，标准规定实现类似复制初始化的“复制省略”机制，如果参数是 `T` 的纯右值，直接使用初始化器本身初始化目标对象。
    -   检查 `T` 的构造函数，通过重载决议决定最佳匹配项。
    -   C++20 起，如果 `T` 是聚合类型，使用类似聚合初始化的方式进行初始化。但是存在以下区别：允许窄化转换，不存在花括号省略机制，没有初始化器的元素将会执行值初始化。
-   否则（`T` 不是类类型），源类型是一个类类型，则会检查其转换函数。
-   否则，如果 `T` 为 `bool` 且源类型为 `std::nullptr_t`，初始化对象为 `false`。
-   尝试应用标准转换。

以下的写法是错误的，因为会和函数声明混淆。这通常可以使用空的花括号代替。

```cpp
std::vector vec(/*参数列表为空*/);
```

### cv 限定符（常量性、易变性）

类型可以通过 `const` 和 `volatile` 修饰，获得常量性或者易变性。修饰符不会影响对象的底层表示、对齐要求等。

数组类型与它的元素拥有相同的 cv 限定符。

对象具有的 cv 限定符，也会给予它的成员。被声明为 `mutable` 的成员除外，它不会继承对象的常量性。

#### 常量性（const）

**具有常量性的对象不能被修改**。直接修改会导致编译错误，而间接修改（例如通过 `const_cast` 获得非常量指针，或者直接修改底层内存）**会导致未定义行为**。

以下代码定义了一个 const 的整数变量。

```cpp
const int x = 5;
// 可以正常读取
std::cout << x;
x = 3;  // 编译错误，不能修改 const 变量
```

#### 易变性（volatile）

具有易变性的对象，每次读写都要求立即和内存同步，禁止编译器进行缓存、指令重排等优化。在涉及信号处理、系统中断、直接操作内存等情况下需要用到。编译器会假设代码始终单线程执行，从而在一些情况下，可能导致意料之外的优化。

## 类型

### 基本类型

C++ 的基本类型，主要有整数类型、浮点数类型等数值类型。

#### 整数类型

有以下对于整数类型的长度修饰符。长度修饰符的效果由实现定义，但是需要满足一定要求。

| 长度修饰符 | 要求         |
| ---------- | ------------ |
| short      | 不小于 16 位 |
| (无)       | 不小于 16 位 |
| long       | 不小于 32 位 |
| long long  | 不小于 64 位 |

完整的整数类型包含以下部分：

| 组成部分   | 描述                                                          |
| ---------- | ------------------------------------------------------------- |
| 长度修饰符 | 指定数字位数要求                                              |
| 符号标识符 | 指定数字有符号（`signed`）/无符号（`unsigned`），不填为有符号 |
| `int`      | 如有其他的单词描述，可以省略                                  |

这几个部分的顺序可以交换，`signed short int`、`long long unsigned int`、`long int signed` 都是合法的。

除了以上的标准整数类型，还有以下的整数类型：

-   布尔类型 `bool`。
-   字符类型。
    -   `signed char`，`unsigned char`。
    -   `char`。以上三个类型的长度相同，但是始终是三个不同类型。`char` 是否有符号由实现定义。
    -   `wchar_t`，`char16_t`（C++11 起），`char32_t`（C++11 起），`char8_t`（C++20 起）。
-   扩展整数类型。
    -   GCC 扩展的 `__int128` 就是扩展整数类型。

此外，标准保证 `sizeof(char)` 为 1，且 `sizeof(char) <= sizeof(short) <= sizeof(int) <= sizeof(long) <= sizeof(long long)`。`sizeof` 返回值的单位为字节，字节的位数由实现定义，但是绝大多数情况下都是 8 位。

#### 浮点数类型

-   `float`。单精度浮点数，通常为 IEEE-754 binary32 格式。
-   `double`。双精度浮点数，通常为 IEEE-754 binary64 格式。
-   `long double`。扩展精度浮点数。
-   由实现定义的扩展浮点数类型。

浮点数不一定映射到 IEEE-754 规定类型。它的精度和占用空间都是实现定义的。大多数实现下，`float` 和 `double` 都是遵循 IEEE-754 的规定，而 `long double` 的实现则更加多样。

一种典型的情况下，`long double` 占用 16 字节的空间，但是有效数据只有 80bit（二进制位）。

### 类型转换

C++ 的类型转换分为隐式（implicit）和显式（explicit）两种。

#### 隐式类型转换

当一个类型在上下文中不适用，但是可以转化为一种合适的类型时，就会发生隐式类型转换。

例如希望给一个 `bool` 类型的变量赋值，但是传入了一个 `int`，就会出现一次隐式转换（0 变为 `false`，非 0 值变为 `true`）。

隐式类型转换可以由以下的步骤组成：

-   零个或一个标准转换序列。
-   零个或一个用户定义的转换。
-   如果使用了用户定义的转换，还可以接受零个或一个标准转换序列。

不允许连续两次标准转换序列，例如 `nullptr` 不能通过 0 作为中转，转换为 `bool` 类型。

传递给构造函数的参数，或者在两个非类类型之间转换，只允许标准转换。

一个标准转换序列，包括以下组成部分：

-   从以下集合中选择零个或一个转换：
    -   左值到右值转换。
    -   数组到指针转换。
    -   函数到指针转换。
-   零次或一次数值提升或数值转换。
-   零次或一次函数指针转换。
-   零次或一次限定符转换。

用户定义的转换，包含接受单个参数的构造函数，或者转换函数。但是二者都不能标记为 `explicit`。例如以下代码可以支持 `int` 到 `A`、`A` 到 `bool` 的隐式类型转换。

```cpp
struct A {
    int value{};
    A() {}
    A(int x): value(x) {}

operator bool() const noexcept {
        return value != 0;
    }
};

A a = 5;
bool flag = a;
```

##### 值类别

在上文中提到了左值和右值的概念，我们在此处先简单地介绍一下。

C++ 的表达式分为**纯右值**（prvalue）、**将亡值**（xvalue）和**左值**（lvalue）这三大类。这里只介绍纯右值和左值，将亡值和“右值引用”章节有关。

左值和右值，这个名称最初的意味是“左值可以出现在赋值运算符的左侧”。尽管现在不是这样，在某些情况下，左值有可能无法赋值，右值有可能允许赋值。

左值用于确定一个已经被存储的特定对象。例如变量 `a`，数组访问 `arr[0]` 都是左值。

纯右值是没有持久存储的临时值，例如：

-   字面量，如 `1`，`3.4`，`'c'`。（字符串字面量除外）
-   算术表达式结果，如 `a + b`。
-   函数调用结果（不返回引用），如 `std::sqrt(4)`。

##### 实例

例如以下代码：

```cpp
#include <iostream>
#include <string>

int main() {
    struct A {
        int value{};
        A() {}
        A(int value): value(value) {}

operator int () const {
            return value + 1;
        }
    };

A a{5};
    bool flag = a;
}
```

以上代码 `bool flag = a` 一句，通过以下途径转换：

-   一个标准转换序列。包含左值到右值的转换。
-   一个用户定义的转换。调用转换函数 `operator int`。
-   一个标准转换序列。包含 `int` 到 `bool` 的数值转换。

##### 上下文相关转换

一些语境下期望的类型为 `bool`，此时进行隐式类型转换，效果相当于显式类型转换 `static_cast<bool>(x)`。

-   `if`、`while`、`for` 的条件表达式。
-   **内置运算符** `!`、`&&`、`||` 的操作数。
-   条件运算符 `?:` 的第一个操作数。
-   `static_assert`、`noexcept`、`explicit` 的条件表达式。

一个典型的案例是，`if (cin >> x)` 这个语句可以成立，此处 `cin` 被转换为了 `bool` 类型，属于上下文相关转换。在一般的语境下，这个隐式转换是无法达成的（使用了 `explicit` 转换函数）。

#### 显式类型转换

C++ 中的显式类型转换，通过以下几类关键字进行。将 `x` 转换为 `T` 类型的方法是 `static_cast<T>(x)`（或使用其他关键字）。

-   [static_cast](https://en.cppreference.com/w/cpp/language/static_cast.html)，适用于一些较为安全的转换，例如：
    -   基础类型间的数值转换。
    -   基类、派生类指针之间互相转化。
    -   `static_cast<void>` 用来丢弃一个值。
    -   调用构造函数、转换函数。（允许使用 `explicit`）
-   [reinterpret_cast](https://en.cppreference.com/w/cpp/language/reinterpret_cast.html)，根据底层内存重新解释对象，例如：
    -   指针和整数互相转换。
    -   无关类型的指针之间互相转化（不能移除 `const`/`volatile`）。
-   [const_cast](https://en.cppreference.com/w/cpp/language/const_cast.html)，适用范围：
    -   对于带有 `const`/`volatile` 修饰类型的指针，可以移除修饰符。
-   [dynamic_cast](https://en.cppreference.com/w/cpp/language/dynamic_cast.html)，适用于多态类型带有运行时检查的转换。此处不做提及。

滥用 `reinterpret_cast` 和 `const_cast` 极易引起未定义行为。原对象为 `const` 时，通过 `const_cast` 去除 const 修饰符之后再修改，**仍然属于未定义行为**。它通常只能用于和接受非常量指针的函数交互，并且可以保证不会真的修改传入内容。

`reinterpret_cast` 可以获得任意类型的指针，但是对这个指针进行解引用，必须保证**目标类型有合适的可访问性**，否则**仍然属于未定义行为**。`T` 只能通过以下的类型被访问：

-   `T` 本身。
-   如果 `T` 为整数类型，`T` 对应的有符号/无符号版本。
-   `char`、`unsigned char`、`std::byte`。这允许通过字符数组来观察对象在内存中的表示。

例如：

```cpp
double x = 5;
using u64 = std::uint64_t;

u64 x1 = *reinterpret_cast<u64 *>(&x);  // UB
u64 x2; std::memcpy(&x2, &x, sizeof(u64));  // memcpy 逐字节复制是安全的
u64 x3 = std::bit_cast<u64>(x);  // std::bit_cast 是 C++20 引入的安全转换方式

union { u64 int_; double double_; } tmp;
tmp.double_ = x; u64 x4 = tmp.int_; // UB；union 不可以访问错误成员
```

使用括号包裹一个类型名，随后接一个表达式，叫做 C 风格类型转换。C 风格转换支持上述所有的转换方式。现在 C++ 中，出于安全性考虑，**不推荐使用这种类型转换**。例如 `(int)3.0`、`(double)(a + b)`。

一些类型后可以接一个括号，传入参数进行类型转换。这种转换方式本质上是对象的直接初始化，但有时会被称为“函数式转换”。例如 `char(32)`，`std::string("test")`。

### 类型别名

C++ 中，可以为类型声明别名，用于简化代码。类型别名和原类型在各种方面都是完全相同的，不会创建新的类型。

#### `using` 类型别名

C++11 引入了 `using` 关键字作为声明类型别名的含义，这也是现在 C++ 推荐的声明方式。用法如下：

```cpp
using i64 = long long;
```

这个语句为 `long long` 声明了一个类型别名 `i64`。

类型别名也适用和变量相同的作用域规则。

`using` 声明别名最大的特点是它可以支持模板。

#### `typedef` 类型别名

`typedef` 声明类型别名的方式与变量相似，源类型在前，别名在后。

```cpp
typedef long long i64;
```

### 字面量类型

C++ 中，所有字面量的类型都是确定的。

#### 整数字面量

通常情况下，一个整数类型字面量的类型通过如下简化规则确定（完整表格见 [cppreference](https://en.cppreference.com/w/cpp/language/integer_literal.html)）。

-   默认情况下为 `int`。如果数字过大，超过 `int` 存储范围，向上依次尝试 `long` 和 `long long` 类型。
-   如果使用了 `U` 后缀，则选定数字的无符号版本。
-   如果使用了 `L` 后缀，则从 `long` 开始尝试。如果使用了 `LL` 后缀，则从 `long long` 开始尝试。

`U` 后缀可以和其他的后缀组成 `UL` 或者 `ULL`。后缀大小写不敏感，但是 `LL` 的两个字母形式必须相同。

特别地，二进制、八进制或者十六进制表达，即使没有指定 `U`，也会尝试选定无符号类型。

例如以下的整数字面量（假设 `int` 和 `long` 为 32 位，`long long` 为 64 位）：

```cpp
5; // 默认为 int
2'147'483'648; // 超过 int 和 long 最大值，为 long long
100LL; // 手动指定为 long long
24llU; // 与大小写、顺序无关，为 unsigned long long
0x80000000;  // unsigned int
```

简单来讲，不指定后缀的整数类型通常为 `int`。如果希望是更大的类型，需要显式指定 `0L`（`long`）或 `0LL`（`long long`）。

#### 浮点数字面量

浮点数字面量的类型由后缀决定。

-   无后缀，表示 `double`。
-   `f` 后缀，表示 `float`。
-   `l` 后缀，表示 `long double`。

同样对大小写不敏感。

### 字符串字面量

字符串字面量的类型是对应的常量字符数组。例如 `"Hello"` 的类型是 `const char[6]`（包含结尾的空字符）。

#### 原始字符串

C++11 引入了原始字符串语法。类似 `R"$(content)$"` 的形式为一个原始字符串，其实际值和 content 相同，并且**无视转义字符，可以换行**。其中的美元符号可以换为任意字符串（也可以为空），它不会出现在真正的内容中。例如：

```cpp
std::cout << R"raw-str(\\\\ ()() """"
\n\n\n\n)raw-str";
```

得到如下输出：

```
\\\\ ()() """"
\n\n\n\n
```

原始字符串的行为和普通的字符串相同。

### 自动类型推导

#### `auto`

C++11 起，[auto](https://en.cppreference.com/w/cpp/language/auto.html) 关键字用作自动类型推导。

变量初始化时，可以使用 `auto` 来代替实际类型。推导类型时有以下规则：

-   忽略初始化表达式的引用性。
-   如果类型说明符不带引用，忽略初始化表达式的 cv 限定符。
-   如果类型说明符是 `auto &&`，根据初始化表达式的类别，推导为左值引用或右值引用（见相关章节）。

例如以下代码：

```cpp
const int x = 10;
auto x1 = x; // x1 的类型为 int，不带 const
volatile auto x2 = x; // x2 的类型为 volatile int，也不带 const
auto &x3 = x; // x3 的类型为 const int &，引用类型保留 const
auto x4{x}; // 各种初始化方式都可以使用 auto
```

C++20 起，`auto` 也可以用于函数参数类型。例如以下代码：

```cpp
auto add(auto a, auto b) { return a + b; }
// 等价于
template <typename Ta, typename Tb>  // 详见模板章节
auto add_(Ta a, Tb b) { return a + b; }
```

lambda 函数自 C++14 起就有类似特性。

#### `decltype`

C++11 起，可以用 `decltype` 推断表达式的类型。

如果参数是一个实体（Entity，如没有括号包裹的变量名、函数名、成员访问表达式），`decltype(entity)` 返回它的类型。

否则，如果参数是类型为 `T` 的其他表达式，基于其值类别：

-   `prvalue`，产生 `T` 类型。
-   `lvalue`，产生 `T &` 类型。
-   `xvalue`，产生 `T &&` 类型。

被 `decltype` 包裹的表达式不会被真正执行。

例如：

```cpp
int x;  // 未初始化
using T1 = decltype(x);  // int
using T2 = decltype((x));  // 此时为表达式，int &
using T3 = decltype(x + 1.0);  // double
// 没有真正使用 x 的值，所以不是 UB。
```

## 数值计算

算术运算等数值计算，算是最常用的操作了。接下来，我将会介绍一些和数值计算相关，可能被忽视的小细节。

### 类型转换

在进行数值计算之前，需要把两个操作数转换为相同类型。

对于整数运算，将会从下表中选定第一个可以同时表示两个操作数的类型，将二者同时转换为这一类型。

-   `int`
-   `unsigned int`
-   `long`
-   `unsigned long`
-   `long long`
-   `unsigned long long`

算术运算的结果类型，和这个转换后的类型相同。例如：

-   `int + long long` -> `long long`
-   `char + char` -> `int`

关于浮点数的运算具有相似的规则，将会把整数转换为浮点数、浮点数转换为精度较高的。例如：

-   `int + float` -> `float`
-   `float + double` -> `double`

一个常见的错误是，STL 容器的 `.size()` 方法返回 `std::size_t`，通常为 64 位无符号整数。于是会出现这样的问题：

```cpp
for (int i = 0; i < v.size() - 1; i++) {
    // 如果 v.size() = 0，相减之后得到的其实是 2^64 - 1
    // 导致循环无法结束
}
```

另一个常见的错误，左移运算符的返回值仍然满足这个规律。所以 `1 << 33` 这样的代码会导致未定义行为。可以写作 `1LL << 33`。

### 数值溢出

所有的数据类型（如整数 `int`，浮点数 `double`）都会有自己的取值范围。当运算结果超过这个范围的时候，就会出现“溢出”，导致意料之外的结果。

不同类型的溢出行为也有所不同。

-   有符号整数：**未定义行为（UB）**。
-   无符号整数：自然溢出。（例如 32 位无符号整数，相当于结果对 $2^{32}$ 取模）
-   浮点数：实现定义，可能是产生 `inf` 等 IEEE-754 特殊值。

另外，数值转换的过程中，如果原值不能被目标类型储存，会有以下行为：

-   目标为有符号整数：实现定义，并在 C++20 起良好定义。（对 $2^N$ 取模）
-   目标为无符号整数：始终良好定义。（对 $2^N$ 取模）
-   目标为浮点数：相关精度问题由实现定义。

在哈希等场景下，我们会期望发生“自然溢出”，这种情况下，必须使用无符号整数。

### 求值顺序

C++ 中，很多求值顺序都是未指定或无序的（为了描述简单，我们暂时不辨析这两个概念）。例如 `f() + g()`，标准允许先调用 `f()` 再调用 `g()`，也允许与其相反的顺序。

简单地讲，一个表达式最好需要满足以下规则，否则很容易出现未定义行为：

-   避免多次修改同一变量。单个表达式，只应该对一个变量修改至多一次。
-   避免同时读写变量。单个表达式，如果对变量进行了修改，就不要再读取它。

特别地，使用逗号分隔两个子表达式通常是安全的，它有良好的定序规则。

#### 详细规则

具体见 [求值顺序 - cppreference](https://en.cppreference.com/w/cpp/language/eval_order.html)。

一次完整的表达式求值，包含值计算和副作用两个操作。在同一个线程中，表达式的所有求值操作通过“先序”规则判定顺序。如果操作 A 先序于（sequenced before，也被翻译为“按顺序早于”）操作 B，那么在完成操作 A 以后才会开始执行操作 B。先序关系具有传递性。

如果表达式 A 先序于表达式 B，只有完成了 A 的值计算和副作用，才会开始进行 B 的值计算和副作用。

C++ 标准说明了几个确定的先序关系，详情可以参考上述链接。

绝大多数运算符，对左右操作数都是没有定序的。函数调用时，参数的求值顺序也是无序的（C++17 开始变为未指定行为）。

未定序的情况下，多次修改或者同时读写同一变量属于未定义行为。

例如这样的一个表达式 `i++ && ++i`，可以按照下文的方式来分析。（个人理解）

把表达式分为如下几个部分：

-   `i++`：求值 `A0`，副作用 `A1`。
-   `++i`：求值 `B0`，副作用 `B1`。
-   逻辑与：求值 `C0`。

用 `->` 表示先序关系，应用相关标准规则可知：

-   `A0 -> A1`。
-   `B1 -> B0`。
-   `A -> B`，`A0 -> C`，`B0 -> C`。

所以这个表达式可以完全定序，`A0 -> A1 -> B1 -> B0 -> C`，不存在未定义行为。

相对地，`i++ + i` 这样的表达式也可以分析出是未定义行为。

### 杂项

#### 运算符优先级

见 [C++ 运算符优先级 - cppreference](https://en.cppreference.com/w/cpp/language/operator_precedence.html)。

#### “表达式”和“语句”

表达式（Expression）和语句（Statement）是两个可能被混淆的概念。

表达式用于计算并一个值，例如以下的几个表达式：

```cpp
a + b  // 简单表达式
(a - b) * ((a + b * c) << 2)  // 表达式可以嵌套和组合
2 * sqrt(2)  // 函数调用也是表达式
```

语句用于执行操作、控制程序运行等。它没有返回值。例如以下的几个语句：

```cpp
int x{100};  // 定义变量
for (int i = 0; i < 100; i++) {  // 循环语句
    if (i % 9 == 2)  // 条件语句
        continue;  // 控制语句
    x++;  // 执行表达式的语句
}
```

#### “短路”机制

逻辑与 `&&`、逻辑或 `||` 运算符有特殊的“短路”机制。它会先计算左侧的表达式，如果此时已经可以确定答案（`&&` 遇到 `false`，`||` 遇到 `true`），就不再计算右侧的表达式。

这个特性主要是用来方便这样的代码：

```cpp
bool flag = (index < n) && (a[index] >= 0); // 如果 index >= n，不会执行右侧导致未定义行为
```

#### 逗号运算符

可以使用逗号连接两个子表达式，其行为是依次执行这两个表达式，然后返回第二个表达式的值。

这在一些情况下可以方便书写。例如：

```cpp
// 尽管 for 循环的这个位置只能执行一条语句，但是可以用逗号表达式依次执行多个逻辑。
for (int i = 0; i < n; i++, cnt++) {}
```

#### 三目运算符

三目运算符可以执行条件判断，在一些情况下可以方便书写。

```cpp
int x = (n >= 0 ? 5 : 2);
// 等价于
int x;
if (n >= 0) { x = 5; }
else { x = 2; }
```

#### 除法优化

对于计算机而言，取模和除法是极其耗时的操作。幸运的是，编译器可以对固定模数除法、取模进行大幅度优化。将除数声明为 `constexpr` 或者 `const`，开启编译器 O2 优化，可以大幅提升除法效率。对于浮点数除以固定值，可以先计算出来这个数的倒数，然后化为乘法计算。

```cpp
constexpr int mod = 998244353;  // constexpr 也可以换成 const
x % mod;  // 编译器可以进行优化
// 浮点数
for (int i = 0; i < n; i++) arr[i] /= 10;
for (int i = 0; i < n; i++) arr[i] *= 0.1;  // 更快
```

## 指针和引用

C++ 对象在内存上的存储，位于一个连续的地址空间。“指针”就是用于描述一个对象的地址。

可以把内存理解成一个大型的数组，“指针”存储的数据就是这个数组的下标（显然这是不严谨的，因为内存中可以存储不同类型的对象）。可以通过指针来读写对象。

### 指针基础

`T *p` 标识一个指向 `T` 类型对象的指针，名称为 `p`。接下来，通过 `*p` 可以访问 `p` 指向的元素（可以进行读写）。

`&x` 表示对 `x` 取地址，即获取一个指向 x 的指针。

例如以下示例：

```cpp
int x{100};
int *p = &x; // p 现在指向 x
*p = 24; // 通过指针间接修改
std::cout << x << '\n'; // 输出 24
```

类型 `T` 的部分可以包含 `const` 这样的修饰符，可以避免通过这个指针修改对象。

可以在星号后面添加 `const`，表示不可以修改“这个指针指向谁”。

例如：

```cpp
int x{10}, y{10};

int const *p1 = &x; // 等价于 const int *p1_
int * const p2 = &x;

*p1 = 100; // 错误！不能通过指针修改 const int
p1 = &y; // 现在 p1 指向 y
*p2 = 100; // 修改 x 的值
p2 = &y; // 错误！不能修改 p2 表示的地址。
```

指针必须指向一个合法的对象，并且是兼容的类型，否则对它解引用（`*p`）是未定义的。

### 常见的不可解引用指针

#### nullptr

C++ 使用 `nullptr` 作为空指针常量，语义上表示指针不指向任何元素。等于 `nullptr` 的指针不可解引用。

#### 悬空指针

当一个对象被销毁之后，指向它的指针就会变成悬空指针。一类典型的悬空指针是通过函数返回局部变量的指针。例如：

```cpp
int *f() {
    int tmp = 10;
    return &tmp;
}

int *p = f();
// 此时对 p 解引用，指向一个被销毁的局部变量，是未定义行为。
```

#### 无效指针

当一个指针指向无效的地址（通常是由于未初始化），对它解引用也是未定义的。

### 指针算术

指针可以进行一些简单的算术运算，如下：

-   指针加/减整数：将指针向前或者向后移动若干个元素。
-   指针减指针：计算它们间隔几个元素。
-   下标访问：`p[n]` 等价于 `*(p + n)`。

指针算术的单位始终是完整元素，而非字节。指针算术必须在同一个数组上进行（运算数的指针、结果的指针等），否则行为未定义。特别地，对于大小为 n 的数组，指向 a[n] 的指针也合法（尾后指针），但是不可解引用。

示例：

```cpp
int arr[100]{}; // 创建一片连续内存
int *p = &arr[5];
int *p1 = p + 5; // 指向 a[10]
int *p2 = p - 3; // 指向 a[2]
int dis = p1 - p2; // 等于 8
int item = p[9]; // a[14] 对应的值为 0
```

指针算术过程，涉及的指针必须处于同一个数组中，否则行为未定义。

### （左值）引用

“引用”在本质上和指针类似，也是通过记录内存地址来关联到另一个对象。不同的是，引用：

-   无需显式解引用。
-   无法修改绑定到哪个对象。
-   必须在初始化时绑定。

例如以下代码：

```cpp
int x = 100;
int &y = x; // 定义一个 x 的引用，名为 y
std::cout << y; // 可以像一个整数一样直接使用 y
y = 10; // x 也被修改为 10
```

引用的类型也可以带有 `const` 修饰，和对应的指针相同，不能通过这个引用来修改原对象。特别地，`const T &` 可以绑定到一个右值（如字面量等）。

很多情况下，对于比较大的对象，我们会使用常量引用来传递参数，减少一次复制的开销。

```cpp
void print(const std::string &s) {
    std::cout << s << '\n';
}
```

通常认为，当按值传递对象会发生大于等于 32 字节的拷贝时，就应当考虑通过常量引用传递。但是整数、很小的结构体，按值传递会更快一些。

### 动态内存分配

在之前，我们提到了“动态存储期”这一概念。这类对象不同于自动存储期，可以有很长的生命周期，不会自动释放，直到被用户显式销毁。

在 C++ 中，可以使用 `new` 创建动态对象，使用 `delete` 释放。具体用法如下：

```cpp
#include <iostream>

auto f() -> int * {
    return new int{5};  // 创建动态对象，返回一个指针
}

auto main() -> int {
    auto ptr = f();  // 动态对象的指针可以跨函数传递
    std::cout << *ptr << '\n';
    delete ptr;  // 必须释放，否则会导致内存泄漏
}
```

一个动态对象，必须在将来的某个时刻进行释放，并且仅能释放恰好一次。如果没有释放，将会导致内存泄漏，浪费大量内存。如果释放多次，则行为未定义。释放内存后再次访问，行为未定义。

这个对象将会按照特定方式初始化：

-   `new int`：默认初始化，**将会持有不确定值**。
-   `new int{5}`：列表初始化。如果花括号为空则是值初始化，均为安全的。
-   `new int(5)`：直接初始化。

可以使用 `new[]` 和 `delete[]` 来动态分配数组。动态分配的数组，大小可以是一个变量。

```cpp
#include <iostream>

auto f(int size) -> int * {
    return new int[size];  // 动态分配内存
    // 此时的数组包含不确定值！
    // 如果希望自动清零，可以使用 new int[100]{}
}

auto main() -> int {
    int n = 100;
    auto arr = f(n);
    arr[0] = arr[1] = 1;
    for (int i = 2; i < n; i++) {
        arr[i] = (arr[i - 1] + arr[i - 2]) % 998'244'353;
    }
    std::cout << arr[n - 1] << '\n';

// 动态分配数组，必须使用 delete[] 释放
    delete[] arr;
}
```

使用 `new` 动态分配的内存，会保证对齐到 `std::max_align_t`，能够满足全部标准对象的对齐要求。

### 底层内存操作

#### operator new

C++ 中，`operator new` 可以用来动态分配特定大小的内存块，但是不进行对象初始化。

```cpp
auto ptr = ::operator new(sizeof(int) * 100);  // 分配 100 个 int 的内存
// ptr 的类型为 void *
```

其中，括号内传入的参数是字节数。

`operator new` 分配的内存，必须通过 `operator delete` 释放。

```cpp
::operator delete(ptr);
```

C++17 起，可以通过 `std::align_val_t` 来指定内存对齐的大小，处理更高对齐要求的特殊对象（如 SIMD 对象）。

```cpp
auto ptr = ::operator new(sizeof(T), std::align_val_t{alignof(T)});
::operator delete(ptr, alignof(T));
```

#### 手动构造、析构

在未初始化的内存上，我们可以手动调用对象的构造函数和析构函数。对于需要延迟构造的对象，需要经历以下四个步骤：

1. 分配内存
2. 构造对象
3. 析构对象
4. 释放内存

手动构造对象，需要使用 `placement new`。其语法如下：

```cpp
T *new_ptr = new (void_ptr) T(/*构造参数*/);
```

这将会在 `void_ptr` 指向的内存空间上，使用指定的参数构造对象，返回新的指针。

手动析构对象，可以通过指针调用它的析构函数。但是需要注意，跟在波浪线之后的，只能有一个标识符，要么是一个该类型的类型别名，要么是原始类名。

```cpp
std::string *ptr = /*...*/;
using str = std::string;
ptr->~str();  // 合法
ptr->~basic_string();  // 合法，std::string 的原始类名叫 std::basic_string<char>
ptr->~std::string();  // 不合法，不能包含作用域解析运算

template <typename T>
void destruct(T *ptr) {
    ptr->~T();  // 合法
}
```

在一个位置已经存在对象的情况下再次构造，或者在不存在对象的情况下再次析构，是未定义行为。

C++20 起，提供函数 `std::construct_at` 和 `std::destroy_at` 用于手动构造和析构对象。

## 数组

数组用于存储多个相同类型、在内存上连续排布的对象。

使用如下方式定义一个数组。

```cpp
int constexpr size = 100;
int arr[size]{};  // 自动清零
```

数组的大小必须是一个正整数，且是编译期常量。通常情况下，如果希望使用变量作为数组大小，这个变量必须标记为 `constexpr`（常量表达式），或者含有常量值的 `const` 变量。

尽管标准不允许，很多编译器还是提供了扩展，允许变量值作为数组大小，称为变长数组（VLA）。

```cpp
#include <iostream>

auto main() -> int {
    int n; std::cin >> n;
    int vla[n];  // 非标准行为！
    // VLA 只能拥有自动存储期

vla[0] = 1;
    for (int i = 1; i < n; i++) {
        vla[i] = vla[i - 1] + 1;
    }
    std::cout << vla[n - 1] << '\n';  // 输入 100，输出 100
}
```

这个代码在 GCC 中是允许的。如果希望观察标准行为，请使用 `-pedantic` 编译选项，对这类编译器扩展给出警告。

很多情况下，数组都会隐式转换为指针。转换后的指针指向数组的首个元素，即 `&a[0]`。

这种转换的出现频率很高，除非正在在作为一个“实体”（例如 `sizeof`，`decltype` 的操作数），或者作为一个左值（例如正在进行取地址）。甚至就连数组的下标访问，本质上也是指针算术。

例如，这些很常用的操作，就涉及数组到指针的转换。

```cpp
std::sort(a, a + n);  // 均转换成指针类型

// 第一个参数转换为指针，但是最后一个参数取的是数组的大小
std::memset(a, 0, sizeof(a));
```

另一个问题是，数组通过函数参数传递，往往实际上传递的也是指针。

```cpp
auto f(int a[3]) -> void {
    static_assert(std::is_same_v<int *, decltype(a)>);
}
```

在这里，我们期望的可能是，数组的元素被逐一复制并传递，但是实际上，这是在传递一个指针，在函数内部的修改会影响到外部数组。这很不符合直觉，所以不推荐使用数组作为函数参数。

数组不能作为函数返回值。以下代码不能通过编译。

```cpp
auto f() -> int[3] { return {1, 2, 3}; }
int(g())[3] { return {1, 2, 3}; }  // 前置类型、后置类型都不行
```

数组不能进行复制（赋值/初始化另一个数组），只能使用 `memcpy` 和 `std::copy` 这些函数操作。但特别地，这不会影响到包含数组的结构体。

```cpp
int a[3]{};
int b[3] = a;  // 错误！

struct S { int a[3]; };
S s1{};
S s2 = s1;  // 正确
```

由于数组存在这些缺陷，在这些场景下，建议使用 `std::array` 来替代。使用以下方式，可以定义一个 int 类型的数组，包含 20 个元素：

```cpp
std::array<int, 20> a;
```

`std::array` 可以进行传参、返回、赋值等操作，都是通过逐个元素复制。如果不希望复制，可以通过显式传递引用来避免。

多维数组可以通过嵌套 `std::array` 代替。

```cpp
std::array<std::array<int, 20>, 10> a;
// 相当于
int a[10][20];
```

`std::array` 不能隐式转换为指针，可以使用 `arr.data()` 或者 `&arr[0]` 获取指针。

## 函数

C++ 使用函数，可以把一段代码封装在一起，共同实现一个功能，进行一个计算。

### 基础知识

函数的基本用法，大家都已经很熟悉了，在这里不做讲述。

```cpp
int square(int x) {
    return x * x;
}

square(5); // 25
```

C++11 起，可以后置标注函数的返回值。这在编写一些使用模板的代码时会有帮助，并且可能更加美观。

```cpp
auto square(int x) -> int {
    return x * x;
}
```

C++14 起，返回值类型可以省略（仅使用 `auto`）。

很多情况下，在传递函数参数的过程中，可以使用聚合初始化来简化代码，无需具体写出类型。

```cpp
struct AVeryLongClassName {
    int a, b;
};

auto f(AVeryLongClassName x) -> void {
    std::cout << x.a << ' ' << x.b << '\n';
}
```

使用时，可以直接传入一个花括号包裹的初始化列表，不需显式写出类型。在这个场景下，可以自动推导出正确类型 `AVeryLongClassName`。

```cpp
f({2, 3});  // 输出 2 3
```

如果函数中的某个参数没有被使用，可以只写类型、不写参数名，来抑制编译器警告。

```cpp
int f(int x, int) { return x + 1; }
// 使用：
f(2, 3);  // 3
```

函数可以先声明，再在后面进行定义。

```cpp
int f(int x);

// ...
int f(int x) { return x + 1; }
```

函数体之前可以添加 `noexcept` 声明，表示这个函数不会抛出异常，用于在一些场景下保证异常安全。建议为移动构造、移动赋值函数添加 `noexcept`。

```cpp
int f(int x) noexcept {
    return x + 1;
}
```

### 函数重载

有些时候，我们可能会希望对多个类型实现类似功能，这种情况下就可以使用函数重载来实现，即允许多个函数拥有同一个名字。

```cpp
int square(int x) { return x * x; }  // (1)
double square(double x) { return x * x; }  // (2)

square(3);  // 调用重载 (1)
square(5.0);  // 调用重载 (2)
```

当调用存在重载的函数时，会通过重载决议判断实际调用哪一项。具体规则十分复杂，可以参考 [cppreference](https://en.cppreference.com/w/cpp/language/overload_resolution.html)。

简单来讲，需要满足以下要求：

-   首先，保证参数个数正确，并且模板推导成功、每个参数都可以隐式转换为相应类型。
-   对于这些可行项，按照以下优先级选择：
    1. 参数精确匹配。（允许左值到右值转换、限定符转换等简单转换）
    2. 只需使用标准转换，其中提升（如 `int` -> `long long`）优于其他转换（如 `double` -> `int`）。
    3. 需要用户定义的转换。（这允许从花括号包裹的初始化列表，转换为类类型）

对于相同优先级的，不带模板的函数优于带有模板的，函数模板之间按照特化程度比较。

如果无法判断两个重载的优先级，则编译错误。

#### 实参依赖查找

实参依赖查找（ADL）允许程序访问其他命名空间中的函数，而无需显式指定命名空间名。在参数包含类类型时，编译器会额外在参数所处的命名空间查找这个函数重载项。

```cpp
namespace A {
    struct S {};
    void f(S) { std::cout << 1; }
};

int main() {
    A::S x;
    f(x);  // 通过实参依赖查找调用 A::f
}
```

实参依赖查找主要是为了方便运算符重载，在命名空间内定义的重载运算符，也能通过 ADL 成功调用。

也有其他函数经常使用 ADL 查找。最经典的是 `swap`，通常情况下约定使用 `swap(x, y)` 来交换两个自定义类型的对象对象，它对这个类型可能有比 `std::swap` 更优的实现。所以标准的交换两个元素的方式是：

```cpp
using std::swap;
swap(x, y);
```

C++20 起，提供了 `std::ranges::swap`。不同于 `std::swap`，它的效果相当于这两步操作。

### 默认参数

在函数声明中，可以为参数指定默认值，使得调用时可以省略部分参数。默认参数必须从参数列表的右侧开始连续指定。

```cpp
void print(int value, int base = 10, int width = 8) {}

print(42, 16, 4);
print(42, 16);    // 等价于 print(42, 16, 8)
print(42);        // 等价于 print(42, 10, 8)
```

存在默认参数的函数，会向重载决议添加多个重载项，例如上文的 `print` 会包括 `print(int)`、`print(int, int)` 和 `print(int, int, int)`。需要小心处理它和其他函数重载的潜在冲突。

### 重载运算符

C++ 允许重载运算符，允许自定义类型之间使用运算符进行操作，调用指定的函数。

定义一个重载运算符，可以使用 `operator` 关键字，形式大概相当于定义了一个叫做 `operator@` 的函数（`@` 是对应运算符）。

绝大多数运算符都可以被重载，以下是一个 `std::string` 乘以整数的重载。

```cpp
auto operator* (std::string const &s, int count) -> std::string {
    std::string res{};
    for (int i = 0; i < count; i++) res += s;
    return res;
}

// 使用
std::string s{"Hello"};  // 必须先转为 std::string
std::cout << s * 5 << '\n';
```

但是需要注意，重载运算符的操作数，不能全为内置类型，（例如这里包含一个 `std::string` 就是合法的）。

也可以在类的定义中，通过成员函数重载运算符（见相关章节）。

### 回调函数

有些时候，函数可以作为另一个函数的参数。这允许代码表达更加丰富的逻辑。

例如，我们有以下的两个需求：

-   找到 $[1, n]$ 的所有偶数，输出到控制台。
-   找到 $[1, n]$ 的所有偶数，存储到一个列表中。

这两个需求很明显十分接近，但是想要使用一个函数来实现，还是有一定的困难。事实上，我们可以提取一个共用的逻辑：找到该范围的所有偶数，通过某种方式提交结果。

那么我们便可以通过这种方式实现：传入整数 `n` 和另一个函数 `f`，每遇到一个偶数 `x`，通过调用 `f(x)` 提交这个答案。

我们使用 Python 语言来表达这个逻辑，因为 C++ 的类型系统可能比较复杂。如果你不了解 Python，可以看成伪代码结合注释理解。

```python
def find_even(n, f):  # 实现函数
    for i in range(1, n + 1):  # 遍历 [1, n] 区间
        if i % 2 == 0:
            f(i)  # 偶数，提交答案

def to_console(x):  # 输出到控制台
    print(x)

res = []  # 结果列表
def to_list(x):  # 输出到 res 列表
    res.append(x)

find_even(20, to_console)  # 使用
find_even(20, to_list)
```

想要在 C++ 中使用函数作为参数，可以考虑以下的方案。

#### 模板

**这是最推荐的方式**，通过模板，可以让函数接收任意类型的参数，自然包括函数。

这种方式不会有任何运行时的开销，并且可以完美支持下文提到的仿函数。

模板的相关知识会在后续章节讲解。

```cpp
template <typename T>
void find_even(int n, T f) {
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) f(i);
    }
}
```

#### 函数指针

在 C++ 中，可以让一个指针指向函数，称为函数指针。可以通过函数指针来调用这个函数。以下代码展现了函数指针的使用。

```cpp
#include <iostream>
#include <random>

int square(int x) {
    return x * x;
}

int cube(int x) {
    return x * x * x;
}

auto main() -> int {
    std::mt19937 random{std::random_device{}()};

using FuncPointer = int (*)(int);  // 类型表示法：返回值 (*)(参数列表)
    FuncPointer ptr{};
    if (random() % 2 == 1) {  // 随机选择一个
        ptr = &cube;
    } else {
        ptr = square;  // 即使不使用取地址符号，函数名也会自动转换为函数指针
    }

std::cout << ptr(6) << '\n';  // 函数指针可以直接使用括号调用，也可以先 (*ptr) 解引用再调用
    // 随机输出 36 或者 216
}
```

于是可以按照如下方式实现 `find_even` 函数。

```cpp
using FuncPtr = int (*)(int);
void find_even(int n, FuncPtr f) {
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) f(i);
    }
}

// 如果不使用类型别名，参数应写作 int (*f)(int)
```

这种方式无法支持仿函数和 lambda 函数，通常不推荐使用。但是函数指针也有其他的用途（例如上一个例子，以及与 C 函数交互等）。

#### std::function

`std::function` 是 C++11 起提供的一个标准库工具，可以存储一类可调用对象（函数或仿函数等），它们有相同的调用签名，即接收同样类型的参数、返回同样类型的值。

```cpp
#include <iostream>
#include <functional>

int square_impl(int x) {
    return x * x;
}

auto main() -> int {
    std::function<int(int)> square = square_impl;
    // lambda 函数也可以使用同样类型的 std::function
    std::function<int(int)> cube = [](int x) { return x * x * x; };
    std::cout << square(5) + cube(2) << '\n';  // 直接使用括号调用
    // 输出 33
}
```

`std::function` 像是适用范围更广的函数指针，在类型中只包括函数的调用签名。与之相对地，函数指针无法指向一个仿函数。

```cpp
void find_even(int n, std::function<int(int)> f) {
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) f(i);
    }
}
```

相比于使用模板，`std::function` 有较大的运行时开销，所以在函数传参的场景下，不建议使用这个方式。它更多用于实现运行时多态。

### 仿函数、lambda 函数

C++ 的函数无法在局部定义，这带来了很大的不便。这使得跨函数共享数据，只能通过参数传递，或者全局变量。

幸运的是，我们可以在局部定义域中定义一个类，并且可以通过成员函数重载函数调用运算符，即 `a(b)`。这使得我们可以通过这种方式模拟一个函数，这就是仿函数。

```cpp
auto main() -> int {
    struct Print {
        auto operator() (/*函数参数列表*/ int x) -> void {
            std::cout << x;
        }
    } print;

print(0);  // 使用和普通函数一致
    return 0;
}
```

仿函数的意义不仅在于可以在函数内部定义，它还是一种有状态的函数。

```cpp
auto main() -> int {
    std::vector<int> vec{1, 2, 3, 4, 5};

int sum{};
    struct Func {
        int &sum;
        auto operator() (int x) -> void {
            sum += x;
        }
    };
    Func func{sum};

// 对 vec 的每个对象 x，调用 func(x)
    std::for_each(vec.begin(), vec.end(), func);

return 0;
}
```

我们通过这种方式，可以在封装函数的同时，读写局部变量。这解决了“只能通过全局变量交换数据”的问题。

但是封装仿函数还是过于麻烦，所以 C++11 引入了 lambda 函数，作为更加方便的替代。lambda 在本质上还是基于仿函数实现。

定义一个 lambda 函数，分为以下三个部分：捕获列表，参数列表，函数体。

```cpp
auto lambda = [/*捕获列表*/](/*参数列表*/) { /*函数体*/ };
```

lambda 函数的类型无法表示（编译器自动生成），必须使用 auto 来接收它。此后可以使用 decltype 获取它的类型。每个 lambda 函数的类型都互不相同。

以上文的仿函数 `Func` 为例，它其实相当于“捕获”了局部变量 `sum`，从而可以对它进行读写。lambda 函数的捕获分为两种，按值捕获、按引用捕获。参考以下示例：

```cpp
auto main() -> int {
    int a{}, b{};

[a]() { a = 4;  /* 错误，按值捕获不能修改 */ };
    [&a]() { a = 5; /* 按引用捕获，会同步修改外部的 a */ };
    [b, &a]() { /* 可以部分变量按值捕获，部分按引用捕获 */ };
    [&]() { a = 1, b = 2; /* 当前作用域内，全部按引用捕获 */ };
    [=]() { /* 全部按值捕获 */ };
    []() { global = 2; /* 全局变量，不进行捕获也可以读写 */ };
}
```

lambda 函数和普通函数的运行时开销相同，经过内联优化后均为零开销。

借助 lambda 函数，可以完美地解决一开始提到的问题。这使得我们可以方便地在函数内部封装子函数，无需依赖全局变量。消除全局变量，可以从根源上解决“多组测试忘记清空数组”这样的问题。

C++14 起，lambda 函数的参数列表可以使用 `auto` 代替参数类型，表示这个位置允许接收任意类型的参数。这个功能本质上是基于模板实现的。C++20 起，普通函数也添加了这个功能。例如 `sort` 的比较函数，现在可以这样写。

```cpp
std::sort(v.begin(), v.end(), [](auto x, auto y) { return x.a < y.a; });
```

lambda 函数的唯一问题可能是递归比较麻烦，无法直接支持递归。我常用的方法是，额外传递一个 `self` 参数，通过它进行递归调用。

```cpp
auto fac = [&](int x) -> int { return x? x * fac(x - 1): 1; };  // 编译失败
auto fac = [&](int x, auto &self) -> int { return x? x * self(x - 1, self): 1; }  // 个人常用的写法，调用的时候需要 fac(5, fac) 的形式
std::function<int(int)> fac = [&](int x) { return x? x * fac(x - 1): 1; }  // 不推荐，有运行时开销
auto fac = [&](this auto fac, int x) { return x? x * self(x - 1): 1; }  // C++23 起，可以直接 fac(5) 调用
```

经过测试，这种函数递归写法的效率和普通函数递归没有差异。

## 类和结构体

有些情况下，我们需要处理几个关联很大的数据（例如分数的分子和分母），便可以封装一个类（class），把它们组合到一起统一管理。在 C++ 中，结构体和类几乎没有区别，通常可以混用。

### 类的基本使用

类的定义使用 `class` 或 `struct` 关键字。为了方便，我们先使用 `struct` 来定义类，后面会提到它们的区别。

```cpp
struct Frac {  // 分数
    // 数据成员
    int nume;  // 分子
    int deno;  // 分母
};
```

接下来，便可以把这个类作为一个独立的类型来使用。通过 `item.member_name` 可以访问它的数据成员。

```cpp
Frac x{};  // 值初始化
x.nume = 5;
std::cout << x.nume;  // 输出 5
```

根据先前所讲的知识，这样的简单类属于“聚合类型”，可以直接使用聚合初始化来为它提供初始值。例如 `Frac{2, 3}`，将会使用这些参数，按照声明顺序初始化类的成员。

对于一个指向 `Frac` 对象的指针，可以使用 `->` 运算符来访问成员。通常 `ptr->member` 可以看作和 `(*ptr).member` 等价。

```cpp
Frac x{3, 4};
Frac *ptr = &x;
std::cout << ptr->nume;  // 相当于 x.nume
```

### 成员函数

有些情况下，我们可能会写出这样的函数。

```cpp
void reciprocal(Frac &f) {  // 把 f 变成它的倒数
    std::swap(f.nume, f.deno);
}
// 使用：
Frac f{2, 3};
reciprocal(f);
```

C++ 支持“成员函数”（又称成员方法），从而可以通过另一种方式来定义和使用这个函数。

```cpp
struct Frac {
    // ...
    void reciprocal() {
        std::swap(nume, deno);
    }
};
// 使用：
Frac f{2, 4};
f.reciprocal();
```

成员函数会在一个对象上进行操作，可以直接通过成员的名称，来访问当前对象上的成员。例如在 `f` 上调用 `reciprocal` 成员函数时，其中的 `nume` 就是 `f.nume`，`deno` 就是 `f.deno`。

成员函数中，还可以通过关键字 `this` 获得一个指针，指向当前对象。也可以使用 `this->nume` 这样的方式来访问成员。

成员函数也可以指定为 `const`，相当于普通函数传入常量引用，具体见以下的例子。

```cpp
struct Frac {
    void print() const {
        std::cout << this->nume << '/' << this->deno << '\n';
    }
};
// 等价于
void print(const Frac &f) {
    std::cout << f.nume << '/' << f.deno << '\n';
}
```

成员函数也可以是重载运算符。调用时，将会以自身作为第一操作数，参数作为后续操作数。部分特殊的重载运算符只能是成员函数。

```cpp
struct Frac {
    auto operator+ (Frac const &other) const -> Frac {
        return {nume * other.deno + deno * other.nume, deno * other.deno};
    };
};

// 使用
Frac{1, 2} + Frac{1, 3};  // Frac{5, 6}
```

成员函数也可以先声明再定义。通过类名访问一个成员，需要使用作用域访问运算符（`::`）。

```cpp
struct Frac {
    void print() const;
};

void Frac::print() const {
    std::cout << "Frac" << std::endl;
}
```

#### 成员可访问性

从本质上讲，成员函数和普通函数几乎没有区别。那么它除了看起来比较好看，还有什么意义呢？

一些情况下，我们不希望一个对象的数据成员被外部程序修改（例如实现一个 `vector`，需要维护存储区的指针和大小，而随意修改它会严重威胁安全性）。

为了解决这个问题，C++ 引入了“成员可访问性”的概念。一个成员，可以指定在什么范围内可被访问。

-   `public`：公开。这个成员可以被外部代码访问。
-   `private`：私有。这个成员只能在当前类的内部访问。
-   `protected`：受保护。这个成员只能在当前类，或者派生类的内部访问（关于“派生类”相关知识，见下文）。

通过以下方式指定成员的可访问性：

```cpp
struct A {
    int a1;  // 默认可访问性
    double a2;
private:
    char a3;  // 接下来都是 private
    long long *a4;  // private
public:
    int a5[3];  // public
};
```

默认可访问性取决于使用 `class` 还是 `struct` 关键字声明这个类。`struct` 则为 `public`，`class` 则为 `private`。

### 构造函数

构造函数是一类特殊的函数，当一个对象通过任何方式初始化的时候，会自动调用它的构造函数。构造函数负责给各个成员提供初始值。

```cpp
struct Frac {
    // ...
    Frac(int x, int y) :
            nume(x),  // 成员初始化器
            deno{y} {
        std::cout << "构造了一个 Frac 对象";
    }
};
```

声明构造函数时，函数名部分与类名相同，不能标注返回值类型。

构造函数分为成员初始化器和函数体两个部分。初始化器可以是任意初始化形式（直接初始化、列表初始化等）。初始化对象的时候，首先通过初始化器，**按照在类中的声明顺序**初始化所有成员，接下来开始执行函数体。

成员初始化器，其求值时的作用域和构造函数的函数体相同。简单来讲，它允许了以下操作：

```cpp
struct A {
    int x, y;
    A(int x, int y):
            x(x), y(y) // 括号外的 x 和 y 是成员名，里面的是参数名
    {
        // 如同在函数体中使用 x 或 y，都是指代参数名
    }
};
```

除此以外，可以在声明成员的时候提供一个默认初始化器。当没有提供初始化器的时候，将会使用这个默认初始化器进行初始化。例如：

```cpp
struct Frac {
    int nume;
    int deno = 1; // 默认成员初始化器
    Frac(int x): nume(x) {}  // deno 将会初始化为 1
};
```

既没有没有初始化器、也没有默认初始化器的成员，会被执行默认初始化。也就是说，这可能导致部分成员**持有未定义的值或错误值**，或者在部分成员无法默认初始化的情况下，导致编译错误。更加致命的是，即使值初始化外层对象，这些被默认初始化的成员也不会赋值为零。

还有人会选择在构造函数的函数体中给数据成员赋值。这种方式可行但不推荐，提供初始化器是更加安全、便捷和高效的做法，尤其是对于复杂类型的成员。

通常情况下，建议给所有的成员都在声明时提供默认初始化器，例如值初始化 `member{}` 或者提供一个默认值 `member = 0` 来规避这个问题。

同一个类可以提供多个构造函数，通过重载决议区分。

有一些构造函数具有特殊的名字和语义，具体如下：

-   `T()`：默认构造函数。用在值初始化等场合。
-   `T(const T &)`：复制构造函数。用于复制一个对象。
-   `T(T &&)`：移动构造函数。（涉及右值引用相关知识）

而且，这些构造函数通常都会被编译器自动生成，除非有成员不支持对应操作。

可以通过 `T() = default;` 这种形式来显式生成这些构造函数。

在 OI 中，很多情况都不需要给简单的结构体定义构造函数。根据聚合初始化相关规则，只有几个公开数据成员的结构体属于“聚合体”，可以直接用花括号形式初始化。详见前文相关章节。

```cpp
struct A {
    int x; double y; char z;
};
A a1{1, 2.0, 'c'}; // 正确
A a2{1, 2.0}; // 正确，等价于 {1, 2.0, '\0'}

// 函数传参
void f(A a, int x) { /*...*/ }
f({3, 4.0, '.'}, 0); // 正确
```

#### 显式构造函数

只接受一个参数的构造函数，可以用于隐式类型转换。但是我们可能并不希望这样。

```cpp
struct A {
    int x;
    A(int x): x(x) {}
};
void f(A x) { /*...*/ }

f(5); // 相当于 f(A{5});
```

这样会降低代码可读性，也会令人困惑。将构造函数声明为 `explicit` 即可避免这样的问题。标记为 `explicit` 的构造函数，不会用于函数传参、返回值、复制初始化等场景。

```cpp
struct A {
    int x;
    explicit A(int x): x(x) {}
};
void f(A x) { /*...*/ }

f(5); // 编译错误
```

建议单个参数的构造函数均使用 `explicit` 修饰，除非真的想要用于隐式转换。

以下案例可以演示 `explicit` 构造函数的重要性。

```cpp
#include <iostream>
#include <vector>

struct A {
    int x{}, y{};
    A(int x): x(x) {}  // 没有使用 explicit 修饰
    A(int x, int y): x(x), y(y) {}
};

auto main() -> int {
    std::vector<A> v;
    // vector 的 insert 可以接收一个 std::initializer_list 来插入多项
    // 此处相当于插入 A{2} 和 A{3}
    v.insert(v.begin(), {2, 3});
    std::cout << v.size() << '\n';  // 插入了 2 个元素
}
```

将单参数的构造函数设定为 `explicit`，则行为正常，只插入一个元素。这种情况下，希望插入两个元素，需要这样写：

```cpp
v.insert(v.begin(), {A{2}, A{3}});
```

#### 委托构造函数

C++11 开始支持“委托构造函数”语法，可以直接调用当前类的其他构造函数。

```cpp
struct Rectangle {
    int width{};
    int height{};

Rectangle() = default;
    Rectangle(int size): Rectangle(size, size) {}  // 正方形
    Rectangle(int width, int height): width{width}, height{height} {}
};
```

要求有一个初始化器为当前类名，然后传入相应的参数。此时不能再包含其他的初始化器。

### 析构函数

当一个对象的生存期结束后，会自动调用它的析构函数，例如以下场景：

-   局部变量的作用域结束时。
-   静态变量在程序结束时。
-   delete 释放动态分配的对象。

析构函数按照如下方式定义：

```cpp
#include <iostream>

struct A {
    ~A() {  // 无参数、无返回值
        std::cout << "~A()" << '\n';
    }
};

auto main() -> int {
    {
        A a;
        std::cout << 1 << '\n';
    } // 此时 a 被销毁，调用析构函数
    std::cout << 2 << '\n';
}
```

输出结果：

```cpp
1
~A()
2
```

绝大多数情况下都不需要显式定义析构函数，编译器会生成一个不做任何事情的默认析构函数。在析构函数执行之后，将会依次执行所有成员的析构函数。（于生命顺序相反）

需要析构函数的场景，通常是这个类在“管理”某个资源的时候，这个资源在对象初始化时获取，在对象销毁时释放。

例如以下的场景中，就必须使用析构函数来保证内存被成功释放。

```cpp
struct DynamicArray {
    int *data = nullptr;
    DynamicArray() = default;
    DynamicArray(std::size_t size): data(new int[size]{}) {}

~DynamicArray() {
        delete[] data;
    }

auto operator[] (std::size_t index) -> int & {
        return data[index];
    }
};
```

#### RAII

通过“析构函数”的设计，我们可以感受到 C++ 中的一个重要设计思想——RAII（资源获取即初始化）。这种设计方式可以通过局部对象来管理资源，让动态资源的生命周期与一个局部对象绑定，通过局部变量的初始化获取资源、局部变量的析构释放资源。

对于一个动态资源，往往要经历获取、使用、释放这三个步骤。而“释放”往往是最容易被遗漏的。可能因为：

-   程序员忘记释放。
-   控制流中断，导致没有执行释放语句。（例如提前 return，或者中途抛出异常）

而显然，由于局部对象的析构不可绕过，RAII 完美的解决了这个问题。

C++ 标准库的很多工具都利用了这种设计。例如 `vector` 的动态内存，通过局部的 `vector` 对象管理，会在调用析构函数时释放。

### 静态成员

静态成员是指一部分和类相关的成员，而与实际对象无关。即同一个类中，所有的静态成员共用一个值。静态成员使用 `static` 关键字声明。

静态成员的生命周期会持续到程序结束，存储在静态存储区中。

#### 数据成员

```cpp
struct S {
    static int count;  // 声明
    S() { count++; }
    ~S() { count--; }
};
int S::count = 0;  // 定义
```

以上代码展示了静态数据成员的用法，这实现了一个计数器，记录当前存在的 `S` 类型对象个数。

静态数据成员需要在类外提供一个唯一的定义。但是存在特例，`constexpr` 的数据成员可以直接声明时定义。以及 C++17 起，可以使用 `inline`，允许在大多数场景下，声明的同时定义静态数据成员。

```cpp
struct S {
    static inline int count = 0;
    static constexpr int maxCount = 10;
};
```

#### 成员函数

静态成员函数，是一类和具体实例无关的函数，无法使用 `this` 指针和其他非静态成员。

```cpp
struct S {
    static int pow(int a, int b, int mod) /*不可以加 const*/ {
        int res = 1;
        for (; b != 0; b >>= 1, a = a * a % mod) {
            if (b & 1) res = res * a % mod;
        }
        return res;
    }
};
```

显然这个快速幂函数，并不会用到对象的状态，所以可以声明为静态的。

### 嵌套类

C++ 支持嵌套类，即可以在一个类中声明其他的类。嵌套类的对象，和外层类的对象之间不发生绑定，即不可以在嵌套类中直接使用外层类的成员。

```cpp
struct Outer {
    int a, b;
    struct Inner {
        int c, d;
    };
};
```

例如这个例子中，可以使用 `Outer::Inner{}` 来创建一个嵌套类的对象。但是这个对象中只包括 `c` 和 `d` 两个数据成员，不包括 `a` 和 `b`，自然也不能使用它。

### 继承

继承是面向对象编程的重要概念，可以用于增强代码复用。在 C++ 中，可以让一个派生类继承于一个基类，然后派生类就可以获得基类的所有成员变量和方法。

继承的语法如下：

```cpp
// 基类
struct Base {
    auto f() -> void {
        std::cout << "f()\n";
    }
};

// 派生类
struct Derived : public Base {
    auto g() -> void {
        std::cout << "g()\n";
    }
};
```

在 C++ 中，使用冒号表示继承关系。基类名之前，紧接一个可访问性标识符，表示继承而来的所有成员，其可访问性不会高于这个权限。即对于基类的 `protected`/`public` 成员，存在如下规则。

-   `public`：保留原有访问权限。
-   `protected`：访问权限变为 `protected`。
-   `private`：访问权限变为 `private`。

基类 `private` 的成员，无法在派生类中访问。

如果不填写这个访问权限，则根据类的声明方式，`struct` 默认为 `public`，`class` 默认为 `private`。

在以上例子中，可以从 `Derived` 类调用继承而来的成员函数 `f()`。

```cpp
Derived d;
d.f();  // f()
d.g();  // g()
d.Base::f();  // f()，显式指定继承路径
```

以下的例子，展现了继承的更详细用法。

```cpp
class ASCIIArt {
protected:
    int size = 5;  // 图形大小
    char fillChar = '*';  // 填充字符
public:
    ASCIIArt() = default;
    ASCIIArt(int size, char fillChar) : size(size), fillChar(fillChar) {}

auto setFill(char ch) -> void {
        fillChar = ch;
    }
};

class Square : public ASCIIArt {
public:
    Square() = default;
    Square(int size, char fillChar) : ASCIIArt(size, fillChar) {}

auto draw() const -> void {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                std::cout << fillChar;
            }
            std::cout << '\n';
        }
    }
};
```

在构造派生类的时候，需要调用基类的构造函数（如果没有显式指定，则会尝试调用默认构造）。在以上的例子中，构造函数 `Square(int size, char fillChar)` 的初始化器 `ASCIIArt(size, fillChar)` 就是在初始化基类，包含基类名和初始化语句。

在派生类完成析构之后，也会自动调用基类的析构函数。

```cpp
Square square(5, '*');
square.setFill('#');
square.draw();
```

派生类中的成员，会隐藏基类中的同名成员（如果有）。对于成员函数，这二者之间并不会发生重载。例如以下代码：

```cpp
struct Base {
    auto f() -> void { std::cout << "Base\n"; }
};

struct Derived : public Base {
    auto f(int) -> void { std::cout << "Derived\n"; }
};
```

在这个情况下，在 `Derived` 对象上调用成员函数 `f()` 会直接报错，而不是调用基类的实现。

可以通过这样的方式，来绘制 5 行 5 列，使用 `#` 填充的正方形。

C++ 还支持多继承，允许一个派生类继承于多个基类，获得它们的所有成员。具体方式如下：

```cpp
struct C : public A, public B {};
```

多继承可能出现“菱形继承”的问题，例如以下示意图，靠下的表示派生类：

```
   A
  / \
 B   C
  \ /
   D
```

这种情况下，D 会持有两份 A 中的数据（一份从 B 继承，一份从 C 继承），导致无法正常使用。这种情况下，可以使用虚继承来解决。

```cpp
struct A {};
struct B : virtual public A {};
struct C : virtual public A {};
struct D : public B, public C {};
```

这样，在一个 `D` 的对象中，只会保存一份 `A` 的数据。然而虚继承会引入运行时开销，并且降低可读性，所以要尽量避免菱形继承。

使用 `static_cast` 可以在派生类指针和基类指针之间互相转换。从派生类到基类指针（向上转型）总是安全的，从基类到派生类（向下转型），如果和实际的对象类型不一致，则是未定义行为。对于向下转型，更加安全的方式是下文提到的 `dynamic_cast`。对于多继承的对象，使用 `reinterpret_cast` 反而会出现问题。

### 多态

多态（Polymorphism）是面向对象编程的另一个重要概念。多态是指，基类的成员函数，在运行时可以根据实际类型，表现出不同派生类的行为。具体来讲：

-   派生类可以覆写基类的成员函数。
-   通过基类的**指针或引用**，指向派生类的对象。
-   调用某个成员函数的时候，实际调用的是被派生类覆盖的版本。
-   C++ 中，多态使用虚函数和继承机制实现。

以下是一个反例，可以说明不使用虚函数的情况下，直接用同名成员隐藏基类成员，并不能真正实现多态。

```cpp
#include <iostream>

struct Base {
    auto f() -> void {
        std::cout << "Base\n";
    }
};

struct Derived : public Base {
    // 反例：通常情况下，派生类函数不能真正“覆盖”（Override）基类函数
    auto f() -> void {
        std::cout << "Derived\n";
    }
};

auto caller(Base &obj) -> void {
    // 这里的 Base 类，和 Base::f() 函数之间静态绑定，所以输出 Base
    obj.f();
}

auto main() -> int {
    Derived obj;
    caller(obj);

// 此时在 Derived 上调用 f()，Derived::f() 只是会“隐藏”Base::f()，输出 Derived
    obj.f();
}
```

为了实现这个需求，C++ 引入了虚函数。虚函数可以实现动态绑定，和真正意义上的“覆盖”基类方法。在基类中指定某个成员函数为 `virtual`，即可把它声明为虚函数，让它可以被覆盖。在派生类上，使用 `override` 声明，确保发生覆盖。

```cpp
struct Base {
    int x{};
    auto virtual f() const -> void { std::cout << "Base\n"; }
};

struct Derived : public Base {
    double y{};
    auto f() const -> void override { std::cout << "Derived\n"; }
};
```

如果使用后置类型声明，需要注意 `override` 关键字需要紧贴函数体的花括号，和指定 `const` 的位置不同。派生类函数想要重写基类函数，需要调用签名完全相同（参数类型、返回值类型等）。

接下来便可以使用这种动态绑定机制了。

```cpp
auto caller(Base &b) -> void {
    b.f();
}

auto main() -> int {
    Derived d;
    caller(d);  // 输出 Derived
}
```

`override` 是可选的，但是十分推荐使用，如果覆写失败会导致编译错误，不会导致更加难以排查的逻辑错误。

需要注意的是，如果发生值复制（例如把 `caller` 从引用改成传值）会导致虚函数失效，全部指向 `Base` 中的实现。

#### 虚函数的本质

每个包含虚函数的类，编译器都会为其生成虚函数表，虚函数表中会存储若干个函数指针。所有虚函数都是通过这些函数指针间接调用的，所以可能会产生一些运行时开销。对应地，非虚函数调用是直接绑定，没有额外开销。

包含虚函数的对象，开头会维护一个指针，指向属于它的虚函数表。

例如上面的例子，`Base` 对象的内存布局为：

```
[ vptr1 | x ]
  ↓
f: Base::f()
```

`Derived` 对象的内存布局为：

```
[ vptr2 | x | y ]
  ↓
f: Derived::f()
```

当 `Derived` 对象的引用转换为 `Base` 类型时，不会影响已经存储的虚表指针。通过 `Base` 类型调用虚函数时，依旧会先通过虚表指针访问对应的虚函数表，然后寻找指定的函数进行调用。对应到这个例子，就是通过 `vptr2` 得到实际指向的函数是 `Derived::f` 然后调用它。

为什么在传值时就会失效？此时会调用 `Base(Base const &)` 进行复制，而编译器生成的复制构造函数，是构造一个新的 `Base` 对象，逐个复制成员，不关心虚表指针。所以新的对象会有自己的虚表指针，指向 `Base`。这个过程又被称为“对象切片”。

#### 虚析构函数

考虑以下场景：

```cpp
struct Base {
    int id{};
    Base(int id): id(id) {}
    auto virtual f() const -> void {
        std::cout << "User id = " << id << '\n';
    }
};

struct Derived : public Base {
    std::string name;
    Derived(int id, std::string const &name): Base(id), name(name) {}
    auto f() const -> void override {
        std::cout << "User id = " << id << " name = " << name << '\n';
    }
};

auto main() -> int {
    Base *ptr = new Derived(1, "Admin");
    ptr->f();
    delete ptr;
}
```

它看起来运行得非常正常，但其实有严重的问题。

首先，要知道 `std::string` 的存储是动态分配一块内存空间，然后维护一个指针指向它。而 `std::string` 的析构函数就是用于释放这片内存。

在 `delete ptr` 执行时，会调用 `Base` 的析构函数。而 `Base` 的析构函数并不会释放 `Derived` 里面额外定义的 `name`，导致字符串的存储区不被释放，从而内存泄漏。

解决这个问题的最好办法是，把析构函数设为虚函数。这样，执行 `delete` 时就可以通过虚函数表获得正确的析构函数，然后正确释放。

#### 动态类型识别

有些时候，我们会想要把基类的指针重新转换成派生类使用。如果实际上这个对象的类型不是目标类型，则会导致未定义行为（之前说到的“向下转型”）。`dynamic_cast` 提供了一种更加安全的解决方案。

能够使用 `dynamic_cast` 向下转型，要求基类至少有一个虚函数（因为会利用编译器创建的虚表信息），通常会选择把析构函数声明为虚函数。

`dyncmic_cast` 向下转型，如果转换失败，根据转换类型不同，出现以下错误：

-   如果是指针转换，返回 `nullptr`。
-   如果是引用转换，抛出 `std::bad_cast` 异常。

```cpp
struct Base {
    virtual ~Base() = default;
};
struct Derived : public Base {};
struct Derived2 : public Base {};

Derived x{};

Base *ptr = &x;
Base &ref = x;

dynamic_cast<Derived *>(ptr);  // 转化成功
dynamic_cast<Derived2 *>(ptr);  // 返回 nullptr
dynamic_cast<Derived2 &>(ref);  // 抛出异常
```

#### 纯虚函数

基类的虚函数，可以不提供默认实现，此时被称为“纯虚函数”。包含纯虚函数的类被称为抽象类，不能直接实例化（创建这个类型的对象）。

```cpp
struct A {
    auto virtual f() -> void = 0;  // = 0 指定为纯虚函数
};
```

抽象类只能通过其派生类对象，通过指针转化来使用。

#### 总结

如果使用 C++ 的多态类型，为了安全，应该遵守以下原则：

-   始终使用 override 重写函数。
-   使用指针/引用操作对象，避免值复制。
-   基类析构函数声明为 `virtual`。
-   向下转型优先使用 `dynamic_cast`。

### 友元和可变声明

#### 友元（friend）

C++ 中，可以声明一个类的友元函数，它是一个自由函数，但是特许它访问这个类的 `protected` 和 `private` 成员。

```cpp
class A {
private:
    int x;
public:
    A(int x): x{x} {}
    friend void f(A a);
};

void f(A a) {
    std::cout << a.x;
}
```

友元函数也可以在声明的同时定义。这种情况下，这个函数只能通过实参依赖查找（ADL）使用。

```cpp
class A {
    friend void f(A a) {
        std::cout << a.x;
    }
};
```

友元函数的一个常见用途是重载输入/输出运算符，因为对象需要作为第二个操作数，所以只能是自由函数的形式。通过友元允许它访问私有成员。

```cpp
class A {
    friend auto &operator<< (std::ostream &os, A a) {
        os << a.x;
        return os;
    }
};
```

也可以声明一个友元类。按照这样的方式声明，`B` 的所有成员函数都可以访问 `A` 的私有成员。

```cpp
class A {
    friend class B;
};
```

#### 可变成员（mutable）

C++ 可以把一个成员设置为 `mutable`，使得即使在 `const` 的对象中，也可以修改这个数据成员。

`mutable` 通常用于特殊场景，需要小心使用。不能因为修改 `muable` 而影响对象的外部表现。

```cpp
struct A {
    mutable int callCount = 0;

void f() const {
        callCount++;
        // ...
    }
};
```

以下是 mutable 一个典型的**错误用法**。

```cpp
struct A {
    mutable int value;
    bool operator< (A other) const {
        return value < other.value;
    }
};

std::set<A> s;
```

此处的比较函数依赖一个 `mutable` 的成员。如果 `value` 被修改，可能会导致 `set` 的平衡树形态错误，出现未定义行为。`set` 返回的对象是 `const`，这本身是一种保护机制，不应该通过 `mutable` 绕过。

### 重载运算符

在函数章节，我们已经介绍过重载运算符相关内容。接下来我们将会介绍一些扩展内容，以及一些编程习惯。

首先，一些运算符只能通过成员函数重载，包括 `->`（指针访问）、`=`（赋值）、`()`（函数调用）、`[]`（下标访问）。

对于自增自减运算符 `++` 和 `--`，可以分别重载其前缀和后缀形式。通过以下方式：

```cpp
struct A {
    auto operator++ () {}  // 前缀形式
    auto operator++ (int) {}  // 后缀形式
};
```

即对于后缀形式，相当于调用 `operator++(a, 0)` 或者 `a.operator++(0)`。

建议前置自增和后置自增的逻辑和内置运算符保持一致。前置自增在函数体中执行自增，然后返回当前对象的引用。后置自增先保留一个副本，执行自增之后返回这个副本。

```cpp
struct A {
    int value;

auto operator++ () -> A & {
        ++value;
        return *this;
    }

auto operator++ (int) -> A {
        auto copy = *this;
        ++value;
        return copy;
    }
};
```

对于非基础类型的迭代器，如果不需要使用返回值（例如循环中的自增），建议使用前置自增来避免复制开销。如果是整数、指针这样的简单类型则没有任何区别，根据自己习惯使用即可。

同样地，赋值运算符、复合赋值运算符（`+=` 等）的行为也建议和内置运算符保持一致，返回自身的引用，便于链式复制。注意，通常不需要自行重载赋值运算符，编译器会自动生成逐个元素赋值。

```cpp
struct A {
    int *data;
    std::size_t size;

auto operator= (A const &other) -> A & {
        if (this == &other) return *this;
        delete[] data;
        size = other.size;
        data = new int[size];
        for (std::size_t i = 0; i != size; ++i) {
            data[i] = other.data[i];
        }
        return *this;
    }
};
```

此外，如果已经实现了相应构造函数，赋值函数可以使用“先构造再交换”的方式实现。这是一个很常用的方法。

```cpp
struct A {
    int *data;
    std::size_t size;

auto operator= (A const &other) -> A & {
        if (this == &other) return *this;

auto tmp{other};
        std::swap(data, tmp.data);
        std::swap(size, tmp.size);  // 如果实现了交换，可以直接调用

return *this;
    }
};
```

为了保证异常安全，移动赋值、移动构造都应该为 `noexcept`。

#### 安全地使用引用参数

我们上面的代码中，特判了 `a = a` 这样的自赋值场景。如果没有这个判断，将会出现十分严重的后果。两个对象共用一个 `data`，开始的时候执行 `delete[]`，原始数据就已经丢失了。尽管这种场景不常见，但对于 `a += a` 等操作也可能出现类似问题。

这也揭示了一个问题，`A const &` 虽然很多场景可以替代值传递，但它本质上还是一个引用，和传值还是会有一些差异。所以使用指针/引用作为参数需要谨慎。

如果把对象的 `this` 指针也看成一个引用参数，这类问题都是来源于几个引用参数出现重叠。**对于函数传参涉及指针/引用的情况，建议遵循以下安全规范**。对于同类型的所有引用：

-   要么所有的引用都是只读引用。（`const T &`）
-   要么仅存在一个写引用（`T &`），不存在其他只读引用。

如果不符合以上规范，那么必须仔细考虑潜在的引用重叠。要么进行预先判断，要么优化实现，使其能够正确处理这种情况。

我们可以认为，不同类型的引用不会指向同一对象。因为这种情况往往已经违反了严格别名原则，属于 UB。

例如，在这个赋值运算符，`this` 指针是一个写引用，`other` 是一个只读引用，所以需要额外处理二者重叠的情况。

这个规则不仅适用于重载运算符，对于任何参数中包含引用的函数，都应该遵守。

## 右值引用和移动语义

C++ 中，`std::vector` 的实现方式是预留一部分空间，在 `push_back` 的时候，如果预留的空间不足，就扩容一倍，然后逐个元素迁移。对于 `int`，这个扩容的过程可以参考以下代码。

```cpp
int constexpr n = 20;
int from[n], to[n * 2];

auto moveData() -> void {
    for (int i = 0; i < n; i++) {
        to[i] = from[i];
    }
}
```

然而 `std::vector` 中存放的并不一定是简单类型。例如，如果这里的 `int` 换成 `std::string`，`to[i] = from[i]` 这一步操作就是字符串的赋值。而 `std::string` 的赋值逻辑，是逐个字符复制，避免影响到原字符串。所以这个过程的总时间复杂度取决于字符串长度之和。

有没有更加高效的解决方案？首先，`std::string` 的内部其实仅存储了一个指向存储区（动态分配）的指针。如果不考虑对原对象的修改，直接移动指针，是一个明显更优的策略。而原对象已经即将被销毁了，所以我们无需在意它的值。

这就是“移动”和“复制”的差异，“复制”不会修改原对象的内容，但是“移动”之后，我们不再需要原对象，所以可以直接通过移动指针，从原对象中“窃取”资源，换取更高的效率。

C++11 引入了移动语义，来支持这样的需求。

在深入讲解语法知识之前，我们不妨想一想，如果你是 C++ 的设计者，会如何设计关于移动的语法？

首先，我们需要一个特殊的构造函数。就像 `T(const T &)` 被称为“复制构造函数”，这个新的就称为“移动构造函数”。当然，为了和复制构造函数之前区分，我们需要在类型名的基础上，添加一个标记（假如叫做 `T(T TO_BE_MOVED)`）。例如 `std::string` 的移动构造函数，就可以这么写：

```cpp
struct string {
    string(string TO_BE_MOVED other):
        data_(other.data_)  // 直接获取内部指针
        // ... 处理其他数据
    {
        // 把原对象变成空指针，否则可能会导致二次释放
        other.data_ = nullptr;
        // ...
    }
};
```

接下来的一个重要的问题，如何标记一次初始化是“移动”而非“复制”？

```cpp
std::vector<int> f() {
    // ...
    return res;
}

std::vector<int> vec = f();
```

首先，以上是一个绝对可以使用移动的场景。通过 `f()` 得到的函数返回值，是一个临时的 `vector` 对象，即将被销毁，再此之前要赋值给局部变量 `vec`。你会发现，这其实是极度浪费的，把原件先复制一份，手里留下复印件之后销毁原件——为什么不直接移动它呢？于是，你得出了一个结论，右值一定可以安全地被移动。（不要考虑复制消除规则，这是 C++17 的内容了）

于是，你得到了一些启发。移动构造和复制构造相同，都是从另一个同类型的对象构造，自然要接受一个指向另一个对象的“引用”。这种引用和普通的引用不同，它只应该指向一个临时对象，表示可以从中“窃取”数据。你决定将它称为“右值引用”，表示为 `T &&`；与之相对，普通的引用称为“左值引用”，表示为 `T &`。

```cpp
struct string {
    // 真正的“移动构造函数”（C++11 起）
    string(string &&other) noexcept {  // 移动构造、移动赋值函数十分推荐加上 noexcept
        // ...
    }

// 对应地，还有“移动赋值函数”
    auto operator= (string &&other) noexcept -> string & {
        // ...
        return *this;
    }
}
```

这自然会涉及值类别的相关内容。在本篇专栏前面的章节中，我们已经介绍过了左值（lvalue）和纯右值（prvalue）。我们规定：纯右值优先绑定到右值引用（`T &&`），但也允许绑定到常量的左值引用（`T const &`）；左值只能绑定到左值引用（`T &`）。

但是，回头看一下，最初的问题似乎还没有解决。尽管这些规定使得纯右值可以自动调用移动构造，但是保存在原位置上的 `from[i]` 是一个左值，还是会调用复制构造。于是你想到，需要允许某种方式，来把一个左值标记为“可移动的”。你引入了一个函数叫做 `mark_as_movable`，把一个左值传入这个函数，便神奇地让它可以绑定到右值引用。这个名字实在太长了，所以实际的 C++ 标准中，将它称为 `std::move`，它不会真正移动什么，只是标记“我想要移动它”。`std::move` 的返回值，值类别属于将亡值（xvalue）。将亡值的引用绑定规则，和纯右值一致。

这个问题在现在得到了完美解决。

```cpp
int constexpr n = 20;
std::string from[n], to[n * 2];

auto moveData() -> void {
    for (int i = 0; i < n; i++) {
        to[i] = std::move(from[i]);
    }
}
```

那么 `std::move` 是怎么实现的呢？其实就是一个显式类型转换，通过 `static_cast<T &&>(x)` 转换为右值引用。标准规定，到右值引用的显式转换，或者返回右值引用的函数调用表达式，值类别为将亡值。

将一个临时对象绑定到右值引用，将会延长它的生存期，直到这个引用本身被销毁。常量左值引用也有类似的性质。但是，不要使用这种方式来优化代码，即使是在 C++17 标准要求之前，编译器也会对函数返回值等情况做优化，优化掉任何额外的复制和移动操作。使用右值引用接受返回值，反而有可能抑制编译器优化。

```cpp
std::vector<int> f() {
    return {1, 2, 3};
}

std::vector<int> &&x = f();  // f() 返回临时对象，生存期延长到和 x 相同
std::vector<int> y = f();  // f() 直接在 y 处构造结果，无复制和移动
```

以及还有另一个问题。目光回到移动构造函数，在其中，我们使用了一个右值引用作为函数参数。但事实上，我们做的操作，更像是把它作为一个左值看待。移动过程中，对原对象做一些操作，例如赋值成员、取地址等，都应该是合理的。所以，**右值引用的值类别是一个左值**。这看起来可能有些奇怪，但其实是合理且必要的。以及从另一个角度看，右值引用也是一个具名对象，它不是左值才显得有些奇怪。

### 万能引用和完美转发

理解以下的内容，可能需要模板的相关知识。为了简化内容分类，我们在右值引用章节讲解。

在泛型编程中，可能会出现这样的代码：

```cpp
template <typename T>
auto f(T &&arg) -> void {
    // ...
}
```

此处的 `T &&` 被称为万能引用（`T` 必须是当前函数上的模板）。根据传入 arg 的值类别（假设是左值/右值的 `int` 类型），类型推导的行为如下：

| 值类别 | T       | T &&     |
| ------ | ------- | -------- |
| 左值   | `int &` | `int &`  |
| 右值   | `int`   | `int &&` |

可以发现，根据值类别的不同，这个参数始终会传入一个左值引用或者右值引用，而不会丢失原始的值类别信息。

然而，获取了值类别信息并没有用处，还有一个很大的问题：无论 `arg` 被推导为左值引用还是右值引用，在使用时（例如作为其他函数的参数）都会是一个左值。为了解决这个问题，需要使用 `std::forward` 函数进行完美转发。

| T       | `std::forward<T>(x)` 的返回值 |
| ------- | ----------------------------- |
| `int`   | `int &&`                      |
| `int &` | `int &`                       |

可以发现，这能够保留 `x` 的值类别，原封不动地传递到内层函数中。这种情况下不可以使用 `std::move` 转发，可能会导致意外地移动左值参数。

`auto &&x` 这样的变量定义，推导规则和万能引用相同。

### 杂项

C++ 中，不推荐传递 `const` 引用，再在函数体中复制一次。这种情况推荐直接按值传递，传入右值时可以把一次复制构造变为移动。但是在不需要额外复制时，或者想要减少心智负担，使用常量引用传参仍是很好的解决方案。

同理，在类的构造函数中传递大对象，有时会写出这样的代码：

```cpp
struct S {
    std::string str;
    S(std::string const &s): str(s) {}
};
```

这种情况其实也是可以优化的，更好的方式是按值传递，然后移动构造。（`std::array` 这种移动构造开销极大的除外）

```cpp
struct S {
    std::string str;
    S(std::string s): str(std::move(s)) {}
};
```

## 模板和编译期计算

模板是处理多类型数据的一个重要工具，可以支持一些类型不同，但是逻辑完全相同的操作。

例如，我们希望自己实现一个 `add` 函数，来计算 `(a + b) % 998244353` 的值。这看起来很简单，但其实要支持 `int`、`long long` 这样的很多类型。于是我们需要编写很多个代码一模一样的函数。

```cpp
int add(int x, int y) { return (x + y) % 998244353; }
long add(long x, long y) { return (x + y) % 998244353; }
long long add(long long x, long long y) { return (x + y) % 998244353; }
// ...
```

C++ 引入了“模板”来解决这类问题。

### 基本使用

```cpp
template <typename T>  // 模板参数
T add(T x, T y) { return (x + y) % 998244353; }
```

这段代码就定义了一个函数模板 `add`。其含义是：任取一个类型 `T`，定义一个函数 `T add(T x, T y)`。这样，我们在上文写到的这三个重载，就分别是 `T` 取 `int`，`long` 和 `long long` 的情况。`T` 可以换成任意类型。

调用这个函数，使用以下方式：

```cpp
int ans = add<int>(1, 2);  // 显式指定，T 取 int
int ans2 = add(0LL, 3LL);  // 模板参数可以自动推导，T 取 long long
```

每次真正使用函数模板的时候，都会填充对应模板参数，然后创建一个新的函数（这个过程被称为“实例化”）。模板实例化期间，才会检查里面的语句是否合法，例如此时再写一个 `add(1.0, 2.0)`（类型推导为 `double`，浮点数不能取模），就会在这个语句处报错。

平时我们使用的 `std::swap`、`std::min`、`std::sort` 这类支持多种类型的函数，都是通过函数模板实现的。

C++ 中，有很多种实体都可以带有模板。包括：

-   类
-   函数
-   类型别名（C++11 起）
-   变量（C++14 起）
-   概念（C++20 起）

例如，我们可以通过类模板来实现一个动态大小的数组。

```cpp
template <typename T>
class DynamicArray {
    T *data_{};
public:
    // 接下来使用 DynamicArray 这个类名，如果没有指定模板参数，默认为 <T>
    DynamicArray(): DynamicArray(1) {}
    DynamicArray(std::size_t size): data_(new T[size]{}) {}
    ~DynamicArray() {
        delete[] data_;
    }

auto operator[] (std::size_t index) -> T & {
        return data_[index];
    }
};
```

接下来，可以使用 `DynamicArray<int>` 这样的方式来使用它。平时我们使用的 `std::set`、`std::vector`、`std::pair` 等类型，都是通过类模板实现。

类模板的不同特化中（模板参数不完全相同），会拥有独自的静态成员。函数模板的不同特化中，也会拥有独自的静态变量。

### 常量表达式

在进一步讲解之前，我们需要了解 `constexpr`（常量表达式，Constant Expression）这一概念。`constexpr` 是 C++11 引入的关键字，声明可以编译期求值的变量、函数。

#### constexpr 变量

很多情况下，一些值在编译期即可确定，这种变量可以使用 `constexpr` 来修饰。

请注意 `constexpr` 和 `const` 是不同的。`const` 只是表示这个变量的值在初始化之后不可变，但是这个值可以是运行时确定的。

很多情况下，我们都需要填写一个 `constexpr` 的值。（例如数组的大小，例如后文要提到的模板参数）

```cpp
constexpr int size = 100;
int array[size];           // 合法，数组大小必须是编译期常量
```

#### constexpr 函数

constexpr 函数是可以在编译期求值的函数，即如果它的参数都是可以在编译期计算的，那么它的求值也将在编译期进行。

这个概念是 C++11 引入的，在接下来的每个版本，都允许 constexpr 函数执行更多的操作，使其更加可用。开始时的 constexpr 函数，除了一条返回语句外，不允许其他语句；C++20 起甚至可以使用 new 和 delete。

```cpp
int constexpr pow10(int x) {  // C++14 起
    int result = 1;
    for (int i = 0; i < x; i++) result *= 10;
    return result;
}

constexpr int x = 3;
int a[pow10(x)];  // 可以用作数组大小
```

### 非类型模板参数

模板参数可以不是类型，可以是具体的值。

```cpp
template <int x, int y>
struct Mul {
    static constexpr int value = x * y;
};
```

整数、枚举和指针可以是模板参数。C++20 起，可以使用浮点数、简单的类类型。

非类型的模板参数，必须填入一个编译期常量。

模板参数和函数参数的行为十分接近，同样支持默认参数。

```cpp
template <typename T = int, std::size_t size = 3>
struct Array { /*...*/ };

// 使用
Array a1{};  // Array<int, 3>（C++17 起）
Array<> a1{};  // Array<int, 3>
Array<double> a2{};  // Array<double, 3>
```

### 模板特化

有些情况下，我们可能会希望，为特定模板参数提供定制实现，这种情况下就可以使用模板特化。

模板特化分为以下两种：

-   全特化，所有的模板参数都指定一个固定类型。
-   偏特化，只有部分模板参数指定了特定类型，仍然包含模板。

类型特征（Type traits，有时称为类型萃取）是模板特化的最常见用途。我们可以通过模板来获取关于一个类型的信息，是否为整数，是否为指针，是否为函数……以下是通过类模板特化实现的一个 `is_integral` 来判断整数类型。这个代码属于全特化。

```cpp
template <typename T>
struct is_integral {
    static constexpr bool value = false;  // 默认不是整数
};

// 对于整数类型
template <>  // 全特化语法，必须使用 template <> 来声明
struct is_integral<int> {
    static constexpr bool value = true;  // 定制 int 的实现，它一定是整数
};

// ...对于所有整数类型特化
```

在使用的时候，便可以用 `is_integral<T>::value` 来判断 `T` 类型是否为整数。实际可以使用标准库的 `std::is_integral<T>::value` 或者 `std::is_integral_v<T>`。

使用偏特化实现的类型特征，一个典型的示例是 `is_same<T, U>` 判断两个类型是否相同。具体实现如下：

```cpp
template <typename T, typename U>
struct is_same {
    static constexpr bool value = false;  // 默认不相同
};

// 偏特化
template <typename T>
struct is_same<T, T> {
    static constexpr bool value = true;
};

// 模仿标准库 is_same_v
template <typename T, typename U>
constexpr bool is_same_v = is_same<T, U>::value;
```

实际可以使用标准库的 `std::is_same<T, U>::value` 或者 `std::is_same_v<T, U>`。

模板特化也可以在数值计算中使用，例如以下是一个编译期计算阶乘的程序。

```cpp
template <int n>
struct fac { static constexpr int value = n * fac<n - 1>::value; };

template <>  // 模板全特化
struct fac<0> { static constexpr int value = 1; };
```

### SFINAE

SFINAE（Substitution Failure Is Not An Error，替换失败不是错误）是 C++ 模板元编程的一个重要概念。

在重载决议的过程中，如果一个函数模板，由于模板替换导致无效代码（但不是严重的语法错误），编译器不会报错，而是会静默地丢弃这个候选项，考虑其他重载。

举一个例子，以下的代码实现一个函数模板，如果输入的对象有 size()、 len() 方法中的任意一个就调用它。（我们假设不会二者兼有）

```cpp
template <typename T>
auto size(T const &t) -> decltype(t.size()) {
    return t.size();
}

template <typename T>
auto size(T const &t) -> decltype(t.len()) {
    return t.len();
}
```

假设我们此时传入了一个 `std::vector`，它只有名为 `size()` 的方法。在第二个重载中，返回值处发生替换失败（没有 `len()`），根据 SFINAE 规则，第二个重载被忽略，只有第一个重载成为候选。

另一个常见的需求是，如果 `T` 满足某个条件，就启用这个重载，否则考虑其他的。标准库提供了 `std::enable_if` 模板，来实现这种“条件启用”的逻辑。

```cpp
template <bool B, typename T = void>
struct enable_if {  };

template <typename T>
struct enable_if<true, T> { using type = T; };

template <bool B, typename T = void>
using enable_if_t = typename enable_if<B, T>::type;
```

以上是 `std::enable_if` 的实现。需要传入一个布尔值 `B` 和一个类型 `T`（默认为 `void`）。具体效果：

-   若 `B` 为 `true`，在其中声明一个类型别名 `using type = T`。
-   若 `B` 为 `false`，则不声明任何类型别名。

可以按照如下的方式使用它。

```cpp
template <typename T>
auto f(T x) -> std::enable_if_t<std::is_integral_v<T>, T> {
    return x % 17;
}
```

其中 `is_integral_v<T>` 用于判断 `T` 是否为整数类型。

在这段代码中，如果传入一个整数类型，则返回值相当于 `std::enable_if_t<true, T>`，即 `T`。如果传入其他类型，返回值是 `std::enable_if_t<false, T>`，但是并没有声明这个类型，于是替换失败，被 SFINAE 忽略。

另一个常见的用法是，借助非类型模板参数。

```cpp
template <typename T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
auto f(T x) -> T {
    return x % 17;
}
```

这种写法的优点是，可以不显式指定返回值类型，而是使用 `auto` 推导。这里的 `int` 也可以换成其他简单类型，例如 `bool`、`char` 等。

还有一个用法是借助默认模板参数。

```cpp
template <typename T, typename /*未命名的模板参数*/ = std::enable_if_t<std::is_integral_v<T>, int>>
auto f(T x) -> T {
    return x % 17;
}
```

但是这个方法其实存在重大缺陷。假如接下来需要一个对于浮点数启用的重载，那么就会出现：

```cpp
template <typename T, typename = /*...*/> auto f(T x) -> T {}
template <typename T, typename = /*...*/> auto f(T x) -> T {}
```

所以实际上，这两个模板的签名是相同的，都需要两个 `typename` 参数，于是编译器会认为这是同一个函数模板的重定义错误，然后报错。建议换用其他方法。

正确的重载方式（通过返回值 `enable_if`）：

```cpp
template <typename T>
auto f(T x) -> std::enable_if_t<std::is_integral_v<T>, T> {
    return x % 17;
}

template <typename T>
auto f(T x) -> std::enable_if_t<std::is_floating_point_v<T>, T> {
    return std::fmod(x, 17);
}
```

### if constexpr

正如上文所讲，希望通过 SFINAE 在编译期使用条件分支，其实是非常麻烦的，代码也十分晦涩难懂。于是 C++17 引入了 `if constexpr`，允许像编写常规代码一样，在编译期进行条件判断。

上文的取模函数，可以像这样实现：

```cpp
template <typename T>
auto f(T x) -> T {
    if constexpr (std::is_integral_v<T>) {
        return x % 17;
    } else if constexpr (std::is_floating_point_v<T>) {
        return std::fmod(x, 17);
    } else {
        static_assert(false, "不支持的类型");
    }
}
```

请注意，`if constexpr` 和运行时的 `if` 是完全不同的，不仅仅是运行时开销的差异。如果此处使用常规的 `if`，将会由于浮点数不支持 `%` 运算符取模，以及 `static_assert(false)` 而报错。甚至可以借助 `if constexpr` 让函数返回不同的类型。

```cpp
template <typename T>
auto f(T x) {
    if constexpr (std::is_integral_v<T>) {
        return x;
    } else {
        return "Hello!";
    }
}
```

### 概念（concept）和约束（requires）

C++20 引入了 concept，可以用更加现代化的方式，对函数模板的参数进行一些约束。

假设有一个函数 `f(x)`，我们希望它只能传入整数类型，或者是 GCC 的扩展类型 `__int128`。于是可以定义一个概念，来描述这个限制。

```cpp
template <typename T>
concept is_int = std::is_same_v<T, __int128> || std::is_integral_v<T>;
```

接下来我们就可以使用这个概念了。最简单的用法是直接用 `is_int<double>` 这样的方式判断一个类型是否符合这个概念，将会获得一个布尔值。更重要的是，概念可以直接写在模板参数中，来约束这个参数的类型。

```cpp
template <is_int T>  // T 必须为整数
auto f(T x) { /*...*/ }
```

这样写，编译器会保证 `T` 类型满足 `is_int` 的概念，否则会忽略这个重载。还有一种等价的写法：

```cpp
auto f(is_int auto x) { /*...*/ }
```

标准库也预定义了一些概念，例如 `std::integral<T>` 表示整数，`std::convertible_to<T, U>` 表示 `T` 可以转换为 `U`，`std::same_as<T, U>` 表示类型相同等。

#### requires

`requires` 和概念一同被引入，表达更加多样的约束方式。相关的内容，分为“requires 子句”和“requires 表达式”两种。

requires 子句，可以用来限制一个函数模板的模板参数。如果条件不成立，就忽略这个重载。

```cpp
template <typename T>
requires (sizeof(T) >= 8);  // requires(常量 bool 值)，要求它必须求值为 true
auto f() -> void { /*...*/ }
```

requires 表达式用于表达更加复杂的约束，它本身会返回一个 `bool` 类型，表示所有的约束是否都被满足。

```cpp
// requires 表达式可以用来定义概念
template <typename T>
concept MyConcept = requires(T a, T b) {
    // requires 中可以“假设”定义若干个 T 类型的变量，然后检查操作合法性

// 简单要求：检查某个表达式是否有效
    a + b;  // 必须支持加法
    a < b;  // 必须支持小于号

// 类型要求：检查嵌套类型是否存在
    typename T::value_type;  // 必须存在这个类型

// 复合要求：检查一个表达式，对它的返回值类型进行约束
    { a + b } -> std::convertible_to<T>;  // 加法返回值可以转化为 T
    // 这里的含义是，假设 a + b 的返回值为 U，概念 std::convertible_to<U, T> 必须成立
    { a.size() } -> std::integral;  // size() 返回值是整数

// 嵌套要求：要求一个 requires 子句成立
    requires (sizeof(T) >= 16);  // 大小足够大
    requires (requires(T a, char b) { a + b; });  // 可以加上一个字符

/*
    此处的逻辑是，第一个 requires 是“子句”，括号里希望一个布尔值。
    第二个 requires 是“表达式”，正好会返回一个布尔值。
*/
};

// 例如，传入一个 std::string 就是合法的
auto f(MyConcept auto const &x) -> void {
    std::cout << x << '\n';
}
```

#### 概念“包含”

定义一个概念时，可能需要用到其他的概念，此时可能会确立“包含”关系，即满足概念 A 的类型一定会满足概念 B。被包含的概念会更加受限，于是会在重载决议中优先考虑。

```cpp
template <typename T>
concept SmallInt = std::integral<T> && (sizeof(T) <= sizeof(int));
// 显然可以保证 SmallInt 一定为 integral

auto f(SmallInt auto x) { std::cout << 1; }
auto f(std::integral auto x) { std::cout << 2; }
```

此时调用 `f(3)` 将会固定调用重载 1，`f(4LL)` 将会固定调用重载 2。使用 `std::enable_if` 这样的解决方案，将不会有这个性质。

### 变参模板

C++11 引入了变参模板，允许函数接受不限个数的参数。

模板参数的结尾，可以添加一个通过省略号声明的参数包，来包含不限数量的参数（可以包含零个）。

```cpp
template <typename ...Types>
struct Tuple {};

Tuple<int, double> t1;
Tuple<int, long, char, short> t2;
```

参数包也可以是非类型模板参数。

```cpp
template <int ...Nums>
struct Numbers {};
```

通过参数包类型，可以声明相同数量的函数参数。

```cpp
template <typename ...Ts>
void f(Ts ...args) {}

template <typename ...Ts>
void f(Ts &&...args) {}  // 可以带引用、万能引用
```

#### 参数包展开

我们将包含参数包的类型或表达式，称为一个“模式”（pattern）。在模式后面加上一个省略号来展开一个包。

```cpp
args...; // 模式为 args
f(args)...;  // 模式为 f(args)
(args * 5 + 2)...; // 模式为 (args * 5 + 2)
```

展开包的过程，相当于给这个参数包的每一项都按照相应模式进行一些处理，然后通过逗号连接。

```cpp
args = 1, 2, 3, 4
sum((args * 2)...)
// 展开成：
sum((1 * 2), (2 * 2), (3 * 2), (4 * 2))
// --------
args = int, double, char
tuple<pair<args, bool>...>
// 展开成：
tuple<pair<int, bool>, pair<double, bool>, pair<char, bool>>
```

多个长度相同的包也可以同步展开，多用于多个函数参数及其类型。

```cpp
Ts = int, double &, char &
args = 5, 7.2, 'x'

f(std::forward<Ts>(args)...)
// 展开成：
f(std::forward<int>(5), std::forward<double &>(7.2), std::forward<char &>('x'))
```

#### 使用方法

C++17 起，支持“折叠表达式”，可以通过二元运算符连接整个参数包进行处理。对于连加、连乘这种常见操作十分好用。

```cpp
template <typename ...Ts>
auto f(Ts const &...args) {
    (args + ...);  // (a1 + (a2 + (a3 + a4)))
    (... + args);  // (((a1 + a2) + a3) + a4)
    (5 + ... + args);  // (((5 + a1) + a2) + a3)
    (args + ... + 5);  // (((a1 + a2) + a3) + 5)
}
```

此处的展开也可以使用上文说的“模式”。以下代码借助逗号运算符来输出多个数。

```cpp
template <typename ...Ts>
auto f(Ts const &...args) {
    ((std::cout << args << ' '), ...);
    /*
    展开成
    (std::cout << 1 << ' '), (std::cout << 2 << ' '), (std::cout << 3 << ' ');
    */
}
```

除此以外，使用参数包的一个经典方法是分离首个参数和后续参数，然后递归处理。例如以下代码，也可以实现依次输出几个参数。

```cpp
auto output() -> void {}  // 递归终止条件

template <typename T, typename ...Ts>
auto output(T const &first, Ts const &...args) -> void {
    std::cout << first << ' ';
    output(args...);  // 递归处理后续参数
}
```

以下代码可以获得参数包的第 `i` 个类型。

```cpp
template <std::size_t index, typename T, typename ...Ts>
struct index_pack {
    using type = index_pack<index - 1, Ts...>;
};

template <typename T, typename ...Ts>
struct index_pack<0, T, Ts...> {
    using type = T;
};
```

以下是一个简易的 `printf` 实现，使用 `%` 代替任何参数，但是没有格式化功能。

```cpp
auto my_printf(const char *format) -> void {
    std::cout << format;
}

template <typename T, typename ...Ts>
auto my_printf(const char *format, T const &val, Ts const &...args) -> void {
    for (; *format != '\0'; ++format) {
        if (*format == '%') {
            if (*++format != '%') {
                std::cout << val;
                return my_printf(format, args...);
            }
        }
        std::cout << *format;
    }
}
```

另外，一个较为实用的功能是可以使用 `sizeof...(pack)` 获取包中的元素数量。

C++ 标准库还提供了 `std::integer_sequence` 用于方便地获取连续自然数组成的包，具体使用方法如下：

```cpp
template <int ...Is>
auto f(std::integer_sequence<int, Is...>) {
    // 调用时，推导出 Is 为 0, 1, 2, 3, 4
    ((std::cout << Is), ...);
}

auto main() -> int {
    f(std::make_integer_sequence<int, 5>{});
    // make_integer_sequence<int, 5> 类型，相当于
    // integer_sequence<int, 0, 1, 2, 3, 4>
    // 此外，还有 std::make_integer_sequence<N>，相当于 std::make_integer_sequence<std::size_t, N>
}
```

## 杂谈

在这个章节中，我们将会讲一些不好归类，但是很有用的语法特性。

### 范围 for 循环

C++11 起，支持通过范围 for 循环，来更方便地遍历一个容器。具体语法如下：

```cpp
for (auto x : vec) {  // 依次输出 vec 中的所有元素
    std::cout << x << ' ';
}
```

其中的 `vec` 是类似 `std::vector`、`std::set` 这样的容器，支持 `.begin()`、`.end()` 返回首尾迭代器。特别地，C 风格数组也可以使用范围 `for` 循环遍历，会依次遍历数组中的所有元素。

`auto x` 可以替换成引用。包括以下允许的形式：

-   `auto &x`：左值引用，允许修改容器内元素的值。
-   `auto const &`：常量左值引用，**防止复制开销**。
-   `auto &&`：万能引用。根据元素值类别推断左值/右值引用。

`auto` 也可以替换成具体的类型。

范围 `for` 循环，等价于以下形式：

```cpp
auto it = vec.begin();
auto end = vec.end();
for (; it != end; ++it) {
    auto x = *it;  // 这里的变量 x 声明方式与冒号左侧部分相同
    // ... 循环体
}
```

所以，**即使使用范围 for 循环，往往也不能在循环途中修改容器**。

### 结构化绑定

C++17 起，可以通过结构化绑定，方便地将一个对象的几个成员绑定到局部变量。例如：

```cpp
std::pair pair{2, 3};

auto [x, y] = pair;
// 相当于
auto x = pair.first;
auto y = pair.second;

// 也可以用其他的初始化方式
auto [x, y]{pair};
auto [x, y](pair);
```

结构化绑定一个对象时，将会把这些局部变量，依次绑定到右侧对象的各个公开成员中（按声明顺序，例如这里就是 `first` 和 `second`）。

数组和 `std::array` 也支持结构化绑定。

```cpp
std::array<int, 3> arr{};
auto [x, y, z] = arr;
```

结构化绑定也支持各种形式的引用，允许修改对象，或者免除复制。包括 `auto`、`const auto &`、`auto &`、`auto &&` 等。建议对于较大的对象使用 `auto const &` 绑定来避免复制开销。

事实上，以下的过程可以更好地描述结构化绑定的行为：

```cpp
std::pair pair{2, 3};

// 首先，按照给定的方式定义一个临时对象
// 假设使用 auto &[x, y] = pair
auto &tmp = pair;

// 接下来，每次使用 x 都替换成 tmp.first，每次使用 y 都替换成 tmp.second
// 例如，std::cout << x; 相当于
std::cout << tmp.first;

// 这里也可以进行修改，并且影响原对象
// 例如 x = 5
tmp.first = 5;  // tmp 是引用，所以会修改原对象
// 相应地，如果使用 auto [x, y] = pair 声明，就和原对象无关

// 绝大多数情况下，x 的行为都和 tmp.first 相同
// 例如 decltype(x), decltype((x))
decltype(tmp.first);  // int（而不是可能被认为的 int &，这是一个实体，会得到 std::pair<int, int>::first 被声明的类型）
decltype((tmp.first));  // int &
```

基于范围的 `for` 循环中也可以使用结构化绑定。

```cpp
for (auto const &[key, value]: map) {
    // ...
}
```

### if 初始化语句

C++17 起，`if` 语句，在条件之前可以添加一个初始化语句，在条件判断之前执行。在此处定义的变量，作用域会在 `if` 的右侧花括号处结束。

```cpp
if (auto res = f(); is_prime(res)) {
    // 接下来可以使用 res
} else {
    // 也可以使用 res
}
// 此处不再可以使用 res
```

### 三路比较运算符

两个对象的大小关系往往分为三类：小于、等于或大于。有些情况下，我们会根据它们的比较关系进行不同的分支操作。

```cpp
std::string s1, s2;
if (s1 < s2) {
    std::cout << "less";
} else if (s1 == s2) {
    std::cout << "equal";
} else {
    std::cout << "greater";
}
```

注意到，这种写法最多会调用两次比较函数，非常浪费。实际上，我们完全有能力一次性判断出它是三种大小关系的哪一个。C++20 引入了“三路比较运算符”，用来表达两个对象的大小关系。

三路比较运算符的返回值通常为 `std::strong_ordering`。它定义了几个常量值，包括（省略 `std::strong_ordering::` 前缀）：

-   `less`，表示左侧小于右侧。
-   `equal` 或 `equivalent`，表示左侧等于右侧。它们是实际上是相等的。
-   `greater`，表示左侧大于右侧。

可以用以下的方式使用：

```cpp
auto cmp = s1 <=> s2;
if (cmp == std::strong_ordering::less) { /*...*/ }
else if (cmp == std::strong_ordering::equal) { /*...*/ }
else { /*...*/ }
```

可以发现，这种写法过于冗长。所以可以使用另一种较为简便的方法，让 `std::strong_ordering` 对象和 `0` 比较，返回布尔值。

-   `cmp < 0`：`less`。
-   `cmp == 0`：`equivalent`。
-   `cmp > 0`：`greater`。

标准类型之间都已经定义了三路比较运算符。可以使用三路比较运算符描述很多的比较逻辑。例如依次按照 `a`、`b`、`c` 比较：

```cpp
if (auto cmp = x.a <=> y.a; cmp != 0) return cmp;
if (auto cmp = x.b <=> y.b; cmp != 0) return cmp;
return x.c <=> y.c;
```

可以重载 `<=>` 运算符，在此之后，编译器会自动生成 `<`、`<=`、`>`、`>=` 这四个运算符。C++20 之后，重载 `==` 运算符会自动生成 `!=` 运算符。

C++20 之后，可以通过如下方式，让编译器自动生成全部六个比较函数。这将会基于各个成员的声明顺序，进行字典序比较。

```cpp
struct S {
    auto operator<=> (S const &) const = default;
};
```

实际上，除了 `std::strong_ordering` 以外，还有几个类似的类型。它们之间的使用方式一致，但是语义有所不同。

-   `std::strong_ordering`：表示两个相等的对象是无法区分的，即如果 `a == b`，一定有 `f(a) == f(b)`。例如字符串比较。
-   `std::weak_ordering`：表示两个相等的对象可能被区分，例如不区分大小写的字符串比较。
-   `std::partial_ordering`：不在意相等对象的可区分性，但是有一个额外的状态，表示这两个对象之间“不可比较”。（例如，浮点数的 `NaN` 返回 `partial_ordering`；其他内置类型返回 `strong_ordering`）

所有比较类别都有 `less`、`greater` 和 `equivalent`，`strong_ordering` 有额外的 `equal`，`partial_ordering` 有额外的 `unordered`。

不同的返回类型不会影响运算符的生成、标准库工具的行为，但是可以体现不同的语义，有利于编写“自解释”的代码。通常情况下使用 `strong_ordering` 即可（例如按照所有成员的字典序比较）。

#### 标准库的比较函数

很多标准库函数允许我们传入比较函数（例如 `std::sort`），用于替代小于号进行比较。这类比较函数需要满足一些约束。（如果是通过自定义类型的重载运算符，也需要满足相同规则）

小于号的语义必须是“严格弱序”，即如同三路比较的结果为 `std::weak_ordering::less`。一个常见的错误是以下代码：

```cpp
std::sort(v.begin(), v.end(), [](auto a, auto b) { return a.val <= b.val; });
```

具体来讲，需要满足以下要求：

-   `!(a < a)`。
-   如果 `a < b`，则 `!(b < a)`。
-   如果 `a < b` 且 `b < c`，则 `a < c`。
-   定义 `equiv(a, b) = !(a < b) && !(b < a)`，表示二者的等价关系；这种等价关系也可传递，即如果 `equiv(a, b)` 且 `equiv(b, c)`，则 `equiv(a, c)`。

以及另外的几个要求：

-   必须能够接受 `const` 类型的参数。（通常使用常量引用或者值传递小对象作为参数）
-   相同的输入必须得到确定的输出。

### 异常处理

异常是 C++ 处理运行时错误的机制。当程序出现运行时错误时，可以跳出常规的代码执行逻辑，转到专用的错误处理代码。

异常处理采用以下方式：

-   异常对象：用于描述发生了什么错误。
-   抛出异常：停止当前函数执行，沿着函数调用栈向上回溯，直到被捕获。这个过程称为“栈展开”。
-   捕获异常：当捕获到特定类型的异常对象，停止栈展开过程，执行对应的处理代码。

但是需要注意，只有代码抛出的异常才能被捕获。越界访问、空指针访问等未定义行为导致的运行时错误无法被捕获。

例如以下代码：

```cpp
int divide(int x, int y) {
    if (y == 0) {
        // 抛出异常，类型为 std::invalid_argument
        throw std::invalid_argument("division by zero.");
    }
    return x / y;
}

int main() {
    try {  // 这个代码块中有可能抛出异常并捕获
        int x{}, y{};
        std::cin >> x >> y;
        std::cout << divide(x, y) << '\n';
    } catch (const std::invalid_argument &err) {
        // 捕获到类型为 std::invalid_argument 的异常，执行处理代码
        // err.what() 返回构造时传递的字符串参数
        std::cout << "Cannot calculate. Error: " << err.what() << '\n';
    } catch (...) {
        // 捕获所有类型的异常
        std::cout << "Unknown Error." << '\n';
    }
}
```

异常对象可以是任意类型（如 `int`），但是习惯使用 `std::exception` 的某个派生类。以下是若干个标准库中定义的异常，使用缩进层级表示继承关系。

```cpp
std::exception
├── std::bad_alloc                // 内存分配失败 (new)
├── std::bad_cast                 // 动态转换失败 (dynamic_cast)
├── std::bad_typeid               // typeid 操作失败
├── std::bad_exception            // 意外异常
├── std::logic_error              // 逻辑错误
│   ├── std::invalid_argument     // 无效参数
│   ├── std::domain_error         // 定义域错误
│   ├── std::length_error         // 长度超出限制
│   └── std::out_of_range         // 超出有效范围
└── std::runtime_error            // 运行时错误
    ├── std::range_error          // 计算结果超出范围
    ├── std::overflow_error       // 算术上溢
    └── std::underflow_error      // 算术下溢
```

如果想要抛出自定义类型的异常，应从某个标准异常派生。可以覆写虚函数 `what()` 返回提示信息。

```cpp
struct MyException : public std::exception {
    std::string message;
    MyException(std::string s) : message("Error: " + std::move(s)) {}

auto what() const noexcept -> char const * override {
        return message.c_str();
    }
};
```

在发生错误时，异常处理的运行时效率非常低（但是正常运行无额外开销）。不要使用异常处理代替正常代码逻辑（例如跳出多层递归），除非异常处理的性能开销可以接受。

在可能抛出异常的代码中，为了保证资源被正确清理，需要使用 RAII 机制，通过对象的析构函数来清理资源。`std::unique_ptr` 可能会有一些帮助。

#### 异常安全

在一个操作中，如果抛出了异常，这个操作将被中断。这也意味着，一个对象可能已经被修改到了一个中间状态，但是无法进一步操作，导致操作未完成的情况下，原始数据丢失。

函数可以有以下几个级别的异常安全保证，是从严格到宽松的关系。

-   不抛出保证。无论如何，该函数都不会抛出异常。可以使用 `noexcept` 显式声明这个函数是不抛出异常的。析构函数、移动构造和赋值、交换函数必须标记为 `noexcept`。
-   强异常保证。如果函数抛出异常，程序将会保持调用前的状态。
-   基本异常保证。如果函数抛出异常，相关对象可能发生数据丢失，但是程序仍然处于有效状态。不会发生资源泄露等更严重问题。
-   无异常保证。如果函数抛出异常，不对程序状态做任何保证。

C++ 标准对标准库函数声明了各自的异常安全保证。

### 编译器扩展

以下的内容均为 GCC 的编译器扩展，而非标准行为。包含编译器扩展的代码会降低可移植性，但是有很多编译器扩展在 OI 中是很方便的。若无特殊说明，这些内容在 NOI 系列考试中大概率是可以使用的，但是**实际请以考试编译环境为准**。

在主流编译器中，GCC 和 clang 有很多相似的扩展。MSVC 则大有不同。

如果你正在研究 C++ 标准语法，请打开 `-ftrapv` 对编译器扩展行为给出警告。

#### 万能头文件

GCC 提供了头文件 `bits/stdc++.h` 包含全部 C++ 标准库头文件。在 OI 中可以避免多次添加头文件，切换上下文，打断思路。

#### \_\_int128

`__int128` 是一种扩展整数类型，能够存储 $[-2^{127}, 2^{127})$ 范围内的整数。它还有无符号变种 `unsigned __int128`，值域为 $[0, 2^{128})$。

它支持和其他整数一致的算术运算（加减乘除模），但是标准库并没有提供支持。例如 `cin` 和 `cout` 不能输入输出 `__int128`，`abs()` 函数不能对 `__int128` 取绝对值。

GCC 默认使用的是名为 `gnu++` 的扩展标准，可能支持 `__int128` 的更多操作。在考场上，请始终使用 `-std=c++14`（或以后可能换用更高标准）编译程序，避免 CE。

#### 内建位运算函数

GCC 提供了很多用来进行位运算的编译器扩展。这些函数的效率很高，远高于手写（可能直接编译成一条硬件指令）。

这些函数都是接受 `unsigned int` 类型。同时提供了不同后缀的变种，接受 `unsigned long` 和 `unsigned long long`。例如：

| 函数              | 参数类型             |
| ----------------- | -------------------- |
| `__builtin_clz`   | `unsigned int`       |
| `__builtin_clzl`  | `unsigned long`      |
| `__builtin_clzll` | `unsigned long long` |

C++20 起，标准库提供了它们的替代品。在调用标准库函数时，可以自动推导类型，但是传入的必须是无符号整数，否则会编译错误。

| 内建函数             | 替代方案               | 描述              |
| -------------------- | ---------------------- | ----------------- |
| `__builtin_popcount` | `std::popcount(x)`     | 二进制“1”的个数   |
| `__builtin_clz`      | `std::countl_zero(x)`  | 二进制前导零数量  |
| `__builtin_ctz`      | `std::countr_zero(x)`  | 二进制后缀零数量  |
| `__builtin_parity`   | `std::popcount(x) & 1` | popcount 的奇偶性 |
| `std::__lg`          | `std::bit_width(x)-1`  | `log2(x)` 下取整  |

`std::__lg` 本质上不是内建函数，而是标准库实现过程中的一个工具函数。因为只有 GCC 配套的 libstdc++ 标准库提供了这个函数，所以它也不具备可移植性，和内建函数性质相似，所以归到这里。

向这些函数中传入 0 是未定义行为。

另外还有一个常用的函数是 `std::__gcd(x, y)`，用于求两个整数的最大公约数，它的性质和 `std::__lg` 一致。C++17 标准提供了 `std::gcd` 替代，并且采用了更高效的“二进制 gcd”算法。

#### 调试宏

GCC 调试宏为标准库工具提供了更多的检查，可以检查容器访问越界、迭代器非法使用，甚至 `lower_bound` 之前没有排序这样的问题。但是**对于原生数组依旧没有任何检查**。

可以使用 `std::array` 或者 `std::vector` 替代所有原生数组，配合调试宏，可以提供越界检查。并且前者不会引入任何的运行时开销。

使用调试宏可以发现绝大多数运行时错误的位置，配合 gdb 工具可以获取更佳体验。

在**头文件之前**添加以下宏定义即可使用调试宏。

```cpp
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#define _GLIBCXX_SANITIZE_VECTOR 1
```

或者添加以下编译选项：

```
-D_GLIBCXX_DEBUG=1 -D_GLIBCXX_DEBUG_PEDANTIC=1 -D_GLIBCXX_SANITIZE_VECTOR=1
```

**调试宏会极大地影响代码运行速度**（让代码的运行时间延长 5~10 倍，甚至更多），所以在提交到 OJ 之前需要删除调试宏。建议在本地编译选项中包含调试宏，而不是通过代码中的 `#define`。进行性能测试前请删除调试宏。

## 实用标准库工具

下方会列出一些比较好用，但又没有 `set`、`pair`、`vector`、`sort` 那样熟知的标准库工具。C++ 标准库其实有很多工具都很好用。

### assert

`assert` 是一个预定义的宏，在 `cassert` 头文件中。它用于确保某个条件成立，否则中断程序运行，并输出诊断信息。例如：

```cpp
void f(int x) {
    assert(x >= 0);
    // ...
}
```

此时这个函数如果传入了一个负数，将会在这一行出现断言失败。此时的报错信息可以提示错误行号，方便调试。

C++26 起可以使用 `contract_assert` 来替代 `assert`，但是在此之前，`assert` 都极为好用。

### 随机数生成器

C++11 起通过 `random` 头文件提供了更加现代的随机数生成器。此前使用 `rand()` 进行随机数生成，随机数质量较低，并且值域上限较小（由实现定义，通常为 32767），无法满足使用。

最常用的随机数生成器是 `std::mt19937`。通过以下方式定义一个 `mt19937` 生成器：

```cpp
std::mt19937 rng{/*seed*/};
```

`mt19937` 生成的是伪随机数，本质上是通过一个种子不断地进行确定变换。相同种子会导致接下来随机数生成的行为一致。

`std::random_device{}()` 可以生成一个真随机数，但是效率较低，通常只用来提供一次随机种子。以下是一个常见的用法：

```cpp
std::mt19937 rng{std::random_device{}()};
```

接下来便可以开始使用 `rng` 生成随机数了。直接使用 `rng()` 可以在 `unsigned int` 值域内均匀随机地生成一个整数。

如果希望生成某个值域内的整数，通常情况下可以简单地通过取模实现。如果希望绝对的均匀随机，可以通过 `std::uniform_int_distribution`。

```cpp
// 假设需要 [1, 10]
int x = rng() % 10 + 1;  // 通常情况下足够
std::uniform_int_distribution dist{1, 10};
int y = dist(rng);
```

如果要生成数据的值域大于 `unsigned int` 值域，也可以安全地使用 `uniform_int_distribution`。

```cpp
long long max = 1e14;

std::uniform_int_distribution<long long> dist{1, max};
auto res = dist(rng);  // res 类型为 long long
```

更多的随机数生成器和随机分布，见 [cppreference](https://en.cppreference.com/w/cpp/header/random.html)。

### ranges

C++20 起添加了 ranges 库，进一步方便了代码编写。一方面优化了标准库算法的使用，另一方面添加了更多的实用功能。

#### ranges 算法

`ranges` 命名空间中重新实现了几乎所有标准库算法（`algorithm` 头文件），最大的特点就是可以不再显式传入 `begin` 和 `end` 参数。

```cpp
std::vector<int> vec;

std::ranges::sort(vec);
std::ranges::sort(vec.begin(), vec.end() - 1);  // 两种方式均可支持
```

所以 C++20 起，建议全面使用 ranges 算法代替旧的标准库算法。

ranges 算法还有一个“投影”特性，可以传入一个投影函数，实际表现相当于将范围内的所有元素进行一次投影，对投影后的元素进行操作，间接影响原始元素。这只是一个直观理解，实际上每个 ranges 算法都对投影函数做了严谨的定义。例如，假设投影函数为 `proj`，`sort` 可以保证排序后的结果，若 `x` 在 `y` 之前，则 `proj(y)` < `proj(x)` 为 `false`。

听起来可能有些抽象。可以通过以下例子理解，这会把所有的元素按照 `second` 排序。

```cpp
std::vector<std::pair<int, int>> vec;
std::ranges::sort(vec, std::less{}/*比较函数*/, [](auto x) { return x.second; }/*投影函数*/);
```

#### 视图

视图（views）是 ranges 库中的另一个重要概念。它可以通过“管道运算符”对范围进行操作，允许进行链式地数据处理。视图通过头文件 `ranges` 提供。

管道运算符实际上是重载的按位或，使用方式为 `range | op`。`range` 是原始范围，然后使用范围适配器 `op` 来描述一个操作，最后返回一个新范围。

例如，`std::views::reverse` 就是一个范围适配器，可以将 `range` 中的元素逆序。以下代码可以逆序输出 `vec` 中的所有元素。

```cpp
std::vector vec{1, 2, 3, 4};
for (auto x: vec | std::views::reverse) {
    std::cout << x << ' ';
}
```

实际上，大多数视图是惰性求值的，即在访问元素的同时进行计算。如果最终的范围遍历一半就中止，不会有额外的计算。

以下是一些常用的视图（省略 `std::views` 命名空间）：

-   `filter(pred)`：筛选符合条件的元素。仅保留 `pred(x)` 为 `true` 的函数。
-   `transform(func)`：映射元素。对每个旧范围的元素 `x`，新范围会包含一个元素 `func(x)`。
-   `take(n)`：只取前 `n` 个元素。
-   `drop(n)`：跳过前 `n` 个元素。
-   `reverse`：反转序列。
-   `join`：展平一层嵌套范围。例如 `{{0, 1}, {2, 3}}` 变为 `{0, 1, 2, 3}`。
-   `split(x)`：根据指定元素分隔范围。例如 `{1, 2, 0, 3, 0, 4}` 按照 `0` 划分，变为 `{{1, 2}, {3}, {4}}`。

以及可以使用 `std::views::iota(a, b)` 生成一个 $[a, b)$ 范围内的连续序列。例如 `std::views::iota(3, 6)` 包含元素 3、4、5。

C++23 起，可以使用 `std::ranges::to` 把一个范围转换为另一个范围，即构造一个指定类型范围，依次包含原范围的所有元素。

例如，以下是一个字符串的分割。

```cpp
std::string s{"abc,de,fg"};
for (auto x: s | std::views::split(',')) {
    std::cout << std::ranges::to<std::string>(x) << '\n';
}
```

以下代码可以输入一个 1-index 的 vector。

```cpp
std::vector<int> vec(n + 1);
for (auto &x: vec | views::drop(1)) std::cin >> x;
```

## 实战：实现简易 vector

在这个章节中，我们将会在最新的 C++ 标准下实现一个简易的 `vector`，支持 `std::vector` 的部分功能。

`vector` 使用一片连续内存存储对象。为了实现扩容操作，采取以下策略：

-   预留一部分内存，足以存储 `capacity` 个元素。但是实际只有 `size` 个元素。
-   当 `size == capacity` 时发生扩容，重新分配内存、移动数据，使得 `capacity` 翻倍。

可以证明，这种策略下 `push_back` 的均摊复杂度是 $O(1)$。

首先，定义一个元素类型 `A`，便于观察 `std::vector` 的行为。

```cpp
struct A {
    int value{};

A() { std::cout << "Default Construct\n"; }
    A(int value): value{value} { std::cout << "Construct" << value << '\n'; }
    A(A const &other): value{other.value} { std::cout << "Copy Construct" << value << '\n'; }
    A(A &&other) noexcept: value{other.value} { std::cout << "Move Construct" << value << '\n'; }

auto operator= (A const &other) -> A & {
        std::cout << "Copy Assign" << value << ' ' << other.value << '\n';
        value = other.value;
        return *this;
    }
    auto operator= (A &&other) noexcept -> A & {
        std::cout << "Move Assign" << value << ' ' << other.value << '\n';
        value = other.value;
        return *this;
    }
};
```

### 动态内存分配

我们先来实现动态内存分配相关操作。事实上，`std::vector` 使用分配器（Allocator）来实现，但是相关机制较为复杂，我们采用简化方案：封装静态成员函数 `allocate` 和 `deallocate` 进行分配和解分配。

```cpp
namespace mystd {
    template <typename T>
    class vector {
        // 分配未初始化内存，足以存储 n 个 T 类型
        auto constexpr static allocate(std::size_t n) -> T * {
            if (n == 0) return nullptr;
            if (std::is_constant_evaluated()) {
                // 编译器开洞实现 std::allocator，可以在编译期动态分配内存
                // 正常的常量求值无法使用 ::operator new
                return std::allocator<T>{}.allocate(n);
            } else {
                // 显式指定对象对齐，允许非标准对齐的对象
                auto ptr = ::operator new(n * sizeof(T), std::align_val_t{alignof(T)});
                return static_cast<T *>(ptr);
            }
        }

// 释放 allocate 分配的内存
        auto constexpr static deallocate(T *ptr, std::size_t n) noexcept -> void {
            if (std::is_constant_evaluated()) {
                std::allocator<T>{}.deallocate(ptr, n);
            } else {
                ::operator delete(ptr, std::align_val_t{alignof(T)});
            }
        }
    };
}
```

### 基本定义

`vector` 需要以下三个成员存储数据：

-   `data_`：存储区开始的指针。
-   `size_`：当前存储的元素数量。
-   `capacity_`：存储区最多能存储的元素数量。

还需要定义一些嵌套类型：

-   `iterator`：迭代器。
-   `const_iterator`：常量迭代器。
-   `value_type`：元素类型，即 `T`。

这里我们直接使用指针作为迭代器。

```cpp
private:
    T *data_ = nullptr;
    std::size_t size_ = 0;
    std::size_t capacity_ = 0;

using iterator = T *;
    using const_iterator = T const *;
    using value_type = T;
public:
    constexpr vector() = default;

auto constexpr size() const noexcept -> std::size_t { return size_; }
    auto constexpr capacity() const noexcept -> std::size_t { return capacity_; }
    auto constexpr data() noexcept -> T * { return data_; }

// begin() end() 需要同时提供 const 和非 const 版本
    auto constexpr begin() const noexcept -> const_iterator { return data_; }
    auto constexpr end() const noexcept -> const_iterator { return data_ + size_; }
    auto constexpr begin() noexcept -> iterator { return data_; }
    auto constexpr end() noexcept -> iterator { return data_ + size_; }
```

### 基础功能

我们将会在这里实现构造函数、析构函数、下标访问等基本功能。

```cpp
public:
    constexpr vector() = default;
    constexpr ~vector() {
        destroy_all();
    }

explicit constexpr vector(std::size_t count)
        : data_(allocate(count)), capacity_(count)
    {
        try {
            for (T *ptr = data_; size_ != count; ++size_, ++ptr) {
                std::construct_at(ptr);
            }
        } catch (...) {
            // 构造失败，销毁资源并释放内存（异常安全）
            destroy_all();  // 由于 size_ 是当前元素数量，可以直接使用
            throw;  // 重新抛出异常
        }
    }
    constexpr vector(std::size_t count, T const &value)
        : data_(allocate(count)), capacity_(count)
    {
        try {
            for (T *ptr = data_; size_ != count; ++size_, ++ptr) {
                std::construct_at(ptr, value);
            }
        } catch (...) {
            destroy_all();
            throw;
        }
    }
    // 复制构造函数
    constexpr vector(vector const &other)
        : data_(allocate(other.size())), capacity_(other.size())
    {
        try {
            T const *in = other.data_;
            T *out = data_;
            for (; size_ != other.size(); ++size_, ++in, ++out) {
                std::construct_at(out, *in);
            }
        } catch (...) {
            destroy_all();
            throw;
        }
    }

// 移动构造函数
    constexpr vector(vector &&other) noexcept
        : data_(other.data_), size_(other.size_), capacity_(other.capacity_)
    {
        // 将另一个容器置空，避免内存多次释放
        other.data_ = nullptr;
        other.size_ = other.capacity_ = 0;
    }

// 接受一个范围内的数据
    template <typename InputIt>
    constexpr vector(InputIt first, InputIt last): vector() {
        // 如果是 ForwardIterator，预先获取区间大小；否则依次 emplace_back
        using category = typename std::iterator_traits<InputIt>::iterator_category;
        constexpr bool is_forward = std::is_base_of_v<std::forward_iterator_tag, category>;

if constexpr (is_forward) {
            std::size_t size = std::distance(first, last);
            reserve(size);
        }

for (; first != last; ++first) {
            emplace_back(*first);
        }
    }

// std::initializer_list
    constexpr vector(std::initializer_list<T> list)
        : vector(list.begin(), list.end()) {}

auto constexpr operator[] (std::size_t pos) -> T & {
        return data_[pos];
    }
    // 同时提供常量的只读下标访问
    auto constexpr operator[] (std::size_t pos) const -> T const & {
        return data_[pos];
    }

// 交换两个 vector
    auto constexpr swap(vector &other) noexcept -> void {
        std::swap(data_, other.data_);
        std::swap(size_, other.size_);
        std::swap(capacity_, other.capacity_);
    }
    // 提供非成员的 swap，允许 ADL 查找
    auto friend constexpr swap(vector &lhs, vector &rhs) noexcept -> void {
        lhs.swap(rhs);
    }
    // 复制赋值
    auto constexpr operator= (vector const &other) -> vector & {
        if (this == &other) return *this;  // 避免自赋值
        vector<T> tmp(other);  // 构造临时对象
        swap(tmp);  // 直接和临时对象交换，复用代码且异常安全
        return *this;
    }
    // 移动赋值
    auto constexpr operator= (vector &&other) noexcept -> vector & {
        vector<T> tmp(std::move(other));  // 移动构造一个临时对象，other 直接置空
        swap(tmp);  // 和临时对象交换，旧资源将在 tmp 销毁时释放
        // 可以证明，这种方式对于自赋值是安全的
        return *this;
    }
private:
    // 销毁所有元素，释放资源
    auto constexpr destroy_all() noexcept -> void {
        T *ptr = data();
        for (std::size_t i = 0; i != size(); ++i, ++ptr) {
            std::destroy_at(ptr);
        }
        deallocate(data(), capacity());
    }
};
```

### 动态扩容

我们将会实现 `push_back`、`emplace_back`，并正确地处理扩容逻辑。

```cpp
auto constexpr back() const -> T const & { return data_[size() - 1]; }
auto constexpr front() const -> T const & { return data_[0]; }
auto constexpr back() -> T & { return data_[size() - 1]; }
auto constexpr front() -> T & { return data_[0]; }

template <typename ...Ts>
auto constexpr emplace_back(Ts &&...args) -> T & {
    // 检查是否需要扩容
    if (size() == capacity()) {
        // 执行扩容
        // 分配一片新的内存
        auto new_capacity = capacity() == 0? 1: capacity() * 2;
        auto new_data = allocate(new_capacity);
        // 直接构造新对象
        auto pos = new_data + size();
        std::construct_at(pos, std::forward<Ts>(args)...);
        // 逐个移动现有元素
        // 但是此处需要注意，仅当移动构造为 noexcept 才能保证强异常安全
        // 否则如果在某个元素移动时抛出异常，将会永久丢失它的状态，无法保证回退
        // 标准库的处理是，如果不能安全地移动，就使用拷贝构造。
        T *in = data();
        T *out = new_data;
        try {
            for (std::size_t i = 0; i != size(); ++i, ++in, ++out) {
                if constexpr (std::is_nothrow_move_constructible_v<T>) {
                    std::construct_at(out, std::move(*in));
                } else {
                    std::construct_at(out, *in);
                }
            }
        } catch (...) {
            // 销毁刚构造的新元素
            std::destroy_at(pos);
            for (auto ptr = new_data; ptr != out; ++ptr) {
                std::destroy_at(ptr);
            }
            deallocate(new_data, new_capacity);
            throw;
        }
        // 释放旧数据
        destroy_all();
        data_ = new_data, capacity_ = new_capacity;
    } else {
        // 直接在结尾构造
        auto pos = data() + size();
        std::construct_at(pos, std::forward<Ts>(args)...);
    }
    ++size_;
    return back();
}

auto constexpr push_back(T const &x) -> void {
    emplace_back(x);
}

auto constexpr push_back(T &&x) -> void {
    emplace_back(std::move(x));
}

auto constexpr reserve(std::size_t new_cap) -> void {
    if (new_cap <= capacity()) return;
    auto new_data = allocate(new_cap);

// 和 emplace_back 相同逻辑，决定移动还是复制
    T *in = data();
    T *out = new_data;
    try {
        for (auto end_ptr = data() + size(); in != end_ptr; ++in, ++out) {
            if constexpr (std::is_nothrow_move_constructible_v<T>) {
                std::construct_at(out, std::move(*in));
            } else {
                std::construct_at(out, *in);
            }
        }
    } catch (...) {
        for (auto ptr = new_data; ptr != out; ++ptr) {
            std::destroy_at(ptr);
        }
        deallocate(new_data, new_cap);
        throw;
    }

destroy_all();
    data_ = new_data;
    capacity_ = new_cap;
}
```

### 其他操作

此处以 `insert` 为例，主要演示何时应该使用构造，何时应该使用赋值。

```cpp
// 这里采取了一种简化的实现方法，按值传参，在内部统一移动
// 对于 std::array 这类移动开销大的对象可能性能较差
// 标准库分别实现了 T const & 和 T &&，更加健壮
// 标准库 insert 没有强异常安全的保证，所以可以直接使用移动赋值和构造
auto constexpr insert(const_iterator pos, T value) -> iterator {
    std::size_t index = pos - begin();
    if (size() == capacity()) {
        // 扩容的同时移动数据
        auto new_capacity = capacity() == 0? 1: capacity() * 2;
        auto new_data = allocate(new_capacity);

T *in = data();
        T *out = new_data;
        try {
            for (; in != pos; ++in, ++out) {
                // 内存位置尚未构造对象，所以使用构造而非赋值
                std::construct_at(out, std::move(*in));
            }
            std::construct_at(out, std::move(value)), ++out;
            for (auto end_ptr = data() + size(); in != end_ptr; ++in, ++out) {
                std::construct_at(out, std::move(*in));
            }
        } catch (...) {
            // 出现异常，保证无资源泄漏即可
            for (auto ptr = new_data; ptr != out; ++ptr) {
                std::destroy_at(ptr);
            }
            deallocate(new_data, new_capacity);
            throw;
        }

destroy_all();
        data_ = new_data, capacity_ = new_capacity;
        ++size_;
    } else {
        // 直接移动数据
        // 最后一个元素使用构造，其他元素使用赋值
        T *out = data() + size();
        // 结尾插入元素，直接构造即可
        if (pos == end()) {
            std::construct_at(out, std::move(value));
            ++size_;
        } else {
            T *in = std::prev(out);
            std::construct_at(out, std::move(*in)), --out, --in;
            ++size_;
            // 此后如果抛出异常，可以保证容器基本信息（size_）正确，但是容器内数据处于未指定状态
            for (; out != pos; --out, --in) {
                // 当这个位置已经有了一个对象，应当使用赋值
                // 否则应当是先销毁再构造，但是用户定义的赋值可能更加高效
                *out = std::move(*in);
            }
            // 此时 out 的位置上同样已经存在对象
            // 通过赋值放置新对象
            *out = std::move(value);
        }
    }
    return begin() + index;  // 转换成非常量迭代器
}

```

其他功能不再演示如何实现。以上功能的完整代码见[洛谷云剪贴板](https://www.luogu.com.cn/paste/n0pegsd0)。

## 结语

不知不觉间，这篇专栏已经包含不少内容了。由于篇幅限制，这个专栏也即将告一段落。

在这个专栏中，我们介绍了很多可能不被大家熟知的语法特性，从基本的变量、类型，到模板元编程这样更加深入的内容。当然，这篇专栏只是 C++ 语言的冰山一角，但是希望你能够从这个专栏得到一些启示，了解到一些比较新鲜的知识。由于个人能力有限，某些地方的表述可能不够清晰，甚至可能存在笔误或理解上的偏差。如果遇到困惑或发现错误，还请多多包涵，也欢迎指正和交流。

正如前言所讲，这些语法特性可能对赛场上的得分不会有帮助，但我相信它们也不会是毫无意义的。也许有一天，你会想要封装属于自己的模板库；也许你会发现，lambda 函数可以简化封装函数的过程，简化你的代码；也许你面对编译器给出的大量报错不再慌张，而是可以冷静地分析其中的函数重载、模板特化；也许你在以后工作中也会使用 C++ 进行开发，这些语法特性会成为你项目中的一砖一瓦……那些看似晦涩的特性，当你真正需要它们时，或许也会展现出惊人的价值。

最后，感谢你与我共同完成这次 C++ 的学习之旅。“路漫漫其修远兮”，编程之路永无止境，我们都是正在探索的初学者。愿你对技术的好奇心永远如初，愿这段内容能成为你未来编程路上的小小助力。

正在渲染内容...