Состав функции в C++/C++ 11

Question

В настоящее время я кодирую некоторые криптографические алгоритмы в 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); 

Я хотел бы сочинить эту функцию на себя п раз. Я выполнил композицию в простой рекурсивной способом, который работает отлично:

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 является переменной? Я думаю, что здесь будет полезен вариационный шаблон, но я не знаю, как их использовать в этом случае.

Благодарим за помощь.

Answer 1

Что-то вдоль этих линий, возможно (непроверенные):

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

EDIT: А во втором случае (tested this time):

#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; 
} 

Answer 2

Быстрая реализация итерации функций с пересылкой аргументов. К сожалению, вспомогательный тип необходим, поскольку шаблоны функций не могут быть частично специализированы.

#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'; 
} 

Answer 3

Вы не показали тело 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.

Вы можете затем explcitly копирования строить новые векторы, когда вы на самом деле хотите, чтобы сделать копию:

vector<uint8_t> v1 = ...; 
vector<uint8_t> v2 = v1; // explicitly take copy 
Fn(v2,10); 

Answer 4

Что о (непроверенные):

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

Мы можем использовать VARIADIC шаблоны функций для нескольких функции (непроверенные):

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) co nstruct автоматически вычисляет возвращаемый тип из встроенной функции. Я не знаю, есть ли подобный автоматический расчет для noexcept

Answer 5

Очень общий пример (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; 

} //() 

Answer 6

Спасибо за интересный вопрос, Габриэль 2013 года. Вот решение. Он работает в 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' << "9 == " << (f * g * h)  (0) \ 
    << '\n' << "3 == " << compose<100>(h) (0) \ 
    << '\n'; 

    return 0; 
} 

Вы можете определить

Matrix compose(Matrix f, Matrix g); 

или

Rotation compose(Rotation f, Rotation g); 

повторно использовать этот код для всех видов вещей.