Wrote by mutouyun. (http://darkc.at/cxx-type-list/)

群裡有個朋友要實現這麼一個功能：如何在編譯期把一個函數類型的參數減少一個。
簡單來說，就是實現下面這個模板：

remove_func_par<2, void(int, long, short)>::type; // type = void(int, long)

根據輸入的編譯期整數，把函數參數表裡對應的參數干掉一個。
為了實現這種功能，我們需要操作變參模板的參數包。比如像這樣：

// make function's parameters from the types
 
template 
struct make_func_par;
 
template 
struct make_func_par>
{
    typedef R type(P...);
};
 
// remove function's parameter
 
template 
struct remove_func_par;
 
template 
struct remove_func_par
{
    using erase_pars_t = typename types_erase, N>::type;
    using type = typename make_func_par::type type;
};

上面這段代碼的思想很簡單，把模板參數包的第N個參數刪掉，然後再將它重新展開成函數的參數表。而types的定義可以非常簡單：

template 
struct types {};

如果定義了一組對types類型做操作的算法，那麼我們就可以把參數包放入types中，然後對它做這樣那樣的事情。。

看到這裡，不知道有沒有朋友想起來很久很久以前，Loki庫裡的TypeList。現代的C++當然不需要再像當年那樣用外敷類和繁瑣的宏來實現這個，使用變參模板加模板元就好了。

一、types的判斷和大小計算

有了上面types的定義之後，下面需要實現一些算法來操作它。首先，在不涉及到容器的查找修改時，最基本的算法簡單來說有下面幾個：判斷容器類型（因為容器是編譯期的一個類型）、計算容器大小、判斷容器是否是空的。下面我們來依次實現它們。

判斷算法非常簡單：

/*
    Is types
*/
 
template 
struct is_types
     : std::false_type
{};
 
template 
struct is_types>
     : std::true_type
{};

有了判斷的算法之後，對於後面的運算就可以在編譯時判斷出傳入的類型是否符合要求。我們可以定義一個專門用來判斷類型合法性的模板：

// Check is types or not
 
template 
struct check_is_types
{
    static_assert(is_types::value, "The template parameter is not a types-list!");
};

在需要的時候，繼承check_is_types就好了。
接下來，是計算types的大小。在有了變參模板，以及針對模板參數包的sizeof運算符以後，這個工作也是非常簡單的：

/*
    Return size
*/
 
template 
struct types_size : std::integral_constant
                  , check_is_types
{};
 
template 
struct types_size>
     : std::integral_constant
{};

通過繼承check_is_types，types_size在傳入參數不是一個types的時候，會在編譯時報出錯誤提示。
有了計算types大小的工具，我們可以為後面的算法再准備兩個編譯時合法性判斷的輔助類：

// Check is index valid or not
 
template 
struct check_is_index_valid
{
    static_assert(IndexN >= 0,                        "Index is out of range!");
    static_assert(IndexN < types_size::value, "Index is out of range!");
};
 
// Check is count valid or not
 
template 
struct check_is_count_valid
{
    static_assert(CountN > 0,                          "Count is too small!");
    static_assert(CountN <= types_size::value, "Count is too large!");
};

check_is_index_valid用來判斷傳入的索引是否超出了指定types的范圍；
check_is_count_valid用來判斷傳入的大小是否超出了指定types的大小。
和check_is_types一樣，在需要的時候繼承這兩個類模板就可以了。

然後，是容器是否為空的判斷：

/*
    Test whether types is empty
*/
 
template 
struct types_empty : std::true_type
                   , check_is_types
{};
 
template 
struct types_empty>
     : std::false_type
{};
 
template <>
struct types_empty>
     : std::true_type
{};

二、types的元素訪問

types的訪問算法就是根據傳入的索引（index）定位類型。我們可以先寫下types_at的定義：

template 
struct types_at : check_is_index_valid
{
    using type = TypesT;
};

接下來，是思考如何通過模板元的遞歸定位元素了。在數學裡，最基本的定位方法就是數個數（是的，你沒聽錯，就是數數）。模板元在遞歸的時候，每次可以去掉參數包中開頭的第一個參數，同時我們讓傳入的index減1。當index為0的時候，對應的參數類型就是我們需要的類型了。算法實現可以像這樣：

template 
struct types_at, N>
     : types_at, N - 1>
{};
 
template 
struct types_at, 0>
{
    using type = T1;
};

上面的第一個types_at特化負責把參數包和index同時減1，並傳入下一層；最後模板的遞歸會在第二個types_at特化處終結。
我們看到，這裡並不需要一個types<>的特化。因為當傳入的模板參數是types<>的時候，它不會匹配到任何一個特化，因此最初的types_at定義就可以搞定這種情況了。

有了types_at之後，我們可以很方便的實現front和back的定位算法：

/*
    Access first element
*/
 
template 
struct types_front
{
    using type = types_at_t;
};
 
/*
    Access last element
*/
 
template 
struct types_back
{
    using type = types_at_t::value - 1>;
};

三、types的連接（Link）和分配（Assign）

這兩個算法都是用來把類型打包成types的。

首先我們來考慮類型的連接。需求很簡單，傳入兩個類型，把它們連接成一個types。
當參數是普通類型時的算法很簡單：

template 
struct types_link
{
    using type = types;
};

當兩個類型都是普通類型時，算法是顯然的。那麼當其中一個類型是一個types時，另一個類型應該被追加到那個types的尾部或頭部：

template 
struct types_link, U>
{
    using type = types;
};
 
template 
struct types_link>
{
    using type = types;
};

假如兩個類型都是types類型，那麼需要把它們連接成一個types：

template 
struct types_link, types>
{
    using type = types;
};

我們注意到，上面的link算法裡考慮了當參數是types的情況。因此在做後面的其它算法時，通過使用這裡的link，會把types內部的types展開。

下面是types的Assign算法。需求是，傳入一個數字N和類型T，types_assign將構造一個由N個T組成的types。
有了上面的types_link以後，我們可以在模板遞歸中一次連接一個T，直到N減少到0為止。算法如下：

template 
struct types_assign
{
    static_assert(N >= 0, "N cannot be less than 0!");
private:
    using tail = typename types_assign::type;
public:
    using type = typename types_link::type;
};
 
template 
struct types_assign<0, T>
{
    using type = types<>;
};

由於使用了types_link連接types，當我們這樣寫時：types_assign<2, types>::type，將會得到：types。

四、types的插入和刪除

插入算法的需求如下：
給定一個types，傳入索引index和類型T，需要把T插入到types的index處。根據這個需求，我們可以先寫出types_insert的定義：

template 
struct types_insert : check_is_types
                    , check_is_index_valid
{
    using type = TypesT;
};

接下來考慮算法。插入算法其實只比數數多了一個步驟，那就是在數到需要的位置後，把T插到那個位置。那麼我們可以先寫上數數的算法：

template 
struct types_insert, N, U>
{
private:
    using tail = typename types_insert, N - 1, U>::type;
public:
    using type = typename types_link::type;
};

每次遞歸，都將數出一個參數，並把剩下的繼續向下傳遞。當所有的遞歸完成後，下一層的types_insert將返回一個已插入完畢的types，那麼把這個types當做結尾，和T1連接在一起就好了。
關鍵的插入將在遞歸終結的時候完成：

template 
struct types_insert, 0, U>
{
    using type = typename types_link>::type;
};

待插入的類型U，被插入到types的索引0處，也就是最開始的位置。
這裡需要特殊考慮一下types<>：

template 
struct types_insert, 0, U>
{
    using type = typename types_link>::type;
};

因為若不添加這個特化的話，types<>會被匹配到types_insert的定義上去，那麼types<>將無法插入任何類型了。
可能有童鞋看到這裡，覺得我們沒必要把types和types<>的特化分開寫，直接這樣就好了：

template 
struct types_insert, 0, U>
{
    using type = typename types_link>::type;
};

看起來好像沒問題，但實際上是不行的。這是因為, 0, U>和, N, U>之間存在二義性。當模板遞歸到最後一層時，N將為0，此時若types大小大於1，這兩個特化都可以被匹配到。
而, 0, U>和, N, U>之間則沒有二義性。因為前面的特化版本是後面一個的特殊情況。

這裡也說明了模板元編程時書寫的一個原則：應該從最普遍的特化版本開始，逐一特殊化各種條件，直到最後的遞歸終結。
這種書寫方法可以保證不會出現模板特化的二義性，只是和數學歸納法的思考方向相反。如果習慣於用數學歸納法之類的方式思考模板元遞歸算法的童鞋，可以先正著寫出算法，再倒著看每個條件是否是逐步特殊化的。

下面我們思考刪除算法。需求：
給定一個types，傳入索引index和數量count，需要把types中從索引index處開始的count個元素刪除。
首先，我們還是先寫出定義：

template 
struct types_erase : check_is_types
                   , check_is_index_valid
{
    using type = TypesT;
};

同樣的，刪除算法也是在數到指定索引位置之後，將後面的元素刪除掉。我們可以把count的需求放在一遍，先定位到需要刪除的位置：

template 
struct types_erase, N, C>
{
private:
    using tail = typename types_erase, N - 1, C>::type;
public:
    using type = typename types_link::type;
};

和上面的插入一樣，types_erase在遞歸後將返回一個處理完畢的types，之後把它和T1連起來就好了。
那麼，當找到需要刪除的索引時，我們自然是刪掉它了。為了思考的簡單，我們可以先考慮刪除一個元素的算法：

template 
struct types_erase, 0, 1>
{
    using type = types;
};

當數到需要刪除的位置時，N一定是等於0的。這個時候若count為1，那麼只需要去掉開頭的T1就可以了。那麼連續刪除count個元素就可以這樣寫：

template 
struct types_erase, 0, C>
     : check_is_count_valid, C>
{
    using type = typename types_erase, 0, C - 1>::type;
};

當count不為1時，刪除開頭的T1，將count減1後繼續向下遞歸。當count為1後，將匹配到前一個模板。由於這裡的count可能超出types的界限，因此需要用check_is_count_valid來檢查count的有效性。
現在，我們回過頭來檢查一下，模板的特化條件是否是逐漸收窄的：

, N, C>
, 0, C>
, 0, 1>

那麼是否所有的情況都考慮到了呢？通過枚舉出所有的特化條件，我們發現只有types<>沒有考慮。對於types_erase來說，types<>沒有刪除的意義，因此直接讓它匹配到types_erase的定義就可以了。當然，這會引起一個編譯期的static_assert，因為任何的index都將超出types<>的范圍。

五、types的查找，以及其它算法

查找算法的需求如下：
給定一個types和類型T，需要在types中找到T所在的第一個索引位置。
首先，我們先寫出定義：

template 
struct types_find : std::integral_constant
                  , check_is_types
{};

接著，我們用數學歸納法的方式來思考：
當types中的第一個元素為T時，索引位置為0；（終結條件）
當types中的第N個元素為T時，索引位置為上一個元素的索引加1。

那麼我們可以先列出需要特化的版本：

, T1>
, U>

接下來，先特化終結條件：

template 
struct types_find, T1>
     : std::integral_constant
{};

然後思考一般情況：索引位置為上一個元素的索引加1，說明我們需要做一個加法。而find的結果有兩種：找到了，和沒找到。當沒找到的時候，模板最終會匹配到types_find的定義上去。而我們在定義裡給出的value是-1。因此在做加法運算時，需要把-1的情況忽略掉：

template 
struct types_find, U>
     : std::integral_constant, U>::value == -1 ? -1 :
                              types_find, U>::value + 1)>
{};

