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

  • A+
Category:Languages

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.

wandbox link

 


A take view that contains n elements has n + 1 valid iterator values: n that correspond to elements in the range, and the n + 1st 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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: