C++ Iterator Pipelining Designs

Question

Supongamos que queremos aplicar una serie de transformaciones, int f1(int), int f2(int), int f3(int), a una lista de objetos. Una forma ingenua sería

SourceContainer source; 

TempContainer1 temp1; 
transform(source.begin(), source.end(), back_inserter(temp1), f1); 
TempContainer2 temp2; 
transform(temp1.begin(), temp1.end(), back_inserter(temp2), f2); 

TargetContainer target; 
transform(temp2.begin(), temp2.end(), back_inserter(target), f3); 

Esta primera solución no es óptima debido a la necesidad de espacio adicional con temp1 y temp2. Por lo tanto, vamos a ser más inteligentes con esto:

int f123(int n) { return f3(f2(f1(n))); } 
... 
SourceContainer source; 
TargetContainer target; 
transform(source.begin(), source.end(), back_inserter(target), f123); 

Esta segunda solución es mucho mejor porque no sólo el código es más simple pero más importante aún hay menos necesidad de espacio sin los cálculos intermedios.

Sin embargo, la composición f123 se debe determinar en tiempo de compilación y, por lo tanto, se fija en tiempo de ejecución.

¿Cómo trataré de hacer esto de manera eficiente si la composición se va a determinar en tiempo de ejecución? Por ejemplo, si este código estaba en un servicio RPC y la composición real, que puede ser cualquier permutación de cualquier subconjunto de f1, f2 y f3, se basa en argumentos de la llamada RPC.

Answer 1

EDITAR: Versión Trabajar en http://ideone.com/5GxnW. La siguiente versión tiene las ideas pero no compila. Admite la comprobación de tipos de tiempo de ejecución y la composición de la función de tiempo de ejecución.

La idea es definir una clase de función genérica (unaria) y una forma de componerlas con las comprobaciones de tipo de tiempo de ejecución. Esto se hace con una combinación de boost::any, boost::function y el tipo de borrado idiomático.

#include <boost/any.hpp> 
#include <boost/function.hpp> 
#include <boost/shared_ptr.hpp> 


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

struct any_function 
{ 
    template <typename Res, typename Arg> 
    any_function(boost::function<Res, Arg> f) 
    { 
     impl = make_impl(f); 
    } 

    boost::any operator()(const boost::any& x) 
    { 
     return impl->invoke(x); 
    } 

    static any_function compose(const any_function& f, 
           const any_function& g) 
    { 
     any_function ans; 
     ans.impl = compose_impl(f.impl, g.impl); 
     return ans; 
    } 

    template <typename T> 
    static any_function id() 
    { 
     using boost::function 
     return any_function(function<T(T)>(identity<T>())); 
    } 

    template <typename Res, typename Arg> 
    boost::function<Res(Arg)> to_function() 
    { 
     using boost::function; 
     return function<Res(Arg)>(to_function_helper(impl)); 
    } 

private: 
    any_function() {} 

    struct impl_type 
    { 
     virtual ~impl_type() {} 
     virtual boost::any invoke(const boost::any&) = 0; 
    }; 

    boost::shared_ptr<impl_type> impl; 

    template <typename Res, typename Arg> 
    static impl_type* make_impl(boost::function<Res(Arg)> f) 
    { 
     using boost::function; 
     using boost::any; 
     using boost::any_cast; 

     class impl : public impl_type 
     { 
      function<Res(Arg)> f; 

      any invoke(const any& x) 
      { 
       const Arg& a = any_cast<Arg>(x); 
       return any(f(a)); 
      } 

     public: 
      impl(function<Res(Arg)> f) : f(f) {} 
     }; 

     return new impl(f); 
    } 

    impl_type* compose_impl(boost::shared_ptr<impl_type> f, 
          boost::shared_ptr<impl_type> g) 
    { 
     using boost::any; 
     using boost::shared_ptr; 

     class impl : public impl_type 
     { 
      shared_ptr<impl> f, g; 

      any invoke(const any& x) 
      { 
       return g->invoke(f->invoke(x)); 
      } 

     public: 
      impl(const shared_ptr<impl>& f, 
       const shared_ptr<impl>& g) 
       : f(f), g(g) 
      {} 
     }; 

     return new impl(f, g); 
    } 

    struct to_function_helper 
    { 
     template <typename Res, typename Arg> 
     Res operator()(const Arg& x) 
     { 
      using boost::any; 
      using boost::any_cast; 

      return any_cast<Res>(p->invoke(any(x))); 
     } 

     to_function_helper(const boost::shared_ptr<impl>& p) : p(p) {} 

    private: 
     boost::shared_ptr<impl> p; 
    }; 
}; 

Ahora, vamos a usar algoritmos estándar y hacer esto (esto funciona incluso en secuencias vacías):

// First function passed is evaluated first. Feel free to change. 
template <typename Arg, typename Res, typename I> 
boost::function<Res(Arg)> pipeline(I begin, I end) 
{ 
    return std::accumulate(begin, end, 
     any_function::id<Arg>, 
     std::ptr_fun(any_function::compose) 
    ).to_function<Res, Arg>(); 
} 

y utilizar los siguientes aplicarlo

std::vector<any_function> f; 
std::vector<double> v; 
std::vector<int> result; 

std::transform(v.begin(), v.end(), 
    result.begin(), 
    pipeline<double, int>(f.begin(), f.end()) 
); 

Usted puede incluso utilizar boost::transform_iterator

