TimothyQiu's Blog

keep it simple stupid

小试 Variadic Template

分类:技术

本文源自于今天对 neuront 童鞋的这篇文章的末尾的那段代码的 C++ 实现的思考。(好多「的」……)

尽管 std::accumulate() 和 Python 的 reduce() 类似,但因为 C艹 的 std::map<std::string, std::map<std::string, int>>std::map<std::string, int> 是不同的类型,所以似乎只能自己用可变参数模板写一个了。

简单起见,我们还是退一步,来解决一个更简单、更不通用、而且似乎和 reduce() 完全无关的问题吧:如何才能一次性取得任意层次的字典值?用更直白的代码表达,就是我们需要一个 GetMapValue() 函数,实现这样的功能:

// 用于缓解眼花缭乱感的宏
#define MAP_LITERAL(...) { __VA_ARGS__ }

// 简单映射
std::map<std::string, std::string>
simple_dict = MAP_LITERAL({"Hello", "World"});

// 「我勒个去居然这么麻烦」映射
std::map<std::string,
         std::map<std::string,
                  std::map<std::string,
                           int>>>
nested_dict = MAP_LITERAL( { "x", MAP_LITERAL( { "y", MAP_LITERAL( { "a", 10 } ) },
                                               { "z", MAP_LITERAL( { "b", 20 } ) } ) });

auto value1 = GetMapValue(simple_dict, "Hello");
std::cout << value1 << std::endl;

auto value2 = GetMapValue(nested_dict, "x", "y", "a");
std::cout << value2 << std::endl;

初始的版本

初步分析,GetMapValue() 需要接受一个 Map 以及至少一个 Key。如此,参数可变,首选 C++11 的可变参数模板。一次性将所有 Key 拿到手后,每次用第一个 Key 获取下一级 Map,而后用余下的 Key 递归,最终获取所要的值。而要写递归,最好先从最简单的情况写起。

template <typename MapType>
auto GetMapValue(MapType const& map, typename MapType::key_type const& key)
    -> typename MapType::mapped_type
{
    return map.at(key);
}

鉴于本人目前对于右值引用还不熟悉,就只用 const& 了(& 只能引用左值;const& 既能引用左值、又能引用右值,但无法修改)。

这里需要注意的是 STL 的几种 Map 里 typedef 到的数据类型,略坑:

不过这样一来,我们的 GetMapValue() 就可以在 STL 的这几种 Map 里通用了。

不被支持的递归 decltype 模板

本来我想,递归版本按照上面这个最简版本写一下就 OK 了。可变参数模板的基本用法我以前的日志有写过;这里唯一麻烦的是返回值,因为通用性,只有最终被调用的版本才知道确切的返回值,不过 decltype 似乎可以救场:

template <typename MapType, typename... MoreKeyTypes>
auto GetMapValue(MapType const& map, typename MapType::key_type const& key,
                 typename MapType::mapped_type::key_type const& anotherKey, MoreKeyTypes... moreKeys)
    -> decltype(GetMapValue(map.at(key), anotherKey, moreKeys...))
{
    return GetMapValue(map.at(key), anotherKey, moreKeys...);
}

然而,编译器不给面子,直接提示模板推导失败,decltype 时找不到接受两个 Key 版本的 GetMapValue()(三个参数)。

似乎,decltype 是不支持递归调用的,亦或者推导时自身还不存在。decltype 以及模板的一些规则真心还不是很熟,所以暂时没有找到真凭实据。

Traits

于是我终于知道为什么世界上会有 Traits 这种东西存在了。(比如 std::basic_string 的模板参数之一就是 class Traits = std::char_traits<CharT>。)Traits 是用来描述某个类型周边信息的东西。这里,我们需要一个 Traits 来计算一个 Map 被使用若干次 Key 后的 Value 类型。

那么很显然的,这个 MapTraits 依旧是可变参数模板、依旧是递归实现。

