整段源码链接
C++的模板元堆排序
要点
- 组建数据结构list
- 组建对list的各种基本操作
- 堆排序中组建堆排序个个函数以及其中 if，for之类的结构
PS：其实你以为这些东西很容易……但是我重构了4遍啊……
PS2: using integer = int; <=> typedef int integer;
PS3: typename是为了显式的告诉编译期这个东西是一个类型
PS4: 不要吐槽取名
下面开始
一. 建立数据结构list
但是这个list呢实际上由cons组成的
即(list 1 2 3) == (cons 1 (cons 2 (cons 3 nil)))
也就是C++中是list<1,2,3> == cons<1, cons<2, cons<3, null>>>
那么首先是想list这东西该怎么来，list的参数必然是可变长参数，这就有点伤脑筋了，所以第一步还是先去解决cons，然后把list定义成cons的递归。
struct null {};
template<class left, class right>
struct cons {};
template<class left>
struct cons<left, null> {};
这里面的null其实并不太好解决，实际上我还未参透null到底是什么，不过这么写是可以用的，但是元函数类要访问越界list访问到它的时候需要小心。
其实这样就完事了，这里的一切其实都好像运行在参数上面，但是这样不用方便使用，我们来为它添加上可以访问到这个序对的左节点(car)和右节点(cdr ,链表中cdr会是除了头节点以外剩下的节点)，再加上计算长度。
template<class left, class right>
struct cons {
using car = left;
using cdr = right;
static int const length = cdr::length + 1; //这里当然是递归了，它会找得到下一层的。
};
template<class left>
struct cons<left, null> {
using car = left;
using cdr = null;
static int const length = 1;
};
接下来要解决list和cons递归体的统一，
template<class head, class ...tail>
struct list_item {
using type = cons<head, typename list_item<tail...>::type>;
};
template<class head>
struct list_item<head> {
using type = cons<head, null>;
};
template<>
struct list_item<null> {
using type = null;
};
为了list和cons巴拉巴拉的真正统一
template<class T, class ...tail> using list = typename list_item<T, tail...>::type;
从此以后所有对list的操作应该都写称对cons巴拉巴体的操作。
二.对链表的操作
四大函数
- 查找链表中的某个值： find_list
- 拷贝链表从start到end：copy_list
- 改变链表中的某个值:：change_list
- 合并两个链表：append
每个函数我们定义它给出的结果是result（是一个类型），实际上这个result会给出新的链表，原来的链表是不会被改变的。
考虑到后面两个可能会基于第一个，那么必然是先写第一个了。
查找链表中的第n个，到底怎么查呢？
别急，我们先模拟一下：比如我们要查找list<555,666,777,888>的第1个 666(第0个是55)
find<1, list<555,666,777,888>>那就是相当于 find<0, list<666,777,888>>, 0是固定找链表的第一个的（给出car就行）那么这样一来递归公式就找到了:
find<n, list> = find<n-1, list::cdr>;
template<int n, class _list> //_list传入诸如cons<num<1>, cons<num<2>, null>>
struct find_list {
using result = typename find_list<n - 1, typename _list::cdr>::result;
};
template<class head>
struct find_list<0, list_item<head>> {
using result = typename list_item<head>::car;
};
template<class _list>
struct find_list<0, _list> {
using result = typename _list::car;
};
那么copy自然是会利用到find的。还是一样，思考原来的例子 list<555,666,777,888>全copy该怎么实现呢
之前说了，result会丢出一个cons的结构体，那么这里必然要用到cons了
copy<0, 2, list<555,666,777,888>> = cons<555，copy<1, 2, list<666,777,888>>>
copy<1, 2, list<666,777,888> = cons<666, copy<2, 2, list<666,777,888>>
copy<2, 2, list<777,888> = cons<777, null> //这里该是null了
答案呼之欲出
template<int start, int end, class _list>
struct copy_list {
using result = cons<typename find_list<start, _list>::result,
typename copy_list<start, end - 1, typename _list::cdr>::result>;
};
template<int start, class _list>
struct copy_list<start, start, _list> {
using result = cons<typename find_list<start, _list>::result, null>;
append一样需要用到cons，
倒不如直接思考传入的是cons的情景：
cons<1, cons<2, null>>想合并 cons<3, cons<4, null>>
想一下发现，list<1,2,3,4>其实就是把cons<1, cons<2, null>>中的null 替换为cons<3, cons<4, null>>
不过这个替换并不容易。再想一下又发现，在cons<3, cons<4, null>>前面包一个数据变成
cons<2 , cons<3, cons<4, null>>也不错，但是实际上从cons<1, cons<2, null>>拆出最里面的也不这么好做
那么只能暴力一点了，直接全拆，先拆第一个cons体，再拆第二个
递归体：
append<cons<1, cons<2, null>>, cons<3, cons<4, null>>>------结果是|=>null
append< cons<2, null>, cons<3, cons<4, null>>>--------------结果是|=>cons<1, null>
append<null , cons<3, cons<4, null>>>-----------------------结果是|=>cons<1, cons<2, null>>
append<null , cons<4, null>>--------------------------------结果是|=>cons<1, cons<2, cons<3,null>>>
append<null , null>>----------------------------------------结果是|=>cons<1, cons<2, cons<3, cons<4, null>>>>
template<class cons1, class cons2>
struct append {
using result = cons<typename cons1::car,
typename append<typename cons1::cdr, cons2>::result>;
};
template<class cons2>
struct append<null, cons2> {
using result = cons<typename cons2::car,
typename append<null, typename cons2::cdr>::result>;
};
template<>
struct append<null, null> {
using result = null;
};
change就写的比较恶心了，当时遇到了访问过界出错，于是生造了一个if结构。
首先change<2, 3, list<555,666,777,888>>给出result为list<555,666,3,888>
怎么change呢，先是copy从0到1，包装3这个数, 然后copy从3到length-1，再把这三个东西组合一下（append）
但是实际上change要分三类，上述所说是change非0非length-1的情况。
change<0 , 某个数 ,list>也简单，但是change<length-1, 某个数 ,list> 必然要提前判断传入的index是不是length -1，如果是，那么给出的结果是cons<某个数, null>
递归体不再赘述……
template<int index, int val, class _list>
struct change_list {
template<bool cond, int index, int length, class _list>
struct if_need_null {};
template<int index, int length, class _list>
struct if_need_null<true, index, length, _list> { using type = null; };
template<int index, int length, class _list>
struct if_need_null<false, index, length, _list> {
using type = typename copy_list<index + 1, length - 1, _list>::result;
};
using result = typename append<typename copy_list<0, index - 1, _list>::result,
cons<num<val>,
typename if_need_null<index == _list::length - 1,
index,
_list::length,
_list>::type>>::result;
};
template<int val, class _list>
struct change_list<0, val, _list> {
using result = typename append<null,
cons<num<val>, typename copy_list<1, _list::length - 1, _list>::result>>::result;
};
