所属分类：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大幅简化函数指针数组、操作实现函数，以及操作符的构造。这些技术和方法可以在大多数需要运行时多态，但又存在大量重复或雷同代码的地方得以应用。