C++ 基础知识指南

· · 科技·工程

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

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

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

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

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

声明

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

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

本文最近更新于 2025/09/14，修复了一些笔误。

前置知识

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

编程工具

编译器

编译器是一种软件，负责将源代码编译成可执行文件。可执行文件（例如 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 优化。

基础语法

输入输出

#include <iostream>
using namespace std;

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

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

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

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

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

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

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

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

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

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。

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

未定义行为和错误程序

接下来的代码中，将会涉及“未定义行为”及相关概念。可以参考 cppreference 页面。

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

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

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

bool f(int x) {
    return x + 1 > x;  // 不溢出的情况下，整数 +1 一定大于自身
}
// 可能优化成：
bool f_(int x) {
    return true;
}
int g(int *ptr) {
    int value = *ptr;  // 已经进行解引用，基于 UB 假设一定不是空指针
    if (ptr == nullptr) {
        return 0;
    } else {
        return value;
    }
}
// 可能优化成：
int g_(int *ptr) {
    return *ptr;
}

变量

#include <iostream>
using namespace std;

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

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

变量名

变量名必须是一个合法的“标识符”（Identifier）。即有以下的要求：

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

除此以外，用户定义的标识符（变量、函数、类型等）不能与关键字完全相同。以双下划线开头（如 __reserved），或者单下划线紧跟大写字母开头（如 _Reserved），行为是未定义的。

变量作用域

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

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

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

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

#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 引入所有名字。

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 这样的方式访问。可以用以下方式创建命名空间别名。

namespace rg = std::ranges;

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

#include <cmath>

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

存储期

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

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

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

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

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

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

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

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

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

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

#include <iostream>

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

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

变量初始化

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

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

核心规则概括

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

零初始化

零初始化（Zero-Initialization）是将对象逐位赋值为 0 的初始化方式。C++ 中没有专用的零初始化语法，但是其他初始化方式可能包含零初始化。

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

默认初始化

默认初始化（Default-Initialization）是在没有指定初始化器时的初始化方式。例如以下场景将会执行默认初始化：

int x;
auto *ptr = new double;

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

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

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

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

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

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

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

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

值初始化

值初始化（Value-Initialization）在使用空初始化器构造对象时执行，以下是几种常见的场景：

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

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

有以下特例：

值初始化的效果如下：

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

聚合初始化

聚合初始化（Aggregate-Initialization）是通过初始化列表来初始化聚合类型的过程。这是一种特殊的列表初始化。

聚合类型

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

指派初始化器

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

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

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

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

初始化流程

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

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

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 填充。

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

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

列表初始化

通过花括号包裹的初始化列表初始化对象的方式，叫做列表初始化（List-Initialization）。

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

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

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

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

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

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

std::initializer_list

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

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

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

复制初始化

复制初始化（Copy-Initialization）指从另一个对象初始化一个对象，在语义上应该发生复制。

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

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

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

直接初始化

直接初始化（Direct-Initialization）通过指定的参数调用构造函数，初始化对象。

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

直接初始化的效果如下：

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

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

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

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

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

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

常量性（const）

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

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

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 都是合法的。

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

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

浮点数类型

浮点数不一定映射到 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 的隐式类型转换。

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] 都是左值。

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

实例

例如以下代码：

#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 一句，通过以下途径转换：

上下文相关转换

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

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

显式类型转换

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

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

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

例如：

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++ 推荐的声明方式。用法如下：

using i64 = long long;

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

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

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

typedef 类型别名

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

typedef long long i64;

字面量类型

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

整数字面量

通常情况下，一个整数类型字面量的类型通过如下简化规则确定（完整表格见 cppreference）。

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

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

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

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）。

浮点数字面量

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

同样对大小写不敏感。

字符串字面量

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

原始字符串

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

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

得到如下输出：

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

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

自动类型推导

auto

C++11 起，auto 关键字用作自动类型推导。

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

例如以下代码：

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 也可以用于函数参数类型。例如以下代码：

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 的其他表达式，基于其值类别：

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

例如：

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

数值计算

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

类型转换

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

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

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

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

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

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

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

