8

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

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

使用范围适配器删除n范围的第一个元素。rdrop

但是，如果我递归地从一个范围中删除元素，编译器会进入一个无限循环。

最小的工作示例：（在 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

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

4

1 回答 1

8

让我们看一下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有一些特殊情况。的类型"hello"sv | views::drop(1)仍然是string_view，不是drop_view<string_view>。所以printCombinations(string_view(range2))应该只生成一个模板实例化。

但看起来 libstdc++ 还没有实现这个功能。因此，您可以手动实现它（但只能进行交易，比如说，subrange）或放弃这里的递归方法。

于 2020-05-18T12:31:15.360 回答