C++ range-v3库:'take'-ing前3个完美数字工作和停止; '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)它应该在找到通过过滤器算法的前三个数字后停止(一个强制算法来过滤掉完美数字,故意不那么有效) .由于前三个完美数字--- 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).至少在我最初发现问题的本地计算机上,使用了版本0.3.6的range-v3,但我不确定coliru和wandbox.

wandbox链接

Answer 1

包含n元素的take视图具有n + 1有效的迭代器值:n对应于范围中的元素,以及n + 1st past-the-end迭代器.迭代take视图必然会形成每个n + 1迭代器 - 实际上,提取由take视图的end迭代器调整的底层迭代器值以执行其他计算是有用的.

take_view我不知道它所适应的范围是一个过滤器,或者你的过滤谓词非常昂贵 - 它只是假设你的谓词是O(1),因为它提供O(1)迭代器操作是必要的.(虽然我们确实忘记在C++ 20中明确要求复杂性要求.)这种情况是我们为什么有复杂性要求的一个很好的例子:如果被调整的范围的迭代器不符合标准的O(1)复杂性要求,视图无法满足其复杂性保证和性能推理变得不可能.

Answer 2

道歉:

我(部分)回答了我自己的问题,因为我认为我已经从机械上了解了这里发生了什么,并且因为额外的细节不适合评论.我不确定这个礼节,所以如果这对问题的编辑会更好 - 那么仍然存在一个问题,就是为什么图书馆是这样设计的 - 请在评论中建议我会高兴地把它移到那里.

过滤直到找到结束迭代器

我不太了解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,会有特殊的逻辑使结果等于std::end(perfects),以便循环退出而不做任何额外的工作.但相反,从实现的角度来看,这是有道理的,结束迭代器实际上对应于filter/ remove_ifview 返回的下一个元素.该filter谓词不断遍历ranges::view::ints(1),直到它找到一个针对谓词的回报true; 大概这会成为结束迭代器,因为它不会在ranged for循环中打印.

以下代码提供了对此的简单演示.在这里,有两个可配置的整数n和m,并且在谓词函数filter返回true了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谓词直到它返回true.由于不会打印返回true的整数9,因此必须std::end(perfects)打破ranged for循环.

剩下的神秘之处在于它为什么会这样做.这不是我所期望的; 它可能会导致意外的行为(例如,如果lambda函数体不是纯粹的并且改变捕获的对象)并且它可能具有很大的性能影响,如原始示例所示,其必须在到达之前执行大约10 ^ 15个模运算.整数33550336.