数值溢出

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

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

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

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

求值顺序

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

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

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

详细规则

具体见 求值顺序 - cppreference。

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

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

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

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

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

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

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

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

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

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

杂项

运算符优先级

见 C++ 运算符优先级 - cppreference。

“表达式”和“语句”

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

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

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

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

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

“短路”机制

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

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

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

逗号运算符

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

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

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

三目运算符

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

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

除法优化

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

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 的指针。

例如以下示例：

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

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

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

例如：

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 的指针不可解引用。

悬空指针

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

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

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

无效指针

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

指针算术

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

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

示例：

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

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

（左值）引用

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

例如以下代码：

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

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

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

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

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

动态内存分配

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

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

#include <iostream>

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

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

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

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

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

#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 可以用来动态分配特定大小的内存块，但是不进行对象初始化。

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

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

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

::operator delete(ptr);

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

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

手动构造、析构

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

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

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

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

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

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

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 用于手动构造和析构对象。

数组

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

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

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

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

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

#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 的操作数），或者作为一个左值（例如正在进行取地址）。甚至就连数组的下标访问，本质上也是指针算术。

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

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

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

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

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

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

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

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

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

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

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

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

std::array<int, 20> a;

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

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

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

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

函数

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

基础知识

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

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

square(5); // 25

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

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

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

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

struct AVeryLongClassName {
    int a, b;
};

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

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

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

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

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

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

int f(int x);

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

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

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

函数重载

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

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

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

当调用存在重载的函数时，会通过重载决议判断实际调用哪一项。具体规则十分复杂，可以参考 cppreference。

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

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

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

实参依赖查找

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

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 更优的实现。所以标准的交换两个元素的方式是：

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

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

默认参数

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

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 乘以整数的重载。

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 就是合法的）。

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

回调函数

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

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

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

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

我们使用 Python 语言来表达这个逻辑，因为 C++ 的类型系统可能比较复杂。如果你不了解 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++ 中使用函数作为参数，可以考虑以下的方案。

模板

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

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

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

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

函数指针

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

#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 函数。

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 起提供的一个标准库工具，可以存储一类可调用对象（函数或仿函数等），它们有相同的调用签名，即接收同样类型的参数、返回同样类型的值。

#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 像是适用范围更广的函数指针，在类型中只包括函数的调用签名。与之相对地，函数指针无法指向一个仿函数。

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)。这使得我们可以通过这种方式模拟一个函数，这就是仿函数。

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

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

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

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 函数，分为以下三个部分：捕获列表，参数列表，函数体。

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

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

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

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 的比较函数，现在可以这样写。

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

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

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 来定义类，后面会提到它们的区别。

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

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

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

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

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

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

成员函数

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

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

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

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，相当于普通函数传入常量引用，具体见以下的例子。

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

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

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}

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

struct Frac {
    void print() const;
};

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

成员可访问性

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

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

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

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

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。

构造函数

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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); // 正确

显式构造函数

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

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

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

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

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

f(5); // 编译错误

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

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

#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，则行为正常，只插入一个元素。这种情况下，希望插入两个元素，需要这样写：

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

委托构造函数

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

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

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

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

析构函数

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

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

#include <iostream>

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

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

输出结果：

1
~A()
2

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

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

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

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（资源获取即初始化）。这种设计方式可以通过局部对象来管理资源，让动态资源的生命周期与一个局部对象绑定，通过局部变量的初始化获取资源、局部变量的析构释放资源。

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

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

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

静态成员

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

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

数据成员

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

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

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

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

成员函数

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

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

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

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

继承

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

继承的语法如下：

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

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

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

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

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

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

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

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

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) 就是在初始化基类，包含基类名和初始化语句。

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

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

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

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

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

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

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

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

struct C : public A, public B {};

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

   A
  / \
 B   C
  \ /
   D

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

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

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

#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 声明，确保发生覆盖。

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 的位置不同。派生类函数想要重写基类函数，需要调用签名完全相同（参数类型、返回值类型等）。

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

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。这个过程又被称为“对象切片”。

虚析构函数

