我们一直强调把C++模板元编程当做一门图灵完备的纯函数式语言来学习，为了证明它这种能力，之前举的都是类似计算阶乘的简单例子，这里我们通过模板元编程的编译期计算能力完成一道相对复杂但是有趣的数学题目。
数一数下图中一共包含多少个三角形：
答案是24，你数对了吗？
现在我们想用模板元编程来实现一段程序，让计算机来帮我们计算结果，该怎么做？
由于模板元编程是一门纯函数式语言，用它来解决问题需要函数式编程的思维。函数式的设计思维和数学计算是天生最匹配的：变量不可变，没有副作用，通过针对问题域构建函数，然后不断的通过函数组合来描述领域问题。
那么如何做呢？
如上三角形中，我们看到的有点，直线以及由线构成的二维图形。针对领域问题建模的时候我们需要选取对解决问题有用的领域概念和属性。那么哪些概念和属性对领域问题有用呢？这时我们采用自顶向下分析，将目标问题逐级降解，最后得到最底层的构建元素，然后再通过自低向上组合来解决问题。
我们的目标问题是数三角形个数。我们能想到的一种简单地让计算机可计算的方法是：遍历图中所有三个点的组合，交给一个函数让它来判断是否是一个三角形，如果是则累计1，最后就能得到结果。
根据判断结果累计并计数的函数很容易写，所以我们关注的焦点转移到如何判断三个点是否为一个三角形？判断三个点是否为三角形需要借助已经存在的这个图形，这个图形中给出了点和线的关系，我们需要依赖这种关系来判断三个点是否为图上存在的一个三角形。
那么我们要提炼哪些概念和关系来判断三个点是否为一个三角形呢？对于上图，任意三个点是否构成一个三角形的判断方式应该是：三个点两两在一条直线上，但是三个点不在同一条直线上。可见我们需要的概念是点和线，并且需要构建一种关系，通过这种关系可以查询指定的一些点是否在某一条直线上！
为了服务上述目的，我们首先需要点的概念，它的属性只要一个ID用于区分不同的点即可。然后需要有线的概念，对于线只要知道它上面有哪些点，用于查询多个点是否在同一条线上。线不需要有ID或者名字等属性，因为经过分析这些对于我们要解决的问题域没有用。
经过上述自顶向下的分析，我们得到以下基本的领域元素：
- 点：需要一个ID或者不重复的名字，用于区分不同的点；
- 直线：唯一的属性就是维护哪些点在当前线上；
- 三角形：三个点，它们满足两两相连但是不同时在一条直线上；
有了三角形的定义，我们判断三个点是否为三角形的算法的伪代码如下：
is_triangle(P1, P2, P3)->
connected(P1, P2) and
connected(P1, p3) and
connected(P2, P3) and
(not in_same_line(P1, P2, P3))
对于上面伪代码中的算法，再自顶向下分析，可以得到如下子算法：
-
connected(P1, P2)：判断两个点是否被同一条直线相连。针对我们前面对点和线的属性定义，这其实就是在判断由两个点组成的集合是否为一条线上所有点的集合的子集的算法。 -
in_same_line(P1, P2, P3)：判断三个点是否在同一条线上。和前面一样，本质是在判断由三个点组成的集合是否为一条线上所有点的集合的子集。
可见我们用到的算法抽象到数学上都是集合运算。
经过上述自顶向下的分析，我们分解出了解决该问题的领域概念和算法。现在我们来自底向上实现。
利用模板元编程来实现，无非就是在模板元编程中找到合适的语言元素来映射上述分析出来的概念和算法。
首先定义点。我们之前把模板元编程的计算对象已经统一到类型上，那么用来表示点的技术手段就只有C++的类型。为了简单我们可以用IntType来表示不同的点，如用__int(1)、__int(2)表示不同的点。但是为了让代码更具类型安全，以及表达力更好，我们仿照IntType为点实现一种专门的类型：
// "tlp/samples/triangle/include/Point.h"
template<int N> struct Point{};
#define __p(N) Point<N>
现在我们可以用Point<1>、Point<2>或者__p(1)、__p(2)来表示不同的点了。
接下来我们来定义线，一条线就是在线上所有点的集合。既然点在C++模板元编程中用类型表示，那么点的集合就是一组类型的集合，我们用之前介绍过的TypeList来表示。
#define __line(...) __type_list(__VA_ARGS__)
同时我们可以用TypeList表示一组点，或者一组线，为了让表达力更好，我们给出如下别名定义：
#define __points(...) __type_list(__VA_ARGS__)
#define __lines(...) __type_list(__VA_ARGS__)
现在我们可以用上面的定义来描述图形了。如下是我们对前面给出的图形的描述：
using Figure = __lines( __line(__p(1), __p(2), __p(8))
, __line(__p(1), __p(3), __p(7), __p(9))
, __line(__p(1), __p(4), __p(6), __p(10))
, __line(__p(1), __p(5), __p(11))
, __line(__p(2), __p(3), __p(4), __p(5))
, __line(__p(8), __p(7), __p(6), __p(5))
, __line(__p(8), __p(9), __p(10), __p(11)));
下来我们可以实现判断三个点是否为三角形的元函数了，我们用下面的测试用例表达出我们对该元函数的期望：
TEST("test triangle")
{
ASSERT_TRUE(__is_triangle(__triple(__p(1), __p(2), __p(3)), Figure));
ASSERT_FALSE(__is_triangle(__triple(__p(1), __p(2), __p(8)), Figure));
};
上面的__triple是三个点的集合，它的定义如下：
// "tlp/samples/triangle/include/Triple.h"
__func_forward_3(Triple, __type_list(_1, _2, _3));
#define __triple(...) Triple<__VA_ARGS__>
可见__triple只不过是限定长度为3的TypeList。
现在针对__is_triangle的测试用例，我们来考虑它的实现。它有两个参数，第一个为三个点的集合，第二个为整个Figure（本质是一组直线的集合）。它需要判断三个点在对应的Figure中是否构成一个三角形。
再回到前面给出的这个伪实现：
is_triangle(P1, P2, P3)->
connected(P1, P2) and
connected(P1, p3) and
connected(P2, P3) and
(not in_same_line(P1, P2, P3))
可以看到实现__is_triangle最主要的是如何定义connected和in_same_line。在前面我们分析过这两个元函数本质上都是在在判断：入参中的点的集合是否为Figure中任一直线上所有点的集合的子集。而这个正好可以直接使用TLP中针对TypeList的Belong元函数：
__belong()：入参为一个list和一个list的集合Lists，判断list是否为Lists集合中任一元素的子集，返回BoolType；
TEST("sublist belongs to lists")
{
using Lists = __type_list( __value_list(1, 2)
, __value_list(2, 3));
ASSERT_TRUE(__belong(__value_list(2, 3), Lists));
ASSERT_TRUE(__belong(__value_list(3), Lists));
ASSERT_FALSE(__belong(__value_list(1, 3), Lists));
};
OK，分析至此，我们给出__is_triangle的实现：
// "tlp/samples/triangle/include/IsTriangle.h"
template<typename Triple, typename Figure> struct IsTriangle;
template<typename P1, typename P2, typename P3, typename Figure>
struct IsTriangle<__type_elem(P1, __type_elem(P2, __type_elem(P3, __null()))), Figure>
{
private:
__func_forward_2(Connected, __belong(__points(_1, _2), Figure));
__func_forward_3(InSameLine, __belong(__points(_1, _2, _3), Figure));
public:
using Result = __and( Connected<P1, P2>
, __and(Connected<P2, P3>
, __and(Connected<P3, P1>, __not(InSameLine<P1, P2, P3>))));
};
#define __is_triangle(...) typename IsTriangle<__VA_ARGS__>::Result
上面IsTriangle的入参第一个是Triple，第二个是Figure。它通过模板特化萃取出Triple中的三个点P1、P2和P3，然后调用内部定义的元函数Connected和InSameLine判断三个点两两相连并且不同时在一条直线上。
有了__is_triangle，我们最后来定义数三角形的算法。我们继续用测试用例来描述我们对该元函数的设计。
TEST("count triangles")
{
using Points = __points( __p(1), __p(2), __p(3), __p(4), __p(5), __p(6), __p(7), __p(8), __p(9), __p(10), __p(11));
using Triples = __comb(Points, __int(3));
ASSERT_EQ(__count_triangles(Triples, Figure), __int(24));
};
上面测试用例中我们先获得所有三个点的组合using Triples = __comb(Points, __int(3))，然后把所有的三个点的列表和Figure传递给__count_triangles，让它帮我们计算出其中合法的三角形个数。__comb()已经被TLP库实现了，我们直接拿来用。
__comb()：入参为list和一个__int(N)，返回由list对于N的所有组合的列表；
对于__count_triangles的实现应该是遍历每一个Triples的成员，对其调用__is_triangle，对满足要求的进行累计。对一个列表进行累积的通用算法是fold，TLP库中已经有了针对TypeList的fold算法实现了:
__fold(List, Acc, Func(T1, T2))：折叠算法；将List所有元素按照Func给的算法折叠成一个值返回，Acc是折叠启动参数；
我们直接使用__fold来实现__count_triangles。
// "tlp/samples/triangle/include/CountTriangles.h"
template<typename Triples, typename Lines>
struct CountTriangles
{
private:
template<typename Sum, typename Triple>
struct Count
{
using Result = __if(__is_triangle(Triple, Lines), __add(Sum, __int(1)), Sum);
};
public:
using Result = __fold(Triples, __int(0), Count);
};
#define __count_triangles(...) typename CountTriangles<__VA_ARGS__>::Result
至此，我们基本上已经实现了这个程序，所有的计算都在C++编译期完成，我们通过测试用例对设计结果进行了校验。
// "tlp/samples/triangle/test/TestTriangle.h"
FIXTURE(TestTriangle)
{
using Figure = __lines( __line(__p(1), __p(2), __p(8))
, __line(__p(1), __p(3), __p(7), __p(9))
, __line(__p(1), __p(4), __p(6), __p(10))
, __line(__p(1), __p(5), __p(11))
, __line(__p(2), __p(3), __p(4), __p(5))
, __line(__p(8), __p(7), __p(6), __p(5))
, __line(__p(8), __p(9), __p(10), __p(11)));
TEST("test a triple whether a triangle")
{
ASSERT_TRUE(__is_triangle(__triple(__p(1), __p(2), __p(3)), Figure));
ASSERT_FALSE(__is_triangle(__triple(__p(1), __p(2), __p(8)), Figure));
};
TEST("count triangles")
{
using Points = __points( __p(1), __p(2), __p(3), __p(4), __p(5), __p(6), __p(7), __p(8), __p(9), __p(10), __p(11));
using Triples = __comb(Points, __int(3));
ASSERT_EQ(__count_triangles(Triples, Figure), __int(24));
};
}
使用模板元编程做计算的介绍就到这里。受限于模板元编程IO能力的缺失，以及C++编译器对模板递归层数的限制以及模板的编译速度，纯粹采用元编程来解决问题是比较少见的。模板元编程大多数场合是为“运行期C++”做服务，一起结合来发挥C++语言的强大威力，后面我们将看到这方面的例子。
网友评论