8

据我了解，range-v3 库的视图操作（目前需要 C++17，但要成为 C++20 中 STL 的官方部分）提供了可链接的类似 STL 的算法，这些算法是延迟评估的。作为一个实验，我创建了以下代码来评估前 4 个完美数字：

#include <iostream>
#include <range/v3/all.hpp>

using namespace std;
int main(int argc, char *argv[]) {
    auto perfects = ranges::view::ints(1)
                    | ranges::view::filter([] (int x) {
                        int psum = 0;
                        for (int y = 1; y < x; ++y) {
                            if (x % y == 0) psum += y;
                        }
                        return x == psum;})
                    | ranges::view::take(3);
    std::cout << "PERFECT NUMBERS:" << std::endl;
    for (int z : perfects) {
        std::cout << z << std::endl;
    } 
    std::cout << "DONE." << std::endl;
}

代码以可能的无限数字范围ranges::view::ints(1)开始ranges::view::take(3)（ . 由于前三个完美数字 —— 6、28 和 496 —— 相当小，我希望这段代码能够快速找到它们，并打印“DONE”。并终止。这正是发生的事情：

coliru——取 3 个完美数字就可以了

但是，假设我想打印前 4 个完美数字，它们仍然很小—— 6、28、496 和 8128。打印 8128 后，程序并没有停止，最终不得不终止；大概它是徒劳地试图计算第五个完美数 33550336，这超出了这种蛮力算法有效找到的能力。

coliru -- 取 4 个完美数尝试取 5+

这对我来说似乎不一致。如果两个测试都失败了，我会理解的（结论是我误解了 range-v3 视图算法的惰性评估），但是 take(3) 成功并停止而 take(4) 对我来说似乎不是一个错误，除非我误解了事情。

我已经用 wandbox 上的几个编译器尝试过这个，它似乎是持久的（尝试过 clang 6.0.1 和 7.0.0，g++ 8.1.0 和 8.2.0）。至少在我最初发现问题的本地计算机上，使用的是 range-v3 的 0.3.6 版，但我不确定 coliru 和 wandbox。

魔杖盒链接

4

2 回答 2

9

包含n元素的视图具有n + 1有效的迭代器值：n对应于范围内的元素，以及n + 1st 结束后迭代器。它旨在迭代取景视图必然形成每个n + 1迭代器 - 实际上，提取由取景视图的end迭代器调整的底层迭代器值以执行额外的计算是有用的。

take_view不知道它正在适应的范围是一个过滤器，或者您的过滤器谓词非常昂贵 - 它只是假设您的谓词是 O(1) ，因为它是提供 O(1) 迭代器操作所必需的。（尽管我们确实忘记在 C++20 中明确说明复杂性要求。）这个案例是我们为什么有复杂性要求的一个很好的例子：如果正在适应的范围的迭代器不符合标准的 O(1)复杂性要求，视图不能满足其复杂性保证，并且对性能进行推理变得不可能。

于 2018-11-16T19:58:40.820 回答
5

道歉：

我（部分）回答了我自己的问题，因为我认为我已经从机械上了解到这里发生了什么，并且因为额外的细节不适合评论。我不确定礼节，所以如果这会更好地作为对问题的编辑——仍然有一个悬而未决的问题是为什么图书馆是这样设计的——请在评论中提出建议，我会很高兴把它移到那里。

过滤直到找到结束迭代器

我不太了解 range-v3 的内部细节，所以我可能没有完全正确的术语。简而言之，这里没有不一致的行为。当对(or )ranges::view::take的调用之后调用 to时，生成的视图对象必须在迭代期间的某个点设置结束迭代器以跳出 for 循环。如果我考虑过，我会想象基于范围的 for 循环仍然会扩展为类似ranges::view::filterranges::view::remove_if

for (auto it = std::begin(perfects); it != std::end(perfects); ++it) {
    ...
}

（顺便说一句，在我的示例中行为相同）并且在找到所需数量的元素后，在后续operator++调用开始时it，将有特殊逻辑使结果等于std::end(perfects)，因此循环退出时不会做任何额外的工作。但是，从实现的角度来看，这是有道理的，结束迭代器实际上对应于filter/remove_if视图返回的下一个元素。filter谓词不断循环，ranges::view::ints(1)直到找到谓词返回的那个true；大概这成为结束迭代器，因为它没有在范围 for 循环中打印。

下面的代码提供了一个简单的演示。这里，有两个可配置的整数n和m，其中的谓词函数对于、for和for都filter返回 true ：x <= nfalsen < x < n+mtruex >= m

#include <iostream>
#include <range/v3/all.hpp>

using namespace std;
int main(int,char**) {
    int n = 5;
    int m = 3;
    auto perfects = ranges::view::ints(1)
                    | ranges::view::filter([&n,&m] (int x) {
                        std::cout << "Checking " << x << "... ";
                        if (x <= n) {
                            return true;
                        } else if (x <= n + m) {
                            std::cout << std::endl;
                            return false;
                        }
                        return true;})
                    | ranges::view::take(n);
    std::cout << "First " << n << " numbers:" << std::endl;
    for (int z : perfects) {
        std::cout << " take it!" << std::endl;
    }
    std::cout << "DONE." << std::endl;
}

您可以在此处为不同的值运行此n代码m：wandbox。默认输出如下：

First 5 numbers:
Checking 1...  take it!
Checking 2...  take it!
Checking 3...  take it!
Checking 4...  take it!
Checking 5...  take it!
Checking 6... 
Checking 7... 
Checking 8... 
Checking 9... DONE.

（我没有重命名变量perfects；显然它不再是一组完美数字了）。即使在第一次n成功之后，也会调用 lambda 谓词，直到它返回true。由于返回 true 的整数 9 没有被打印出来，它必须是std::end(perfects)打破范围 for 循环的那个。

对我来说剩下的谜团是它为什么这样做。这不是我所期望的。它可能导致意外的行为（例如，如果 lambda 函数体不是纯的并改变捕获的对象）并且它可能会产生很大的性能影响，如原始示例所示，它必须执行大约 10^15 模运算才能达到整数 33550336。

于 2018-11-16T19:47:24.653 回答