有了查找算法以後，判斷types中是否存在某個類型就非常簡單了：

template 
struct types_exist
     : std::integral_constant::value != -1)>
{};

接下來，讓我們思考一個一般化的算法：
逐個遍歷給定types中的元素，當該元素滿足某個條件時，對這個元素做某件事情。
我們可以把定義寫成下面這樣：

template  class If_, typename V,
template  class Do_, typename U>
struct types_do_if : check_is_types
{
    using type = TypesT;
};

If_用來把types中的某個類型T1，和給定的V做判斷；Do_將接受If_的判斷結果，對T1和U一起做某件事（比如置換）。
上面這句話說出來可能有點繞口，實際上寫成代碼並不復雜：

using done = typename Do_::value, U, T1>::type;

我們從這裡可以得到處理後的結果類型done。那麼一般化的算法就是把done和剩下的（T1以外的）元素連起來。需要注意的是，處理是遞歸的，因此最後寫出來應該是這個樣子：

template  class If_, typename V,
template  class Do_, typename U>
struct types_do_if, If_, V, Do_, U>
{
private:
    using tail = typename types_do_if, If_, V, Do_, U>::type;
    using done = typename Do_::value, U, T1>::type;
public:
    using type = typename types_link::type;
};

費這麼大勁寫這個一般化的算法有什麼用呢？下面我們來看看它的威力。