考虑以下场景：

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 向下转型，如果转换失败，根据转换类型不同，出现以下错误：

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);  // 抛出异常

纯虚函数

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

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

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

总结

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

友元和可变声明

友元（friend）

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

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）使用。

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

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

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

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

class A {
    friend class B;
};

可变成员（mutable）

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

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

struct A {
    mutable int callCount = 0;

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

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

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

std::set<A> s;

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

重载运算符

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

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

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

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

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

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

struct A {
    int value;

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

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

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

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

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;
    }
};

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

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 指针也看成一个引用参数，这类问题都是来源于几个引用参数出现重叠。对于函数传参涉及指针/引用的情况，建议遵循以下安全规范。对于同类型的所有引用：

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

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

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

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

右值引用和移动语义

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

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 的移动构造函数，就可以这么写：

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

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

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

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

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

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

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）。将亡值的引用绑定规则，和纯右值一致。

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

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 标准要求之前，编译器也会对函数返回值等情况做优化，优化掉任何额外的复制和移动操作。使用右值引用接受返回值，反而有可能抑制编译器优化。

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

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

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

万能引用和完美转发

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

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

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

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

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

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

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

模板和编译期计算

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

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

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++ 引入了“模板”来解决这类问题。

基本使用

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 可以换成任意类型。

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

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++ 中，有很多种实体都可以带有模板。包括：

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

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 的值。（例如数组的大小，例如后文要提到的模板参数）

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

constexpr 函数

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

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

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)];  // 可以用作数组大小

非类型模板参数

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

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

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

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

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

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 来判断整数类型。这个代码属于全特化。

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> 判断两个类型是否相同。具体实现如下：

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>。

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

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() 方法中的任意一个就调用它。（我们假设不会二者兼有）

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 模板，来实现这种“条件启用”的逻辑。

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）。具体效果：

可以按照如下的方式使用它。

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 忽略。

另一个常见的用法是，借助非类型模板参数。

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 等。

还有一个用法是借助默认模板参数。

template <typename T, typename /*未命名的模板参数*/ = std::enable_if_t<std::is_integral_v<T>, int>>
auto f(T x) -> T {
    return x % 17;
}

但是这个方法其实存在重大缺陷。假如接下来需要一个对于浮点数启用的重载，那么就会出现：

template <typename T, typename = /*...*/> auto f(T x) -> T {}
template <typename T, typename = /*...*/> auto f(T x) -> T {}

所以实际上，这两个模板的签名是相同的，都需要两个 typename 参数，于是编译器会认为这是同一个函数模板的重定义错误，然后报错。建议换用其他方法。

正确的重载方式（通过返回值 enable_if）：

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，允许像编写常规代码一样，在编译期进行条件判断。

上文的取模函数，可以像这样实现：

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 让函数返回不同的类型。

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。于是可以定义一个概念，来描述这个限制。

template <typename T>
concept is_int = std::is_same_v<T, __int128> || std::is_integral_v<T>;

接下来我们就可以使用这个概念了。最简单的用法是直接用 is_int<double> 这样的方式判断一个类型是否符合这个概念，将会获得一个布尔值。更重要的是，概念可以直接写在模板参数中，来约束这个参数的类型。

template <is_int T>  // T 必须为整数
auto f(T x) { /*...*/ }

这样写，编译器会保证 T 类型满足 is_int 的概念，否则会忽略这个重载。还有一种等价的写法：

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 子句，可以用来限制一个函数模板的模板参数。如果条件不成立，就忽略这个重载。

template <typename T>
requires (sizeof(T) >= 8)  // requires(常量 bool 值)，要求它必须求值为 true
auto f() -> void { /*...*/ }

requires 表达式用于表达更加复杂的约束，它本身会返回一个 bool 类型，表示所有的约束是否都被满足。

// 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。被包含的概念会更加受限，于是会在重载决议中优先考虑。

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 引入了变参模板，允许函数接受不限个数的参数。

模板参数的结尾，可以添加一个通过省略号声明的参数包，来包含不限数量的参数（可以包含零个）。

template <typename ...Types>
struct Tuple {};

