Is it possible to match recursively integer template parameters in C++?

Question

I have the following problem. I define a N dimensional vector as so

#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 wish to write a higher order function Map that can transform the leaf elements of the nested vector no matter how deep and return a new nested vector of the same shape. I have tried

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

and then use it in main like

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

However I get compile errors

<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

I'm guessing that the compiler isn't smart enough ( or the standard doesn't specify how ) to figure out the parameter N by deduction. Is there a way I can achieve this?

I previously had this working but in a different way by actually deriving from std::vector but I don't like this solution as it would be nice to have it work with currently existing code without having to introduce a new wrapper type.

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

live code at https://godbolt.org/z/AMxpuj

Answer 1

You can't deduce from a typedef - especially a typedef declared within a helper class - because there's no way for the compiler to perform the reverse mapping from a type to combinations of arguments.

(Consider that in the general case this is impossible since someone might specialize struct NVector<100, float> { using type = std::vector<char>; };, and the compiler has no way to know whether this is intended.)

To help the compiler out you could define the reverse mapping:

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

Possible usage (C++17, but it's easy enough to translate to archaic dialects):

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

Answer 2

As has already been pointed out in other answers, the problem here is that the nested-name-specifier in a qualified-id is a non-deduced context [temp.deduct.type]/5.1. Other answers have also already presented numerous different ways in which to make your original approach work. I would like to take a step back and consider what it actually is you want to do.

All your problems stem from the fact that you're trying to work in terms of the helper template NVector. The sole purpose of this helper template would seem to be to compute a specialization of nested std::vector. The sole purpose of the helper template MapResult would seem to be to compute the specialization of nested std::vector that would be necessary to capture the result of applying your arbitrary mapper function to each element of the nested input vector structure. Nothing forces you to express your Map function template in terms of these helper templates. In fact, life is a lot simpler if we just get rid of them. All you actually wanted to do is apply an arbitrary mapper function to each element of a nested std::vector structure. So let's just do that:

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

working example here

Simply drop the trailing return types if you can use C++14 or newer.

---

If what you actually want to do is just store and work on an nD array, consider that a structure of nested std::vector is not necessarily the most efficient way of doing so. Unless you need each sub-vector to be of potentially different size, there's no reason to have the number of dynamic memory allocations you perform grow exponentially with the number of dimensions and pointer-chase your way to each element. Just use one std::vector to hold all elements of the nD array and define a mapping between logical nD element indices and 1D linear storage index, for example, in a way similar to what was suggested in this answer. Doing so will not only be more efficient than nesting vectors, but also allows you to easily change the memory layout in which your data is stored. Furthermore, since the underlying storage is a plain linear array, iterating over all elements can be done using just a simple loop and the answer to your question of mapping one range of elements to another would simply be std::transform…