c++ - 如何使用可变参数模板在 c++11 中生成左关联表达式(又名左折叠)?
问题描述
我想使用 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 的人,折叠表达式可用于使用二元运算符生成左右折叠。但这些在 c++11 中不可用。
作为一个相关问题:上述模板要求明确指定类型 T,如fold_right<int,div>(...)
. 是否有某种方法可以制定模板以便只需要操作,例如fold_right<div>(...)
. 我认为T
可以推断出类型,但是我看不到一种方法可以将模板参数排序为binary_op<>
第一个。
谢谢!
解决方案
左边的参数包有问题。更好地将其重新实现为右侧的参数包:
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...);
}
推荐阅读
- sql - 如何使用相同的数据集更改 2 列或更多列的名称
- agora.io - Agora.io 是否提供类似 whatsapp 的通话功能?
- electron - 如何将文件保存到电子js中的应用程序文件夹
- angular - 忽略路由中的 Angular 11 + ionic 5 runGuardsAndResolvers 标志
- backbone.js - 使用 StickIt 绑定到 Backbone Marionette 的 UI 哈希
- node.js - 这个 if 语句究竟做了什么?
- shell - sed如何过滤以前的冗余条件
- swift - 有什么办法可以在 Xcode 中 StackView 的间距选择中添加乘数
- angular - 尝试运行 Angular 项目后生成的错误
- c - 如何在 typedef 函数上强制执行 SAL 注释?