22

我目前正在用 C++11 编写一些需要大量函数组合的加密算法。我必须处理两种类型的组合：

  1. 在其自身上组合一个函数的次数不定。在数学上，对于某个函数 F，F^n(x) = (F^{n-1} o F)(x) = F^{n-1}(F(x))。

  2. 将不同的功能组合在一起。例如，对于某些相同类型的函数 f,g,h,i,j 和 k，我将有 f(g(h(i(j(k(x))))))。

就我而言，我使用 F 的以下定义：

const std::vector<uint8_t> F(const std::vector<uint8_t> &x);

我想自己编写这个函数 n 次。我以一种简单的递归方式实现了组合，效果很好：

const std::vector<uint8_t> compose(const uint8_t n, const std::vector<uint8_t> &x)
{
    if(n > 1)
       return compose(n-1, F(x));

    return F(x);
}

对于这种情况，是否有更有效的方法可以使用 c++11 但不使用 BOOST来实现这种组合？当然，如果可能的话，使用这种形式会很棒：

answer = compose<4>(F)(x); // Same as 'answer = F^4(x) = F(F(F(F(x))))'

对于第二种情况，我想实现可变数量的函数的组合。对于给定的一组函数 F0, F1, ..., Fn 与 F 具有相同的定义，是否有一种有效且适当的方法来组合它们，其中 n 是可变的？我认为可变参数模板在这里会很有用，但我不知道在这种情况下如何使用它们。

谢谢你的帮助。

4

7 回答 7

17

这些方面的东西，也许（未经测试）：

template <typename F>
class Composer {
  int n_;
  F f_;
public:
  Composer(int n, F f) : n_(n), f_(f) {}

  template <typename T>
  T operator()(T x) const {
    int n = n_;
    while (n--) {
      x = f_(x);
    }
    return x;
  }
};

template <int N, typename F>
Composer<F> compose(F f) {
  return Composer<F>(N, f);
}

编辑：对于第二种情况（这次测试）：

#include <iostream>

template <typename F0, typename... F>
class Composer2 {
    F0 f0_;
    Composer2<F...> tail_;
public:
    Composer2(F0 f0, F... f) : f0_(f0), tail_(f...) {}

    template <typename T>
    T operator() (const T& x) const {
        return f0_(tail_(x));
    }
};

template <typename F>
class Composer2<F> {
    F f_;
public:
    Composer2(F f) : f_(f) {}

    template <typename T>
    T operator() (const T& x) const {
        return f_(x);
    }
};

template <typename... F>
Composer2<F...> compose2(F... f) {
    return Composer2<F...>(f...);
}

int f(int x) { return x + 1; }
int g(int x) { return x * 2; }
int h(int x) { return x - 1; }

int main() {
  std::cout << compose2(f, g, h)(42);
  return 0;
}
于 2013-09-28T20:38:05.150 回答
12

感谢 2013 年的 Gabriel 提出的有趣问题。这是一个解决方案。它适用于 c++14。

#include <functional>
#include <iostream>
using std::function;

// binary function composition for arbitrary types
template <class F, class G> auto compose(F f, G g) {
  return [f, g](auto x) { return f(g(x)); };
}

// for convienience
template <class F, class G> auto operator*(F f, G g) { return compose(f, g); }

// composition for n arguments
template <class F, typename... Fs> auto compose(F f, Fs &&... fs) {
  return f * compose(fs...);
}

// composition for n copies of f
template <int i, class F>
// must wrap chain in a struct to allow partial template specialization
struct multi {
  static F chain(F f) { return f * multi<i - 1, F>::chain(f); }
};
template <class F> struct multi<2, F> {
  static F chain(F f) { return f * f; }
};
template <int i, class F> F compose(F f) { return multi<i, F>::chain(f); }

int main(int argc, char const *argv[]) {

  function<double(int)> f = [](auto i) { return i + 3; };
  function<int(double)> g = [](auto i) { return i * 2; };
  function<int(int)> h = [](auto i) { return i + 1; };

  std::cout << '\n'
            << "9   == " << compose(f, g, f)(0) << '\n'
            << "5   == " << (f * g * h)(0) << '\n'
            << "100 == " << compose<100>(h)(0) << '\n';

  return 0;
}

你可以定义

Matrix compose(Matrix f, Matrix g);

或者

Rotation compose(Rotation f, Rotation g);