template <typename MapType, typename KeyType, typename... KeyTypes>
struct MapTraits
{
    typedef typename MapTraits<typename MapType::mapped_type, KeyTypes...>::mapped_type mapped_type;
};

template <typename MapType, typename KeyType>
struct MapTraits<MapType, KeyType>
{
    typedef typename MapType::mapped_type mapped_type;
};

完全体

不出所料,最终的代码是一番如此纠结的景象。看这样的代码眼睛压力山大。

template <typename MapType>
auto GetMapValue(MapType const& map, typename MapType::key_type const& key)
    -> typename MapType::mapped_type
{
    return map.at(key);
}

template <typename MapType, typename... MoreKeyTypes>
auto GetMapValue(MapType const& map, typename MapType::key_type const& key,
                typename MapType::mapped_type::key_type const& anotherKey, MoreKeyTypes... moreKeys)
    -> typename MapTraits<typename MapType::mapped_type, typename MapType::mapped_type::key_type, MoreKeyTypes...>::mapped_type
{
    return GetMapValue(map.at(key), anotherKey, moreKeys...);
}

完整的测试代码见这个 Gist:https://gist.github.com/timothyqiu/6877974

Traits 的小插曲

我第一次写的时候,把 MapTraits 的特化形式写成了这样:

template <typename MapType>                             // 正式版本: typename MapType, typename KeyType
struct MapTraits<MapType, typename MapType::key_type>   // 正式版本: MapType, KeyType
{
    typedef typename MapType::mapped_type mapped_type;
};

其实只是用 typename MapType::key_type 替换了一个正式版本里的模板参数 KeyType 而已。这样做其实也并非不可,只不过产出的是「高标准、严要求」的代码:

// 正式版本可行,但是在这个版本里一堆模板错误
auto value2 = GetMapValue(nested_dict, "x", "y", "a");

// 两个版本都可行
auto value2 = GetMapValue(nested_dict, std::string("x"), std::string("y"), std::string("a"));

原理大致是,这个版本因为把特化形式的第二个模板参数固定成了第一个参数的 key_type,所以如果使用了和 key_type 不同但是可以隐式转换的类型,会导致模板推导失败。

C++C++11

已有 4 条评论 »

  1. 虽然不明白怎么回事, 但好像再加个重载不用 traits 也可以 (gcc version 4.7.3 / Xubuntu 13.04)

    template <typename MapType> auto GetMapValue(MapType const& map, typename MapType::key_type const& key) -> typename MapType::mapped_type { return map.at(key); } / 加个红色有角三参数的在这里 / template <typename MapType, typename OneMoreKeyType> auto GetMapValue(MapType const& map, typename MapType::key_type const& key, OneMoreKeyType const& keyx) -> typename MapType::mapped_type::mapped_type { return map.at(key).at(keyx); } template <typename MapType, typename... MoreKeyTypes> auto GetMapValue(MapType const& map, typename MapType::key_type const& key, typename MapType::mapped_type::key_type const& anotherKey, MoreKeyTypes... moreKeys) -> decltype(GetMapValue(map.at(key), anotherKey, moreKeys...)) { return GetMapValue(map.at(key), anotherKey, moreKeys...); }

    顺便自卖一下 C++11 右值引用原理 http://blog.bitfoc.us/?p=222

    1. @Neuron Teckid

      因为例子里的 GetMapValue(nested_dict, "x", "y", "a") 需要引用接受 2 个 Key 的版本(GetMapValue(nested_dict["x"], "y", "a")),你添的这个正好把接受 2 个 Key 的版本补上了……但是 3、4、5 个或者更多的版本的依旧没法自动生成……所以 GetMapValue(another_dict, 1, 2, 3, 4) 还是木有办法编译的……

  2. C++14 ,支持 return type deduction. 再等等吧

    说话模块的代码真心丑。
    C++再往下发展,应该要让元编程更加优雅……

    1. @唐风

      C++14 的 Concept Lite 似乎可以方便不少东西的样子 = =

添加新评论 »