C++ Iterator Pipelining Designs

Question

Supponiamo di voler applicare una serie di trasformazioni, int f1(int), int f2(int), int f3(int), a un elenco di oggetti. Un modo semplice sarebbe

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

Questo prima soluzione non è ottimale a causa del requisito di spazio extra con temp1 e temp2. Quindi, andiamo più intelligente con questo:

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

Questa seconda soluzione è molto meglio perché non solo il codice è più semplice ma ancora più importante c'è meno necessità di spazio senza i calcoli intermedi.

Tuttavia, la composizione f123 deve essere determinata al momento della compilazione e pertanto viene fissata in fase di esecuzione.

Come potrei provare a farlo in modo efficiente se la composizione deve essere determinata in fase di esecuzione? Ad esempio, se questo codice era in un servizio RPC e la composizione effettiva - che può essere una permutazione di qualsiasi sottoinsieme di f1, f2 e f3 - è basata su argomenti della chiamata RPC.

Answer 1

EDIT: versione Lavorare in http://ideone.com/5GxnW. La versione seguente ha le idee ma non viene compilata. Supporta il controllo del tipo di runtime e la composizione delle funzioni del tempo di esecuzione.

L'idea è di definire una classe di funzione generica (unaria) e un modo per comporli con verifiche del tipo di runtime. Questo viene fatto con una combinazione di boost::any, boost::function e l'idioma di cancellazione del tipo.

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

Ora, usiamo algoritmi standard e fare questo (questo funziona anche su sequenze vuote):

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

e utilizzare il seguente per applicarlo

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

È anche possibile utilizzare 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

si dovrebbe usare un funtore al posto di funzione e passare necessario trasformare le funzioni in costruttore di functor

qualcosa come

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

se avete bisogno di numero variabile di funzioni quindi modificare Functor firma costruttore da utilizzare vettore di funzioni e riempire quel vettore prima di chiamare la trasformazione.

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, dovremmo essere in grado di utilizzare auto per eliminare dover specificare il tipo di argomento/ritorno. Per il momento ho pensato che fossero uguali, anche se in teoria, ti potrebbe piacere la possibilità di includere le conversioni nel mix.

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

Proprio definiscono un iteratore che fa quello che si vuole:

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