8

The ranges library in C++20 supports the expression

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

to remove the first n elements of a range r with the range adaptor drop.

However if I recursively drop elements from a range, the compiler enters an infinite loop.


Minimal working example: (takes infinite time to compile in 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;
}

expected output:

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

a b
a c
b c

Why does this take infinite time to compile and how should I resolve the problem?

0

2 Answers 2

8

Let's take a look at the string case (just because that type is shorter) and manually examine the call stack.

printCombinations(range2) calls printCombinations<string>. The function recursively calls itself with tail. What's the type of tail? That's drop_view<ref_view<string>>. So we call printCombinations<drop_view<ref_view<string>>>. Straightforward so far.

Now, we again recursively call ourselves with tail. What's the type of tail now? Well, we just wrap. It's drop_view<drop_view<ref_view<string>>>. And then we recurse again with drop_view<drop_view<drop_view<ref_view<string>>>>. And then we recurse again with drop_view<drop_view<drop_view<drop_view<ref_view<string>>>>>. And so forth, infinitely, until the compiler explodes.

Can we fix this by maintaining the same algorithm? Actually, yes. 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 for views that it recognizes and won't rewrap. The type of "hello"sv | views::drop(1) is still string_view, not drop_view<string_view>. So printCombinations(string_view(range2)) should only generate a single template instantiation.

But it looks like libstdc++ doesn't implement this feature yet. So you can either implement it manually (but only trafficking in, say, subrange) or abandon the recursive approach here.

3
  • Is there a way to implement the values.empty() base case using a more specific template? Something like template<range::empty_range T> void printCombination(T values) {}? If such a template is allowed it could terminate the recursion. May 18, 2020 at 12:46
  • 1
    @ProgrammierPatrick The size of these ranges is a runtime property, so no.
    – Barry
    May 18, 2020 at 12:49
  • Makes sense. Thank you for your help May 18, 2020 at 12:52
1

Although this is very old question, but I came across this annoying bug/(or maybe feature) today, and this is how I solved it without much change to the original code.

#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;
}

By creating span, we make the typename of the variable simply span instead of deeply nested typenames as shown in the accepted answer.

You can check it here on goldbolt that it works exactly as expected.

UPDATE: You can replace the use of std::span with std::ranges::subrange and it will cover even more cases. For example, std::span does not work with std::ranges::views::reverse.

2
  • 1
    Thanks for mentioning std::ranges::subrange, this seems to be the best solution for the problem. I haven't used ranges since. Would you keep the general template <range T> void printCombinations(T values), or would is make more sense to expose the subrange directly as the parameter as template <class T> void printCombinations(subrange<T> values)? Dec 7, 2022 at 16:15
  • @ProgrammierPatrick I'm sorry I don't know it myself. Similar to you, I also do not have much experience of using ranges. Dec 8, 2022 at 8:21

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.