有没有一种有效的方法可以在转换后使用views::filter？（范围适配器）

Question

奇怪行为的常见示例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）。演示

---

我们必须知道：

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

...只是语法糖：

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

---

问题解释：

实现了一些模拟版本后views::filter，问题似乎是：

• 与其他迭代器不同，它在（搜索可接受的值）filter::iterator期间工作operator ++
• operator *旨在提取值，但filter::iterator工作已经完成并丢失（我们不需要重新搜索可接受的值，但我们确实需要重新计算它）
• 由于视图的常量时间复制约束，我们无法存储结果（该值可以是数组）

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

view = container | Transform | Filter1 | Filter2 | Filter3

Pr(F3)（对丑陋的图表表示歉意）圆圈代表正在完成的工作Print F3（模拟示例中完成的工作）：

我们可以看到，如果我们仅组合过滤器或仅组合变换，那么我们就不会重复这项工作 - 问题在于变换上方有过滤器（图中上方）。

在最坏的情况下， 当我们期望时，我们会得到[其中n(x)数量x]：
n(iterations) = n(filters) * n(transforms)
n(filters) + n(transforms)

我们可以通过这个例子看到抛物线增长与线性增长。

---

问题

有时transform需要先做一些事情才能确定要做什么filter，那么如何避免额外的工作量呢？这似乎很重要，因为views它们旨在迭代容器，这是瓶颈领域。

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

Answer 1

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

从交替的过滤器和视图中，每个过滤器似乎都会构建其下方所有变换的列表，然后使用此变换列表来评估结果。所以修改你的例子

#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 来评估一切。现在我们有了结果。

请注意，这是根据观察得出的概念模型。我还没有搜索标准或代码来检查这一点，这只是示例中的显示方式。

您可以将其视为一棵树

G
|\
U U
|  \
F   \
|\   \
T T   T

每个过滤器都会产生一个分支，过滤器和变换在左侧，变换在右侧。我们评估每个过滤器节点的左侧，然后评估过滤器节点本身，然后评估每个过滤器节点的右侧分支。

复杂度正如你所说，O((n_filters+1)*n_transforms)。

我怀疑，如果您提供了 constexpr 作为转换，那么编译器可以将其优化为 的简单线性评估TFUG，因为它会发现每次评估的返回值都是相同的。然而，在转换中添加 std::cout 的行为意味着这不是 constexpr，因此这些优化无法发生。

因此，我怀疑这里发生的情况是，通过尝试显示 C++ 代码的结构，您已经停止了二进制代码中发生的优化。

当然，您可以通过创建 constexpr 转换并检查在打开优化的情况下增加视图层时运行时发生的情况来测试这一点。

编辑

我最初说过，我认为过滤器正在缓存转换列表，如果它们这样做，那么如果转换是 constexpr 那么它们可能会缓存这些传输的结果。经过反思和更多阅读，我认为过滤器根本没有缓存转换列表。他们在递增迭代器时评估每个分支的左侧，在解引用时评估右侧。

然而，我仍然认为通过 constexpr 转换，编译器可以有效地优化它。并且在不检查代码的情况下，也许过滤器可以进行缓存 - 我相信这里有人知道。所以我认为测试 constexpr 优化示例仍然有用。