C++模板泛型入门之汉诺塔

栏目: C++ · 发布时间: 7年前

内容简介:C++模板泛型入门之汉诺塔

前言

最近由于在项目中用到了一些模板技巧如SFINAE之类,突然对这类“屠龙之技”产生了浓厚的兴趣。换而言之就是,既然有机会在正常的C艹工程里面使用函数式的技巧,总会让人忍不住拿更复杂的东西练练手。于是在拜读了某位大神的《 Brainfuck Compile Time Evaluator 》之后,决定自己写几个简单的玩具,比如求解一些经典的递归问题之类,就先从汉诺塔开始吧。

基本实现

这里就不再赘述正常的递归版本实现了,要把它转化成模板,我们首先定义存储目标结果的结构如下:

template <typename T, T a, T b>
struct pair {
  static constexpr auto first = a;
  static constexpr auto second = b;
};

接下来,我们定义一个用于存储结果的序列:

template <typename... Args>
struct sequence {};

然后定义一个连接两个 sequence 生成一个新 sequence 的方法:

template <typename... Args1, typename... Args2>
struct concat<sequence<Args1...>, sequence<Args2...>> {
  using type = sequence<Args1..., Args2...>;
};

有了基本的序列存储和连接操作,我们就可以定义汉诺塔的递归求解操作了,如下所示:

template <int, typename T, T a, T b, T c>
struct hanoi;

template <typename T, T a, T b, T c>
struct hanoi<1, T, a, b, c> {
  using type = sequence<pair<T, a, c>>;
};

template <int n, typename T, T a, T b, T c>
struct hanoi {
  using type = typename concat<
                 typename concat<typename hanoi<n - 1, T, a, c, b>::type,
                                 sequence<pair<T, a, c>>
                                >::type,
                 typename hanoi<n - 1, T, b, a, c>::type
               >::type;
};

这里我们实际上是先声明模板接口,然后定义两个实例,分别是正常的递归版本,以及递归终止时的偏特化版本。这样编译器就可以正确求解这个问题了。

最后的问题在于如何输出我们的结果,这里同样采取递归的方式来解开参数包:

// here we use T for type "sequence<>"
template <typename T>
void print(T) {}

template <typename T, typename... Args>
void print(sequence<T, Args...>) {
  std::cout << T::first << "->" << T::second << std::endl;
  print(sequence<Args...>());
}

int main(int, const char*[]) {
    print(typename hanoi<3, char, 'A', 'B', 'C'>::type());
}

注意到在上述汉诺塔实现中,我们只要保证模板参数a, b, c具有相同的类型,并且都重载了流输出运算符即可。看起来是一种很不错的泛型抽象。完整代码见 这里

编译命令为: g++ hanoi.cpp -std=c++14 -O2 -o hanoi

优化I

Clang 对C++模板推导的最大递归深度有限制,因此默认情况下程序的汉诺塔层数 最大只能设置为8 ,输出结果是255次移动操作。而当我们这样编译程序以后,会发现程序体积达到了惊人的 216KB (Clang 8.0, macOS 10.12)。然而,这种静态编译器推导, 理想情况下的体积占用应该与我们直接“打表”生成的程序体积相当 ,即正比于输出结果的长度。只编码输出结果的话绝不应该有这么大。用 objdump 瞄一眼到底生成了什么,我们会发现里面有255个不同参数类型的 print 函数。由于每个函数的符号名中都包含了完整的类型名称 sequence<...> ,而且它的长度随着参数包展开而慢慢变短,所以这巨长的符号名就要占用不少体积,确切滴说 空间复杂度是多项式级别的 。于是果断用 strip 去掉这些无用的符号,重新看下体积,会发现减小为 80KB 。但问题在于,虽然长长的符号名去掉了,但是生成的这几百个函数体还在,所以还是有不小的空间占用。

优化II

接下来我们尝试从代码的层面予以优化。既然这样递归展开参数包导致了过长的参数名,我们可以考虑换一种方式,如果编译期间直接把所有结果推导为静态字符串,最后一起输出呢?这里我们使用 std::integer_sequence 来解决这个问题,首先定义一个向序列前面追加元素的方法:

template <typename seq, typename seq::value_type...>
struct prepend;

