在基于概念的递归功能模板上扣除“自动"之前使用“自动" [英] Use of 'auto [...] 'before deduction of 'auto' with recursive, concept-based function template

问题描述

我想创建一个 deep_flatten 函数模板，该模板将产生一个 range 元素，这些元素被深 join 深度结合.例如，如果仅考虑嵌套的 std :: vector s，我可以拥有:

I wanted to create a deep_flatten function template that would produce a range of elements that are deeply joined. For example, if we take into account only nested std::vectors, I can have:

template <typename T>
struct is_vector : public std::false_type { };

template <typename T, typename A>
struct is_vector<std::vector<T, A>> : public std::true_type { };

template <typename T>
auto deepFlatten(const std::vector<std::vector<T>>& vec) {
    using namespace std::ranges;
    if constexpr (is_vector<T>::value) {
        auto range = vec | views::join;
        return deepFlatten(std::vector(range.begin(), range.end()));
    } else {
        auto range = vec | views::join;
        return std::vector(range.begin(), range.end());
    }
}

这使我能够做到:

std::vector<std::vector<std::vector<int>>> nested_vectors = {
        {{1, 2, 3}, {4, 5}, {6}},
        {{7},       {8, 9}, {10, 11, 12}},
        {{13}}
};

std::ranges::copy(
        deep_flatten(nested_vectors),
        std::ostream_iterator<int>(std::cout, " ")
);

会按预期将以下文本打印到控制台中:

which prints into the console the following text, as expected:

1 2 3 4 5 6 7 8 9 10 11 12 13

但是，我不太喜欢这种解决方案.它不仅效率低下(创建许多临时矢量)，而且还仅适用于 std :: vector s.我认为我可以使用更多的 c ++ 20 魔术，并使用 std :: ranges :: range 概念:

But, I don't like this solution that much. Not only it's inefficient (creating a number of temporary vectors), but it also works only with std::vectors. I figured that I could use some more of c++20 magic and use std::ranges::range concept:

namespace rng {
    template <std::ranges::range Rng>
    auto deep_flatten(Rng&& rng) {
        using namespace std::ranges;

        if constexpr (range<Rng>) {
            return deep_flatten(rng | views::join);
        } else {
            return rng | views::join;
        }
    }
}

在我看来，这很简单-我们有一个 std :: ranges :: range ，我们检查它的值类型.根据是否是嵌套范围，我们递归或简单地返回 join ed元素.

This seemed to me pretty straightforward - we have a std::ranges::range and we inspect it's value type. Depending on whether it's a nested range, we recurse or simply return joined elements.

可悲的是，它不起作用.尝试运行后:

Sadly, it doesn't work. After trying to run:

int main() {
    std::set<std::vector<std::list<int>>> nested_ranges = {
            {{1, 2, 3}, {4, 5}, {6}},
            {{7},       {8, 9}, {10, 11, 12}},
            {{13}}
    };

    std::ranges::copy(
            rng::deep_flatten(nested_ranges),
            std::ostream_iterator<int>(std::cout, " ")
    );
}

我收到一条错误消息:

In instantiation of 'auto rng::deep_flatten(Rng&&) [with Rng = std::ranges::join_view<std::ranges::ref_view<std::set<std::vector<std::__cxx11::list<int> > > > >]':
     required from 'auto rng::deep_flatten(Rng&&) [with Rng = std::set<std::vector<std::__cxx11::list<int> > >&]'
     required from here
     error: use of 'auto rng::deep_flatten(Rng&&) [with Rng = std::ranges::join_view<std::ranges::ref_view<std::set<std::vector<std::__cxx11::list<int> > > > >]' before deduction of 'auto'
     39 |             return deep_flatten(rng | views::join);
        |                    ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

在研究了类似的问题之后，我无法真正理解为什么错误出现在这里.

Having researched similar problems, I cannot really get why the error appears here.

我正在使用 gcc版本10.1.0(Rev3，由MSYS2项目构建)

推荐答案

这里有两个问题.

第一个问题是您的:

namespace rng {
    template <std::ranges::range Rng>
    auto deep_flatten(Rng&& rng) {
        using namespace std::ranges;

        if constexpr (range<Rng>) { // <==
            return deep_flatten(rng | views::join);
        } else {
            return rng | views::join;
        }
    }
}

此函数是无限递归的. deep_flatten 被约束为 range< Rng> ，因此 if constexpr 始终存在，因此我们永远不会输入基本情况.这只是一个错误-我们正在检查错误的内容，这不是我们是否在范围内，而是在我们的基础值是一个范围内.那是:

This function is infinitely recursive. deep_flatten is constrained range<Rng>, so the if constexpr check there is always going to be true, so we're never going to enter the base case. This is just a bug - we're checking the wrong thing, it's not if we're a range, it's if our underlying value is a range. That's:

namespace rng {
    template <typename Rng>
    auto deep_flatten(Rng&& rng) {
        using namespace std::ranges;

        auto joined = rng | views::join;    
        if constexpr (range<range_value_t<decltype(joined)>>) {
            return deep_flatten(joined);
        } else {
            return joined;
        }
    }
}

在这里，我们进入第二个问题，这是标准库的问题.什么 rng |views :: join 的意思是:

And here we get into the second problem, which is the standard library's problem. What rng | views::join means is:

名称 views :: join> 表示范围适配器对象([range.adaptor.object]).给定一个子表达式 E ，表达式 views :: join(E)等同于 join_view {E} .

The name views​::​join denotes a range adaptor object ([range.adaptor.object]). Given a subexpression E, the expression views​::​join(E) is expression-equivalent to join_­view{E}.

但是对于已经是 join_view 特化的 E 的 join_view {E} ...现在由于没有操作而无法操作类模板参数推导(CTAD)-副本推导候选者是最佳候选者，因此我们的嵌套 join 操作实际上成为单个 join .您最初的实现绕过了这个问题，因为它不是 join - join_view ，而是总是 join - vector

But join_view{E} for an E that's already a specialization of join_view... is a no-op right now because of class template argument deduction (CTAD) - the copy deduction candidate is the best candidate, so our nested join operation actually becomes a single join. Your original implementation gets around this problem because it's not join-ing a join_view, it's always join-ing vectors.

我已提交 LWG 3474 .

同时，我们可以通过直接使用 join_view 并明确指定模板参数来解决 views :: join 问题:

In the meantime, we can work around the views::join problem by just directly using join_view and specifying the template argument explicitly:

namespace rng {
    template <typename Rng>
    auto deep_flatten(Rng&& rng) {
        using namespace std::ranges;


        auto joined = join_view<views::all_t<Rng>>(rng);

        if constexpr (range<range_value_t<decltype(joined)>>) {
            return deep_flatten(joined);
        } else {
            return joined;
        }
    }
}

这有效.

这篇关于在基于概念的递归功能模板上扣除“自动"之前使用“自动"的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！