Tuple<int, double> t1;
Tuple<int, long, char, short> t2;

参数包也可以是非类型模板参数。

template <int ...Nums>
struct Numbers {};

通过参数包类型，可以声明相同数量的函数参数。

template <typename ...Ts>
void f(Ts ...args) {}

template <typename ...Ts>
void f(Ts &&...args) {}  // 可以带引用、万能引用

参数包展开

我们将包含参数包的类型或表达式，称为一个“模式”（pattern）。在模式后面加上一个省略号来展开一个包。

args...; // 模式为 args
f(args)...;  // 模式为 f(args)
(args * 5 + 2)...; // 模式为 (args * 5 + 2)

展开包的过程，相当于给这个参数包的每一项都按照相应模式进行一些处理，然后通过逗号连接。

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>>

多个长度相同的包也可以同步展开，多用于多个函数参数及其类型。

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 起，支持“折叠表达式”，可以通过二元运算符连接整个参数包进行处理。对于连加、连乘这种常见操作十分好用。

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)
}

此处的展开也可以使用上文说的“模式”。以下代码借助逗号运算符来输出多个数。

template <typename ...Ts>
auto f(Ts const &...args) {
    ((std::cout << args << ' '), ...);
    /*
    展开成
    (std::cout << 1 << ' '), (std::cout << 2 << ' '), (std::cout << 3 << ' ');
    */
}

除此以外，使用参数包的一个经典方法是分离首个参数和后续参数，然后递归处理。例如以下代码，也可以实现依次输出几个参数。

auto output() -> void {}  // 递归终止条件

template <typename T, typename ...Ts>
auto output(T const &first, Ts const &...args) -> void {
    std::cout << first << ' ';
    output(args...);  // 递归处理后续参数
}

以下代码可以获得参数包的第 i 个类型。

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 实现，使用 % 代替任何参数，但是没有格式化功能。

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 用于方便地获取连续自然数组成的包，具体使用方法如下：

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_index_sequence<N>，相当于 std::make_integer_sequence<std::size_t, N>
}

杂谈

在这个章节中，我们将会讲一些不好归类，但是很有用的语法特性。

范围 for 循环

C++11 起，支持通过范围 for 循环，来更方便地遍历一个容器。具体语法如下：

for (auto x : vec) {  // 依次输出 vec 中的所有元素
    std::cout << x << ' ';
}

其中的 vec 是类似 std::vector、std::set 这样的容器，支持 .begin()、.end() 返回首尾迭代器。特别地，C 风格数组也可以使用范围 for 循环遍历，会依次遍历数组中的所有元素。

auto x 可以替换成引用。包括以下允许的形式：

auto 也可以替换成具体的类型。

范围 for 循环，等价于以下形式：

auto it = vec.begin();
auto end = vec.end();
for (; it != end; ++it) {
    auto x = *it;  // 这里的变量 x 声明方式与冒号左侧部分相同
    // ... 循环体
}

所以，即使使用范围 for 循环，往往也不能在循环途中修改容器。

结构化绑定

C++17 起，可以通过结构化绑定，方便地将一个对象的几个成员绑定到局部变量。例如：

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 也支持结构化绑定。

std::array<int, 3> arr{};
auto [x, y, z] = arr;

结构化绑定也支持各种形式的引用，允许修改对象，或者免除复制。包括 auto、const auto &、auto &、auto && 等。建议对于较大的对象使用 auto const & 绑定来避免复制开销。

事实上，以下的过程可以更好地描述结构化绑定的行为：

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 循环中也可以使用结构化绑定。

for (auto const &[key, value]: map) {
    // ...
}

if 初始化语句

C++17 起，if 语句，在条件之前可以添加一个初始化语句，在条件判断之前执行。在此处定义的变量，作用域会在 if 的右侧花括号处结束。

if (auto res = f(); is_prime(res)) {
    // 接下来可以使用 res
} else {
    // 也可以使用 res
}
// 此处不再可以使用 res

三路比较运算符

两个对象的大小关系往往分为三类：小于、等于或大于。有些情况下，我们会根据它们的比较关系进行不同的分支操作。

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:: 前缀）：

