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的情况（只是因为该类型较短），然后手动检查调用堆栈。

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对于可识别且不会重新包装的视图具有一些special cases。"hello"sv | views::drop(1)的类型仍然是string_view，而不是drop_view<string_view>。因此，printCombinations(string_view(range2))应该只生成一个模板实例。

但是看来libstdc ++尚未实现此功能。因此，您可以手动实现它（但只能进行交易，例如subrange），也可以在此处放弃递归方法。