首先，是types的置換算法：
給定一個types，以及類型T，U；要求把所有types中的T都換成U。
有了上面的types_do_if，實現這個算法非常輕松：

template 
struct types_replace
     : types_do_if
{};

當在types中找到類型T的時候，就把它變成U。代碼和語言描述基本是一致的。

接下來，考慮一個移除的算法：
給定一個types，和類型T，要求從types中移除所有的T。
通過types_do_if實現如下：

template 
struct types_remove
     : types_do_if>
{};

我們可以看到，上面std::conditional後面的類型是types<>。原因是types_do_if裡使用types_link連接結果。那麼直接給定一個空的types，它和類型U連接後的結果仍然是U。
看到這裡，我們其實可以寫得更簡單點：

template 
struct types_remove
     : types_replace>
{};

使用types<>置換掉types裡的T，結果和移除是一樣的。
這裡再思考一步：如果需要移除的類型T本身，也是一個types列表，那麼我們可以批量移除掉多個類型。實現算法其實很簡單：

template 
struct types_remove>
{
private:
    using rm_t = typename types_remove::type;
public:
    using type = typename types_remove>::type;
};

從types中取出一個元素做types_remove，把結果和剩下的types放到遞歸裡就可以了。

通過types_do_if還可以實現很多特殊操作，在這裡就不再展開了。
接下來，我們實現types的“壓縮”算法。當types裡有多個重復元素的時候，如何把重復的內容剔除掉，只保留一個呢？
同樣的，我們先寫出定義：

