为什么写这篇博客呢？其实是感觉我队友的代码更接近 C 风格，而非 C++ 风格。其实 C++ 中也有非常多好用的特性可以应用于算法竞赛，我来说说我一些体会。

写在前面

本人不是计算机专业的，我是学电子信息的，学 C++ 只是爱好。如果这篇博客中有所错误，还请各位大佬指正。

在这篇博客的中的 C++ 标准，通常指的是 C++11 到 C++20。对于 C++23 或者之后的标准来说，至少现在算法竞赛并不太支持。

对于现代 C++，本人也是在学习中，诸多疏漏和错误请谅解。

不写 using namespace std;

这是我从 jiangly 那里学来的。实际上在工程中几乎不会出现 using namespace std;

也就是在使用标准库命名空间内关键字的时候需要加上 std:: 也就是使用作用域解析操作符

例如：

当然，在算法竞赛中，为了书写的速度，写上当然没事。

不过你可以使用 using 去声明类型的别名，例如

使用这样的方式去替代 typedef 或者 #define 的方式

伟大的 jiangly 曾经说过：

别 TM #define int long long 了

所以请改掉这种写法，使用 typedef 或者 using 的方式

不觉的这样很涩情吗？

使用 iostream 而非 stdio

对于输入输出来说，一开始刚学竞赛的时候，我的理解是使用 scanf 明显快于 cin 。然而在学习一段时间之后，我了解到 cin 比较慢是因为有一个和 stdio 的同步，而且 std::endl 会刷新缓存区，这两点造成了其速度比较慢。

所以以上的代码的用处就是关闭同步流。当然关闭同步流之后，和 stdio 是不能混用的。而在需要换行的时候使用 '\n' 而非 std::endl 就不会刷新缓存区，也会使速度变快。当然我觉得 iostream 最大的好处在于模版。在输入输出的时候是由编译器根据上下文判断类型，而非使用格式化字符串。这不仅仅在写代码的时候更加容易，在工程中也会使得读入更加安全。

使用容器而非数组

以下列举两种不同风格的代码：

C 风格

C++ 风格

也就是说，使用容器的好处在于减少了初始化的过程，及用及开，不使用的时候就会自动销毁。当然使用容器自然不如使用数组的速度，但是对于现在的算竞来说，大多数的 OJ 和比赛都支持 O(2) 优化，也就不需要担心 STL 的速度了。

对于 C 风格的代码来说，多组数据的初始化相当麻烦，一般使用 memset 实现。当然写成 memset(a, 0, sizeof a); 是不行的，在最坏的情况下时间复杂度为 $O(TN)$ ，这显然会超时。所以需要计算出每一次需要用的数组范围，例如 memset(a, 0, sizeof(int) * n) ，n 代表这个 case 的数据量，这样就不会超时。

所以相较之下，使用容器明显方便很多。

使用 lambda 表达式

在 C 风格的代码中，我们定义一个函数往往是在全局定义的，这意味着如果这个函数需要某个变量，就需要传入这个变量或者开在全局。而在 C++ 中给出了另一种使用函数的方法，就是 lambda 表达式。总的来说，它长的比较像这样：[] () {} 。

直接看它的形式或许比较抽象，但是如果在一个实际例子中来看就会比较简单。例如：

这是一个判断素数的函数，看上去非常简单。实际上 [] 表示的是捕获列表，这表示在函数体中可以捕获到的变量，例如 [a, b] () {} 的含义就是，在函数中可以存在变量 a, b 。当然，这里是深拷贝，也可以在变量名之前加上 & 来传递引用。对于 STL 来说，一般都是需要传递引用。当然也可以不加选择的捕获所有变量，例如 [&] 的意思就是捕获在父域中的所有变量，以引用的形式；[=] 的意思就是以值传递的形式捕获父域中的所有变量。当然也可以不捕获全部的变量，在 [] 中写上变量名，就是以值的方式捕获这个变量，而加上 & 就是以引用形式捕获。

