c++ - 根据运行时决策组合不同的迭代器

Question

我有一个算法，给定任意数量的 vector 运行一个特定的算法并返回结果。

可以从输入文件中读取 vector ，其中包含以 csv 格式表示 vector 的行，或者用户可以指定正整数(大于 2)n、k、m，程序将生成 n 个 vector ，其中每个 k 坐标随机分布在[0,m-1]范围内。

用户可以在可应用于每个 vector 的多个函数之间进行选择，例如将每个函数乘以标量、对每个元素应用模数、将第 N 个坐标归零等。

我考虑的解决方案是像标准算法一样使用迭代器(例如 std::copy)

template<class InputIt>
int my_transform(InputIt begin, InputIt end){
    // ... stuff from begin to end
    return result;
}

虽然它在我使用 std::istream_iterator 时有效作为参数，我非常有信心我会使用 boost::function_input_iterator对于生成的值和 boost::transform_iterator要应用所需的功能，我不太确定如何根据用户输入在运行时进行这些组合。

我可以在执行 my_transform 之前聚合所有用户输入，但是我如何将它应用到生成的迭代器上，因为它可以是 std::istream_iterator 中的任何内容到 boost::transform_iterator 还是 boost::function_input_iterator？

附言:

• 如标签中所述，我正在研究 VS13，因此解决方案应该与其兼容。
• 迭代不止一次不是一种选择，因为这些文件可能会变得非常大。

Answer 1

我想你想要 Boost Range 的

• join
• 和 any_range(基于 any_terator)

或者，您可以重新设计算法以默认在“流”模式下工作，并动态写入输出迭代器。

更新一个演示程序

下面的示例演示了如何连接(不同类型的)输入范围的任意组合，然后对其组合元素应用任意序列的转换函数。

主程序如下:

int main(int argc, char const** argv) {
    using InIt = std::istream_iterator<int>;

    if (argc!=4) return 255;
    std::ifstream f1(argv[1]), f2(argv[2]), f3(argv[3]);

    auto r1 = boost::make_iterator_range(InIt(f1), {}),
         r2 = boost::make_iterator_range(InIt(f2), {}),
         r3 = boost::make_iterator_range(InIt(f3), {});    
    auto r4 = boost::make_iterator_range(boost::make_function_input_iterator(r10gen_, 0), { r10gen_, 10 });

    srand(time(0));
    for (int i : random_compose_input(r1,r2,r3,r4) 
               | transformed(random_transform(
                    [](int i) { return i/3; },
                    [](int i) { return -4*i; },
                    [](int i) { return 100+i; },
                    [](int i) { return sqrt(abs(i)); }
                 ))
        )
    { 
        std::cout << i << " ";
    }
}

其中函数 random_compose_input 和 random_transform 执行输入范围和转换​​函数的运行时选择。

random_compose_input 返回一个 any_range，它包装了所选组合的连接范围的推导类型:

/////////////////////////////////////////////
// runtime composition of any input ranges
using AnyR = boost::any_range<int const, boost::single_pass_traversal_tag, int>;

template <typename R1, typename R2, typename R3, typename R4>
    AnyR random_compose_input(R1 const& r1, R2 const& r2, R3 const& r3, R4 const& r4) 
{
    int select = rand()%16;
    std::cout << "selected inputs " << std::showbase << std::hex << select << std::dec << "\n";
    switch(select) {
        case  0:
            static int const* dummy = nullptr;
            return boost::make_iterator_range(dummy, dummy);
        case  1: return multi_join(r1            );
        case  2: return multi_join(    r2        );
        case  3: return multi_join(r1, r2        );
        case  4: return multi_join(        r3    );
        case  5: return multi_join(r1,     r3    );
        case  6: return multi_join(    r2, r3    );
        case  7: return multi_join(r1, r2, r3    );
        case  8: return multi_join(            r4);
        case  9: return multi_join(r1,         r4);
        case 10: return multi_join(    r2,     r4);
        case 11: return multi_join(r1, r2,     r4);
        case 12: return multi_join(        r3, r4);
        case 13: return multi_join(r1,     r3, r4);
        case 14: return multi_join(    r2, r3, r4);
        case 15: return multi_join(r1, r2, r3, r4);
    }
    throw "oops";
}

注意 multi_join 是 join 出现的地方。请参阅完整的程序 list ，了解使用可变函数模板的(直接)实现。

而 random_transform 组合恰好是 boost::function<int(int)> :

