Можно ли сопоставить рекурсивно целочисленные параметры шаблона в C ++? - PullRequest
Новая
       39

Можно ли сопоставить рекурсивно целочисленные параметры шаблона в C ++?

8 голосов
/ 29 января 2020

У меня следующая проблема. Я определяю N-мерный вектор следующим образом: 

#include <vector>
#include <utility>
#include <string>


template <int N, typename T>
struct NVector{
    typedef std::vector<typename NVector<N-1,T>::type> type;
};
template <typename T> struct NVector<1,T> {
    typedef std::vector<T> type;
};

I wi sh, чтобы написать функцию более высокого порядка Map , которая может преобразовывать листовые элементы вложенного вектора, независимо от того, насколько глубоко и вернуть новый вложенный вектор той же формы. Я попытался 


template <int N, typename T, typename Mapper>
struct MapResult {
    typedef decltype ( (std::declval<Mapper>()) (std::declval<T>()) ) basic_type;
    typedef typename NVector<N, basic_type>::type vector_type;
};

template <int N, typename T, typename Mapper>
typename MapResult<N,T,Mapper>::vector_type 
    Map( typename NVector<N,T>::type const & vector,  Mapper mapper)
{
    typename MapResult<N,T,Mapper>::vector_type out;
    for(auto i = vector.begin(); i != vector.end(); i++){
        out.push_back(Map(*i,mapper));
    }
    return out;
}

template <typename T, typename Mapper>
typename MapResult<1,T,Mapper>::vector_type  
    Map(typename NVector<1,T>::type const & vector, Mapper mapper)
{
    typename MapResult<1,T,Mapper>::vector_type out;
    for(auto i = vector.begin(); i != vector.end(); i++){
        out.push_back(mapper(*i));
    }
    return out;
}

, а затем использовать его в основном как 

int main(){

    NVector<1,int>::type a = {1,2,3,4};
    NVector<2,int>::type b = {{1,2},{3,4}};

    NVector<1,std::string>::type as = Map(a,[](int x){return std::to_string(x);});
    NVector<2,std::string>::type bs = Map(b,[](int x){return std::to_string(x);});
}

Однако я получаю ошибки компиляции 

<source>:48:34: error: no matching function for call to 'Map'

    NVector<1,double>::type da = Map(a,[](int x)->int{return (double)x;});

                                 ^~~

<source>:20:5: note: candidate template ignored: couldn't infer template argument 'N'

    Map( typename NVector<N,T>::type const & vector,  Mapper mapper)

    ^

<source>:31:5: note: candidate template ignored: couldn't infer template argument 'T'

    Map(typename NVector<1,T>::type const & vector, Mapper mapper)

    ^

<source>:49:34: error: no matching function for call to 'Map'

    NVector<2,double>::type db = Map(b,[](int x)->int{return (double)x;});

                                 ^~~

<source>:20:5: note: candidate template ignored: couldn't infer template argument 'N'

    Map( typename NVector<N,T>::type const & vector,  Mapper mapper)

    ^

<source>:31:5: note: candidate template ignored: couldn't infer template argument 'T'

    Map(typename NVector<1,T>::type const & vector, Mapper mapper)

    ^

2 errors generated.

Compiler returned: 1

Я предполагаю, что компилятор не не достаточно умен (или стандарт не определяет, как), чтобы выяснить параметр N путем вычета. Есть ли способ, которым я могу достичь этого?

Раньше у меня это работало, но по-другому, фактически производным от std :: vector, но мне не нравится это решение, так как было бы неплохо, чтобы оно работало с существующим на данный момент кодом без необходимости вводить новый тип оболочки. 

/// define recursive case
template <int N, typename T>
struct NVector : std::vector<NVector<N-1,T>>;
/// define termination case
template <typename T> 
struct NVector<1, T> : public std::vector<T>;

действующий код на https://godbolt.org/z/AMxpuj

Ответы [ 7 ]

3 голосов
/ 29 января 2020

Вы не можете сделать вывод из typedef, особенно из typedef, объявленного внутри вспомогательного класса, потому что у компилятора нет возможности выполнить обратное отображение типа в комбинации аргументов.

(Учтите, что в общем случае это невозможно, поскольку кто-то может специализировать struct NVector<100, float> { using type = std::vector<char>; };, и компилятор не может знать, предназначено ли это.)

Чтобы помочь компилятору, вы можете определить обратное отображение: 

template<class T> struct NVT { static constexpr auto D = 0; using V = T; };
template<class T> struct NVT<std::vector<T>> : NVT<T> {
    static constexpr auto D = NVT<T>::D + 1;
};

Возможное использование (C ++ 17, но достаточно просто для перевода на архаи c диалекты): 

