所屬分類：C/C++ C++ 語言
-----------------------------------------

優化variant實現
上一次，我大概制作了一個variant類型，并設法賦予這個類型同C++內置類型幾乎一樣的行為。但是，具體實現起來，倒是有點望而生畏。想想看，如果我的variant需要包容5種類型，那么單單一個操作符，就需要5×5+1=26個操作符重載（那單獨一個是variant類型操作數的重載）。所有二元操作符都是如此。
通過蠻力來實現variant，盡管可能，但著實愚蠢。我們必須尋找更簡單有效的實現途徑，避免為了一個“屁眼大的”variant（請原諒我說粗話）寫上幾萬行代碼，而且這些代碼就像一窩小豬仔那樣相像。好在C++為我們提供了充足的現代武器，使我們擁有足夠的火力擺平這些問題。
讓我們先從操作數都是variant的二元操作符入手：
variant  operator+( const variant& v1, const variant& v2) {…}
…
簡單起見，先考察operator+的實現，然后擴展到其他操作符。
由于操作數是variant類型，那么它們可能代表不同的類型。我們必須知道操作數的實際類型，才能對其實施相應的+操作。最傳統的辦法就是使用switch：
variant operator+(const variant& v1, const variant& v2) {
switch(v1.get_type_code())
{
case vt_double:
switch(v2.get_type_code())
{
case vt_double:
…;
break;
…
}
case vt_int:
switch(v2.get_type_code())
{
case vt_double:
…;
break;
…
}
…
}
}
好家伙，又是一個組合爆炸。一步步來，我們先來處理這堆討人嫌的switch…case…。一般而言，對于一個函數（操作符）內的的大量分派操作，可以使用包含函數指針的數組或者容器替代。如果標記值（這里的vt_...）是連續的，可以直接使用數組；如果標記值不連續，可以使用關聯容器。這里vt_...是連續的，所以用數組比較方便：
typedef variant (*add_op_t)(const variant& v1, const variant& v2);
add_op_t tbl_type_ops[3][3];//函數指針表，假設variant對應三種類型
variant add_op_double_double(const variant& v1, const variant& v2){…}
variant add_op_double_int(const variant& v1, const variant& v2){…}
…
variant add_op_int_double(const variant& v1, const variant& v2){…}
…
tbl_type_ops [vt_double][vt_double]=add_op_double_double;
tbl_type_ops [vt_double][vt_int]=add_op_double_int;
…
variant operator+(const variant& v1, const variant& v2) {
returntbl_type_ops [v1.get_type_code()][v2.get_type_code](v1, v2);
}
operator+的代碼是簡單了，但是它的代碼實際上轉嫁到每個專用操作函數add_op_...上去了。并沒有簡化多少。下一步，我們來處理這些add_op_...：
template<typename VT1, typename VT2>
variant add_op(const variant& v1, const variant&v2) {
throwexception(string(“cannot add type ”)+typeid(VT1).typename()
+”to”+typeid(VT2).typename());
}//主函數模板，對應不兼容類型的操作。拋出異常。
template<>
variant<double, double> add_op(const variant& v1, const variant&v2) {
returnvariant(v1.dbval+v2.dbval);
}//針對double+double的操作
…
tbl_type_ops [vt_double][vt_double]=add_op<double, double>;
tbl_type_ops [vt_double][vt_int]=add_op<double,int>;
…
利用函數模板，及其特化，消化掉一部分的冗余代碼。利用主函數模板實現所有不能互操作的類型操作，而可操作的類型則使用特化的模板實現。當然，冗余代碼還是存在，這部分我們一會兒再處理。先來看看tbl_type_ops的填充。這部分代碼也存在組合爆炸。為消除這個問題，我請出了模板元編程（TMP）。當然，我沒有那么好的本事去直接倒騰TMP，我“借用”了boost::mpl::vector來實現這步優化：
//使用mpl::vector存放variant包容的類型
typedef boost::mpl::vector<double, int, string>op_types;
const int n_types=boost::mpl::size<op_types>::value;
//操作函數指針表
typedef variant (*add_op_t)(const variant& v1, const variant& v2);
add_op_t tbl_type_ops[n_types][n_types];
//填充函數指針表單個元素
template<int m, int n>
inline void set_tbl_type() {
typedefmpl::deref<mpl::advance<mpl::begin<op_types>::type, 
mpl::int_<m> >::type>::typetype_1;
typedefmpl::deref<mpl::advance<mpl::begin<op_types>::type, 
mpl::int_<n> >::type>::typetype_2;

tbl_type_ops [m][n]=add_op<type_1, type_2>;
}
//填充函數指針表單元的函數對象類
template<int m, int n>
struct fill_tbl_types_n
{
void operator()() {
set_tbl_type<m-1, n-1>();//填充函數指針單元
fill_tbl_types_n<m, n-1>()();//遞歸
}
};
template<int m>
struct fill_tbl_types_n<m, 0>//特化，遞歸結束
{
void operator()() {}
};
//填充函數指針表行的函數對象類
template<int m, int n>
struct fill_tbl_types_m
{
void operator()() {
fill_tbl_types_n<m, n>()();//創建并調用fill_tbl_types_n函數對象
fill_tbl_types_m<m-1, n>()();//遞歸
}
};
template<int n>
struct fill_tbl_types_m<0, n>//特化，遞歸結束
{
void operator()() {}
};
void fill_tbl_op() {
fill_tbl_types_m<n_types, n_types>()();
}
這里運用函數對象類模板的特化，構造了函數指針表的填充自動函數。在需要時，只需調用fill_tbl_op()函數即可。該函數中創建fill_tbl_types_m<n_types, n_types>函數對象，然后調用。這個函數對象的operator()首先創建并調用fill_tbl_types_n<m, n>函數對象。后者先調用set_tbl_type<m-1, n-1>模板函數，執行填充tbl_type_op數組的[m-1, n-1]單元格。然后遞歸調用fill_tbl_types_n<m, n-1>函數對象。直到n-1==0，編譯器便會選擇特化版本的fill_tbl_types_n<m, 0>函數對象。該特化的operator()操作符重載是空的，因此遞歸結束。這樣完成一行的填充。然后，fill_tbl_types_m<m, n>則遞歸調用fill_tbl_types_m<m-1, n>函數對象，填充下一行。直到調用fill_tbl_types_m<0, n>特化版本，結束遞歸。
現在需要仔細看一下set_tbl_type<>函數模板。該模板上來就是兩個typedef。這兩個typedef創建了兩個類型別名，分別用m和n做索引，從boost::mpl::vector<double, int, string>中取出相應的類型：
typedefmpl::deref<mpl::advance<mpl::begin<op_types>::type, 
mpl::int_<m> >::type>::typetype_1;
…
頭暈是吧。我的頭還有點暈呢。這就是模板元編程，不停地鼓搗類型。具體的操作可以參考boost文檔或《The Template Meta-programming》一書，我這里就不多說了，反正就是從一個存放類型的vector中取出所需的類型。
這樣獲得的兩個類型用來實例化add_op<>()模板函數，并且填充到tbl_type_ops[m][n]元素中。
這樣，利用TMP和GP兩種強大的機制，消除了tbl_type_ops填充的組合爆炸問題。如果我們需要向variant中加入新的類型，那么只需在mpl::vector<double, int, string>中直接加入類型即可：
typedef mpl::vector<double, int, string, bool, datetime>op_types;
OK，下面回過頭，來處理add_op<>中存在的組合爆炸。對于每一對可以直接或間接相加的類型，都需要做一個add_op<>的特化版本。這當然不夠好。我們可以進一步抽象add_op，然后加以優化。我把整個add_op<>模板改寫成如下代碼：
template<typename VT1, typename VT2>
variant add_op(const variant& v1, const variant& v2) {
typedeftype_ret<VT1, VT2>::typeRetT;
returnvariant(v1.operator RetT()+v2.operator RetT());
}
這里，我首先利用type_ret模板（模板元函數）獲得兩個操作數相加后應有的返回類型。這個模板一會說明。然后，調用variant上的類型轉換操作符，將兩個操作數轉換成返回類型。最后相加，并創建返回variant對象。代碼非常簡單，沒法再簡單了。
再來看看type_ret<>：
template<typename T1, typename T2>
struct type_ret
{
typedefT1type;
};
template<>
struct type_ret<int, double>
{
typedefdoubletype;
};
template<>
struct type_ret<string, double>
{
typedefdoubletype;
};
…//其他類型對的返回類型
type_ret<>是典型的模板元函數，沒有任何實際代碼，只有編譯時計算的typedef。主模板將第一個類型參數typedef出一個別名。其后的模板特化對于一些特殊的情況做出定義，如int和double相加返回第二個操作數類型double（即所謂的類型提升）。
我們現在已經優化了variant+varint的代碼。現在來看看如何優化variant類型和其他類型的加法：
template<typename T>
variant operator+(const variant& v1, const T& v2) {
returnv1+variant(v2);
}
template<typename T>
variant operator+(const T& v1, const variant& v2) {
returnvariant(v1)+v2;
}
這非常簡單，直接利用了variant+variant，將其它類型的操作數轉換成variant類型，然后相加。


