c++ - 如何仅使用参数包在 C++11 中实现 boost MPL FOLD ？

Question

boost mpl 有更常见的算法 - fold 。该算法是许多其他算法的基础。

template< typename Seq, typename State, typename Op> struct fold { ... }
//Here Seq is <T0,T1,...,Tn> any sequence.
// result of fold is  op<  op < ...< op<State,T0>::type, T1>::type > ... >, Tn>::type

欲了解更多信息，请阅读link .

Fold 在 c++11 中使用可变参数模板可能会重新定义如下:

 template< typename state, typename op, typename ...elements> struct fold;

如何实现不是问题，而是如何仅使用参数来实现它 打包是困难或可能无法解决的问题。

问:是否可以只使用参数打包来实现？

我想要类似的东西

template< typename OP, typename State, typename ...T>
struct fold
{
     // only for illustration
     typedef  apply< apply<....<apply<Op,State,T>>...>::type type; 
};

Answer 1

这里是对数模板递归深度 fold 实现的尝试。

#include <cstddef>

template<typename... Ts> struct types {};
template<typename T, typename U>
struct concat;
template<typename... Ts, typename... Us>
struct concat< types<Ts...>, types<Us...> > {
  typedef types<Ts..., Us...> result;
};
template<typename Ts, typename Us>
using Concat = typename concat<Ts, Us>::result;

template<std::size_t n, typename Ts>
struct split;
template<std::size_t n, typename... Ts>
struct split<n, types<Ts...>> {
private:
  typedef split<n/2, types<Ts...>> one;
  typedef split<n-n/2, typename one::right> two;
public:
  typedef Concat< typename one::left, typename two::left > left;
  typedef typename two::right right;
};
template<typename... Ts>
struct split<0, types<Ts...>> {
  typedef types<> left;
  typedef types<Ts...> right;
};
template<typename T, typename... Ts>
struct split<1, types<T, Ts...>> {
  typedef types<T> left;
  typedef types<Ts...> right;
};
template<template<typename, typename>class OP, typename State, typename Ts>
struct fold_helper;
template<template<typename, typename>class OP, typename State, typename... Ts>
struct fold_helper<OP, State, types<Ts...>> {
private:
  typedef split<sizeof...(Ts)/2, types<Ts...>> parts;
  typedef typename parts::left left;
  typedef typename parts::right right;
  typedef typename fold_helper<OP, State, left>::result left_result;
public:
  typedef typename fold_helper<OP, left_result, right>::result result;
};
template<template<typename, typename>class OP, typename State>
struct fold_helper<OP, State, types<>> {
  typedef State result;
};
template<template<typename, typename>class OP, typename State, typename T>
struct fold_helper<OP, State, types<T>> {
  typedef typename OP<State,T>::type result;
};
template<template<typename, typename>class OP, typename State, typename... Ts>
struct fold {
  typedef typename fold_helper<OP, State, types<Ts...>>::result type;
};
template<template<typename, typename>class OP, typename State, typename... Ts>
using Fold = typename fold<OP, State, Ts...>::type;

template<typename left, typename right>
struct op_test {
  typedef int type;
};

int main() {
  Fold< op_test, double, int, char, char*, int* > foo = 8;
}

在这里，我首先获取线性列表，并使用 split 元函数将其分成两个半长列表。

一旦我有了两半，我就会 fold 前半部分，然后获取结果并 fold 后半部分。

虽然完成了 O(N) 工作，但在任何时候你的深度都仅为 O(lg(N))。

我没有看到为什么我们不能实现 O(lg(lg(N)) 深度的理论原因，但我也没有看到这一点:最大深度约为 1000，你必须有几十个类型列表上的嵌套 fold 需要 100 秒才能耗尽模板堆栈空间:根据我的经验，编译器在达到对数深度限制之前就会崩溃。

现在它编译: http://ideone.com/CdKAAT

split 是处理长列表的一种通常有用的方法，无需每个元素递归一次。一旦你进行了对数分割，fold 和 fold_helper 就非常明显了。