составление функций в C ++ / C ++ 11
В настоящее время я пишу некоторые криптографические алгоритмы на C ++ 11, которые требуют много композиций функций. Есть 2 типа композиции, с которыми мне приходится иметь дело:
-
Составьте функцию на себя переменное количество раз. Математически для определенной функции F F ^ n (x) = (F ^ {n-1} o F) (x) = F ^ {n-1} (F (x)).
-
Составьте разные функции вместе. Например, для некоторых функций 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 является переменной?
Я думаю, что здесь будет полезен шаблон с переменным числом, но я не знаю, как использовать их в этом случае.
Спасибо за вашу помощь.
Решение
Возможно, что-то в этом роде (не проверено):
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 года.
Вот решение. Работает на с ++ 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);
использовать этот код для всех видов вещей.
Очень общий пример (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;
} // ()
Быстрая реализация итерации функции с пересылкой аргументов. Тип помощника, к сожалению, необходим, потому что шаблоны функций не могут быть частично специализированными.
#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';
}
Вы не показали тело 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);
Как насчет (не проверено):
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