C ++ Iterator Конвейерные проекты

Question

Предположим, мы хотим применить серию преобразований int f1(int), int f2(int), int f3(int) к списку объектов. Наивный путь был бы

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

Это первое решение не является оптимальным из-за необходимости дополнительного пространства для temp1 и temp2. Итак, давайте разберемся с этим:

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

Это второе решение намного лучше, потому что не только код проще, но и, что более важно, меньше промежуточного пространства без промежуточных вычислений.

Однако состав f123 должен быть определен во время компиляции и, следовательно, фиксирован во время выполнения.

Как бы я попытался сделать это эффективно, если состав будет определен во время выполнения? Например, если этот код находился в службе RPC, а фактическая композиция - которая может быть любой перестановкой любого подмножества f1, f2 и f3 - основана на аргументах вызова RPC.

Answer 1

РЕДАКТИРОВАТЬ : рабочая версия на http://ideone.com/5GxnW.Версия ниже имеет идеи, но не компилируется.Он поддерживает проверку типов во время выполнения и композицию функций во время выполнения.

Идея состоит в том, чтобы определить общий (унарный) класс функций и способ их составления с помощью проверок типов во время выполнения.Это делается с помощью комбинации boost::any, boost::function и идиомы стирания типа.

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

Теперь давайте используем стандартные алгоритмы и делаем это (это работает даже на пустых последовательностях):

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

и используйте следующее, чтобы применить его

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

Вы даже можете использовать 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

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

С C ++ 0x мы должны иметь возможность использовать auto, чтобы исключить необходимость указывать тип аргумента / возвращаемого значения.На данный момент я предположил, что они одинаковы, хотя в теории вам может понравиться возможность включать конверсии в микс.

Answer 3

вы должны использовать функтор вместо функции и передавать необходимые функции преобразования в конструктор функтора

что-то вроде

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

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

Answer 4

Просто определить итератор, который делает то, что вы хотите:

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

Answer 5

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