¿Es posible hacer coincidir parámetros de plantilla enteros recursivamente en C ++?

Tengo el siguiente problema. Defino un vector N dimensional como tal

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

Deseo escribir un mapa de función de orden superior que pueda transformar los elementos de hoja del vector anidado sin importar cuán profundo y devolver un nuevo vector anidado de la misma forma. Yo he tratado

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

y luego usarlo en main como

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

Sin embargo, obtengo errores de compilación

<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

Supongo que el compilador no es lo suficientemente inteligente (o el estándar no especifica cómo) para calcular el parámetro N por deducción. ¿Hay alguna manera de lograr esto?

Anteriormente tenía esto funcionando pero de una manera diferente al derivar realmente de std :: vector, pero no me gusta esta solución, ya que sería bueno que funcione con el código existente sin tener que introducir un nuevo tipo de contenedor.

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

código en vivo en https://godbolt.org/z/AMxpuj

No se puede deducir de un typedef, especialmente un typedef declarado dentro de una clase auxiliar, porque no hay forma de que el compilador realice el mapeo inverso de un tipo a combinaciones de argumentos.

(Tenga en cuenta que, en el caso general, esto es imposible ya que alguien podría especializarse struct NVector<100, float> { using type = std::vector<char>; };, y el compilador no tiene forma de saber si esto está destinado).

Para ayudar al compilador, puede definir la asignación inversa:

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

Posible uso (C ++ 17, pero es bastante fácil de traducir a dialectos arcaicos):

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

Como ya se ha señalado en otras respuestas, el problema aquí es que el especificador de nombre anidado en un id calificado es un contexto no deducido [temp.deduct.type] /5.1 . Otras respuestas también han presentado numerosas maneras diferentes de hacer que su enfoque original funcione. Me gustaría dar un paso atrás y considerar qué es lo que realmente quieres hacer.

Todos sus problemas provienen del hecho de que está tratando de trabajar en términos de la plantilla auxiliar NVector. El único propósito de esta plantilla auxiliar parece ser calcular una especialización de anidado std::vector. El único propósito de la plantilla auxiliar MapResultparece ser calcular la especialización de anidada std::vectorque sería necesaria para capturar el resultado de aplicar su mapperfunción arbitraria a cada elemento de la estructura del vector de entrada anidada. Nada lo obliga a expresar su Mapplantilla de función en términos de estas plantillas auxiliares. De hecho, la vida es mucho más simple si nos deshacemos de ellos. Todo lo que realmente quería hacer es aplicar una mapperfunción arbitraria a cada elemento de una std::vectorestructura anidada . Entonces hagamos eso:

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

ejemplo de trabajo aquí

Simplemente suelte los tipos de retorno final si puede usar C ++ 14 o posterior.

Si lo que realmente quiere hacer es simplemente almacenar y trabajar en una matriz n D, considere que una estructura de anidada std::vectorno es necesariamente la forma más eficiente de hacerlo. A menos que necesite que cada sub-vector tenga un tamaño potencialmente diferente, no hay razón para que el número de asignaciones de memoria dinámica que realice crezca exponencialmente con el número de dimensiones y persiga su puntero hacia cada elemento. Solo use uno std::vectorpara contener todos los elementos de la matriz n D y defina un mapeo entre los índices lógicos de elementos n D y el índice de almacenamiento lineal 1D, por ejemplo, de una manera similar a lo sugerido en esta respuesta. Hacerlo no solo será más eficiente que los vectores de anidación, sino que también le permite cambiar fácilmente el diseño de la memoria en la que se almacenan sus datos. Además, dado que el almacenamiento subyacente es una matriz lineal simple, la iteración sobre todos los elementos se puede hacer usando solo un bucle simple y la respuesta a su pregunta de asignar un rango de elementos a otro simplemente sería std::transform...

No necesitas NVectordefinir MapResulty 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;
}

En general, typename NVector<N,T>::typeno le permite deducir N,Tporque podría haber muchas instancias de una plantilla que produzca el mismo tipo anidado.

Sé que escribiste un mapeo 1: 1, pero el idioma no lo requiere, por lo que no hay soporte para trabajar de esta manera hacia atrás. Después de todo, usted escribió typename NVector<N,T>::type , pero lo que realmente está pasando es std::vector<std::vector<int>>o lo que sea. No hay una forma general de respaldarlo.

La solución simple es usar NVector como un tipo de valor en lugar de solo una forma de producir vectores 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;
};

a continuación, cambiar Mapa y MapResult para trabajar directamente en términos de NVector<N,T>, lo que permite la deducción de tipo como de costumbre. Por ejemplo, el Mapa general se convierte en

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

Finalmente, debe declarar sus variables locales como NVector<1,int>no ::type, y desafortunadamente los inicializadores se vuelven un poco más feos ya que necesita envolver un extra {}en cada nivel. Sin NVectorembargo, siempre puedes escribir un constructor para evitar esto.

Ah, y considere usar en std::transformlugar de escribir ese bucle a mano.

Puede utilizar una especialización parcial para deducir N al revés, por así decirlo.

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

Esto podría usarse con SFINAE para hacer algo como

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)

Es perfectamente cierto que el compilador no intenta adivinar lo que quiere decir, porque es ambiguo. ¿Quieres llamar a la función con NVector<2, int>o NVector<1, std::vector<int>>? Ambos son totalmente válidos y ambos le darían el mismo tipo de typemiembro.

Su solución anterior funcionó, ya que probablemente pasó el vector en este tipo (por lo que el argumento tenía tipo NVector<2, int>y desde allí es fácil deducir los parámetros de plantilla correctos). Tienes tres posibilidades en mi opinión:

1. Envuelva de std::vectornuevo en su tipo personalizado. Pero lo haría no con herencia sino solo con un miembro y conversión implícita al tipo de ese miembro.
2. Agregue algún tipo de parámetro de etiqueta ( Nvector<N,T>lo haría) que desambigua la llamada.
3. Llamada con argumentos de plantilla explícitos.

Creo que el tercero es el más fácil y claro.

Ty Nno son deducibles en:

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

En cambio, podrías hacer:

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

Manifestación