而在 () 的是函数的参数列表，这和我们熟悉的是一致的。-> 之后我们可以写上函数的类型。而且 lambda 表达式也是支持递归的，也就是说我们可以拿它来写 dfs 。

当然我们可以使用 auto 让编译器去推导表达式的类型，这样会方便很多。不过如果还要写 dfs 的话，就不能单纯的只写 auto 了，编译器推导的能力也是有限的。不过需要注意的是，定义 lambda 表达式和定义变量是差不多的，在结尾需要写上 ;，这是和函数定义有区别的。

而在使用上，lambda表达式和函数并没有区别。在 C++ 风格的代码中常常是 lambda 表达式和容器配合使用；在 C 风格的代码中往往是数组和函数配合使用。

而部分函数也会将 lambda 表达式作为参数传入。非常常用的就是 std::sort(begin, end, cmp) ，这里的 cmp 就是传入一个 lambda 表达式。例如我们对一个 std::pair<int, int> 数组 a 按照第二关键字排序，不考虑第一关键字就可以这么写：std::sort(a + 1, a + 1 + n, [&](std::pair<int, int> &x, std::pair<int, int> &y) -> bool { return x.second < y.second})); ，这样的好处在于不需要重载小于号，更加灵活。

在认识到以上这些之后，让我们重新思考一下这个捕获列表。对于一个 lambda 表达式来说，捕获列表只会被捕获一次，也就是在它定义的时候。也就是说当你捕获一个引用后，如果原来的变量被销毁了，那么这时候再去调用 lambda 就容易出错。同样的如果你捕获了一个值后，无论你在 lambda 之外如何改变这个值，在 lambda 中这个值仍然不会变，而且这个值是只读的，如果你希望在局部修改它，需要写上 mutable。

迭代器

迭代器是用来遍历容器的，可以看成是容器对应的指针。

这是一段 ChatGPT 对于迭代器的解释:

C++ 中的迭代器是一种用于遍历容器元素的抽象概念。它提供了一种统一的访问容器内元素的方式，使得算法能够与特定容器的实现细节解耦。迭代器的使用使得代码更加通用、灵活，可以应用于各种容器类型，如 std::vector、std::list、std::map 等。

迭代器的基本操作包括：递增（++）、递减（--）、解引用（*）、成员访问（->）等。不同类型的容器可能提供不同种类的迭代器，包括正向迭代器、反向迭代器、常量迭代器等。

C++ 标准库提供了几种不同类型的迭代器，每种都有其特定的功能和适用范围：

1. 输入迭代器（Input Iterator）：只能从容器中读取数据，且只能向前移动。例如 std::istream_iterator。
2. 输出迭代器（Output Iterator）：只能向容器中写入数据，且只能向前移动。例如 std::ostream_iterator。
3. 前向迭代器（Forward Iterator）：可以读取和写入容器中的数据，且只能向前移动。例如 std::forward_list 的迭代器。
4. 双向迭代器（Bidirectional Iterator）：可以读取和写入容器中的数据，并且支持向前和向后移动。例如 std::list 的迭代器。
5. 随机访问迭代器（Random Access Iterator）：功能最强大的迭代器，可以以常数时间执行任意位置的移动和访问。例如 std::vector、std::deque、std::array 等的迭代器。

在使用迭代器时，需要注意遵循容器的迭代器失效规则，以避免出现未定义行为。此外，对于不同类型的迭代器，支持的操作和性能特征可能会有所不同，应根据具体情况选择合适的迭代器类型。

我们可以使用迭代器去遍历一个容器，例如 std::map

在 GPT 的介绍中提到的未定义行为比如像插入删除迭代器之后的元素，这样会造成迭代器的失效，所以需要使用另外的方法。

其实 erase 是有返回值的，我们可以使用这种方法去防止迭代器的失效。

模版和泛型编程

泛型编程是一种编程范式，旨在编写通用、灵活和高效的代码，以处理多种不同类型的数据或数据结构，而无需为每种类型编写单独的代码。泛型编程的核心思想是将算法与数据类型分离开来，使得相同的算法能够用于不同类型的数据。

