C++20 范围适配器的递归应用导致编译时无限循环

recursive application of C++20 range adaptor causes a compile time infinite loop

C++20 中的范围库支持表达式

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

使用范围适配器 drop.

删除范围 r 的前 n 个元素

但是,如果我递归地删除范围中的元素,编译器将进入无限循环。


最小工作示例:(在 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

为什么这需要无限的时间来编译,我应该如何解决这个问题?

让我们看一下 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 was about reducing this kind of template instantiation bloat (although it didn't have an example as amusing as this one). And so drop_view has a few special cases 可识别且不会重新包装的视图。 "hello"sv | views::drop(1) 的类型仍然是 string_view,而不是 drop_view<string_view>。所以 printCombinations(string_view(range2)) 应该只生成一个模板实例化。

但看起来 libstdc++ 还没有实现这个功能。因此,您可以手动实现它(但只能贩卖,比如 subrange),或者在这里放弃递归方法。