typedef boost::transform_iterator< 
    boost::function<double, int>, 
    std::vector<double>::const_iterator 
> iterator; 

boost::function<double, int> f = pipeline<double, int>(f.begin(), f.end()); 
std::copy(iterator(v.begin(), f), iterator(v.end(), f), result.begin()); 

Answer 2

se debe utilizar un funtor en lugar de la función y pasar sea necesario transformar las funciones en el constructor del funtor

algo así como

typedef int (*FunctionType)(int); 

class Functor 
{ 
    FunctionType m_f1; 
    FunctionType m_f2; 
    FunctionType m_f3; 
public: 
    Functor(FunctionType f1, FunctionType f2, FunctionType f3): 
     m_f1(f1), m_f2(f2), m_f3(f3) 
    {} 
    int operator()(int n) 
    { 
     return (*m_f1)((*m_f2)((*m_f3)(n))); 
    } 
}; 

// ... 

transform(source.begin(), source.end(), back_inserter(temp1), Functor(f1,f2,f3)); 

si necesita número variable de funciones a continuación, cambie Functor firma constructora de usar vectores de funciones y llene ese vector antes de llamar a transformar.

Answer 3

template<class T> 
class compose { 
    typedef T (*f)(T); 

    f first_func; 
    f second_func; 

public: 

    compose(f one,f two) : 
     first_func(one), 
     second_func(two)   
    {} 

    T operator()(T const &input) { 
     T temp = first_func(input); 
     return second_func(temp); 
    } 
}; 

#ifdef TEST 

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

#include <iostream> 

int main(int argc, char **argv) { 
    compose<int> x(f, g); 
    compose<int> y(g, f); 

    std::cout << x(6) << std::endl; 
    std::cout << y(6) << std::endl; 

    typedef int (*func)(int); 

    func funcs[] = {f, g, h}; 

    compose<int> z(funcs[atoi(argv[1])], funcs[atoi(argv[2])]); 
    std::cout << z(6); 

    return 0; 
} 

#endif 

Con C++ 0x, debemos ser capaces de utilizar auto para eliminar tener que especificar el tipo de argumento/retorno. Por el momento, he supuesto que son lo mismo, aunque en teoría, es posible que le guste la posibilidad de incluir conversiones en la mezcla.

Answer 4

typedef int (*f_t)(int); 

int f1(int a) { return a + 1; } 
int f2(int a) { return a * 2; } 
int f3(int a) { return a * a; } 

int main() 
{ 
    std::vector<f_t> ff = {f1, f2, f3}; 
    std::vector<int> source = {1, 2, 3, 4}, target; 

    std::transform(source.begin(), source.end(), std::back_inserter(target) 
    , [&](int a) { for (f_t &f : ff) a = f(a); return a; }); 

    // print target 
    std::copy(target.begin(), target.end(), std::ostream_iterator<int,char>(std::cout,"\n")); 
    system("pause"); 
    return 0; 
} 

Answer 5

Sólo definir un iterador que hace lo que quiere:

template<typename T> 
struct source 
{ 
    virtual source<T>& operator++(void) = 0; 
    virtual T operator*(void) = 0; 
    virtual bool atend() = 0; 
}; 

struct source_exhausted 
{ 
}; 

template<typename T> 
bool operator==(const source<T>& comparand, const source_exhausted&) 
{ return comparand.atend(); } 

template<typename T> 
bool operator!=(const source<T>& comparand, const source_exhausted&) 
{ return !comparand.atend(); } 

template<typename T> 
bool operator==(const source_exhausted&, const source<T>& comparand) 
{ return comparand.atend(); } 

template<typename T> 
bool operator!=(const source_exhausted&, const source<T>& comparand) 
{ return !comparand.atend(); } 

template<typename T, typename iterT, typename endT> 
struct source_iterator : source<T> 
{ 
    iterT m_iter; 
    endT m_end; 
    source_iterator(iterT iter, endT end) : m_iter(iter), m_end(end) {} 

    virtual source<T>& operator++(void) { ++m_iter; return *this; } 
    virtual T operator*(void) { return *m_iter; } 
    virtual bool atend() { return m_iter == m_end; } 
}; 
template<typename T, typename iterT, typename endT> 
auto make_source_iterator(iterT iter, endT end) -> source_iterator<decltype(*iter), iterT, endT> 
{ 
    return source_iterator<decltype(*iter), iterT, endT>(iter, end); 
} 
template<typename TContainer> 
auto make_source_iterator(TContainer& c) -> source_iterator<typename TContainer::value_type, decltype(c.begin()), decltype(c.end())> 
{ 
    return source_iterator<typename TContainer::value_type, decltype(c.begin()), decltype(c.end())>(c.begin(), c.end()); 
} 

template<typename TIn, typename TOut, typename TXform> 
struct source_transformer : source<TOut> 
{ 
    source<TIn>& m_src; 
    TXform const m_f; 
    source_transformer(source<TIn>& src, TXform f) : m_f(f), m_src(src) {} 

    virtual source<TOut>& operator++(void) { ++m_src; return *this; } 
    virtual TOut operator*(void) { return m_f(*m_src); } 
    virtual bool atend() { return m_src.atend(); } 
}; 
template<typename TIn, typename TOut, typename TXform> 
auto make_source_transformer(source<TIn>& src, TXform f) -> source_transformer<TIn, decltype(f(*(TIn*)0)), TXform> 
{ 
    return source_transformer<TIn, decltype(f(*(TIn*)0)), TXform>(src, f); 
}