/////////////////////////////////////////////
// random composition of transformation
using Xfrm = boost::function<int(int)>;

template <typename F1, typename F2, typename F3, typename F4>
    Xfrm random_transform(F1 const& f1, F2 const& f2, F3 const& f3, F4 const& f4) 
{
    int select = rand()%16;
    std::cout << "selected transforms " << std::showbase << std::hex << select << std::dec << "\n";
    switch(select) {
        case  0: return [=](int i){ return   (  (  (  (i)))); };
        case  1: return [=](int i){ return   (  (  (f1(i)))); };
        case  2: return [=](int i){ return   (  (f2(  (i)))); };
        case  3: return [=](int i){ return   (  (f2(f1(i)))); };
        case  4: return [=](int i){ return   (f3(  (  (i)))); };
        case  5: return [=](int i){ return   (f3(  (f1(i)))); };
        case  6: return [=](int i){ return   (f3(f2(  (i)))); };
        case  7: return [=](int i){ return   (f3(f2(f1(i)))); };
        case  8: return [=](int i){ return f4(  (  (  (i)))); };
        case  9: return [=](int i){ return f4(  (  (f1(i)))); };
        case 10: return [=](int i){ return f4(  (f2(  (i)))); };
        case 11: return [=](int i){ return f4(  (f2(f1(i)))); };
        case 12: return [=](int i){ return f4(f3(  (  (i)))); };
        case 13: return [=](int i){ return f4(f3(  (f1(i)))); };
        case 14: return [=](int i){ return f4(f3(f2(  (i)))); };
        case 15: return [=](int i){ return f4(f3(f2(f1(i)))); };
    }
    throw "oops";
}

对于示例，我硬编码了 4 个输入范围和 4 个潜在的转换步骤。

• 这会产生高效的代码。

• 但如果您愿意，您总是可以从“空白”AnyR 或 boost::function<int(int)> 开始:

   boost::function<int(int)> xfrm = [](int i){return i;};
  
   while (std::getline(std::cin, line))
   {
       if      (line == "+2") xfrm = [=](int i) { return xfrm(i) + 2 };
       else if (line == "-2") xfrm = [=](int i) { return xfrm(i) - 2 };
       else if (line == "*2") xfrm = [=](int i) { return xfrm(i) * 2 };
       else if (line == "/2") xfrm = [=](int i) { return xfrm(i) / 2 };
   }
  

  (请注意行为与静态已知 lambda 的组成的细微差别:lambda 具有推导的返回类型(例如，执行 double 的返回类型为 sqrt(abs(i)))，并保持该类型。由于 boost::function 删除了此信息，它在转换序列中的每一步都隐含地强制转换为 int。)

警告:2 个库错误

这里有两个库错误:

1. this bug 分辨率为 in comment#2 in the tracker

