Библиотека C ++ range-v3: «взятие» первых 3 совершенных чисел работает и останавливается;«4» не останавливается после 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». и прекратить. И это именно то, что происходит:

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 элементов, имеет 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 for ranged.

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

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