C++17: Simplify Code with Fold Expressions

本篇作为 Understanding variadic templates 的进阶内容，同时，Fold Expressions 也是 C＋＋17 最常用的特性之一。

Fold Expressions 的基本概念

C＋＋11中，参数包只能在需要参数列表的上下文展开，比如函数递归。而递归函数需要终止条件，因此往往需要提供一个同名的函数来终止递归。

举个例子：

void print()
{
    std::cout << '\n';
}

template<typename F, typename... Args>
void print(F first, Args... args)
{
    std::cout << first << ' ';
    print(args...);
}

我们无法在函数主体中展开，例如不能这样做：

template<typename... Args>
void print(Args... args)
{
    std::cout << ... << args << std::endl;
}

但是可以通过逗号表达式和初始化列表在函数主体展开参数包。

例子如下：

template<typename... T>
void print(T&&... args)
{
    std::initializer_list<int>{([](const auto& t) {
                std::cout << t << std::endl;
        }(std::forward<T>(args)), 0)...};
}

短短的一行代码中，便已使用了 initializer list、lambda、perfect forwarding、comma operator 等多种特性。

由于参数包只能在需要参数列表的上下文展开，因而不用递归，便需要一个支持可变参数的类型，initializer_list 刚好满足条件。

此外，我们知道 initializer_list 只支持单类型，而需要处理的参数却是不同类型的，所以再借助逗号表达式来实现目的。

逗号表达式基于一个基本的事实，看如下代码：

int a = 1;
int b = 2;
int c = 5;
a = (a = b, c);

a 最终的结果将为 5，在逗号操作符所连接的表达式中，会从左往右依次执行。本例中，首先会执行 (a = b)，然后返回 c，所以 a 的值便为 c 的值。

依据这个事实可以在 initializer_list 中展开参数包，表面上是在初始化 initializer_list，实际上是在初始化过程中利用逗号表达式展开参数包。

这样的代码写起来依旧麻烦，所以在 C＋＋17，提供了 Fold Expressions（折叠表达式），可以直接在函数主体中展开参数包。

可以简单地通过 Fold expr 来改写上述例子：

template<typename... Args>
void print(Args... args)
{
    ((std::cout << args << ' '), ...);
    std::cout << '\n';
}

具体细节，见于下节。

Fold Expressions 的细节疏理

Fold Expression 的语法比较简单，可以直接参考 cppref。

语法分为一元操作和二元操作。pack 指的就是参数包，op 指的是操作类型，有一个 op 的是一元操作，两个 op 的是二元操作。

我们先来看一元操作，来写一个最简单的输出函数：

template<typename... T>
void print(T&&... args)
{
        (std::cout << ... << args) << '\n';
}

这是使用的是第(2)个语法，即一元左折叠，需要注意的是：括号也是语法的一部分。

因为 cout 输出后会返回一个 ostream，所以可以不断输出所有参数，展开后的代码如下：

print(1, 2, 3, 4);
((((std::cout << 1) << 2) << 3) << 4) << '\n';

但是注意不能这样写：

std::cout << (args << ... << '\n');

这是右折叠，别忘了 operator<< 本义为左移操作符，所以执行结果会出人意料。

上述输出函数的缺点在于输出内容之间没有空格，若要在每个参数的输出之间加入空格，最简单的方式是借助逗号表达式，例子便是上节末尾的代码：

template<typename... Args>
void print(Args&&... args)
{
    ((std::cout << args << ' '), ...);
    std::cout << '\n';
}

当然还有其它的做法，若你想在处理参数之前或之后添加额外的操作，可以额外定义一个函数：

template<typename F, typename... Args>
void print(F first, const Args&... args)
{
    std::cout << first;
    auto space = [](const auto& arg) {
        std::cout << ' ' << arg;
    };
    (..., space(args));
    std::cout << '\n';
}

区别在于，第二种做法不支持 0 个参数，而逗号表达式可以支持，不过小做修改便可支持：

template<typename... Args>
void printer(const Args&... args)
{
    auto space = [](const auto& arg) {
        std::cout << arg << ' ';
    };

    (..., space(args));
    std::cout << '\n';
}

但是不是任何时候都可折叠0个参数的，比如：

template<typename... Args>
auto sum(Args... args)
{
    return (... + args);
}

这是个求和函数，它必须要返回一个值，所以 0 参时会报错。

这种情况就应该使用二元折叠，你可以翻回本节头部去查看二元的语法，其中的 init 的意思就是初始值，面对 0 参时依旧可以运行。

因此例子可以更改为：

template<typename... Args>
auto sum(Args... args)
{
    // binary left fold
    return (0 + ... + args);

    // binary right fold
    //return (args + ... + 0);  
}

这里使用了二元左折叠，在这种情况下和二元右折叠没有区别，但一般都优先使用左折叠。

假如我们要相加字符串，那么左折叠与右折叠便有差异了。

重写一个例子用来连接字符串：

template<typename... Args>
auto strcat(Args&&... args)
{
    // unary left fold
    return (... + args);
}

若像下面这样调用：

std::cout << strcat(std::string{"Have"}, "a", "nice", "day!") << '\n';

输出结果将为：

空格问题暂且不论。现在若把参数调用的顺序稍微切换，

std::cout << strcat("Have", "a", "nice", std::string("day!")) << '\n';

便是完全不同的结果：

现在编译不过了。

这是由于原生字符串不支持 operator+，第一个调用中将 string 放在首位，因为它内部重载了 operator+，所以可以进行加法，之后会返回一个 string，遂可将所有参数组成完整的字符串。

而第二个调用中，string 处于尾部，而实现却为一元左折叠，由于前面的参数不支持 operator+ 而编译出错。

