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

Представление дубля, содержащее n элементов, имеет n + 1 допустимых значений итератора: n, которые соответствуют элементам в диапазоне, и n + 1st итератор за концом. Предполагается, что итерация по представлению Take обязательно формирует каждый из этих итераторов n + 1 — действительно, полезно извлечь базовое значение итератора, адаптированное итератором end представления Take для выполнения дополнительных вычислений.

take_view не знает, что диапазон, который он адаптирует, является фильтром или что ваш предикат фильтра чрезмерно дорог - он просто предполагает, что ваш предикат равен O(1), поскольку это необходимо для обеспечения O(1) операций итератора. (хотя мы забыли сделать это требование сложности явным в C++20.) случай является очень хорошим примером того, почему у нас есть требования к сложности: если итераторы адаптируемого диапазона не соответствуют требованиям стандарта к сложности O (1), представление не может соответствовать его гарантиям сложности, и рассуждения о производительности становятся невозможными.

Извинения:

Я (частично) отвечаю на свой вопрос, потому что я думаю, что понял, что здесь происходит, механически, и потому что дополнительные подробности не вписываются в комментарий. Я не уверен в этикете, поэтому, если это было бы лучше в качестве редактирования вопроса --- все еще остается открытым вопрос о том, почему библиотека разработана таким образом --- пожалуйста, предложите это в комментариях я с радостью перенесу его туда.

Фильтрация до тех пор, пока не будет найден конечный итератор

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

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