将此代码重用于各种事情。

于 2016-04-01T02:47:06.617 回答
2

一个非常普遍的例子（g++ -std=c++1y composition.cpp）：

// ---------------------------------------------------------
// "test" part
// ---------------------------------------------------------
int f(int a) { return 2*a; }
double g(int a) { return a+2.5; }
double h(double a) { return 2.5*a; }
double i(double a) { return 2.5-a; }

class Functor {
  double x;
public:
  Functor (double x_) :  x(x_) { }
  double operator() (double a) { return a*x; }
};

// ---------------------------------------------------------
// ---------------------------------------------------------
int main () {

  auto l1 = [] (double a) { return a/3; };
  auto l2 = [] (double a) { return 3.5+a; };

  Functor fu {4.5};

  auto compos1 = compose (f, g, l1, g, h, h, l1, l2); 

  auto compos2 = compose (compos1, l1, l2, fu);

  auto x = compos2 (3);

  cout << x << endl;
  cout << compos2(3) << endl;

  cout << fu(l2(l1(l2(l1(h(h(g(l1(g(f(3))))))))))) << endl;

} // ()

图书馆部分：

// ---------------------------------------------------------
// "library" part
// ---------------------------------------------------------
template<typename F1, typename F2>
class Composite{
private:
  F1  f1;
  F2  f2;

public:
  Composite(F1  f1,  F2  f2) : f1(f1), f2(f2) { }

  template<typename IN>
  decltype(auto) operator() (IN i)   
  { 
    return f2 ( f1(i) ); 
  }
};

// ---------------------------------------------------------
// ---------------------------------------------------------
template<typename F1, typename F2>
decltype(auto) compose (F1 f, F2 g) {
  return Composite<F1, F2> {f,g};
}

// ---------------------------------------------------------
// ---------------------------------------------------------
template<typename F1, typename... Fs>
decltype(auto) compose (F1  f,  Fs  ... args) 
{
  return compose (f, compose(args...));
}

整个程序：

//  g++ -std=c++1y composition.cpp 

#include <iostream>

using namespace std;

// ---------------------------------------------------------
// "library" part
// ---------------------------------------------------------
template<typename F1, typename F2>
class Composite{
private:
  F1  f1;
  F2  f2;

public:
  Composite(F1  f1,  F2  f2) : f1(f1), f2(f2) { }

  template<typename IN>
  decltype(auto) operator() (IN i)   
  { 
    return f2 ( f1(i) ); 
  }
};

// ---------------------------------------------------------
// ---------------------------------------------------------
template<typename F1, typename F2>
decltype(auto) compose (F1 f, F2 g) {
  return Composite<F1, F2> {f,g};
}

// ---------------------------------------------------------
// ---------------------------------------------------------
template<typename F1, typename... Fs>
decltype(auto) compose (F1  f,  Fs  ... args) 
{
  return compose (f, compose(args...));
}

// ---------------------------------------------------------
// "test" part
// ---------------------------------------------------------
int f(int a) { return 2*a; }
double g(int a) { return a+2.5; }
double h(double a) { return 2.5*a; }
double i(double a) { return 2.5-a; }

class Functor {
  double x;
public:
  Functor (double x_) :  x(x_) { }
  double operator() (double a) { return a*x; }
};

// ---------------------------------------------------------
// ---------------------------------------------------------
int main () {

  auto l1 = [] (double a) { return a/3; };
  auto l2 = [] (double a) { return 3.5+a; };

  Functor fu {4.5};

  auto compos1 = compose (f, g, l1, g, h, h, l1, l2); 

  auto compos2 = compose (compos1, l1, l2, fu);

  auto x = compos2 (3);

  cout << x << endl;
  cout << compos2(3) << endl;

  cout << fu(l2(l1(l2(l1(h(h(g(l1(g(f(3))))))))))) << endl;

} // ()
于 2014-12-31T23:27:01.850 回答
1

带有参数转发的函数迭代的快速实现。不幸的是，辅助类型是必需的，因为函数模板不能部分专门化。

#include <functional>
#include <iostream>
using namespace std;

template<int n, typename A>
struct iterate_helper {
  function<A(A)> f;
  iterate_helper(function<A(A)> f) : f(f) {}
  A operator()(A&& x) {
    return f(iterate_helper<n - 1, A>(f)(forward<A>(x)));
  };
};