只需将 strcat 改为一元右折叠便能编译第二个调用，但此时又无法支持第一个调用。

解决之道如下：

template<typename... Args>
auto strcat(Args&&... args)
{
    // unary left fold
    return ((std::string{} + args + " ") + ...);
}

对于每一个字符串，都在开头添加一个空 string，这样就能针对所有形式。

Filter Fold Expressions

若你想对解包结果添加约束，可以组合逗号表达式和逻辑运算符（&&, ||, !）使用来添加过滤。

举个例子，若想写一个只打印偶数的输出函数，可以这样编写：

#include <iostream>

template<typename... Args>
void print_even_number(Args... args)
{
    bool b = false;
    ((b = [](int arg) { return arg % 2 == 0; }(args) && (std::cout << args << ' ')), ...);
    std::cout << '\n';
}

int main()
{
    print_even_number(1, 2, 3, 4, 5, 6, 12, 11, 18, 19);

    return 0;
}

输出结果为：

给了一个未使用变量警告，可以使用 C++17 的 [[maybe_unused]] 特性来消除。

bool b [[maybe_unused]] = false;

此外，还可以结合 type traits 来使用，比如我们想实现一个判断容器类型是否一致的功能，可以这样编写：

template<typename H, typename... Ts>
struct is_same_type {
    static constexpr bool value =  (std::is_same_v<H, Ts> && ...);
};

// will be true
is_same_type<int, int, decltype(3)>::value;

标准中的 array 就使用了这个技巧来判断类型是否一致。

编译期排序

Fold Expressions 也可以和一些算法结合起来使用。

这里有个来自网络的编译期排序例子，可以参考一 二。

#include <iostream>
#include <array>
#include <utility>

template<typename Values> struct SortImpl;

template<typename I, I... values>
constexpr auto sort(std::integer_sequence<I, values...> sequence)
{
    return SortImpl<decltype(sequence)>::sort();
}

template<typename I, I... values>
struct SortImpl<std::integer_sequence<I, values...>>
{
    static constexpr auto sort() {
        // 创建4位索引序列
        return sort(std::make_index_sequence<sizeof...(values)>{});
    }

    template<std::size_t... index>
    static constexpr auto sort(std::index_sequence<index...>) {
        // 创建integer_sequence，用于返回排序好的结果
        return std::integer_sequence<I, ith<index>()...>{};
    }

    template<std::size_t i>
    static constexpr auto ith() {
        I result{};

        // 利用rankOf计算当前数值所应排列的位置，再和索引比较，相同则返回对应的数值
        ((i >= rankOf<values>() && i < rankOf<values>() + count<values>()
                ? result = values : I{}), ...);
        return result;
    }

    template<I x> // 排序位置，例如第一次调用：(0 > 5) + (0 > 2) + (0 > 2) == 0，则应排第0个
    static constexpr auto rankOf() { return ((x > values) + ...); }

    template<I x> // 计算相同数值的个数
    static constexpr auto count() { return ((x == values) + ...); }
};

template<typename I, I... values>
constexpr auto toArray(std::integer_sequence<I, values...>)
{
    // 转换成数组，以便输出
    return std::array<I, sizeof...(values)> { values... };
}

int main()
{
    auto y = toArray(sort(std::index_sequence<0, 5, 2, 2>{}));

    for(auto& elem : y) {
        std::cout << elem << ' ';
    }
    std::cout << '\n';
}

关键位置我已经提供了注释，主要是利用了 integer_sequence 和 fold expression，前者用于提供索引，后者用于找出该索引所应对应的值的位置和计算重复次数，索引与位置重复次数一比较，就能找到索引对应的值。

运行结果如下：

Pretty-print std::tuple

我们还可以利用 fold expressions 来方便地打印 tuple 的元素，例子如下：

#include <iostream>
#include <tuple>
#include <utility>

template<typename T, std::size_t... Is>
void print_tuple(const T& tup, std::index_sequence<Is...>)
{
    std::cout << "(";
    (..., (std::cout << (Is == 0 ? "" : ", ") << std::get<Is>(tup)));
    std::cout << ")\n";
}

template<typename... T>
void print_tuple(const std::tuple<T...>& tup)
{
    print_tuple(tup, std::make_index_sequence<sizeof...(T)>());
}

int main()
{
    print_tuple(std::make_tuple("apple", "pineapple", "cherry", "lemon", "mango"));
}

输出如下：

std::tuple 提供的 get<I>(tup) 是编译期的，若需要运行期访问 tuple，也很简单，代码如下：

template<typename T, std::size_t... Is>
void get_tuple(std::size_t i, const T& tup, std::index_sequence<Is...>)
{
    (..., ((Is == i) && (std::cout << std::get<Is>(tup))));
    std::cout << '\n';
}

template<typename... T>
void get_tuple(std::size_t i, const std::tuple<T...>& tup)
{
    get_tuple(i, tup, std::make_index_sequence<sizeof...(T)>());
}

// call
auto tup = std::make_tuple("apple", "pineapple", "cherry", "lemon", "mango");
get_tuple(1, tup);

输出如下：

折叠函数调用

Fold expressions 也可以用折叠访问任意基类的共有成员，一个小例子：

#include <iostream>

template<typename... Bases>
struct Foo : private Bases...
{
    void 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()
{
    Foo<A, B, C> foo;
    foo.print();
}

输出将为：

总结

Fold expressions 可以简化代码，完成一些本来实现起来较麻烦的操作。

本篇介绍了基本概念与用法，并提供了大量的例子，相信大家读完之后对其已不陌生。

实际上，它的用法还有很多，有一些用法相当复杂，大家平时可以再多思考下它的其它用处。此外，C++20 的一些特性也能和它结合使用，等介绍到的时候会补充。