折叠表达式的递归展开原理 ​

面试考点 ​

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 ...) 等语法,在编译期将参数包展开为嵌套的运算符调用,替代了变参模板中繁琐的递归写法。四种形式(一元/二元左/右折叠)覆盖不同需求。面试中要能写出折叠表达式、手动展开它的结果、解释空包的处理规则、以及左右折叠的区别。