第十一章 折叠表达式
自C++17起, 其特性有支持带一个(可带有初始值的)参数包(parameter pack)的所有实参能使用二元操作符并计算结果.
例如, 下列的函数能返回所有传入实参的和:
template <typename ...T>
auto foldSum(T... args) {
return (... + args); // ((arg1 + arg2) + arg3)...
}
注意, return 表达式里的括号是折叠表达式的一部分并且不能省略.
函数调用 foldSum(47, 11, val, -1); 使模版实例化并执行: return 47 + 11 + val + -1;.
函数调用 foldSum(std::string("hello"), "world", "!"); 使模版实例化为: return std::string("hello") + "world" + "!";
还要注意, 折叠表达式实参的次序可以不同并且效果也不一样 (可能看起有点反直觉): 例如写成 (... + args) 的结果则是 ((arg1 + arg2) + arg3)..., 该含义是重复地“往后添加”(post-adds)东西. 你也可以写成 (args + ...), 该含义是重复地“往前添加”(pre-adds)东西, 因此其结果为: (arg1 + (arg2 + arg3))....
11.1 折叠表达式的目的
折叠表达式避免了需要递归地去实例化模版并作用于一个参数包的所有形参. 在 C++17 之前, 你必须这样实现:
template <typename T>
auto foldSumRec(T arg) {
return arg;
}
template <typename T1, typename ...Ts>
auto foldSumRec(T1 arg1, Ts... otherArgs) {
return arg1 + foldSumRec(otherArgs...);
}
这样的一种实现不仅写起来繁琐, 并且它也给 C++ 编译器造成负担. 使用
template <typename ...T>
auto foldSum(T... args) {
return (... + args); // ((arg1 + arg2) + arg3)...
}
对于程序员和编译器双方的工作明显有所减少.
11.2 折叠表达式的使用
给定形参 args 和一个操作符 op, C++17 允许我们写成
- 要么是一元左折叠(unary left fold)
( ... op args), 它将展开为:(...(arg1 op arg2) op ... argN-1) op argN) - 要么是一元右折叠(unary right fold)
(args op ...), 它将展开为:(arg1 op (arg2 op ... (argN-1 op argN)...)
其中括号是必需的. 但是, 括号和省略号 (...) 不必用空格隔开.
比起知道左和右折叠表达式的预期结果, 理解两者的差别更重要. 例如, 甚至在使用 + 操作符时就有可能出现不同的效果. 在使用左折叠表达式时:
template <typename ...T>
auto foldSumL(T... args) {
return (... + args); // ((arg1 + arg2) + arg3)...
}
调用 foldSumL(1, 2, 3) 则计算出 ((1 + 2) + 3). 这也意味着下列示例代码是能被编译的:
std::cout << foldSumL(std::string("hello"), "world", "!") << "\n"; // 编译通过.
记住操作符 + 用于标准字符串类型则至少有一个操作数是 std::string 类型. 因为使用了左折叠表达式, 则函数第一次调用将计算 std::string("hello") + "world", 其返回结果为一个 std::string 类型的字符串, 因此再加上字面形式的字符串 "!" 也是有效的.
然而, 以下的函数调用:
std::cout << foldSumL("hello", "world", std::string("!")) << "\n"; // 编译报错.
将不能被编译, 因为其计算得到 (("hello" + "world") + std::string("!")), 而两个字面形式的字符串是不允许用操作符 + 进行拼接的.
然而, 我们可以将实现改成:
template <typename ...T>
auto foldSumL(T... args) {
return (args + ...); // (arg1 + (arg2 + arg3))...
}
调用 foldSumL(1, 2, 3) 则计算出 (1 + (2 + 3)). 这意味着下列示例代码就不再能被编译:
std::cout << foldSumL(std::string("hello"), "world", "!") << "\n"; // 编译报错.
而以下的函数调用现在能被编译:
std::cout << foldSumL("hello", "world", std::string("!")) << "\n"; // 编译通过.
因为几乎在所有情况下, 计算的次序都是从左至右, 通常, 参数包的左折叠语法(参数在末尾)应该更受青睐(除非它没有作用):
(... + args); // 更受青睐的折叠表达式语法
11.2.1 空参数包的处理
如果一个折叠表达式使用了空参数包, 则应用以下规则:
- 如果使用了操作符
&&, 则其值为true. - 如果使用了操作符
||, 则其值为false. - 如果使用了操作符
,, 则其值是void(). - 其他操作符的调用则是不良形式 (ill-formed).
对于所有其他情况 (一般而言) 你可以添加一个初始值: 给定一个参数包 args, 一个初始值 value 和一个操作符 op, C++17 也允许我们写成:
- 要么一个二元左折叠(binary left fold)
(value op ... op args), 它将展开为:((...((value op arg1) op arg2) op ... op argN-1) op argN)— 要么一个二元右折叠(binary right fold)(args op ... op value), 它将展开为:(arg1 op (arg2 op ... op (argN-1 op (argN op value))...))
在省略号两边的操作符 op 必须相同.
例如, 下列定义允许传递一个空参数包
template <typename ...T>
auto foldSum(T... s) {
return (0 + ... + s); // sizeof...(s) == 0 的情况也可行
}
在概念上, 不论我们添加 0 作为首个操作数或最后一个操作数应该都无所谓.
template <typename ...T>
auto foldSum(T... s) {
return (s + ... + 0); // sizeof...(s) == 0 的情况也可行
}
但对于一元折叠表达式其不同的计算次序则比预期结果更重要, 而二元左折叠表达式则更受青睐:
(value + ... + args); // 更受青睐的二元折叠表达式语法
还有, 首个操作数可能是特别的, 比如这个例子:
template <typename ...T>
void print(const T&... args)
{
(std::cout << ... << args) << "\n";
}
这里, 重要的是首次调用是传递给 print() 的第一个实参的输出, 其返回的输出流作用于其它输出的调用. 其它实现可能无法编译甚至得到发生无法预料的事情. 例如, 使用
std::cout << (args << ... << "\n");
调用print(1) 将编译通过但打印出的值 1 会向左移10位 ('\n' 的值通常为 10), 因此输出的结果为 1024.
注意, 在这个例子 print() 中没有空格分隔参数包的各个元素. 这样的调用 print("hello", 42, "world") 将会打印 hello42world.
为了用空格将传入的元素分隔开, 你需要一个helper函数以确保除了第一个实参之外在打印前加上空格. 例如, 用以下 helper 函数模版 spaceBefore() 可以办到:
// tmpl/addspace.hpp
template <typename T>
const T& spaceBefore(const T& arg) {
std::cout << ' ';
return arg;
}
template <typename First, typename... Args>
void print(const First& firstarg, const Args&... args) {
std::cout << firstarg;
(std::cout << ... << spaceBefore(args)) << '\n';
}
这里, (std::cout << ... << spaceBefore(args)) 这个折叠表达式展开成: (std::cout << spaceBefore(arg1) << spaceBefore(arg2) << ...)
因此, 在参数包 args 中每个元素都调用一个helper函数, 在返回被传递的实参之前打印出一个空格字符, 写入输出流 std::cout 里. 为了确保这不会应用到第一个实参, 我们添加了额外的首个形参并且不对其使用 spaceBefore().
注意, 参数包的输出的计算需要所有输出在左边.
我们也能在print()里面使用lambda来定义spaceBefore():
template <typename First, typename ...Args>
void print(const First& firstarg, const Args&... args) {
std::cout << firstarg;
auto spaceBefore = [](const auto& arg) {
std::cout << '';
return arg;
};
(std::cout << ... << spaceBefore(args)) << '\n';
}
然而, 注意 lambda 通过值返回对象, 这意味着将创建传入实参的没必要的拷贝. 避免不必要拷贝的方式是通过显式声明lambda的返回类型要为const auto&或decltype(auto):
template <typename First, typename ...Args>
void print(const First& firstarg, const Args&... args) {
std::cout << firstarg;
auto spaceBefore = [](const auto& arg) -> const auto& {
std::cout << '';
return arg;
};
(std::cout << ... << spaceBefore(args)) << '\n';
}
如果你不能够将这些语句组合成这样一条语句, 那你用的C++就不能称为真正的C++:
template <typename First, typename ...Args>
void print(const First& firstarg, const Args& ...args) {
std::cout << firstarg;
(std::cout << ... << [](const auto& arg) -> decltype(auto) {
std::cout << ' ';
return arg;
}(args)) << '\n';
}
不过, 一种更简单实现print()的方式是使用一个lambda打印空格和实参并将其传递给一个一元折叠表达式(脚注: 感谢 Barry Revzin 提出来):
template <typename First, typename ...Args>
void print(First first, const Args& ...args) {
std::cout << first;
auto outWithSpace = [](const auto& arg) {
std::cout << ' ' << arg;
};
(..., outWithSpace(args));
std::cout << '\n';
}
通过使用一个额外的用**auto声明的模版参数**, 我们可以使print()更灵活地将字符类型的分隔符, 字符串或任意其它可打印的类型参数化.
11.2.2 已支持的操作符
除了., ->, 和 [] 这些操作符之外, 你可以使用所有二元操作符作用于折叠表达式.
折叠的函数调用
折叠表达式
// tmpl/foldcalls.cpp
#include <iostream>
// 可变数目的基类模版
template <typename ...Bases>
class MultiBase : private Bases...
{
public:
void print() {
// 调用所有基类的 print()
(..., Bases::print());
}
};
struct A {
void print() { std::cout << "A::print()\n"; }
};
struct B {
void print() { std::cout << "B::print()\n"; }
};
struct C {
void print() { std::cout << "C::print()\n"; }
};
int main()
{
MultiBase<A, B, C> mb;
mb.print();
}
这里,
template <typename ...Bases>
class MultiBase : private Bases...
{
...
};
允许我们用可变数目的基类初始化对象:
MultiBase<A, B, C> mb;
并且使用
(..., Base::print());
这个折叠表达式被展开为调用每一个基类的print. 这个折叠表达式展开后如下所示:
(A::print(), B::print(), C::print());
然而, 注意到,操作符的性质与我们使用左折叠表达式或右折叠表达式没什么关系. 这些函数总是从左往右被调用. 使用
(Base::print(), ...);
这个括号只是将调用组合起来, 因此第一个print()和其它两个print()的结果组合了一起如下所示:
A::print(), (B::print(), C::print());
但因为,操作符的计算次序总是从左向右, 仍然是在括号里面两个为一组的函数调用之前先调用第一个函数, 并且仍然是中间的函数在右边函数之前调用.
尽管如此, 这就像左表达式的结果并且能跟其计算次序匹配上, 还是建议在折叠多个函数调用时使用左折叠表达式.
组合Hash函数
一个使用,操作符组合Hash值的例子. 这个例子如下:
template <typename T>
void hashCombine(std::size_t& seed, const T& val)
{
seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template <typename ...Type>
std::size_t combineHashValue(const Type& ...args)
{
std::size_t seed = 0; // 初始种子
(..., hashCombine(seed, args)); // hashCombine() 调用链
return seed;
}
通过调用
std::size_t combinedHashValue("Hello", "World", 42);
中间的这条语句展开成:
(hashCombine(seed, "Hello"), hashCombine(seed, "World")), hashCombine(seed, 42));
使用这个定义, 我们可以容易地为一个某个类型的对象定义一个新的Hash函数, 例如 Customer:
struct CustomerHash
{
std::size_t operator()(const Customer& c) const {
return combineHashValue(c.getFirstname(), c.getLastname(), c.getValue());
}
};
这样我们就可以将 Customers 放入一个 std::unordered_set 的容器:
std::unordered_set<Customer, CustomerHash> coll;
折叠的路径遍历
你也可以使用折叠表达式去遍历一个二叉树的路径通过操作符->*:
// tmpl/foldtraverse.cpp
// 定义二叉树结构和用于遍历的helper函数.
struct Node {
int value;
Node* left;
Node* right;
Node(int i = 0) : value(i), left(nullptr), right(nullptr) {}
...
};
auto left = &Node::left;
auto right = &Node::right;
// 使用折叠表达式遍历树:
template <typename T, typename ...TP>
Node* traverse(T np, TP... paths) {
return (np ->* ... ->* paths); // np ->* path1 ->* path2 ...
}
int main()
{
// 初始二叉树的结构:
Node* root = new Node{0};
root->left = new Node{1};
root->left->right = new Node{2};
...
// 遍历二叉树:
Node* node = traverse(root, left, right);
...
}
这里,
(np ->* ... ->* paths)
使用一个折叠表达式从np开始去遍历可变数目的paths的元素. 当调用:
traverse(root, left, right);
这个折叠表达式的调用展开成:
root->left->right
11.2.3 使用折叠表达式作用于类型
// tmpl/ishomogeneous.hpp
#include <type_traits>
// 检查传递的类型是否为同一类:
template <typename T1, typename ...TN>
struct IsHomogeneous {
static constexpr bool value = (std::is_same<T1, TN>::value && ...);
};
// 检查传递的实参是否有相同类型:
template <typename T1, typename ...TN>
constexpr bool isHomogeneous(T1, TN...)
{
return (std::is_same<T1, TN>::value && ...);
}
这个类型 trait IsHomogeneous<> 可被使用如下:
IsHomogeneous<int, Size, decltype(42)>::value
此情况下, 这个初始化成员变量value的折叠表达式展开成:
std::is_same<int, MyType>::value && std::is_same<int, decltype(42)>::value
这个函数模版isHomogeneous<>() 可被使用如下:
isHomogeneous(43, -1, "hello", nullptr)
此情况下, 这个初始化成员变量value的折叠表达式展开成:
std::is_same<int, int>::value && std::is_same<int, const char*>::value && std::is_same<int, std::nullptr_t>::value
通常, 操作符&&是短路的(第一false则终止计算).
在标准库里的**std::arary<>的推导规则**使用这种特性.
11.3 后记
折叠表达式最初由Andrew Sutton和Richard Smith在https://wg21.link/n4191中提出. 最后这个特性的公认措辞由Andrew Sutton和Richard Smith在https://wg21.link/n4295中制定的. Thibaut Le Jehan 在 https://wg21.link/n0036 中提出了删除对操作符*, +, &和|支持空参数包的情况.