Logic
向着梦想进发
Logic's Blog

【快速入门】C++特性在算法竞赛中的一点应用

为什么写这篇博客呢?其实是感觉我队友的代码更接近 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::vectorstd::liststd::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::vectorstd::dequestd::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 函数内部,可以保留参数的值类别,从而正确地处理传递给它的参数。

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

赞赏
本文作者: Logic
本文链接: https://i.needwe.top/smarter-c-plus-plus/
本文采用 CC BY-NC-SA 4.0 Unported 协议进行许可
#
首页      coding      【快速入门】C++特性在算法竞赛中的一点应用

发表回复

textsms
account_circle
email

Logic's Blog

【快速入门】C++特性在算法竞赛中的一点应用
为什么写这篇博客呢?其实是感觉我队友的代码更接近 C 风格,而非 C++ 风格。其实 C++ 中也有非常多好用的特性可以应用于算法竞赛,我来说说我一些体会。 写在前面 本人不是计算机…
扫描二维码继续阅读
2024-03-01