- A+

As I understand it, the range-v3 library's view operations (requires C++17 currently, but to become an official part of the STL in C++20) provides chainable STL-like algorithms that are lazily evaluated. As an experiment, I created the following code to evaluate the first 4 perfect numbers:

`#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; } `

The code starts with a possible infinite range of numbers (`ranges::view::ints(1)`

), but because the view algorithm ends with `ranges::view::take(3)`

it should halt after finding the first three numbers passing the filter algorithm (a brute-force algorithm to filter out perfect numbers, intentionally not that efficient). Since the first three perfect numbers --- 6, 28, and 496 --- are fairly small, I expect this code to quickly find these, print "DONE." and terminate. And that's exactly what happens:

coliru -- taking 3 perfect numbers works just fine

However, let's say I want to print the first 4 perfect numbers, which are still all fairly small --- 6, 28, 496, and 8128. After printing 8128 the program does not halt and eventually has to be terminated; presumably it is vainly trying to compute the fifth perfect number, 33550336, which is beyond the ability of this brute-force algorithm to efficiently find.

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

This seems inconsistent to me. I would have understood if both tests had failed (concluding that I had misunderstood the lazy evaluation of range-v3's view algorithms), but the fact that take(3) succeeds and halts while take(4) does not seems like a bug to me, unless I'm misunderstanding things.

I've tried this with several compilers on wandbox and it seems to be persistent (tried clang 6.0.1 and 7.0.0, g++ 8.1.0 and 8.2.0). At least on my local computer, where I found the issue originally, version 0.3.6 of range-v3 is being used, but I'm not sure about coliru and wandbox.

A take view that contains `n`

elements has `n + 1`

valid iterator values: `n`

that correspond to elements in the range, and the `n + 1`

st past-the-end iterator. It is intended that iterating over the take view necessarily forms each of those `n + 1`

iterators - indeed, it's useful to extract the underlying iterator value adapted by the take view's `end`

iterator to perform additional computations.

`take_view`

doesn't know that the range it's adapting is a filter, or that your filter predicate is inordinately expensive - it simply assumes that your predicate is O(1) as is necessary for it to provide O(1) iterator operations. (Although we did forget to make that complexity requirement explicit in C++20.) This case is a very good example of why we have complexity requirements: if the iterators of the range being adapted don't meet the Standard's O(1) complexity requirements, the view can't meet its complexity guarantees and reasoning about performance becomes impossible.