Библиотека C++ range-v3: "взятие" первых 3 совершенных чисел работает и останавливается; "первые четыре" не останавливаются после 4

Question

Насколько я понимаю, операции просмотра библиотеки range-v3 (в настоящее время требуется C++17, но для того, чтобы стать официальной частью STL в C++20) предоставляют цепочечные 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". и прекратить. И это именно то, что происходит:

колиру - брать 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 элементы имеет n + 1 допустимые значения итератора: n которые соответствуют элементам в диапазоне, и n + 1Первый итератор прошлого. Предполагается, что повторение взгляда обязательно формирует каждый из этих n + 1 итераторы - действительно, полезно извлечь базовое значение итератора, адаптированное в представлении взятия 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_if Посмотреть. filter Предикат продолжает цикл ranges::view::ints(1) пока он не найдет тот, для которого возвращается предикат true; предположительно это становится конечным итератором, так как он не печатается в цикле for.

Простая демонстрация этого обеспечивается следующим кодом. Здесь есть два настраиваемых целых числа n а также mи предикатная функция в filter возвращает истину для 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 успехи, лямбда-предикат вызывается, пока не вернется true, Поскольку целое число, которое возвращает true, 9, не печатается, оно должно быть std::end(perfects) это нарушает дальний цикл.

Для меня остается загадкой, почему он это делает. Это не то, что я ожидал; это может привести к неожиданному поведению (например, если тело лямбда-функции не является чистым и изменяет захваченные объекты), и это может иметь большое влияние на производительность, как продемонстрировано в исходном примере, который должен был бы выполнить примерно 10^15 операций по модулю, прежде чем достичь целое число 33550336.