我們一直強調(diào)把C++模板元編程當做一門圖靈完備的純函數(shù)式語言來學習派歌，為了證明它這種能力厂抽，之前舉的都是類似計算階乘的簡單例子洛心，這里我們通過模板元編程的編譯期計算能力完成一道相對復雜但是有趣的數(shù)學題目沾凄。
數(shù)一數(shù)下圖中一共包含多少個三角形：
答案是24喜滨，你數(shù)對了嗎？
現(xiàn)在我們想用模板元編程來實現(xiàn)一段程序鲜滩，讓計算機來幫我們計算結(jié)果伴鳖，該怎么做节值？
由于模板元編程是一門純函數(shù)式語言徙硅，用它來解決問題需要函數(shù)式編程的思維。函數(shù)式的設計思維和數(shù)學計算是天生最匹配的：變量不可變搞疗，沒有副作用嗓蘑，通過針對問題域構(gòu)建函數(shù)，然后不斷的通過函數(shù)組合來描述領域問題匿乃。
那么如何做呢桩皿？
如上三角形中，我們看到的有點幢炸，直線以及由線構(gòu)成的二維圖形泄隔。針對領域問題建模的時候我們需要選取對解決問題有用的領域概念和屬性。那么哪些概念和屬性對領域問題有用呢宛徊？這時我們采用自頂向下分析佛嬉，將目標問題逐級降解，最后得到最底層的構(gòu)建元素闸天，然后再通過自低向上組合來解決問題暖呕。
我們的目標問題是數(shù)三角形個數(shù)。我們能想到的一種簡單地讓計算機可計算的方法是：遍歷圖中所有三個點的組合苞氮，交給一個函數(shù)讓它來判斷是否是一個三角形湾揽，如果是則累計1，最后就能得到結(jié)果笼吟。
根據(jù)判斷結(jié)果累計并計數(shù)的函數(shù)很容易寫库物，所以我們關(guān)注的焦點轉(zhuǎn)移到如何判斷三個點是否為一個三角形？判斷三個點是否為三角形需要借助已經(jīng)存在的這個圖形贷帮，這個圖形中給出了點和線的關(guān)系戚揭，我們需要依賴這種關(guān)系來判斷三個點是否為圖上存在的一個三角形。
那么我們要提煉哪些概念和關(guān)系來判斷三個點是否為一個三角形呢皿桑？對于上圖毫目，任意三個點是否構(gòu)成一個三角形的判斷方式應該是：三個點兩兩在一條直線上蔬啡，但是三個點不在同一條直線上《婆埃可見我們需要的概念是點和線箱蟆，并且需要構(gòu)建一種關(guān)系，通過這種關(guān)系可以查詢指定的一些點是否在某一條直線上刮便！
為了服務上述目的空猜，我們首先需要點的概念，它的屬性只要一個ID用于區(qū)分不同的點即可恨旱。然后需要有線的概念辈毯，對于線只要知道它上面有哪些點，用于查詢多個點是否在同一條線上搜贤。線不需要有ID或者名字等屬性谆沃，因為經(jīng)過分析這些對于我們要解決的問題域沒有用。
經(jīng)過上述自頂向下的分析仪芒，我們得到以下基本的領域元素：
- 點：需要一個ID或者不重復的名字唁影，用于區(qū)分不同的點；
- 直線：唯一的屬性就是維護哪些點在當前線上掂名；
- 三角形：三個點据沈，它們滿足兩兩相連但是不同時在一條直線上；
有了三角形的定義饺蔑，我們判斷三個點是否為三角形的算法的偽代碼如下：
is_triangle(P1, P2, P3)->
connected(P1, P2) and
connected(P1, p3) and
connected(P2, P3) and
(not in_same_line(P1, P2, P3))
對于上面?zhèn)未a中的算法锌介，再自頂向下分析，可以得到如下子算法：
connected(P1, P2)：判斷兩個點是否被同一條直線相連猾警。針對我們前面對點和線的屬性定義孔祸，這其實就是在判斷由兩個點組成的集合是否為一條線上所有點的集合的子集的算法。in_same_line(P1, P2, P3)：判斷三個點是否在同一條線上肿嘲。和前面一樣融击，本質(zhì)是在判斷由三個點組成的集合是否為一條線上所有點的集合的子集。
可見我們用到的算法抽象到數(shù)學上都是集合運算雳窟。
經(jīng)過上述自頂向下的分析尊浪，我們分解出了解決該問題的領域概念和算法。現(xiàn)在我們來自底向上實現(xiàn)封救。
利用模板元編程來實現(xiàn)拇涤，無非就是在模板元編程中找到合適的語言元素來映射上述分析出來的概念和算法。
首先定義點誉结。我們之前把模板元編程的計算對象已經(jīng)統(tǒng)一到類型上鹅士，那么用來表示點的技術(shù)手段就只有C++的類型。為了簡單我們可以用IntType來表示不同的點惩坑，如用__int(1)掉盅、__int(2)表示不同的點也拜。但是為了讓代碼更具類型安全，以及表達力更好趾痘，我們仿照IntType為點實現(xiàn)一種專門的類型：
// "tlp/samples/triangle/include/Point.h"
template<int N> struct Point{};
#define __p(N) Point<N>
現(xià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__)
現(xiàn)在我們可以用上面的定義來描述圖形了罚攀。如下是我們對前面給出的圖形的描述：
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)));
下來我們可以實現(xiàn)判斷三個點是否為三角形的元函數(shù)了党觅，我們用下面的測試用例表達出我們對該元函數(shù)的期望：
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斋泄。
現(xiàn)在針對__is_triangle的測試用例，我們來考慮它的實現(xiàn)镐牺。它有兩個參數(shù)炫掐，第一個為三個點的集合，第二個為整個Figure（本質(zhì)是一組直線的集合）睬涧。它需要判斷三個點在對應的Figure中是否構(gòu)成一個三角形募胃。
再回到前面給出的這個偽實現(xiàn)：
is_triangle(P1, P2, P3)->
connected(P1, P2) and
connected(P1, p3) and
connected(P2, P3) and
(not in_same_line(P1, P2, P3))
可以看到實現(xiàn)__is_triangle最主要的是如何定義connected和in_same_line。在前面我們分析過這兩個元函數(shù)本質(zhì)上都是在在判斷：入?yún)⒅械狞c的集合是否為Figure中任一直線上所有點的集合的子集畦浓。而這個正好可以直接使用TLP中針對TypeList的Belong元函數(shù)：
__belong()：入?yún)橐粋€list和一個list的集合Lists痹束，判斷l(xiāng)ist是否為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的實現(xiàn)：
// "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的入?yún)⒌谝粋€是Triple夺溢，第二個是Figure论巍。它通過模板特化萃取出Triple中的三個點P1、P2和P3风响，然后調(diào)用內(nèi)部定義的元函數(shù)Connected和InSameLine判斷三個點兩兩相連并且不同時在一條直線上嘉汰。
有了__is_triangle，我們最后來定義數(shù)三角形的算法状勤。我們繼續(xù)用測試用例來描述我們對該元函數(shù)的設計鞋怀。
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，讓它幫我們計算出其中合法的三角形個數(shù)密似。__comb()已經(jīng)被TLP庫實現(xiàn)了攒读，我們直接拿來用。
__comb()：入?yún)閘ist和一個__int(N)辛友，返回由list對于N的所有組合的列表薄扁；
對于__count_triangles的實現(xiàn)應該是遍歷每一個Triples的成員，對其調(diào)用__is_triangle废累，對滿足要求的進行累計邓梅。對一個列表進行累積的通用算法是fold，TLP庫中已經(jīng)有了針對TypeList的fold算法實現(xiàn)了:
__fold(List, Acc, Func(T1, T2))：折疊算法邑滨；將List所有元素按照Func給的算法折疊成一個值返回日缨，Acc是折疊啟動參數(shù)；
我們直接使用__fold來實現(xiàn)__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
至此匣距，我們基本上已經(jīng)實現(xiàn)了這個程序，所有的計算都在C++編譯期完成哎壳，我們通過測試用例對設計結(jié)果進行了校驗毅待。
// "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++編譯器對模板遞歸層數(shù)的限制以及模板的編譯速度尸红，純粹采用元編程來解決問題是比較少見的。模板元編程大多數(shù)場合是為“運行期C++”做服務刹泄，一起結(jié)合來發(fā)揮C++語言的強大威力外里，后面我們將看到這方面的例子。
