是否可以在 C++ 中递归匹配整数模板参数？

Question

我有以下问题。我这样定义一个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;
};

我希望编写一个高阶函数 Map 可以转换嵌套向量的叶元素，无论嵌套向量有多深 return 一个新的嵌套向量相同的形状。我试过了


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

然后像

一样在main中使用它

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

Answer 1

您不能从 typedef 中推断出来——尤其是在 helper 中声明的 typedef class——因为编译器无法执行从类型到参数组合的反向映射。

（考虑到在一般情况下这是不可能的，因为有人可能专门化 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，但翻译成古代方言是easy enough）：

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

通常 typename NVector<N,T>::type 不允许您推断 N,T 因为可能有许多个模板实例产生相同的嵌套类型。

我知道您写了一个 1:1 映射，但语言不需要它，因此不支持以这种方式向后工作。毕竟，您写了 typename NVector<N,T>::type，但您实际传递的是 std::vector<std::vector<int>> 或其他内容。没有通用的方法来取消它。

简单的解决方案是使用 NVector 作为值类型，而不仅仅是一种生成向量 typedef 的方法。

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> 工作，这允许像往常一样进行类型推导。比如一般的Map就变成了

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 而不是手动编写该循环。

Answer 3

可以这么说，您可以使用偏特化来向后推导 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)

Answer 4

这是完全正确的，编译器不会试图猜测你的意思，因为它是模棱两可的。您要使用 NVector<2, int> 还是 NVector<1, std::vector<int>> 调用函数？两者都是完全有效的，并且都会给你相同的 type 成员类型定义。

您之前的解决方案有效，因为您可能传递了这种类型的向量（因此参数的类型为 NVector<2, int>，从那里很容易推断出正确的模板参数）。我认为你有三种可能：

在您的自定义类型中再次包装 std::vector。但我不会通过继承来做到这一点，而只是通过成员和到该成员类型的隐式转换。
添加某种标记参数（Nvector<N,T> 可以）来消除调用的歧义。
使用显式模板参数调用。

我觉得第三个最简单明了

Answer 5

正如其他答案中已经指出的那样，这里的问题是 nested-name-specifier 在 qualified-id 是非推导上下文 [temp.deduct.type]/5.1。其他答案也已经提出了许多不同的方法来使您的原始方法起作用。我想退后一步，考虑一下你到底想做什么。

你所有的问题都源于你试图根据帮助模板 NVector 来工作。这个辅助模板的唯一目的似乎是计算嵌套 std::vector 的特化。辅助模板 MapResult 的唯一目的似乎是计算嵌套 std::vector 的特化，这是捕获将任意 mapper 函数应用于每个元素的结果所必需的嵌套输入向量结构。没有什么会强迫您根据这些帮助模板来表达您的 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;
}

工作示例here

如果可以使用 C++14 或更新版本，只需删除尾随的 return 类型。

如果您真正想要做的只是存储和处理 nD 数组，请考虑嵌套 std::vector 的结构不一定是最有效的这样做的方式。除非您需要每个子向量的大小可能不同，否则没有理由让您执行的动态内存分配的数量随着维数和指针追逐到每个元素的数量呈指数增长。只需使用一个 std::vector 来保存 nD 数组的所有元素并定义逻辑 nD 元素索引和一维线性之间的映射存储索引，例如，以类似于 . 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…

中建议的方式

Answer 6

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

Demo

Answer 7

您不需要 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;
}

是否可以在 C++ 中递归匹配整数模板参数？

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

c++

templates

template-meta-programming

c++11