----------------------------------------------------------------------

好，加法完成了。但還有其他操作符。每個操作符都做那么一個函數指針表，也不見得高明到哪里去。現在需要整合優化這些操作符。這里，我想到了兩種方法：一種是將函數指針表和填充操作整個地封裝在一個模板中，模板參數采用int op形式。每一種操作符對應一個整數（或枚舉值），并利用某種手段（如singleton）唯一生成一組全局的函數表，以此處理每一種操作。另一種方法是為函數指針表加一個維度（二維擴展到三維），新的維度對應不同的操作符。前一種方法靈活性強些，而且有利于性能優化；而后一種方法實現簡單。這里我使用后一種方法：
enum
{
vt_op_add=0,
vt_op_add_assign=1,
vt_op_equal=2,
vt_op_not_equal=3
…
};
const int vt_op_num=10;

template<typename T, int op>
struct var_op;

template<typename T>
struct var_op<T, vt_op_add>
{
T operator()(const T& v1, const T& v2) {
returnv1+v1;
}
}

template<typename T>
struct var_op<T, vt_op_equal>
{
bool operator()(const T& v1, const T& v2) {
returnv1==v1;
}
}
…
template<typename VT1, typename VT2, int op>
variant variant_op(const variant& v1, const variant& v2) {
typedeftype_ret<VT1, VT2>::typeRetT;
returnvariant(var_op<RetT,op>()(v1.operator RetT()+v2.operator RetT()));
}
我使用了一個函數對象模板var_op<>抽象各種算法（二元）。針對每一種運算符特化。抽象的variant_op函數模板實例化var_op<>，然后調用。獲得相應的操作。
觀察variant_op的模板參數，會發現已經包含了一個操作的基本要素。（眼下這個形式正好符合逆波蘭表達式）。
接下來，只需將函數指針數組，及其填充算法加以擴展，便可大功告成：
add_op_t tbl_type_ops[n_types][n_types][vt_op_num];
//填充函數指針表單個元素
template<int m, int n, int op>
inline void set_tbl_type() {
typedefmpl::deref<mpl::advance<mpl::begin<op_types>::type, 
mpl::int_<m> >::type>::typetype_1;
typedefmpl::deref<mpl::advance<mpl::begin<op_types>::type, 
mpl::int_<n> >::type>::typetype_2;

tbl_type_ops [m][n][op]=add_op<type_1, type_2, op>;
}

