C++ range-v3 库：'take'-ing 前 3 个完美数字工作并停止； 'take'-ing 前 4 不会在 4 后停止

Question

据我所知，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) 结束，所以它应该在找到前三个数字通过过滤算法后停止 (a蛮力算法来过滤掉完美的数字，故意不那么有效）。由于前三个完全数 --- 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 的视图算法的懒惰评估），我会理解的，但是 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

道歉：

我正在（部分地）回答我自己的问题，因为我认为我已经机械地了解了这里发生的事情，并且因为额外的细节不适合评论。我不确定礼节，所以如果这作为对问题的编辑会更好 --- 仍然存在 为什么 库是这样设计的悬而未决的问题 ---请在评论中提出建议，我会很乐意将其移至那里。

过滤直到找到结束迭代器

我不太了解 range-v3 的内部结构，所以我的术语可能不太正确。简而言之，这里没有不一致的行为。当对 ranges::view::take 的调用跟随对 ranges::view::filter（或 ranges::view::remove_if）的调用时，生成的视图对象必须在迭代期间的某个时刻设置结束迭代器以跳出 for 循环.如果我考虑一下，我会想象基于范围的 for 循环仍然会扩展为

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

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

下面的代码提供了一个简单的演示。这里，有两个可配置的整数n和m，filter中的谓词函数returns为x <= n，false为n < x < n+m，以及 true 对于 x >= 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 谓词也会被调用，直到它 returns true。由于 returns true 的整数 9 没有被打印出来，所以一定是 std::end(perfects) 打破了范围 for 循环。

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

Answer 2

包含 n 个元素的视图具有 n + 1 个有效的迭代器值：n 对应于范围内的元素，以及第 n + 1 个过去-结束迭代器。旨在迭代 take 视图必然形成每个 n + 1 迭代器 - 实际上，提取由 take 视图的 end 迭代器适配的基础迭代器值以执行额外计算是有用的。

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

C++ range-v3 库：'take'-ing 前 3 个完美数字工作并停止； 'take'-ing 前 4 不会在 4 后停止

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

c++

lazy-evaluation

range-v3

c++17