本文源自于今天对 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 到的数据类型，略坑：

• key_type 是 Key 的类型
• mapped_type 是 Value 的类型
• value_type 是 Map 中实际存储的键值对的具体类型（如 std::pair<key_type, mapped_type>）

不过这样一来，我们的 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