可以用以下的方式使用：

auto cmp = s1 <=> s2;
if (cmp == std::strong_ordering::less) { /*...*/ }
else if (cmp == std::strong_ordering::equal) { /*...*/ }
else { /*...*/ }

可以发现，这种写法过于冗长。所以可以使用另一种较为简便的方法，让 std::strong_ordering 对象和 0 比较，返回布尔值。

标准类型之间都已经定义了三路比较运算符。可以使用三路比较运算符描述很多的比较逻辑。例如依次按照 a、b、c 比较：

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 之后，可以通过如下方式，让编译器自动生成全部六个比较函数。这将会基于各个成员的声明顺序，进行字典序比较。

struct S {
    auto operator<=> (S const &) const = default;
};

实际上，除了 std::strong_ordering 以外，还有几个类似的类型。它们之间的使用方式一致，但是语义有所不同。

所有比较类别都有 less、greater 和 equivalent，strong_ordering 有额外的 equal，partial_ordering 有额外的 unordered。

不同的返回类型不会影响运算符的生成、标准库工具的行为，但是可以体现不同的语义，有利于编写“自解释”的代码。通常情况下使用 strong_ordering 即可（例如按照所有成员的字典序比较）。

标准库的比较函数

很多标准库函数允许我们传入比较函数（例如 std::sort），用于替代小于号进行比较。这类比较函数需要满足一些约束。（如果是通过自定义类型的重载运算符，也需要满足相同规则）

小于号的语义必须是“严格弱序”，即如同三路比较的结果为 std::weak_ordering::less。一个常见的错误是以下代码：

std::sort(v.begin(), v.end(), [](auto a, auto b) { return a.val <= b.val; });

具体来讲，需要满足以下要求：

以及另外的几个要求：

异常处理

异常是 C++ 处理运行时错误的机制。当程序出现运行时错误时，可以跳出常规的代码执行逻辑，转到专用的错误处理代码。

异常处理采用以下方式：

但是需要注意，只有代码抛出的异常才能被捕获。越界访问、空指针访问等未定义行为导致的运行时错误无法被捕获。

例如以下代码：

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 的某个派生类。以下是若干个标准库中定义的异常，使用缩进层级表示继承关系。

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() 返回提示信息。

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 可能会有一些帮助。

异常安全

在一个操作中，如果抛出了异常，这个操作将被中断。这也意味着，一个对象可能已经被修改到了一个中间状态，但是无法进一步操作，导致操作未完成的情况下，原始数据丢失。

函数可以有以下几个级别的异常安全保证，是从严格到宽松的关系。

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 工具可以获取更佳体验。

在头文件之前添加以下宏定义即可使用调试宏。

#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 头文件中。它用于确保某个条件成立，否则中断程序运行，并输出诊断信息。例如：

void f(int x) {
    assert(x >= 0);
    // ...
}

此时这个函数如果传入了一个负数，将会在这一行出现断言失败。此时的报错信息可以提示错误行号，方便调试。

C++26 起可以使用 contract_assert 来替代 assert，但是在此之前，assert 都极为好用。

随机数生成器

C++11 起通过 random 头文件提供了更加现代的随机数生成器。此前使用 rand() 进行随机数生成，随机数质量较低，并且值域上限较小（由实现定义，通常为 32767），无法满足使用。

最常用的随机数生成器是 std::mt19937。通过以下方式定义一个 mt19937 生成器：

std::mt19937 rng{/*seed*/};

mt19937 生成的是伪随机数，本质上是通过一个种子不断地进行确定变换。相同种子会导致接下来随机数生成的行为一致。

std::random_device{}() 可以生成一个真随机数，但是效率较低，通常只用来提供一次随机种子。以下是一个常见的用法：

std::mt19937 rng{std::random_device{}()};

接下来便可以开始使用 rng 生成随机数了。直接使用 rng() 可以在 unsigned int 值域内均匀随机地生成一个整数。

如果希望生成某个值域内的整数，通常情况下可以简单地通过取模实现。如果希望绝对的均匀随机，可以通过 std::uniform_int_distribution。

