有了list的结构定义，我们就可以为其定义相关算法了。由于list是递归结构，所以其算法也都是递归算法。
一般情况下递归算法的设计和数学归纳法比较类似，基本套路是先定义出算法中最显而易见的值的结果（也就是递归结束条件），然后假设算法对“n - 1”已经可计算，再用其描述出对于“n”的算法。
对于用惯了使用命令式语言中循环语句（如C语言中while、for）的程序员，刚开始接触和设计递归算法往往不是那么得心应手，但是相信通过刻意练习绝对是可以掌握这种思维方法的。
下面，我们首先实现求list长度的元函数Length。
// "tlp/list/algo/Length.h"
template<typename TL> struct Length;
template<>
struct Length<NullType>
{
using Result = IntType<0>;
};
template<typename Head, typename Tail>
struct Length<TypeElem<Head, Tail>>
{
using Result = typename Add<IntType<1>, typename Length<Tail>::Result>::Result;
};
#define __length(...) typename Length<__VA_ARGS__>::Result
对Length，我们首先定义出空list的值为0。对于非空list，我们假设Length<Tail>已经计算出来了，那么整个list的长度就是Length<Tail>的结果再加一。
测试如下：
TEST("get the length of type list")
{
ASSERT_EQ(__length(__type_list(int, char, short)), __int(3));
};
接下来我们来实现元函数TypeAt，给它一个list和一个index，它将返回对应list中index位置的元素。如果index非法，或者list为空，则返回__null()。
// "tlp/list/algo/TypeAt.h"
template<typename TL, typename Index> struct TypeAt;
template<int V>
struct TypeAt<NullType, IntType<V>>
{
using Result = NullType;
};
template<typename H, typename T>
struct TypeAt<TypeElem<H, T>, IntType<0>>
{
using Result = H;
};
template<typename H, typename T, int i>
struct TypeAt<TypeElem<H, T>, IntType<i>>
{
using Result = typename TypeAt<T , IntType<i - 1>>::Result;
};
#define __at(...) typename TypeAt<__VA_ARGS__>::Result
如上，先定义出对于空list，返回NullType；然后定义当index是0则返回当前list头元素。最后定义当list非空，且index不为0的情况，就是返回剩余元素list中的第i - 1个元素。
针对它的测试如下：
TEST("get null from list by overflow index")
{
using List = __type_list(int, char, short, long);
ASSERT_INVALID(__at(List, __int(4)));
};
TEST("get the type by index")
{
using List = __type_list(int, char, short, long);
ASSERT_EQ(__at(List, __int(2)), short);
};
借助__index_of()我们可以实现出判断某一元素是否在list中的元函数__is_included()。
#define __is_included(...) __valid(__index_of(__VA_ARGS__))
TEST("estimate a type whether included in a list")
{
using List = __type_list(int, short, long);
ASSERT_TRUE(__is_included(List, int));
ASSERT_FALSE(__is_included(List, char));
};
掌握了递归算法的设计技巧，类似地可以轻松实现__append()元函数，它的入参为list和类型T；它返回一个在入参list尾部追加类型T之后的新list；
// "tlp/list/algo/Append.h"
template<typename TL, typename T> struct Append;
template<>
struct Append<NullType, NullType>
{
using Result = NullType;
};
template<typename T>
struct Append<NullType, T>
{
using Result = typename TypeList<T>::Result;
};
template<typename H, typename T>
struct Append<NullType, TypeElem<H, T>>
{
using Result = TypeElem<H, T>;
};
template<typename Head, typename Tail, typename T>
struct Append<TypeElem<Head, Tail>, T>
{
using Result = TypeElem<Head, typename Append<Tail, T>::Result>;
};
#define __append(...) typename Append<__VA_ARGS__>::Result
针对__append()元函数的测试如下：
TEST("append a type to an empty list")
{
ASSERT_EQ(__append(__empty_list(), char), __type_list(char));
};
TEST("append a list to an empty list")
{
using List = __type_list(int, char);
ASSERT_EQ(__append(__empty_list(), List), List);
};
TEST("append an empty list_to a list")
{
using List = __type_list(int, char);
ASSERT_EQ(__append(List, __empty_list()), List);
};
TEST("append a type to a list")
{
using List = __type_list(int, short);
using Expected = __type_list(int, short, long);
ASSERT_EQ(__append(List, long), Expected);
};
TEST("append a list to a list")
{
using List = __type_list(int, short);
using Expected = __type_list(int, short, char, long);
ASSERT_EQ(__append(List, __type_list(char, long)), Expected);
};
上面测试用例中出现的__empty_list()的定义如下：
// "tlp/list/EmptyList.h"
using EmptyList = NullType;
#define __empty_list() EmptyList
关于基本算法的实现就介绍到这里。TLP库中一共实现了关于list的如下基本元函数：
-
__length()：入参为list，返回list的长度； -
__at()：入参为list和index，返回list中第index个位置的元素； -
__index_of()：入参为list和类型T，返回list中出现的第一个T的index位置；如果不存在则返回__null(); -
__is_included()：入参为list和类型T，判断T是否在list中；返回对应的BoolType； -
__append()：入参为list和类型T，返回一个新的list。新的list为入参list尾部追加类型T之后的list； -
__erase()：入参为list和类型T，返回一个新的list。新的list为入参list删除第一个出现的类型T之后的list； -
__erase_all()：入参为list和类型T，返回一个新的list。新的list为入参list删除所有出现的类型T之后的list； -
__unique()：入参为一个list，返回一个去除所有重复元素后的新的list。 -
__replace()：入参为list和两个类型T，U；返回一个将list中出现的第一个T替换成U之后的新list； -
__replace_all()：入参为list和两个类型T，U；返回一个将list中出现的所有T替换成U之后的新list； -
__is_subset()：入参为两个list，判断前一个list是否为后一个的子集，返回BoolType； -
__belong()：入参为一个list和一个list的集合Lists，判断list是否为Lists集合中任一元素的子集，返回BoolType； -
__comb()：入参为list和一个__int(N)，返回由list对于N的所有排列组合的列表；
网友评论