template<typename A>
struct iterate_helper<1, A> {
  function<A(A)> f;
  iterate_helper(function<A(A)> f) : f(f) {}
  A operator()(A&& x) {
    return f(forward<A>(x));
  };
};

template<int n, typename A>
function<A(A)> iterate(function<A(A)> f) {
  return iterate_helper<n, A>(f);
}

int succ(int x) {
  return x + 1;
}

int main() {
  auto add5 = iterate<5>(function<int(int)>(succ));
  cout << add5(10) << '\n';
}
于 2013-09-28T20:34:07.350 回答
1

这是一个简单的 c++14 解决方案（可能会重写为 c++11）：

#include <iostream>

// base condition
template <typename F>
auto compose(F&& f)
{
    return [a = std::move(f)](auto&&... args){
        return a(std::move(args)...);
    };
}

// recursive composition
// from compose(a, b, c...) to compose(ab, c...)
template <typename F1, typename F2, typename... Fs>
auto compose(F1&& f1, F2&& f2, Fs&&... fs)
{
    return compose(
        [first = std::move(f1), second = std::move(f2)]
        (auto&&... args){
            return second(first(std::move(args)...));
        },
        std::move(fs)...
    );
}

可能的用法：

int main()
{
const auto f = compose(
  [](const auto n){return n * n;},
  [](const auto n){return n + 2;},
  [](const auto n){return n + 2;}
);
std::cout << f(10) << std::endl; // outputs 104
}

这是一个包含更多示例的 repo 链接：https ://github.com/nestoroprysk/FunctionComposition

于 2019-08-10T23:56:21.660 回答
0

您还没有显示 的​​正文F，但是如果您可以修改它以使其改变输入以形成输出，则将签名更改为：

void F(std::vector<uint8_t>& x);

此后，您可以将 Fn 实现为：

void Fn(std::vector<uint8_t>& x, size_t n)
{
    for (size_t i = 0; i < n; i++)
        F(x);
}

如果它更有效，编译器将为您展开循环，但即使它不是局部变量的增量/比较，也将比调用 F 快几个数量级。

然后，当您真正想要复制时，您可以明确地复制构造新向量：

vector<uint8_t> v1 = ...;
vector<uint8_t> v2 = v1; // explicitly take copy
Fn(v2,10);
于 2013-09-29T15:29:11.333 回答
0

怎么样（未经测试）：

template < typename Func, typename T >
T  compose_impl( Func &&, T &&x, std::integral_constant<std::size_t, 0> )
{ return std::forward<T>(x); }

template < typename Func, typename T, std::size_t N >
T compose_impl( Func &&f, T &&x, std::integral_constant<std::size_t, N> )
{
    return compose_impl( std::forward<Func>(f),
     std::forward<Func>(f)(std::forward<T>( x )),
     std::integral_constant<std::size_t, N-1>{} );
}

template < std::size_t Repeat = 1, typename Func, typename T >
T  compose( Func &&f, T &&x )
{
    return compose_impl( std::forward<Func>(f), std::forward<T>(x),
     std::integral_constant<std::size_t, Repeat>{} );
}

我们可以为多个函数使用可变参数函数模板（未经测试）：

template < typename Func, typename T >
constexpr  // C++14 only, due to std::forward not being constexpr in C++11
auto chain_compose( Func &&f, T &&x )
 noexcept( noexcept(std::forward<Func>( f )( std::forward<T>(x) )) )
 -> decltype( std::forward<Func>(f)(std::forward<T>( x )) )
{ return std::forward<Func>(f)(std::forward<T>( x )); }

template < typename Func1, typename Func2, typename Func3, typename ...RestAndT >
constexpr  // C++14 only, due to std::forward
auto  chain_compose( Func1 &&f, Func2 &&g, Func3 &&h, RestAndT &&...i_and_x )
 noexcept( CanAutoWorkHereOtherwiseDoItYourself )
 -> decltype( auto )  // C++14 only
{
    return chain_compose( std::forward<Func1>(f),
     chain_compose(std::forward<Func2>( g ), std::forward<Func3>( h ),
     std::forward<RestAndT>( i_and_x )...) );
}

即将到来的decltype(auto)构造会自动计算内联函数的返回类型。我不知道是否有类似的自动计算noexcept

于 2013-09-29T16:30:56.223 回答