在 C++ 中，泛型编程主要通过模板来实现。

我对于模板的理解在于，它是在编译的时候完成计算的，也是简化代码强有力的工具。当然它也支持不定长的参数（因为它会使用递归的方式定义）。你可以理解为它把类型也当成参数传入，当然这个过程是在编译过程中完成的。它分为两种，函数模板和类模板。当然它们理解起来是相似的。

对于函数模板，我们可以使同一个函数处理不同的类型数据。例如这个快读代码，只要类型定义了算数运算和位运算，就可以使用这个函数读入。也就是这是一个通用的函数。

当然使用函数的时候，需要传入这个类型。有两种情况，一种是编译器可以推导出类型，这种情况就可以传入，例如使用这个快读函数的时候就直接写 read(x) 即可；另一种是编译器无法推导出类型，则需要传入，例如另一种形式的快读， long long x = read<long long>() 。

而类模版其实我们使用的非常普遍了，也就是在容器中。在定义容器的时候，都会使用到模版。这里不再说明了。

这里说明一下模板参数，分为三类：

1. 类型参数 typename T 或者 class T
2. 非类型参数（常量表达式） template<int N>
3. 模板参数包 template<typename ...Args>

我们可以使用模板参数包实现任意长度参数列表的函数，例如这个最大值函数：

这个函数就可以传入任意长度的参数，并求出最大值。

结构化绑定和 range-based-for

结构化绑定的写法通常类似于这样

当然，你可以在auto之后加上&来获取引用。

而range-based-for可以非常方便的遍历一个容器，当然这会遍历整个容器。如果你只是希望遍历部分容器，C++23 的 std::veiw 或许可以帮到你。但是这个特性太新了。

不过即使这样，range-based-for仍然是一个非常好用的技巧。

请看：

这是一个遍历vector的示例。同样的你可以使用结构化绑定 [] 使得代码变得更加简单

当时可以使用引用。不过请注意如果是复制的话，这个值将会是只读的。

甚至可以使用初始化列表，

如果你使用过 range-based-for 的话，我相信你会爱上它的。

右值引用和通用引用

通常在 C++ 中我们使用的比较多的是左值引用。那么什么是右值引用呢？

首先我们需要区分左右值：在C++中，左值（lvalue）是指表达式的结果是可以被存储在内存中的位置（地址）的值。换句话说，左值表示的是一个具体的内存位置，可以对其进行赋值操作。通常情况下，变量、数组元素、以及通过引用获得的对象都是左值。而右值（rvalue）是指表达式的结果是临时值，不能被存储在内存中的值。右值通常是字面常量、临时对象或者表达式的计算结果。

显然，左值引用就是对于左值的引用，右值引用就是对于右值的引用，而通用引用就是会自动推导左值还是右值。

当然在算法竞赛中我们不需要学习这么多东西，我们只需要知道怎么使用就可以。

回到之前的在 lambda 表达式中留下来的问题，什么是 auto && 呢？

通用引用是 C++11 中引入的一种引用类型，也称为转发引用（forwarding reference）。通用引用是由 T&& 的形式表示的，其中 T 是模板参数。通用引用可以用于接受任意类型（包括左值和右值）的参数，并且可以保留其值的左值或右值属性。

通用引用通常与模板一起使用，特别是在编写通用代码时非常有用，因为它们能够处理各种类型的参数，并且能够保留参数的值类别（左值或右值）。

通用引用的主要应用场景之一是完美转发（perfect forwarding），这是一种技术，允许将参数传递给其他函数，同时保留原始参数的值类别。这在实现泛型函数、类模板以及 STL 中的模板时非常有用。

以下是一个使用通用引用的简单示例：

在上面的示例中，forward_value 函数接受一个通用引用作为参数，因此可以接受任意类型的参数。在 main 函数中，它分别传递了一个左值 x 和一个右值 5 + 3。在 forward_value 函数内部，可以保留参数的值类别，从而正确地处理传递给它的参数。

所以通用引用就是在于可以同时处理左值和右值，使得代码更加简单。