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

Question

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

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

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

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

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

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 ？

我认为它本质上归结为能够从参数包中“弹出”最后一个参数，这是我在 left_fold 中尝试做的。上面的模板，但正如我所说，这导致了编译器错误。

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

注意 2:对于那些熟悉 c++17 的人， fold expressions 可用于通过二元运算符生成左右折叠。但这些在 c++11 中不可用。

作为一个相关问题:上面的模板需要明确指定类型 T，如 fold_right<int,div>(...) .有什么方法可以制定模板，以便只需要操作，例如fold_right<div>(...) .我会认为类型 T可以推断，但我没有看到一种方法来命令模板参数来放置 binary_op<>首先。

谢谢!

Answer 1

左边的参数包有问题。最好将其重新实现为右侧的参数包:

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...);
}