template <typename T, T... x1, T... x2>
struct prepend<std::integer_sequence<T, x1...>, x2...> {
  using type = std::integer_sequence<T, x2..., x1...>;
};

然后我们就可以定义一个将先前的 sequence 格式化为 std::integer_sequence 的方法:

template <typename T>
struct seq2str {};

template <typename T>
struct seq2str<sequence<T>> {
  using type = std::integer_sequence<typename T::type,
      T::first, '-', '>', T::second, '\n'>;
};

template <typename T, typename... Args>
struct seq2str<sequence<T, Args...>> {
  using type = typename prepend<
      typename seq2str<sequence<Args...>>::type,
      T::first, '-', '>', T::second, '\n'
      >::type;
};

最后,只要把我们的 std::integer_sequence 打印出来即可:

template <typename T, T... xs>
void print_seq(std::integer_sequence<T, xs...>) {
    bool Do[] = { (std::cout << xs, true)... };
    (void)Do;
}

int main(int, const char*[]) {
  print_seq(typename seq2str<
              typename hanoi<8, char, 'A', 'B', 'C'>
              ::type
            >::type ());
}

这样编译出来的程序体积只要48KB,又有了明显的提升。完整的代码在 这里

优化III

上述代码有一个明显的问题,就是失去了泛型的抽象特性。如果我们把 hanoi<3, char, 'A', 'B', 'C'> 换成 hanoi<3, int, 1, 2, 3> ,会发现输出结果彻底不正常,用于格式化的箭头等等也被作为 int 类型来输出了。并且,如果我们查看一下生成的二进制,会发现生成了一个参数类型巨长的,并且函数体也很复杂的 print_seq 函数,这个函数会调用很多次 std::cout 。确切滴说,函数符号名的长度以及调用 cout 的次数 与结果字符串中字符的数量相当 。所以虽然这样的程序体积已经正比于输出长度了,但其实还应该有进一步优化的空间。

再考察一下我们对 pair 的定义,会发现我们只要在这里加上一个静态的 print() 方法就足够了:

template <typename T, T a, T b>
struct pair {
  static constexpr auto first = a;
  static constexpr auto second = b;
  static void print() { std::cout << first << "->" << second << std::endl; }
};

然后在打印输出的时候没必要如此麻烦地转成静态字符串,完全可以直接展开类型包调用其 print() 方法:

template <typename... Args>
void print_seq(sequence<Args...>) {
    bool Do[] = { (Args::print(), true)... };
    (void)Do;
}

int main(int, const char*[]) {
    print_seq(typename hanoi<8, char, 'A', 'B', 'C'>::type());
}

这样的话我们会发现,该版本不会失去泛型特性,并且编译后二进制体积也控制得足够好,仅有 16KB 大小。完整代码在 这里

总结

为什么最后这个版本就有效地控制了二进制体积呢?还是操起 objdump ,我们会发现它的二进制中仅仅包含 \(\binom{3}{2} = 6\)pair::print() 方法,显然是在编译过程中做了哈希去重;而在函数 print_seq 中,包含的是255次对这些不同 pair::print() 方法的 直接调用 ,每一次调用只占 5 字节。所以,这个版本几乎完全等价于打表,甚至可以说优于打表,也就不难理解为何二进制体积如此之小了。

另外,有人可能会好奇,这类模板技巧主要有哪些用途呢?其实答案是……毫无卵用:joy::joy::joy:


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

后谷歌时代:大数据的衰落及区块链经济的崛起

后谷歌时代:大数据的衰落及区块链经济的崛起

乔治·吉尔德 / 现代出版社 / 2018-9-5 / 68

以大数据和机器智能为基础的谷歌时代(信息互联网时代)是一个令人敬畏的时代。但它即将终结。 《后谷歌时代》一书的作者乔治•吉尔德是一位颇具远见卓识的智者。他在技术和文化领域具有无与伦比的视野和见地。他向读者描述了谷歌所面临信任与安全危机,并勇敢地预测了即将到来的后谷歌时代。 谷歌用其惊人的“搜索和排序”能力吸引了整个世界。功能强大的搜索引擎,看似免费小应用,诸如视频、地图、电子邮箱等,让......一起来看看 《后谷歌时代:大数据的衰落及区块链经济的崛起》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码