template<class NV, class Mapper>
auto Map(NV const& vector, Mapper mapper) {
    static constexpr auto N = NVT<NV>::D;
    using T = typename NVT<NV>::V;
    if constexpr (N == 0)
        return mapper(vector);
    else
    {
        typename MapResult<N,T,Mapper>::vector_type out;
        for (auto const& x : vector)
            out.push_back(Map(x, mapper));
        return out;
    }
}
2 голосов
/ 29 января 2020

Как уже указывалось в других ответах, проблема здесь заключается в том, что спецификатор вложенного имени в квалифицированном-идентификаторе представляет собой не выводимый контекст [temp.deduct.type] /5.1. Другие ответы также уже представили множество различных способов заставить ваш оригинальный подход работать. Я хотел бы сделать шаг назад и подумать, чем на самом деле вы хотите заниматься.

Все ваши проблемы связаны с тем, что вы пытаетесь работать с использованием вспомогательного шаблона NVector. Казалось бы, единственная цель этого вспомогательного шаблона - вычислить специализацию вложенного std::vector. Казалось бы, единственная цель вспомогательного шаблона MapResult состоит в том, чтобы вычислить специализацию вложенного std::vector, который был бы необходим для получения результата применения вашей произвольной функции mapper к каждому элементу вложенной входной векторной структуры. Ничто не заставляет вас express ваш Map шаблон функции в терминах этих вспомогательных шаблонов. На самом деле, жизнь намного проще, если мы просто избавимся от них. Все, что вы на самом деле хотели сделать, - это применить произвольную функцию mapper к каждому элементу вложенной структуры std::vector. Так что давайте просто сделаем это: 

template <typename T, typename Mapper>
auto Map(std::vector<T> const& vector, Mapper&& mapper) -> std::vector<decltype(mapper(std::declval<T>()))>
{
    std::vector<decltype(mapper(std::declval<T>()))> out;
    out.reserve(vector.size());
    for (auto& v : vector)
        out.push_back(mapper(v));
    return out;
}

template <typename T, typename Mapper>
auto Map(std::vector<std::vector<T>> const& vector, Mapper&& mapper) -> std::vector<decltype(Map(std::declval<std::vector<T>>(), mapper))>
{
    std::vector<decltype(Map(std::declval<std::vector<T>>(), mapper))> out;
    out.reserve(vector.size());
    for (auto& v : vector)
        out.push_back(Map(v, mapper));
    return out;
}

рабочий пример здесь

Просто отбросьте конечные типы возврата, если вы можете использовать C ++ 14 или новее.

Если то, что вы на самом деле хотите сделать, это просто сохранить и работать с массивом n D, учтите, что структура вложенного std::vector не обязательно является наиболее эффективным способом сделать это. Если вам не требуется, чтобы каждый субвектор имел потенциально различный размер, нет причин для того, чтобы количество динамически выделяемых вам выделений памяти c росло экспоненциально с количеством измерений и следило за указателями на каждом элементе. Просто используйте один std::vector для хранения всех элементов массива n D и определите отображение между логическими индексами элементов n D и 1D линейным индексом хранения, например, аналогично на то, что было предложено в этот ответ . Это будет не только эффективнее, чем векторы вложений, но и позволит вам легко изменять структуру памяти, в которой хранятся ваши данные. Кроме того, поскольку базовое хранилище представляет собой простой линейный массив, итерацию по всем элементам можно выполнить с помощью простого l oop, и ответ на ваш вопрос о сопоставлении одного диапазона элементов другому будет просто std::transform ...

1 голос
/ 29 января 2020

Вам не нужно NVector для определения MapResult и Map. 

template <int N, typename T>
struct NVector{
    typedef std::vector<typename NVector<N-1,T>::type> type;
};
template <typename T> struct NVector<1,T> {
    typedef std::vector<T> type;
};

template <typename T, typename Mapper>
struct MapResult {
    typedef decltype(std::declval<Mapper>()(std::declval<T>())) type;
};

template <typename T, typename Mapper>
struct MapResult<std::vector<T>, Mapper> {
    typedef std::vector<typename MapResult<T, Mapper>::type> type;
};

template <typename T, typename Mapper, typename Result = typename MapResult<T, Mapper>::type>
Result Map(T const& elem, Mapper&& mapper)
{
    return mapper(elem);
}

template <typename T, typename Mapper, typename Result = typename MapResult<std::vector<T>, Mapper>::type>
Result Map(std::vector<T> const& vector, Mapper&& mapper)
{
    Result out;
    out.reserve(vector.size());
    for (auto& v : vector)
        out.push_back(Map(v, mapper));
    return out;
}
0 голосов
/ 29 января 2020

T и N не вычитаются из: 

template <int N, typename T, typename Mapper>
typename MapResult<N,T,Mapper>::vector_type 
    Map(typename NVector<N,T>::type const & vector,  Mapper mapper)

