рекурсивное применение адаптера диапазона C++20 вызывает бесконечный цикл времени компиляции

Question

Библиотека диапазонов в C++20 поддерживает выражение

auto view = r | std::views::drop(n);

убрать первый n элементы диапазона r с адаптером диапазона drop.

Однако, если я рекурсивно отбрасываю элементы из диапазона, компилятор входит в бесконечный цикл.

---

Минимальный рабочий пример: (требуется бесконечное время для компиляции в GCC 10)

#include <ranges>
#include <iostream>
#include <array>
#include <string>

using namespace std;

template<ranges::range T>
void printCombinations(T values) {
    if(values.empty())
        return;

    auto tail = values | views::drop(1);

    for(auto val : tail)
        cout << values.front() << " " << val << endl;

    printCombinations(tail);
}

int main() {
    auto range1 = array<int, 4> { 1, 2, 3, 4 };
    printCombinations(range1);
    cout << endl;

    string range2 = "abc";
    printCombinations(range2);
    cout << endl;
}

ожидаемый результат:

1 2
1 3
1 4
2 3
2 4
3 4

a b
a c
b c

Почему для компиляции требуется бесконечное время и как мне решить проблему?

Answer 1

Давайте посмотрим на string case (просто потому, что этот тип короче) и вручную проверьте стек вызовов.

printCombinations(range2) звонки printCombinations<string>. Функция рекурсивно вызывает себя сtail. Какой типtail? Этоdrop_view<ref_view<string>>. Итак, мы называемprintCombinations<drop_view<ref_view<string>>>. Пока все просто.

Теперь мы снова рекурсивно вызываем себя с помощью tail. Какой типtail сейчас? Ну что ж, просто заворачиваем. Этоdrop_view<drop_view<ref_view<string>>>. И затем мы снова возвращаемся сdrop_view<drop_view<drop_view<ref_view<string>>>>. И затем мы снова возвращаемся сdrop_view<drop_view<drop_view<drop_view<ref_view<string>>>>>. И так до бесконечности, пока компилятор не взорвется.

Можем ли мы исправить это, сохранив тот же алгоритм? На самом деле да. P1739 был о сокращении такого рода раздувания экземпляров шаблонов (хотя у него не было такого забавного примера, как этот). И другиеdrop_viewимеет несколько особых случаев для представлений, которые он распознает и не переносит заново. Тип"hello"sv | views::drop(1) все еще string_viewне drop_view<string_view>. ТакprintCombinations(string_view(range2)) должен генерировать только один экземпляр шаблона.

Но похоже, что libstdC++ еще не реализует эту функцию. Таким образом, вы можете реализовать его вручную (но только торговлю, скажем, subrange) или отказаться от рекурсивного подхода.

Answer 2

Хотя это очень старый вопрос, но сегодня я столкнулся с этой досадной ошибкой/(или функцией), и именно так я решил ее без особых изменений в исходном коде.

      #include <ranges>
#include <iostream>
#include <array>
#include <string>
#include <span>   /////// <------ added this

using namespace std;

template<ranges::range T>
void printCombinations(T values_) {  // <--- Changed values to values_
    auto values = std::span(values_);  // <--- defined values here
    if(values.empty())
        return;

    auto tail = values | views::drop(1);

    for(auto val : tail)
        cout << values.front() << " " << val << endl;

    printCombinations(tail);
}

int main() {
    auto range1 = array<int, 4> { 1, 2, 3, 4 };
    printCombinations(range1);
    cout << endl;

    string range2 = "abc";
    printCombinations(range2);
    cout << endl;
}

Создавая диапазон, мы делаем переменную простоspanвместо глубоко вложенныхtypenames, как показано в принятом ответе.

Вы можете проверить это здесь, на goldbolt , что он работает именно так, как ожидалось.

ОБНОВЛЕНИЕ: вы можете заменить использование наstd::ranges::subrangeи это покроет еще больше случаев. Например,std::spanне работает сstd::ranges::views::reverse.