C++模板元编程—-堆排序

目录

前言

经过前两次经验的积累,终于来到了麻烦的堆排序。在一开始接触模板元编程的时候,我就期望有一天能够写出元编程堆排序的代码。原因是看了知乎大佬的一篇文章《在简历上写了“精通 C++”后……》。由于学识浅薄,感觉只能接触到模板元编程这一部分,所以便开始了对模板元编程的研究。经过多次的学习研究,最终在今天完成了这一成就。但是时间花了三个小时左右,所以时间肯定是不能达标了,但是也算是一个比较奇特的经历吧。

相比较于前两种排序方式,堆排序需要交换操作,更多的判断操作,随机读取等。这一些都不是模板元编程擅长的地方,但是幸运的是都是有办法实现。

实现的一些小细节

Debug

前两次实现的时候,运气很好,结束的时候都没有出现什么bug,但是这一次的比较麻烦,出现了比较严重的bug。但是由于限制,没办法进行很好的调试。于是通过编译器的报错机制,我写了一个元编程的断言。当输入的flag为false时,便会报错。

template<bool>
struct m_assert;

template<>
struct m_assert<true> {
    typedef int result_type;
};

template<>
struct m_assert<false> {};

使用的时候在需要查看的类里面,放入一个类似的语句,然后将flag改成相应的条件,就可以得到调用栈了。

typename m_assert<m_or<begin != 0, T::size != 3>::result>::result_type non_data;

实现的方法也很简单,就是区分truefalse,当输入为true时,结构体便有result_type类型,而false则没有。此时如果使用其的result_type,便会产生报错,以便观察程序的调用。编译输出为:

断言输出

但是这一种方法没办法打印当前调用的输出,因此我又增加了一层:

template<bool flag, typename ...T>
struct m_assert_print{
    typedef typename m_assert<flag>::result_type result_type;
};

使用方法也类似,如果需要打印当前调用的输出,便将要打印的内容作为T输入即可,譬如:

typename m_assert_print<m_or<begin != 0, T::size != 3>::result, result_type>::result_type non_data;

此时的编译输出为:

断言打印输出

可以看到相比较之前的输出,这一次的输出多了一层,而在这一层里,包含了需要打印的内容。

惰性求值

我一开始一直以为C++是没有实现惰性求值的,但是经过一系列的实验,和查找资料,好像C++是存在一定的惰性求值的。譬如

template<>
struct m_assert<false> {};

template<bool flag, typename ...T>
struct m_assert_print{
    typedef typename m_assert<flag>::result_type result_type;
};

template<bool flag>
struct ErrorType {
    typedef typename m_assert<flag>::result_type result_type;
};

struct Test {
    typedef typename m_if<true, ErrorType<true>, ErrorType<false>>::result_type::result_type result_type;
};

如果是没有惰性求值的存在,这一段代码是应该报错的。因为在ErrorType<false>中引用了m_assert<fasle>::result_type。而在上一部分就提到过,应该是会必报错的。

而对于另一个写法

struct Test {
    typedef typename m_if<true, ErrorType<true>::result_type, ErrorType<false>::result_type>::result_type result_type;
};

编译期却提示错误,甚至将ErrorType模板修改成

template<bool flag>
struct ErrorType {
    typedef typename m_assert<flag>::result_type result1_type;
    typedef int result_type;
};

编译器也还是会报错。

通过查阅资料总结的话,编译期对于出现的模板并不会全部的具现化。但是如果使用了其中的类型,便会对其进行具现化[1]。因此,通过这个特性,是有办法设计出一些惰性加载的类,但是由于当时并不知道,所以实现的时候采取了偏特化的方法,防止编译时走向一些奇怪的方向。

简单的来说,就是通过增加一个valid输入,来判断需不需要对这个支线进行下去。如果为fasle,则返回默认值,如果为true,则返回操作后的值,配合m_if,便可以得到想要的结果。

总结

总的来说,模板元编程是C++里面一个比较有趣的部分。由于其晦涩难懂,也成为了许多大佬秀操作的地方。但是随着C++标准的完善,它的难度也在不断的降低。在C++17的时候,大部分的函数都可以使用constexpr来修饰了,这让模板元编程在值运算的时候失去了一部分函数式编程的特点。而C++20中的constraintsconcepts,让模板偏特化有了更大的活力。

源代码://gist.github.com/ink19/9fdcca26e89655e8c1b80da56ee04c65

Ref

[1] //www.jianshu.com/p/f2477d2c19ea

博客原文://www.cnblogs.com/ink19/p/cpp_template_heap_sort.html

Tags: