C++——折叠表达式

2025-04-09

Collapse.

a.k.a. Reduce?

cppreference中对于 fold expression 的介绍非常简洁明了：

Reduces(folds) a pack over a binary operator.

即，将一个参数包在一个二元运算符上~~“约减”（笔者自创的翻译.cpp，以后还是先用"reduce"原名比较好）~~。

参考“Lattice Reduction”的翻译“格基规约”，"reduce"译为“规约”庶几尚可。

reduce 是一种处理序列元素的方法，其主要参数是元素序列ls和一个二元函数f，和一个（可选的）初始值I。
其伪代码可表示如下：

//reduce(ls,f)
I = ls[0];
for(i : ls[1:])
{
    I = f(I,i);
}
return I;

//reduce(ls,f,I)
for(i : ls)
{
    I = f(I,i);
}
return I;

可见没有初始值I时，其本质就是将ls的第一个元素取作初始值，并在剩余的元素上执行reduce操作。

fold 在操作上和 reduce 类似，但一般区分 fold 和 reduce 的标志就是初始值（前者默认必须有初值，后者默认可选）。

语义上，可以认为 reduce 涉及的二元操作符（函数）应满足交换律和结合律，而 fold 没有这一要求。
C++23~~给ranges algorithm添油加醋时~~考虑到由于C++的concept只能约束语法而非语义，故为避免歧义，新加入的fold家族算法都采用了 fold 之名；又考虑到初始值的需求，故其中存在fold_left_first等变种，将在后续详述之。

语法

C++中 fold expression 主要针对的是可变模板参数包(variadic template parameter pack)。

下述内容默认读者具有可变模板参数的基本知识，若不然，可移步C++——可变模板参数作参考。

其调用语法有四种：假设存在二元操作符 op ，参数包 pack （和初始值 init）：

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

其中，op 是C++的32个二元运算符之一；二元折叠中两个操作符必须一致。
pack 必须是一个未展开的参数包，init 则不允许是一个未展开的参数包，同时二者都不能含有优先级高于 op 的操作符（若有，则必须以括号()保护之）。

假设 pack 中的参数分别为 (E1,E2,...,En)，则上述展开的结果如下：

(pack op ...) = (((E1 op E2) op E3) ... op En)；
(... op pack) = (())

对于一元左/右折叠，若参数包为空，则当且仅当操作符为[逻辑与&&，逻辑或||，逗号,之一]时程序才能通过编译，此时其值分别为false、true和void。否则将报编译错误。

简单的应用实例：

template<size_t... Ns>
constexpr size_t mul_result = (Ns * ...);

static_assert(mul_result<3,3,5> == 45); //passes
static_assert(mul_result<256,512,0> == 0); //passes

template<bool... vals>
constexpr bool disjunction_v = (vals && ...);

static_assert(disjunction_v<true,true,false> == false); //passes
static_assert(disjunction_v<> == false); //passes
//static_assert(mul_result<> == 0); //Not compile: pack is empty for binary operator *


template<size_t... Ns>
//constexpr size_t add_init = (Ns + ... + 1*2); //Not Compile: precedence of * is higher than operator + in fold expression
constexpr size_t add_init = (Ns + ... + (1*2)); //OK

应用场景

fold expression 最大的应用场景在于让很多必须递归展开参数包的函数、结构体、变量等能够一次完成展开定义，保证可读性的同时最大限度减弱了模板膨胀带来的代码体积增大、效率下降等负面影响。

如现在定义一个类似python的print函数~~先当C++23的std::print不存在，反正人家也不支持括号一套直接输出.cpp~~：

template<class ...Types>
void print(Types&&... args)
{
    (std::cout << ... << args);
}

print(1,2,3); //Output: 123
print("Hello C++",23,'!'); //Output: Hello C++23!

在没有 fold expression 语言层面的支持时，其只能按照如下方式实现：

template<class Type,class ...Types>
void print(Type&& type,Types&&... args)
{
    std::cout << type;
    print(std::forward<Types>(args)...);
}

template<class Type>
void print(Type&& type)
{
    std::cout << type;
}

代码编写更加繁琐的同时，由于上述编译时每次调用都会产生sizeof...(Types) + 1个新的实例~~忽略少得可怜的参数包组合恰好全等的概率~~。
递归代码运行效率偏低的同时，产生可执行文件的体积会大幅增加。
相对地，对于 fold expression 编写的参数包每次调用只会产生一个新的实例。

进阶的应用除了~~玩转各种operator~~，还有对参数包中的每个元素“处理”的玩法。如若希望上述的print函数能够像python一样自定义sep和end（当然都是编译期指定），可以如此：

template<char sep,char end,class ...Types>
void print(Types&&... args)
{
    ((std::cout << args << sep),...);
}

template<class ...Types>
void print(Types&&... args)
{
    print<' ','\n'>(std::forward<Types>(args)...);
}

由于折叠表达式的循环操作只能施加于元素上，因此此处只能退而求其次——利用~~万能的~~operator,来完成输出。

假设需对模板/函数参数包args中的每个元素，通过函数f处理~~transform~~后再用于折叠表达式，则应将args用f包裹（此时不要加...展开）后再根据需求应用折叠表达式的语法（相当于把可变模板的语法搬过来）。如：

template<class ...Types>
void print(Types&&... args)
{
    (std::cout << ... << std::addressof<Types>(args));
}

tips：保留左右值属性的目的是为了触发std::addressof对右值的“截胡”，避免输出无意义的变量临时地址（因为右值引用在函数体内是左值；参考C++——右值引用与移动语义。

注意事项

