5

取自 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具体化，但这不是重点）。

我可以在这里看到两个选项：

  1. 这些操作由 range-v3融合rng，当通过某个迭代器访问给定的元素时，这两个操作因此应用于该元素。

  2. 当请求给定元素时，整个remove_if操作将被应用vi，然后该操作的输出向量被馈送到transform. 因此，我们最终得到了一个完整的“ trasformed + removed_if ”向量，它使我们能够访问所需的元素。

我很确定选项（1）是实际发生的事情。如果是这样的话，range-v3 是如何做到这一点的呢？它是否具有某种通用组合代码以组合无限数量的按视图组合操作？

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

range-algorithms元问题：如果选项（1）是事实，那么考虑到它们将一个简单的范围（由多个视图组成，通过操作融合按需计算）作为输入，并行化不是非常简单吗？

4

1 回答 1

2

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

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

为什么 C++ 范围“变换 - > 过滤器”为匹配过滤器谓词的值调用变换两次？

更多细节

关于使操作并行，它可能类似于 std 库实现，通过向每个 AST 节点添加一个标记参数来说明您是否要并行执行。有关详细信息，请参阅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 类库，它在功能上与 range-v3 有重叠。）

于 2021-04-23T05:32:17.783 回答