c++ - 有没有一种在转换后使用 views::filter 的有效方法？ (范围适配器)

<分区>

views::filter 的奇怪行为的常见示例:

#include <iostream>
#include <ranges>
#include <vector>

int main ()
{
    using namespace std;

    auto ml = [](char c) // ml = make lambda (always accepts / transforms to 1)
    {
        return [c](int) {cout << c; return 1;};
    };

    vector<int> vec = {1};
    
    auto view = vec
        | views::transform  (ml('T'))
        | views::filter     (ml('F'));
    
    // use view somehow:
    return *view.begin();
}

输出TFT(注意额外的T)。 demo

我们必须知道:

auto view = vec
    | views::transform  (ml('A'))
    | views::filter     (ml('B'));

...只是语法糖:

auto view = views::filter(views::transform(vec, ml('A')), ml('B'));

问题解释:

实现了一些mock versions views::filter 的问题似乎是:

与其他迭代器不同，filter::iterator 在 operator++ 期间工作(搜索可接受的值)
operator * 旨在提取值，但使用 filter::iterator 工作已经完成并丢失(我们不需要重新搜索一个可接受的值，但我们确实需要重新计算它)
由于 constant-time copy constraint，我们无法存储结果对于 View (值可以是一个数组)

为了在图片中解释这一点，我们将展示迭代的过程:

view = container | Transform | Filter1 | Filter2 | Filter3

(为丑陋的图表道歉)圆圈代表正在为 Print F3 完成的工作 Pr(F3)(在模拟示例中完成的工作):

我们可以看到，如果我们只组合过滤器或只组合转换，那么我们就不会重复这项工作 - 问题在于过滤器位于转换上方(图中上方)。

在最坏的情况下，我们得到 [where n(x) number of x]:
n(迭代)= n(过滤器)* n(转换)
当我们期望 n(filters) + n(transforms)

我们可以通过 this example 看到这种抛物线与线性增长.

问题

有时需要先完成transform，然后才能确定要filter 的内容，那么如何避免额外的工作量呢？这似乎很重要，因为 View 旨在迭代容器，这是瓶颈领域。

有没有办法在这种情况下使用 std::views 而不会出现上述巨大的减速？

最佳答案

我认为考虑这一点的一个好方法是过滤器需要获取其输入的值才能决定是否执行过滤。然后当你评估过滤器的输出时，我们必须再次评估，除非过滤器已经缓存了输入(见下文)。

从交替的过滤器和 View 来看，似乎每个过滤器都构建了一个包含其下方所有转换的列表，然后使用此转换列表来评估结果。所以修改你的例子

#include <iostream>
#include <ranges>
#include <vector>

int main()
{

    auto ml = [](char c) // ml = make lambda (always accepts / transforms to 1)
    {
        return [c](int) {std::cout << c; return 1; };
    };

    std::vector<int> vec = { 1,1,1 };
    auto view = vec
        | std::views::transform(ml('T'))
        | std::views::filter(ml('F'))
        | std::views::transform(ml('U'))
        | std::views::filter(ml('G'));

    for( auto v : view)
        std::cout << v << ",";

    return 0;
}

给出输出

TFTUGTU1,TFTUGTU1,TFTUGTU1,

我们想要获取输入，然后进行变换 T、过滤 F、变换 U、过滤 G。因此我们可能已经得到预期的输出 TFUG1。然而，这似乎是发生了什么

过滤器 G 需要知道该值是否已经被过滤，并且需要知道元素值才能知道它是否应该自己进行任何过滤。所以它将这个返回链传递到下一个过滤器 - F。

过滤器 F 需要知道它是否需要过滤，因此它评估转换 T，然后进行过滤并发现它可以传递值，因此它将 T 添加到它的转换列表中。

G 现在可以决定是否需要过滤。它使用 F 的变换列表(仅包括 T)以及 F 和 G 之间的任何变换来评估输入。因此我们称变换为 T 和 U。

G 现在进行过滤并发现它可以传递值。所以它将下面的所有转换添加到它的转换列表中，这个列表现在是 T 和 U。

最后我们想要这个值，所以 G 通过调用它的转换列表 T 和 U 来评估所有东西。我们现在有了结果。

请注意，这是一个来自观察的概念模型。我没有搜索标准或代码来检查这一点，它只是示例中的样子。

你可以把它看成一棵树