C++迭代器流水线设计

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--is基于来自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());