Использование 'auto [...]' перед вычетом 'auto' с рекурсивным шаблоном функции на основе концепций - PullRequest
Новая
       95

Использование 'auto [...]' перед вычетом 'auto' с рекурсивным шаблоном функции на основе концепций

8 голосов
/ 04 августа 2020

Я хотел создать шаблон функции deep_flatten, который производил бы range элементов, которые join очень редки. Например, если мы принимаем во внимание только вложенные std::vector s, я могу иметь: 

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, " ")
);

, который выводит в консоль следующее текст, как и ожидалось: 

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

Но , мне не очень нравится это решение. Это не только неэффективно (создает несколько временных векторов), но также работает только с std::vector s. Я подумал, что могу использовать еще немного magi c и использовать концепцию std::ranges::range: 

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 элементов.

К сожалению, это не работает. После попытки запустить: 

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);
        |                    ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Изучив аналогичные проблемы, я не могу понять, почему здесь появляется ошибка .

Я использую gcc version 10.1.0 (Rev3, Built by MSYS2 project)

1 Ответ

7 голосов
/ 04 августа 2020

Здесь две проблемы.

Первая проблема ваша: 

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 всегда будет истинной, поэтому мы никогда не будем вводить базовый случай. Это просто ошибка - мы проверяем не то, что не то, если мы диапазон, а если наше базовое значение является диапазоном. Это: 

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 означает:

Имя views​::​join обозначает объект адаптера диапазона ([range.adaptor.object]). Учитывая подвыражение E, выражение views​::​join(E) эквивалентно выражению join_­view{E}.

Но join_view{E} для E, которое уже является специализацией join_view ... сейчас не работает из-за вывода аргументов шаблона класса (CTAD) - кандидат на вывод копии является лучшим кандидатом, поэтому наша вложенная операция join фактически становится одной join. Ваша первоначальная реализация решает эту проблему, потому что это не join -ing a join_view, это всегда join -ing vector s.

Я отправил LWG 3474 .

Тем временем мы можем обойти проблему views::join, просто используя join_view и явно указав аргумент шаблона: 

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

Это работает.

...