2. 另一个我不知道的错误，其中 any_iterator 无法在不添加构造函数重载的情况下包装 function_input_iterator:

   function_input_iterator(base_type const& b) : base_type(b) {};
   

   这是因为在某些时候 any_iterator 继续仅使用基类(这可能会在 function_input_iterator 库中修复。

完整代码

由于上面提到的错误，它不能完全在 Coliru 上运行，但这里有一个完整的程序，可以在我的 GCC 和 clang 安装上以 c++11 模式编译:

Live On Coliru

#include <boost/function.hpp>
#include <boost/range.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/any_range.hpp>
#include <boost/range/join.hpp>
#include <boost/iterator/function_input_iterator.hpp>

using namespace boost::adaptors;

#include <iostream>
#include <fstream>
#include <vector>

/////////////////////////////////////////////
// multi_join utility
namespace detail {
    struct multi_join_dispatch {
        template <typename R1> static R1 call(R1&& r1) 
            { return std::forward<R1>(r1); }

        template <typename R1, typename... Rs> static auto call(R1&& r1, Rs&&... ranges) 
            -> decltype(boost::range::join(std::forward<R1>(r1), call(std::forward<Rs>(ranges)...)))
            { return boost::range::join(std::forward<R1>(r1), call(std::forward<Rs>(ranges)...)); }
    };
}

template <typename... Rs> auto multi_join(Rs&&... ranges) 
    -> decltype(detail::multi_join_dispatch::call(std::forward<Rs>(ranges)...))
    { return detail::multi_join_dispatch::call(std::forward<Rs>(ranges)...); }

/////////////////////////////////////////////
// generate random numbers [0..9]
struct r10gen {
    typedef int result_type;
    int operator()() const { return rand()%10; } 
} static r10gen_;

/////////////////////////////////////////////
// runtime composition of any input ranges
using AnyR = boost::any_range<int const, boost::single_pass_traversal_tag, int>;

template <typename R1, typename R2, typename R3, typename R4>
    AnyR random_compose_input(R1 const& r1, R2 const& r2, R3 const& r3, R4 const& r4) 
{
    int select = rand()%16;
    std::cout << "selected inputs " << std::showbase << std::hex << select << std::dec << "\n";
    switch(select) {
        case  0:
            static int const* dummy = nullptr;
            return boost::make_iterator_range(dummy, dummy);
        case  1: return multi_join(r1            );
        case  2: return multi_join(    r2        );
        case  3: return multi_join(r1, r2        );
        case  4: return multi_join(        r3    );
        case  5: return multi_join(r1,     r3    );
        case  6: return multi_join(    r2, r3    );
        case  7: return multi_join(r1, r2, r3    );
        case  8: return multi_join(            r4);
        case  9: return multi_join(r1,         r4);
        case 10: return multi_join(    r2,     r4);
        case 11: return multi_join(r1, r2,     r4);
        case 12: return multi_join(        r3, r4);
        case 13: return multi_join(r1,     r3, r4);
        case 14: return multi_join(    r2, r3, r4);
        case 15: return multi_join(r1, r2, r3, r4);
    }
    throw "oops";
}

/////////////////////////////////////////////
// random composition of transformation
using Xfrm = boost::function<int(int)>;

template <typename F1, typename F2, typename F3, typename F4>
    Xfrm random_transform(F1 const& f1, F2 const& f2, F3 const& f3, F4 const& f4) 
{
    int select = rand()%16;
    std::cout << "selected transforms " << std::showbase << std::hex << select << std::dec << "\n";
    switch(select) {
        case  0: return [=](int i){ return   (  (  (  (i)))); };
        case  1: return [=](int i){ return   (  (  (f1(i)))); };
        case  2: return [=](int i){ return   (  (f2(  (i)))); };
        case  3: return [=](int i){ return   (  (f2(f1(i)))); };
        case  4: return [=](int i){ return   (f3(  (  (i)))); };
        case  5: return [=](int i){ return   (f3(  (f1(i)))); };
        case  6: return [=](int i){ return   (f3(f2(  (i)))); };
        case  7: return [=](int i){ return   (f3(f2(f1(i)))); };
        case  8: return [=](int i){ return f4(  (  (  (i)))); };
        case  9: return [=](int i){ return f4(  (  (f1(i)))); };
        case 10: return [=](int i){ return f4(  (f2(  (i)))); };
        case 11: return [=](int i){ return f4(  (f2(f1(i)))); };
        case 12: return [=](int i){ return f4(f3(  (  (i)))); };
        case 13: return [=](int i){ return f4(f3(  (f1(i)))); };
        case 14: return [=](int i){ return f4(f3(f2(  (i)))); };
        case 15: return [=](int i){ return f4(f3(f2(f1(i)))); };
    }
    throw "oops";
}

int main(int argc, char const** argv) {
    using InIt = std::istream_iterator<int>;

    if (argc!=4) return 255;
    std::ifstream f1(argv[1]), f2(argv[2]), f3(argv[3]);

    auto r1 = boost::make_iterator_range(InIt(f1), {}),
         r2 = boost::make_iterator_range(InIt(f2), {}),
         r3 = boost::make_iterator_range(InIt(f3), {});

    auto fi_b = boost::make_function_input_iterator(r10gen_, 0);
    auto fi_l = boost::make_function_input_iterator(r10gen_, 10);
    auto r4 = boost::make_iterator_range(fi_b, fi_l);

    srand(time(0));
    for (int i : random_compose_input(r1,r2,r3,r4) 
               | transformed(random_transform(
                    [](int i) { return i/3; },
                    [](int i) { return -4*i; },
                    [](int i) { return 100+i; },
                    [](int i) { return sqrt(abs(i)); }
                 ))
        )
    { 
        std::cout << i << " ";
    }
}

当我用例如运行它时

watch ./test <(echo {100..110}) <(echo {200..220}) <(echo {300..330})

典型的输出是

selected transforms 0x3
selected inputs 0x2
-264 -268 -268 -268 -272 -272 -272 -276 -276 -276 -280 -280 -280 -284 -284 -284 -288 -288 -288 -292 -292

或者，例如

selected transforms 0x1
selected inputs 0x8
0 0 2 2 0 1 2 1 1 2