范围-v3视图组合和视图计算并行化

Question

下面的示例取自range-v3文档，演示了一个简单的views流水线组合，以生成一个range。

std::vector<int> const vi{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
using namespace ranges;
auto rng = vi | views::remove_if([](int i){return i % 2 == 1;})
              | views::transform([](int i){return std::to_string(i);});

我知道views::foo相当于类似于foo_view()的东西，因此上面的例子最后如下所示：

transform_view(remove_if_view(vi, <lambda>), <lambda>)

现在的问题是：

remove_if和transform操作的顺序是如何进行的？(我知道它们是懒惰的，它们实际上不是在这个步骤中计算出来的，而不是稍后rng实现时计算出来的，但这不是重点)。

我可以在这里看到两种选择：

当通过某个迭代器访问给定的consequently.元素时，这两个操作将应用于元素

1. 。

1. 当请求给定元素时，整个remove_if操作被应用于整个vi，然后将该操作的输出向量输入到transform中。因此，我们最终得到了一个完整的“转换+ removed_if”向量，它允许我们访问所需的元素.

。

我非常肯定的是，选项(1)是实际发生的事情。如果是这样的话，range-v3是如何实现的呢？它是否有某种通用的组合代码，以便将无限数量的按视图组合操作结合起来？

附带问题: range-v3视图公开了什么样的迭代器？我认为random-access迭代器下面的任何东西都会使并行化变得不可能。

元问题:如果选项(1)是事实，那么，如果将range-algorithms并行化难道不是非常简单的事情，因为它们接受一个简单的范围(由多个视图组成，按需计算和操作融合)？

Answer 1

如果我不得不猜测，那么我会说|操作符构建了一个操作的编译时AST (抽象语法树)。如果将该AST存储到一个名为range的变量中，然后调用auto it = std::begin(range)，则会实现一个迭代器，其类型将是非平凡的(除非使用类型擦除)。当您调用*it时，它计算所有转换操作，从取消引用原始迭代器的当前状态开始。当您调用++it时，它会稍微复杂一些。它需要做几件事。它需要提升基本迭代器，但也需要计算所有中间转换，以便可以计算remove_if中的谓词。如果谓词返回true，则在跳过项时，需要再次高级基迭代器。

如果将transform放在remove_if之前，这可能会导致管道效率低下。转换将对每个项进行两次评估。一次用于推进迭代器，另一次用于读取当前值。如果转换不是琐碎的，那么就会出现减速。如果转换有副作用，那么不好的事情就会发生。看见

Why C++ ranges "transform -> filter" calls transform twice for values that match the filter's predicate?

了解更多详细信息

关于使操作并行的问题，可能会通过向每个AST节点添加一个标记参数来实现类似于std库的实现，并说明是否要并行执行。有关详细信息，请参阅https://www.modernescpp.com/index.php/parallel-algorithm-of-the-standard-template-library

例如

vector<int> v = ...

// standard sequential sort
std::sort(v.begin(), v.end());

// sequential execution
std::sort(std::parallel::seq, v.begin(), v.end());

// permitting parallel execution
std::sort(std::parallel::par, v.begin(), v.end());

// permitting parallel and vectorized execution
std::sort(std::parallel::par_unseq, v.begin(), v.end());

这种模式可以扩展到range-v3，但实际上重载是新的实现，实现起来也不简单。

在这个主题的rangev3 github页面中有一个公开的问题，还有一些您可能感兴趣的其他链接。

https://github.com/ericniebler/range-v3/issues/921

(我不是range-v3的贡献者，但我实现了自己的范围，就像库一样，它的功能与range -v3有重叠。)