template<int m, int n, int op>
struct fill_tbl_types_op
{
void operator()() {
set_tbl_type<m-1, n-1, op-1>();
fill_tbl_types_op<m, n, op-1>()();//遞歸
}
};
template<int m, int n>
struct fill_tbl_types_op<m, n, 0>//特化，遞歸結束
{
void operator()(){}
}

template<int m, int n, int op>
struct fill_tbl_types_n
{
void operator()() {
fill_tbl_types_op<m, n, op>();
fill_tbl_types_n<m, n-1, op>()();//遞歸
}
};
template<int m, int op>
struct fill_tbl_types_n<m, 0, op>//特化，遞歸結束
{
void operator()() {}
};

template<int m, int n, int op>
struct fill_tbl_types_m
{
void operator()() {
fill_tbl_types_n<m, n, op>()();
fill_tbl_types_m<m-1, n, op>()();//遞歸
}
};
template<int n, int op>
struct fill_tbl_types_m<0, n, op>//特化，遞歸結束
{
void operator()() {}
};

void fill_tbl_op() {
fill_tbl_types_m<n_types, n_types, vt_op_num>()();
}

template<typename RetT, int op>
struct var_oper
{
RetT operator()(const variant& v1, const variant& v2) {
returntbl_type_ops [v1.get_type_code()][v2.get_type_code]
[op](v1, v2).operator RetT();
}
template<int op>
struct var_oper<variant, op>
{
variant operator()(const variant& v1, const variant& v2) {
returntbl_type_ops [v1.get_type_code()][v2.get_type_code]
[op](v1, v2);
}
于是操作符的實現，成了以下形式：
variant operator+(const variant& v1, const variant& v2) {
returnvar_oper<variant, vt_op_add>(v1, v2);
}
bool operator==(const variant& v1, const variant& v2) {
returnvar_oper<bool, vt_op_equal>(v1, v2);
}
…
如果還覺得復雜，那么可以進一步使用宏做一些包裝。
好了，variant的優化基本上完成了。當然還會有一些方面值得我們去進一步地優化，比如可以利用boost的type traits和標準庫的limit優化type_ret模板的實現和類型轉換操作的實現等等。這里不再贅述。
需要說明的是，整個優化僅僅針對代碼，并未考慮性能問題。在優化的過程中，某些手法的使用實際上降低的性能。比如函數指針表存在間接調用，不如直接使用inline函數來的高效。而且，函數指針表要求所有指向的函數必須以相同的類型返回。為了兼容+、-等操作，我使用了值返回。但對于+=等操作符完全可以利用引用返回，以提升性能。如果要解決這種問題，需要用前面提到的模板封裝函數指針表的方案，為每一個操作符創建一個函數指針表加以解決。
另一個性能問題主要是在variant與其它類型的操作中，其它類型轉換成variant類型然后再計算。比起直接使用目標類型計算慢不少。這個問題也可以利用GP和TMP消除，但代碼會復雜不少。
理論上，利用inline和編譯器優化，可以消除大部分性能問題。但不是所有的，函數指針表的間接調用，是無論如何也優化不掉的。
此外，我在實現函數指針表的構造算法時，沒有使用函數模板，而是使用了函數對象模板（重載operator()的模板）。這是因為函數模板目前不能局部特化，而這里是必須的。另一方面，由于使用了遞歸，函數模板無法做到inline()，而使用函數對象模板則不會有此限制。表達式fill_tbl_types_m()();最終（優化）編譯后的結果會是這樣（偽碼）：
tbl_type_ops [2][2][0]=add_op<string, string, 0>;
tbl_type_ops [2][1][0]=add_op<string, int, 0>;
…
tbl_type_ops [1][2][0]=add_op<int, string, 0>;
…
遞歸和函數對象的調用沒有了，完全inline化了。inline函數有時卻無法做到這一點。而fill_tbl_types_op等模板實際上起到了代碼生成器的作用。這也是GP的一個鮮為人知的功能。如果你有一大堆代碼需要編寫，而這些代碼有很強的規律性和重復性，那么請優先考慮使用模板來為你生成代碼，又快又好。
該總結了。如果審視一些代碼，會發現只要存在重復和規律性，我們總能利用一些技術和方法加以優化，減少代碼量，簡化代碼結構，減少潛在錯誤，最終提高開發效率。這里，我使用了C++的泛型編程和模板元編程技術，大幅優化了variant類型中的大量冗余代碼。并且為variant類型構建了一個靈活，而又易于擴充的結構。此類技術有很廣的應用，不僅僅局限在variant這種底層構件中。相關的一個應用就是構造抽象類工廠，在《Modren C++ Design》一書中，有很完整的案例。
此外，這類技術對于調和運行時多態（OOP）和編譯時多態（GP）的矛盾有很大的作用。variant只有在運行時方能確定其具體的類型，而C++的模板只能提供編譯時的GP。我利用函數指針數組（當然在更復雜的應用中，可以利用OOP的動多態機制），實現運行時分派操作。而利用GP和TMP大幅簡化函數指針數組、操作實現函數，以及操作符的構造。這些技術和方法可以在大多數需要運行時多態，但又存在大量重復或雷同代碼的地方得以應用。