template 
struct types_compact : check_is_types
{
    using type = TypesT;
};

如何判斷內容有重復？其實很簡單，當我們從types中取出一個元素T1，那麼剩下的內容裡，所有的T1都將是重復的，刪掉就可以了。
算法寫出來就是這樣：

template 
struct types_compact>
{
private:
    using rm_t = typename types_remove, T1>::type;
    using tail = typename types_compact::type;
public:
    using type = typename types_link::type;
};

最後，一個特殊且有用的算法是倒序（reverse），即把types中的元素倒過來。實現如下：

template 
struct types_reverse : check_is_types
{
    using type = TypesT;
};
 
template 
struct types_reverse>
{
private:
    using head = typename types_reverse>::type;
public:
    using type = typename types_link::type;
};

每次取出第一個元素，然後把它放到最後面即可。

六、types的排序

在編譯期排序和運行期其實並沒什麼不同，只是算法的選擇上需要考慮一下。假設是從大到小排列，那麼最直觀的想法是每次遞歸都從types中找到最大的元素，然後把它放到頭上去。這樣遞歸完畢後整個types就是有序的了。
這種想法其實就是選擇排序（Selection sort）。
當然，我們也可以實現插入，或者快排。如果讀者感興趣的話，可以自己實現一下。

使用選擇排序，首先需要能從types中找到放在最前面的那個元素。在這裡我們不使用現成的比較算法，而寫成可以讓外部指定比較算法。那麼select的算法定義如下：

template  class If_>
struct types_select_if : check_is_types
{
    using type = TypesT;
};

我們先用數學歸納法思考下算法：
當types中只有1個元素T1時，直接返回T1；（終結條件）
當types中有1個元素以上時，先得到T1以外的其它元素的select結果（S），然後將T1和S一起放入If_中。若If_為true，那麼選擇T1，否則選擇S。

同樣，先列出特化條件：

, If_>
, If_>

然後是它們的實現：

template  class If_>
struct types_select_if, If_>
{
    using type = T1;
};
 
template  class If_>
struct types_select_if, If_>
{
private:
    using select_t = typename types_select_if, If_>::type;
public:
    using type = typename std::conditional::value, T1, select_t>::type;
};

可以看到，代碼和前面歸納法的描述是一致的。
接下來，是排序的實現。首先是定義：

template  class If_>
struct types_sort_if : check_is_types
{
    using type = TypesT;
};

和上面一樣，先用數學歸納法思考下：
當types中只有1個元素T1時，直接返回types；（終結條件）
當types中有1個元素以上時，先得到types的select結果（S），之後從types中刪除S，然後對結果遞歸運算，最後把S連接到頭部。

列出特化條件：

, If_>
, If_>

最後是實現：

template  class If_>
struct types_sort_if, If_>
{
    using type = types;
};
 
template  class If_>
struct types_sort_if, If_>
{
private:
    using types_t = types;
    using sl_t = typename types_select_if::type;
    using er_t = typename types_erase::value>::type;
    using tail = typename types_sort_if::type;
public:
    using type = typename types_link::type;
};

我們來看看排序的效果：

using types_t = types;
 
template 
struct is_large
     : std::integral_constant sizeof(U))>
{};
 
using sort_t = types_sort_if::type;
// sort_t = types

尾聲

實際項目中，我們往往不會像這樣寫這麼多模板元的代碼。如果有類似需求，可能會考慮直接使用Boost.MPL，或者在Loki.TypeList的基礎上加一層變參模板的外敷。

自己完整的實現一次模板元的容器操作算法的意義，在於可以大大加深對模板元編程，以及對變參模板的理解。
有了這些經驗之後，在不方便使用第三方庫時，能夠快速自撸一些簡單且可靠的模板元算法，來完成一些編譯期計算的需求；同時也可以幫助我們更清晰的理解和分析一些C++模板庫（STL、Boost之類）裡的泛型算法。

另外，目前的std::tuple的實現方式其實是類似上面的types的。比如gnuc的libstdc++裡的定義：

// Forward declarations.
template
class tuple;

而目前stl裡對std::tuple的編譯期操作很簡單，只有std::tuple_size和std::tuple_element兩種。如果想增加std::tuple的編譯期運算功能，也可以自行采用上面類似的算法做拓展。

---

完整代碼及測試下載請點擊：types

Wrote by mutouyun. (http://darkc.at/cxx-type-list/)