固若金汤的`concept`

由于表达式的折叠展开不太直观~~且又在模板的刀尖上乱舞~~， fold expression 出错时报错信息的可读性预期会很差。因此应用时，建议使用C++20的具名concept来前置约束之，结合折叠表达式在模板变量中的应用，不需大费周章即可防患于未然。如：

template<class Ty>
concept correctly_outputable = requires(Ty&& arg)
{
    {std::cout << arg} -> std::same_as<std::ostream&>;
}

template<class ...Types>
void func(Types&&... args)
{
    (std::cout << ... << args);
}

假设现在有一个~~手搓失败的~~类，~~不小心~~忘记重载了operator<<，然后被打包进了func输出，约束和不约束的报错信息可读性大相径庭：

class ErrorOutput
{

};

int main()
{
    ErrorOutput e{};
    func("Object representation:\n",e,7,10.29);
}

由于重载的“贪心”机制，若不加以约束，编译器会尝试将所有可能的左操作数为std::ostream&的operator<<重载都尝试一遍：

main.cpp: In instantiation of 'void func(Types&& ...) [with Types = {const char (&)[24], ErrorOutput&, int, double}]':
main.cpp:24:9:   required from here
   24 |     func("Object representation:\n",e,7,10.29);
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:13:16: error: no match for 'operator<<' (operand types are 'std::basic_ostream<char>' and 'ErrorOutput')
   13 |     (std::cout << ... << args);
      |     ~~~~~~~~~~~^~~~~~~~~~~~~~~
(more than 400 lines omitted)
/usr/local/include/c++/14.2.0/ostream:774:39: note: the expression 'is_class_v<_Tp> [with _Tp = std::basic_ostream<char, std::char_traits<char> >&]' evaluated to 'false'
  774 |     concept __derived_from_ios_base = is_class_v<_Tp>
      |                                       ^~~~~~~~~~~~~~~

若以如下方法约束func，报错信息的可读性就会大幅提升：

1 2	template<class ...Types> void func(Types&&... args) requires (correctly_outputable<Types> && ...) /**/

main.cpp: In function 'int main()':
main.cpp:24:9: error: no matching function for call to 'func(const char [24], ErrorOutput&, int, double)'
   24 |     func("Object representation:\n",e,7,10.29);
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:11:6: note: candidate: 'template<class ... Types> void func(Types&& ...) requires (correctly_outputable<Types> && ...)'
   11 | void func(Types&&... args) requires( correctly_outputable<Types> && ...)
      |      ^~~~
main.cpp:11:6: note:   template argument deduction/substitution failed:
main.cpp:11:6: note: constraints not satisfied
main.cpp: In substitution of 'template<class ... Types> void func(Types&& ...) requires (correctly_outputable<Types> && ...) [with Types = {const char (&)[24], ErrorOutput&, int, double}]':
main.cpp:24:9:   required from here
   24 |     func("Object representation:\n",e,7,10.29);
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:11:6:   required by the constraints of 'template<class ... Types> void func(Types&& ...) requires (correctly_outputable<Types> && ...)'
main.cpp:11:66: note: the expression '(correctly_outputable<Types> && ...) [with Types = {const char (&)[24], ErrorOutput&, int, double}]' evaluated to 'false'
   11 | void func(Types&&... args) requires( correctly_outputable<Types> && ...)
      |

~~虽然这已经扯到concept的优点上了，~~归根结底还是concept在模板编程中应用的重要性，尤其是在 fold expression 一类的复杂场景中；详见C++——Concepts。

非模板的替代方案

同时，尽管 fold expression 是一个效率非常高的解决方案，但并不推荐滥用之。
由于其作用在参数包上，因此本质上依然是在进行模板编程——而模板编程受制于实例化的编译、运行开销及其必须在编译期执行的属性，部分问题仍然提倡用非模板的方式解决。如在参数类型可预测且相同的前提下，可以使用std::initializer_list<Ty>来进行参数打包，对编译期“打表”的要求可以通过constexpr或consteval约束之。

constexpr int sum(std::initializer_list<int> ls)
{
    return std::accumulate(ls.begin(),ls.end(),0);
}

constexpr int prod(std::initializer_list<int> ls)
{
    return std::accumulate(ls.begin(),ls.end(),1,[](int x,int y){return x*y;});
}

template<size_t N,std::enable_if_t<N >= 2,int> = 0>
constexpr std::array<int,N> fib_N()
{
    std::array<int,N> res{1,1};
    for(int i=0;i<N-2;++i)
    {
        res[i+2] = res[i] + res[i+1];
    }
    return res;
}

应用难度与注释

从应用经验看 fold expression 的应用难度比较高，很多情况下其展开式并不那么直观，若编写/注释不当易对可读性产生较大影响（主要原因之一是...后置）。

template<class ...Tys>
void func(Tys&&... args) requires (((sizeof(Tys) < 7 && std::is_trivially_copy_constructible_v<Tys>) && ...) && sizeof...(Tys) < 7) 
{
    /*...*/
}

当然从表达编译期约束之意上，上述形式已接近最优解。
缓解此问题的方法还是回归到前两点：使用具名concept分解约束（避免使用SFINAE等可读性较差的方法），并尽可能采用ranges等非模板的函数方案。

结语

fold expression 在可变模板参数包的应用中，堪称一柄难以驾驭的利剑；初看其语法和约束或许有些绕人（且需要大量的预备知识以理解之），但只需在实践中多加运用体会，加以在注释、运用范围、concept辅助等要点处多加注意，定能在自身对现代C++的理解更为通透的同时，充分感受到游走于模板之间的惬意。