// 假设需要 [1, 10]
int x = rng() % 10 + 1;  // 通常情况下足够
std::uniform_int_distribution dist{1, 10};
int y = dist(rng);

如果要生成数据的值域大于 unsigned int 值域，也可以安全地使用 uniform_int_distribution。

long long max = 1e14;

std::uniform_int_distribution<long long> dist{1, max};
auto res = dist(rng);  // res 类型为 long long

更多的随机数生成器和随机分布，见 cppreference。

ranges

C++20 起添加了 ranges 库，进一步方便了代码编写。一方面优化了标准库算法的使用，另一方面添加了更多的实用功能。

ranges 算法

ranges 命名空间中重新实现了几乎所有标准库算法（algorithm 头文件），最大的特点就是可以不再显式传入 begin 和 end 参数。

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 排序。

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 中的所有元素。

std::vector vec{1, 2, 3, 4};
for (auto x: vec | std::views::reverse) {
    std::cout << x << ' ';
}

实际上，大多数视图是惰性求值的，即在访问元素的同时进行计算。如果最终的范围遍历一半就中止，不会有额外的计算。

以下是一些常用的视图（省略 std::views 命名空间）：

以及可以使用 std::views::iota(a, b) 生成一个 [a, b) 范围内的连续序列。例如 std::views::iota(3, 6) 包含元素 3、4、5。

C++23 起，可以使用 std::ranges::to 把一个范围转换为另一个范围，即构造一个指定类型范围，依次包含原范围的所有元素。

例如，以下是一个字符串的分割。

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。

std::vector<int> vec(n + 1);
for (auto &x: vec | views::drop(1)) std::cin >> x;

实战：实现简易 vector

在这个章节中，我们将会在最新的 C++ 标准下实现一个简易的 vector，支持 std::vector 的部分功能。

vector 使用一片连续内存存储对象。为了实现扩容操作，采取以下策略：

可以证明，这种策略下 push_back 的均摊复杂度是 O(1)。

首先，定义一个元素类型 A，便于观察 std::vector 的行为。

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 进行分配和解分配。

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 需要以下三个成员存储数据：

还需要定义一些嵌套类型：

这里我们直接使用指针作为迭代器。

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_; }

基础功能

我们将会在这里实现构造函数、析构函数、下标访问等基本功能。

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，并正确地处理扩容逻辑。

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 为例，主要演示何时应该使用构造，何时应该使用赋值。

// 这里采取了一种简化的实现方法，按值传参，在内部统一移动
// 对于 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;  // 转换成非常量迭代器
}

其他功能不再演示如何实现。以上功能的完整代码见洛谷云剪贴板。

结语

不知不觉间，这篇专栏已经包含不少内容了。由于篇幅限制，这个专栏也即将告一段落。

在这个专栏中，我们介绍了很多可能不被大家熟知的语法特性，从基本的变量、类型，到模板元编程这样更加深入的内容。当然，这篇专栏只是 C++ 语言的冰山一角，但是希望你能够从这个专栏得到一些启示，了解到一些比较新鲜的知识。由于个人能力有限，某些地方的表述可能不够清晰，甚至可能存在笔误或理解上的偏差。如果遇到困惑或发现错误，还请多多包涵，也欢迎指正和交流。

正如前言所讲，这些语法特性可能对赛场上的得分不会有帮助，但我相信它们也不会是毫无意义的。也许有一天，你会想要封装属于自己的模板库；也许你会发现，lambda 函数可以简化封装函数的过程，简化你的代码；也许你面对编译器给出的大量报错不再慌张，而是可以冷静地分析其中的函数重载、模板实例；也许你在以后工作中也会使用 C++ 进行开发，这些语法特性会成为你项目中的一砖一瓦……那些看似晦涩的特性，当你真正需要它们时，或许也会展现出惊人的价值。

最后，感谢你与我共同完成这次 C++ 的学习之旅。“路漫漫其修远兮”，编程之路永无止境，我们都是正在探索的初学者。愿你对技术的好奇心永远如初，愿这段内容能成为你未来编程路上的小小助力。