如何使用可变参数模板在 C++11 中生成左关联表达式（也称为左折叠）？

Question

我想使用 C++ 模板通过二元运算聚合（折叠）多个参数。

这样的模板可以按如下方式使用：

fold<add>(100,10,5) 扩展为 add(add(100, 10), 5)

上面显示的特定扩展是 "left fold"。扩展 add(100, add(10, 5)) 是 "right fold"。假设 add 函数执行简单的整数加法，右折叠和左折叠产生相同的结果，115。

但考虑执行整数除法 (div(a,b)=a/b) 的函数 div。在这种情况下，关联性很重要，左右折叠会产生不同的结果：

fold_left<div>(100,10,5)  --> div(div(100, 10), 5) --> div(10, 5) -->  2
fold_right<div>(100,10,5) --> div(100, div(10, 5)) --> div(100, 2) --> 50

使用可变参数模板生成右关联版本（fold_right）很简单，但我一直无法弄清楚如何生成左关联版本（fold_left).以下 fold_left 的尝试实施导致编译器错误：

#include <iostream>

template <typename T> using binary_op = T(*)(const T& a, const T& b);

// The terminal (single-argument) cases of the variadic functions defined later. 
template<typename T, binary_op<T> Operation> inline T fold_right(const T& t) { return t; }
template<typename T, binary_op<T> Operation> inline T fold_left(const T& t) { return t; }

// Combines arguments using right-associative operation
// i.e. fold_right<T,op>(A,B,C) --> op(A, op(B,C))
template<typename T, binary_op<T> Operation, typename ... Rest> 
inline T fold_right(const T& t, Rest... rest) {
    return Operation(t, fold_right<T, Operation>(rest...));
}

// Combines arguments using left-associative operation
// i.e. fold_left<T,op>(A,B,C) --> op(op(A,B), C)
template<typename T, binary_op<T> Operation, typename ... Rest> 
inline T fold_left(Rest... rest, const T& t) {
    return Operation(fold_left<T, Operation>(rest...), t);
}

inline int add(const int& a, const int& b) { return a+b; }
inline int div(const int& a, const int& b) { return a/b; }

int main() {
    std::cout << fold_right<int,div>(100,10,5) //  (100 / (10 / 5))  = 50
              << "\n"
              << fold_left<int,div>(100,10,5)  //  Compiler error!
              << std::endl;
    return 0;
}

如何使用可变参数模板（在 c++11 中）来正确实现 fold_left？

我认为它本质上归结为能够 "pop" 参数包的最后一个参数，我试图在上面的 left_fold 模板中这样做，但正如我所说，这导致编译器错误。

注意：我在这个问题中使用了简单的算术运算和整数作为示例，但答案应该足够通用以使用任意函数处理对象聚合（假设它 returns与其参数相同类型的对象）。

注2：对于熟悉c++17的人来说，fold expressions可以用二元运算符产生左折叠和右折叠。但是这些在c++11中是不可用的。

作为相关问题：上述模板要求明确指定类型 T，如 fold_right<int,div>(...) 中所示。有什么方法可以制定模板，以便只需要操作，例如fold_right<div>(...)。我认为可以推断出 T 类型，但我看不到一种方法来命令模板参数将 binary_op<> 放在第一位。

谢谢！

Answer 1

这就是非尾随函数参数包的神奇之处：它们仅从显式提供的模板参数中推导出来。

这意味着 rest... 在 fold_left<int,div>(100,10,5) 调用中为空。因此，您的函数只有一个参数，而不是 3.

Answer 2

左边的参数包有问题。最好重新实现为右边的参数包：

template<typename T, binary_op<T> Operation> 
inline T fold_left(const T& t) { return t; }

template<typename T, binary_op<T> Operation, typename ... Rest>
inline T fold_left(const T& a, const T& b, Rest... rest) {
    return fold_left<T, Operation>(Operation(a,b), rest...);
}

Answer 3

Michael 回答了您的第一个问题。第二个可能有不同的答案。我的首选方法是将您的操作定义为具有模板成员的仿函数：

#include <type_traits>
struct homogene_add{
    template<typename T>
    T operator()(T const& lhs, T const& rhs){/*...*/}
};

struct mixed_add{
    template<typename L, typename R>
    std::common_type<L,R>::type
    operator()(L const& lhs, R const& rhs){/*...*/}
};

template<typename binary_op, typename ... Args> 
std::common_type<Args...>::type
fold_right(const Args&... args);

template<typename binary_op, typename First, typename ... Args>
std::common_type<First, Args...>::type
fold_right(const First& init, const Args&... args) {
    binary_op op;
    return op(init, fold_right<binary_op>(args...));
};

template<typename binary_op, typename First>
const First& fold_right(const First& init) {
    return init;
};

CV 资格和价值正确性，我留给 OP。

如何使用可变参数模板在 C++11 中生成左关联表达式（也称为左折叠）？

How can a variadic template be used to generate a left-associative expression (aka left fold) in c++11?

c++

templates

fold

variadic-templates

c++11