折叠表达式的递归展开原理
面试考点
C++17 折叠表达式(fold expressions)让变参模板的操作变得简洁。面试官考察你是否理解四种折叠形式的展开规则、空包的处理、以及和传统递归模板的对比。
核心概念
折叠表达式对参数包中的所有元素应用一个二元运算符,将其"折叠"成单个值。它消除了变参模板中手写递归终止条件的需要。编译器在编译期展开折叠表达式为一系列嵌套的运算符调用。
四种折叠形式
| 形式 | 语法 | 展开结果 |
|---|---|---|
| 一元右折叠 | (pack op ...) | (p1 op (p2 op (... op pN))) |
| 一元左折叠 | (... op pack) | (((p1 op p2) op ...) op pN) |
| 二元右折叠 | (pack op ... op init) | (p1 op (p2 op (... op (pN op init)))) |
| 二元左折叠 | (init op ... op pack) | ((((init op p1) op p2) op ...) op pN) |
基本示例
cpp
#include <iostream>
#include <string>
#include <vector>
#include <type_traits>
// ============================
// 示例1:四种折叠形式的展开
// ============================
// 一元左折叠:(... + args)
// 展开为 ((arg1 + arg2) + arg3) + ...
template<typename... Args>
auto sum_left(Args... args) {
return (... + args);
}
// 一元右折叠:(args + ...)
// 展开为 arg1 + (arg2 + (arg3 + ...))
template<typename... Args>
auto sum_right(Args... args) {
return (args + ...);
}
// 二元左折叠:(init + ... + args)
// 展开为 (((init + arg1) + arg2) + arg3) + ...
template<typename... Args>
auto sum_with_init(Args... args) {
return (0 + ... + args); // init = 0
}
// 二元右折叠:(args + ... + init)
// 展开为 arg1 + (arg2 + (arg3 + ... + init))
template<typename... Args>
auto sum_right_init(Args... args) {
return (args + ... + 0); // init = 0
}
void fold_forms_demo() {
// sum_left(1, 2, 3, 4) 展开为 ((1 + 2) + 3) + 4 = 10
std::cout << "左折叠: " << sum_left(1, 2, 3, 4) << std::endl;
// sum_right(1, 2, 3, 4) 展开为 1 + (2 + (3 + 4)) = 10
std::cout << "右折叠: " << sum_right(1, 2, 3, 4) << std::endl;
// 有初始值的版本可以处理空参数包
std::cout << "空包+init: " << sum_with_init() << std::endl; // 0
}
// ============================
// 示例2:对比传统递归写法
// ============================
// C++11/14 递归写法:需要基础情况 + 递归情况
// 基础情况
template<typename T>
T add_recursive(T x) {
return x;
}
// 递归情况
template<typename T, typename... Rest>
T add_recursive(T first, Rest... rest) {
return first + add_recursive(rest...);
}
// C++17 折叠表达式:一行搞定
template<typename... Args>
auto add_fold(Args... args) {
return (... + args);
}
void comparison_demo() {
std::cout << "递归: " << add_recursive(1, 2, 3, 4, 5) << std::endl;
std::cout << "折叠: " << add_fold(1, 2, 3, 4, 5) << std::endl;
}
// ============================
// 示例3:常用折叠模式
// ============================
// 逻辑与:所有参数为 true
template<typename... Args>
bool all_true(Args... args) {
return (... && args);
// 空包返回 true(&& 的单位元)
}
// 逻辑或:至少一个参数为 true
template<typename... Args>
bool any_true(Args... args) {
return (... || args);
// 空包返回 false(|| 的单位元)
}
// 逗号折叠:依次执行
template<typename... Args>
void print_all(Args... args) {
((std::cout << args << " "), ...);
// 展开为:(cout << arg1 << " "), (cout << arg2 << " "), ...
std::cout << std::endl;
}
// 逗号折叠 + lambda:带分隔符打印
template<typename... Args>
void print_sep(const std::string& sep, Args... args) {
bool first = true;
auto print_one = [&](const auto& arg) {
if (!first) std::cout << sep;
first = false;
std::cout << arg;
};
(print_one(args), ...);
std::cout << std::endl;
}
void patterns_demo() {
std::cout << "all_true: " << all_true(true, true, true) << std::endl; // 1
std::cout << "all_true: " << all_true(true, false, true) << std::endl; // 0
std::cout << "any_true: " << any_true(false, false, true) << std::endl; // 1
print_all(1, "hello", 3.14);
print_sep(", ", 1, "hello", 3.14);
}
// ============================
// 示例4:push_back 多个元素
// ============================
template<typename T, typename... Args>
void push_back_all(std::vector<T>& vec, Args&&... args) {
// 逗号折叠:对每个 arg 调用 push_back
(vec.push_back(std::forward<Args>(args)), ...);
// 展开为:
// vec.push_back(arg1), vec.push_back(arg2), ...
}
void push_back_demo() {
std::vector<int> v;
push_back_all(v, 1, 2, 3, 4, 5);
std::cout << "vector: ";
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
}
// ============================
// 示例5:类型检查折叠
// ============================
// 检查所有类型是否相同
template<typename T, typename... Rest>
constexpr bool all_same_type() {
return (std::is_same_v<T, Rest> && ...);
}
// 检查所有类型是否都是算术类型
template<typename... Ts>
constexpr bool all_arithmetic() {
return (std::is_arithmetic_v<Ts> && ...);
}
void type_check_demo() {
static_assert(all_same_type<int, int, int>());
static_assert(!all_same_type<int, double, int>());
static_assert(all_arithmetic<int, double, float>());
static_assert(!all_arithmetic<int, std::string>());
std::cout << "类型检查 static_assert 全部通过" << std::endl;
}
// ============================
// 示例6:折叠表达式用于流式输出
// ============================
template<typename... Args>
void log(Args&&... args) {
// 二元左折叠:(std::cout << ... << args)
// 展开为 ((std::cout << arg1) << arg2) << arg3
(std::cout << ... << args) << std::endl;
}
void stream_demo() {
log("x=", 42, " y=", 3.14, " name=", "test");
}
// ============================
// 示例7:空包的处理规则
// ============================
/*
一元折叠对空包有特殊规则:
- && 空包结果是 true
- || 空包结果是 false
- , (逗号)空包结果是 void()
- 其他运算符对空包是编译错误
二元折叠可以处理空包(结果是 init 值),所以更安全。
*/
template<typename... Args>
auto safe_sum(Args... args) {
return (0 + ... + args); // 空包返回 0
}
template<typename... Args>
auto safe_product(Args... args) {
return (1 * ... * args); // 空包返回 1
}
int main() {
std::cout << "=== 四种折叠形式 ===" << std::endl;
fold_forms_demo();
std::cout << "\n=== 对比递归 ===" << std::endl;
comparison_demo();
std::cout << "\n=== 常用模式 ===" << std::endl;
patterns_demo();
std::cout << "\n=== push_back ===" << std::endl;
push_back_demo();
std::cout << "\n=== 类型检查 ===" << std::endl;
type_check_demo();
std::cout << "\n=== 流式输出 ===" << std::endl;
stream_demo();
std::cout << "\n=== 空包 ===" << std::endl;
std::cout << "safe_sum() = " << safe_sum() << std::endl;
std::cout << "safe_product() = " << safe_product() << std::endl;
return 0;
}空包的默认值
| 运算符 | 空包结果 |
|---|---|
| && | true |
| || | false |
| , | void() |
| 其他(+, *, - 等) | 编译错误 |
折叠表达式 vs 递归模板
| 特性 | 折叠表达式 | 递归模板 |
|---|---|---|
| 代码量 | 一行 | 至少两个函数 |
| 可读性 | 简洁明了 | 需要理解递归终止 |
| 编译速度 | 快(不产生递归实例化) | 慢(每层递归都实例化) |
| 调试 | 简单 | 复杂 |
| 灵活性 | 限于二元运算符 | 任意逻辑 |
常见问题
左折叠和右折叠有什么实际区别?
对于加法、乘法这些满足结合律的运算符没有区别。但对于减法、除法或流式输出(<<),左右折叠结果不同。比如 (... - args) 展开为 ((1-2)-3) = -4,而 (args - ...) 展开为 1-(2-3) = 2。流式输出必须用左折叠 (std::cout << ... << args)。
一元折叠为什么不能处理所有空包?
标准只为 &&、||、逗号定义了空包的默认值(它们的"单位元")。其他运算符没有通用的单位元(比如减法的单位元是什么?),所以空包是编译错误。用二元折叠提供初始值可以解决这个问题。
折叠表达式能用自定义运算符吗?
可以,只要参数包元素的类型重载了该运算符。所有 C++ 的二元运算符(+, -, , /, %, ^, &, |, <<, >>, +=, -=, =, ==, !=, <, >, <=, >=, &&, ||, ,, ., ->)都支持折叠。
适用场景
- 变参函数中对所有参数求和/求积
- 对所有参数执行同一操作(如 push_back)
- 逻辑判断(所有为真/至少一个为真)
- 流式输出多个值
- 编译期类型检查
注意事项
- 一元折叠空包只有 &&、||、逗号安全,其他用二元折叠
- 左折叠和右折叠对非结合运算符结果不同
- 流式输出用左折叠:
(std::cout << ... << args) - 折叠表达式的 pack 必须是未展开的参数包
- 不能在折叠表达式的 op 位置使用不同的运算符
总结
C++17 折叠表达式通过 (... op pack) 或 (pack op ...) 等语法,在编译期将参数包展开为嵌套的运算符调用,替代了变参模板中繁琐的递归写法。四种形式(一元/二元左/右折叠)覆盖不同需求。面试中要能写出折叠表达式、手动展开它的结果、解释空包的处理规则、以及左右折叠的区别。