折叠表达式(Fold Expression),低速下脚现代C++ Chapter 2 Exercise

折叠表达式(Fold Expression),低速下脚现代C++ Chapter 2 Exercise

October 15, 2021

折叠表达式(Fold Expression):低速下脚现代C++ Chapter 2 Exercise

最近在看高速上手现代C++,这是一本很不错的书,作者用仅80余页的长度介绍了C++自C++11以来至C++20带来的许多特性。这些特性给C++带来了语言可用性上的强化,运行期的强化 etc. 以及使得这门语言本身更好地支持例如函数式编程的范式。

每一章的结尾作者都会提供一些简单的小题目,其中第二章的小题目cover了折叠表达式(Fold Expression, since C++17)和结构化绑定(Structured Binding, since C++17)。在自己闲着摸索的时候发现了一个有意思的小事情,于是稍微写点东西记录一下。

感觉光看这本书和课后的题的话,内容还是不太能掌握,可能跟着其他博客看一看会比较好。

为什么需要Fold Expression?

模版是C++比较重要的一个板块之一,但是C++11之前,模版的参数数量是固定的。自从C++11之后,新引入的表示方法允许声明时引入任意数量的参数,即如下形式:

1
template<typename... Ts>

有了可变长模版,我们就可以写一个允许任意长度参数的函数模版了。一个显而易见的好处是,我们可用这样的语法实现以下函数功能,并且只要写一个函数模版。

1
2
3
// 一个函数模版 mean_val,接受任意长度的参数,返回平均值
mean_val(1,2,3) // return 2
mean_val(2,3,4,5) // return 3.5

不过在C++17之前,这样的函数模版在解包(unpack)的时候会比较麻烦,因为我们在写函数模版的时候并不知道究竟会传几个参数进来,而参数包又不像是std::vector之类的容器有简单的方式进行遍历,因此我们对于函数参数的实际操作就变得比较麻烦。

1
2
3
4
5
6
//比如说我想实现max_val,但是我并没有直观的方式遍历args的内容
template<typename... Ts>
void foo(Ts... args)
{
//我该怎么获得args的内容呢?
}

不过目前来说,我们可以通过sizeof… 来计算参数的个数:

1
2
3
4
5
6
7
template<typename... Ts>
void foo(Ts... args)
{
std::cout<<sizeof...(args)<<std::endl
}

foo(1,2,3) // cout:3

一个比较常见的做法是利用递归来进行参数解包:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//书中的案例
#include <iostream>
template<typename T0> void printf1(T0 value) {
std::cout << value << std::endl;
}

template<typename T, typename... Ts>
void printf1(T value, Ts... args) {
std::cout << value << std::endl;//每次取出一个T,然后递归再取出一个T
printf1(args...);
}

int main() {
printf1(1, 2, "123", 1.1); //输出所有参数
return 0;
}

这么做的确比较繁琐,而C++17中引入了一种比较简洁的方式来实现这种功能需求,这就是标题里的折叠表达式。

  • 考虑下面的代码,下面的函数模版可以实现任意长度立即数的求和。
1
2
3
4
5
6
7
8
9
10
#include <iostream>
template<typename ... T>
auto sum(T ... t) //C++14,函数返回值自动推断
{
return (t + ...); //折叠表达式
}

int main() {
std::cout << sum(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) << std::endl;
}

不过书中没有仔细讲这个折叠表达式的内容,因此原理上就有些不清晰,这里做一些补充。

折叠表达式的语法:

  • pack op ... (一元右折叠 / unary right fold)
  • ... op pack (一元左折叠 / unary right fold)
  • pack op ... op init (二元右折叠 / binary right fold)
  • init op ... op pack (二元左折叠 / binary left fold)

其中,pack是参数包,即上述代码中的t,op即operator,支持32种二元运算符,例如+,-,*,/ , init表示最后一层展开时二元运算符的另一个操作数。 其中在二元折叠中两个operator要保持一致。

以上四个表达式和以下内容等价:

1
2
3
4
(args op ...) <-> (arg1 op (arg2 op (arg3 op (... op (arg_n-1 op arg_n)))))
(... op args) <-> (((arg1 op arg2) op ...) op arg_n)
(args op ... op init) <-> (arg1 op (... op (arg_n−1 op (arg_n op init))))
(init args op ... op ) <-> ((((init op arg1) op arg2) op ...) op arg_n)

这么写可能还是有点晕,举两个例子可能更好:

1
2
3
args = [1,2,3]
(args - ...) <-> (1 - (2 - 3))
(3 - ... - args) <-> (((3-1)-2)-3)

Ref: https://en.cppreference.com/w/cpp/language/fold

下面是一个注意点,由于运算符优先级问题,第一种备注是掉的写法并不被接受,需要写成第二种写法

1
2
3
4
5
6
template<typename ...Args>
int sum(Args&&... args)
{
// return (args + ... + 1 * 2); // Error: operator with precedence below cast
return (args + ... + (1 * 2)); // OK
}

作业题:

利用折叠表达式写一个计算求均值的函数模版:

答案如下:

1
2
3
4
5
6
7
8
9
10
11
template <typename... T>
auto mean(T... t)
{
return (t + ...) / sizeof...(t);
}

int main()
{
std::cout << mean(1, 2, 3, 4, 5) << std::endl;
}
//output: 3

但是…

不知道为什么我突然想试着把 + 改成 -

1
(t - ...)/sizeof...(t) <-> (1-(2-(3-(4-5)))) = (int)3/5 = 0

这个例子倒是没有问题,如果我改成左折叠:

1
2
 return (... - t) / sizeof...(t);
//output: 3689348814741910320

这个一长串数字并不是随机数,运行了好几次都是同一个结果。但是:

1
(... - t)/sizeof...(t) <-> ((((1-2)-3)-4)-5)/5 = -13/5

本应该输出-2才对,那么究竟是哪里出问题了呢?

探索

首先我查看了折叠表达式和sizeof…(t)的返回值,用lldb调试后发现数值没有问题,那么应该是除法这一步出了问题。

image-20220101230639043

当我将p的类型从auto改为int之后,返回值就变成-2了:

image-20220101230834880

那么看来应该是sizeof…返回值的问题。

解释:

询问学长之后发现,sizeof...返回的是一个size_t类型的值,在64-bit操作系统中类型是uint64_t,即64位无符号整型。然后折叠表达式自动推断返回为int(int32_t), 二者做除法的时候int被提升到uint64_t,然后又因为负数的符号位在最高位,被转换成unsigned的时候,数值就变得非常大了。

可以具体算一下这个3689348814741910320的由来,结果是一致的。

1
2
-13 = (hex) FFFFFFFFFFFFFFF3 -> 18,446,744,073,709,551,603
int(18,446,744,073,709,551,603 / 5) = 3689348814741910320

所以需要注意的是,一行的表达式,其实包含了一次类型推断和一次隐式类型转换,所以使用的时候需要比较小心一些。

1
2
3
4
5
(t + ...) / sizeof...(t);
//equivalent as below
auto p = (t + ...);
size_t i = sizeof...(t);
return p/i;

等我看完Chapter 4的时候可能会再来写一点内容,感觉还是得一边看一边跟着例子写一点才好。