C++ 范围-v3 库 : 'take' -ing first 3 perfect numbers works and halts; 'take' -ing first 4 doesn't stop after 4

Question

据我了解，range-v3 库的 View 操作(目前需要 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))，但是因为 View 算法以 ranges::view::take 结束(3) 它应该在找到前三个数字通过过滤算法后停止(一种用于过滤完美数字的蛮力算法，故意不那么有效)。由于前三个完全数 --- 6、28 和 496 --- 相当小，我希望这段代码能够快速找到它们，并打印“DONE”。并终止。而这正是发生的事情:

coliru -- taking 3 perfect numbers works just fine

但是，假设我想打印前 4 个完全数，它们仍然非常小 --- 6、28、496 和 8128。在打印 8128 之后，程序不会停止，最终必须终止；据推测，它正在徒劳地尝试计算第五个完美数 33550336，这超出了这种蛮力算法有效查找的能力。

coliru -- taking 4 perfect numbers tries to take 5+

这对我来说似乎不一致。如果两个测试都失败了(结论是我误解了 range-v3 的 View 算法的懒惰评估)，我会理解的，但是 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。

wandbox link

Answer 1

包含 n 元素的 take View 具有 n + 1 有效迭代器值:n 对应于范围内的元素，并且n + 1st 尾后迭代器。旨在迭代 take View 必然形成那些 n + 1 迭代器中的每一个 - 实际上，提取由 take View 的 end 迭代器适配的底层迭代器值是有用的执行额外的计算。

take_view 不知道它正在调整的范围是一个过滤器，或者您的过滤器谓词非常昂贵 - 它只是假设您的谓词是 O(1)，因为它需要提供 O(1) 迭代器操作。 ( Although we did forget to make that complexity requirement explicit in C++20 。)这个案例很好地说明了为什么我们有复杂性要求:如果被适配范围的迭代器不满足标准的 O(1) 复杂性要求， View 就不能满足其复杂性保证并且关于性能的推理变得不可能。