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

Puga

Straight out of my head - you should use deductible template type T as argument and use enable_if – Scintilla

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

Johnston

This looks great. What's the transform to turn it into C++11 ( without if constexpr ). Is there a generic way to do this? Stuck with old compiler :( – Puga

@Puga Create struct with partial specialization for N==0 and others – Scintilla

Nice. Here's how I did it in C++11: godbolt.org/z/bNzFk3 - it's amazing how quickly the skills for writing in old versions get rusty! – Johnston

That's nicer than my version. I didn't really need to create the structs. Yes if constexpr is super nice. Pity I can't use it. With a couple of tweaks I got the code working all the way back to VS2010. Golden :) !! – Puga

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…

Obligate

Sorry but you have missed what it is I'm trying to do. I don't want to write N Map functions for the N levels of nesting I need to support and then have to write another one when I find that I need (N+1) levels of support. See the answer from https://mcmap.net/q/1342961/-is-it-possible-to-match-recursively-integer-template-parameters-in-c – Puga

@Puga My understanding was that you want to apply a mapping function to an arbitrarily-nested structure of std::vectors. Above approach does exactly that and works for any N!? There are two overloads, one matching the case of a vector that contains yet another vector and leads to recursing down a level, and one handling the base case where recursion stops… – Obligate

@Puga I have expanded the example to include a test cases for a 3-way nested vector to demonstrate that it works: godbolt.org/z/ksyn5k ;) – Obligate

With regards to your last comment in the answer. I really do need vectors as the leaf vectors are all different lengths and contain large objects. – Puga

@Puga ok, well, in that case you'll want to go with the nested vectors I guess. I just thought I'd mention it just in case. – Obligate

Answer 3

You don't need NVector to define MapResult and 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;
}

Adalie

I fixed up a couple of errors you had in the code. It now compiles. Nice solution. – Puga

Unfortunately the VS2010 compiler ( yes I have to ) doesn't support default template arguments on functions – Puga

But easily fixable. The default template parameters were just sugar to prevent copy paste. This works in VS2010 ( for any poor souls who have to ) gist.github.com/bradphelan/da494160adb32138b46aba4ed3fff967 – Puga

Answer 4

In general typename NVector<N,T>::type doesn't allow you to deduce N,T because there could be many instances of a template that produce the same nested type.

I know you wrote a 1:1 mapping, but the language doesn't require it, and so there's no support for working backwards this way. After all, you wrote typename NVector<N,T>::type, but what you're actually passing is std::vector<std::vector<int>> or whatever. There's no general way to back it out.

The simple solution is to use NVector as a value type rather than just a way to produce vector 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;
};

then change Map and MapResult to work directly in terms of NVector<N,T>, which allows type deduction as usual. For example, the general Map becomes

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

Finally you need to declare your local variables as NVector<1,int> with no ::type, and unfortunately the initializers become a bit uglier since you need to wrap an extra {} around each level. You can always write a constructor for NVector to get around this, though.

Oh, and consider using std::transform instead of writing that loop by hand.

Brougham

OP's mapping is actually not 1:1 since they do not forbid T to be of type std::vector. – Lolland

Answer 5

You can use a partial specialization to deduce N backwards so to speak.

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

This could be used with SFINAE to do something like

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)

Vladi

Answer 6

It is perfectly right, that the compiler does not try to guess what you mean, because it is ambiguous. Do you want to call the function with NVector<2, int> or NVector<1, std::vector<int>>? Both are totally valid and both would give you the same type member typedef.

Your previous solution worked, since you probably passed the vector in this type (so the argument had type NVector<2, int> and from there it is easy to deduce the right template parameters). You have three possibilities in my opinion:

1. Wrap the std::vector again in your custom type. But I would do that not with inheritance but just with a member and implicit conversion to that member's type.
2. Add some kind of tag parameter (Nvector<N,T> would do) that disambiguates the call.
3. Call with explicit template arguments.

I think the third is the easiest and clearest.

Lolland

Answer 7

T and N are non deducible in:

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

Instead, you might do:

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

Demo

Trimolecular