Вместо этого вы можете сделать следующее: 

// final inner transformation
template <typename T, typename Mapper>
auto Map(const std::vector<T>& v, Mapper mapper)
-> std::vector<typename std::decay<decltype(mapper(*std::begin(v)))>::type>
{
    std::vector<typename std::decay<decltype(mapper(*std::begin(v)))>::type> ret;
    ret.reserve(v.size());
    std::transform(std::begin(v), std::end(v), std::back_inserter(ret), mapper);
    return ret;
}

// recursive call
template <typename T, typename Mapper>
auto Map(const std::vector<std::vector<T>>& v, Mapper mapper)
-> std::vector<typename std::decay<decltype(Map(*std::begin(v), mapper))>::type>
{
    std::vector<typename std::decay<decltype(Map(*std::begin(v), mapper))>::type> ret;
    ret.reserve(v.size());
    std::transform(std::begin(v),
                   std::end(v),
                   std::back_inserter(ret),
                   [&](const std::vector<T>& inner){ return Map(inner, mapper);});
    return ret;
}

Демо

0 голосов
/ 29 января 2020

Совершенно верно, что компилятор не пытается угадать, что вы имеете в виду, потому что это неоднозначно. Вы хотите вызвать функцию с помощью NVector<2, int> или NVector<1, std::vector<int>>? Оба являются полностью действительными, и оба дают вам один и тот же type член typedef.

Ваше предыдущее решение сработало, так как вы, вероятно, передали вектор в этом типе (поэтому аргумент имел тип NVector<2, int>, и из него легко вывести правильные параметры шаблона). На мой взгляд, у вас есть три варианта:

  1. Снова оберните std::vector в свой пользовательский тип. Но я бы сделал это не с наследованием, а только с помощью члена и неявного преобразования в тип этого члена.
  2. Добавьте некоторый параметр тега (Nvector<N,T> сделает), который устраняет неоднозначность вызова.
  3. Вызов с явными аргументами шаблона.

Я думаю, что третий самый простой и понятный.

0 голосов
/ 29 января 2020

Вы можете использовать частичную специализацию, чтобы вывести, так сказать, N назад. 

#include <iostream>
#include <vector>

template <typename T, int depth = 0>
struct get_NVector_depth {
    static constexpr int value = depth;
};

template <typename T, int depth>
struct get_NVector_depth<std::vector<T>, depth> {
    static constexpr int value = get_NVector_depth<T, depth+1>::value;
};

int main() {
    std::cout << get_NVector_depth<std::vector<std::vector<int>>>::value;
    std::cout << get_NVector_depth<std::vector<int>>::value;
}

Это можно использовать с SFINAE, чтобы сделать что-то вроде 

template <typename T, typename Mapper, std::enable_if_t<get_NVector_depth<T>::value == 1, int> = 0>
typename MapResult<1,T,Mapper>::vector_type  
    Map(const T& vector, Mapper mapper)
0 голосов
/ 29 января 2020

В общем случае typename NVector<N,T>::type не позволяет выводить N,T, потому что может быть много экземпляров шаблона, которые производят один и тот же вложенный тип.

Я знаю, что вы написали отображение 1: 1, но язык не требует этого, и поэтому нет никакой поддержки для обратной работы. В конце концов, вы написали typename NVector<N,T>::type, но на самом деле вы проходите std::vector<std::vector<int>> или что-то еще. Там нет общего способа отказать в этом.

Простое решение состоит в том, чтобы использовать NVector в качестве типа значения, а не просто как способ создания векторных typedefs. 

template <int N, typename T>
struct NVector{
    using nested = std::vector<NVector<N-1,T>>;
    nested vec;
};
template <typename T> struct NVector<1,T> {
    using nested = std::vector<T>;
    nested vec;
};

, затем изменить Map и MapResult работать напрямую в терминах NVector<N,T>, что позволяет вычитать тип как обычно. Например, общая карта становится 

template <int N, typename T, typename Mapper>
typename MapResult<N,T,Mapper>::vector_type 
    Map(NVector<N,T> const & vector,  Mapper mapper)
{
    typename MapResult<N,T,Mapper>::vector_type out;
    for(auto i = vector.vec.begin(); i != vector.vec.end(); i++){
        out.vec.push_back(Map(*i,mapper));
    }
    return out;
}

Наконец, вам нужно объявить ваши локальные переменные как NVector<1,int> без ::type, и, к сожалению, инициализаторы становятся немного уродливее, так как вам нужно обернуть лишнюю {} вокруг каждого уровня. Вы всегда можете написать конструктор для NVector, чтобы обойти это, однако.

О, и рассмотрите возможность использования std::transform вместо записи этого l oop вручную.

...