2. 模板元编程基础

2.1 编程,元编程,模板元编程

技术的学习是一个登山的过程。第一章是最为平坦的山脚道路。而从这一章开始,则是正式的爬坡。无论是我写作还是你阅读,都需要付出比第一章更多的代价。那么问题就是,付出更多的精力学习模板是否值得?

这个问题很功利,但是一阵见血。因为技术的根本目的在于解决需求。那C++的模板能做什么?

一个高(树)大(新)上(蜂)的回答是,C++里面的模板,犹如C中的宏、C#和Java中的自省(restropection)和反射(reflection)一样,是一个改变语言内涵,拓展语言外延的存在。

程序最根本的目的是什么?复现真实世界或人所构想的规律,减少重复工作的成本,或通过提升规模完成人所不能及之事。但是世间之事万千,有限的程序如何重现复杂的世界呢?

答案是“抽象”。论及具体手段,无外乎“求同”与“存异”:概括一般规律,处理特殊情况。这也是软件工程所追求的目标。一般规律概括的越好,我们所付出的劳动也就越少。

同样的,作为脑力劳动的产品,程序本身也是有规律性的。《Modern C++ Design》中的前言就抛出了一连串有代表性的问题:

如何撰写更高级的C++程式?
如何应付即使在很干净的设计中仍然像雪崩一样的不相干细节?
如何构建可复用组件,使得每次在不同程式中应用组件时无需大动干戈?

我们以数据结构举例。在程序里,你需要一些堆栈。这个堆栈的元素可能是整数、浮点或者别的什么类型。一份整型堆栈的代码可能是:

class StackInt
{
public:
    void push(Int v);
    Int pop();
    Int Find(Int x)
    {
        for(Int i = 1; i <= size; )
        {
            if(data[i] == x) { return i; }
        }
    }
    // ... 其他代码 ...
};

如果你要支持浮点了,那么你只能将代码再次拷贝出来,并作如下修改:

class StackFloat
{
public:
    void push(Float v);
    Float pop();
    Int Find(Float x)
    {
        for(Int i = 1; i <= size; )
        {
            if(data[i] == x) { return i; }
        }
    }
    // ... 其他代码 ...
};

当然也许你觉得这样做能充分体会代码行数增长的成就感。但是有一天,你突然发现:呀,Find 函数实现有问题了。怎么办?这个时候也许你只有两份这样的代码,那好说,一一去修正就好了。如果你有十个呢?二十个?五十个?

时间一长,你就厌倦了这样的生活。你觉得每个堆栈都差不多,但是又有点不一样。为了这一点点不一样,你付出了太多的时间。吃饭的时间,泡妞的时间,睡觉的时间,看岛国小电影顺便练习小臂力量的时间。

于是便诞生了新的技术,来消解我们的烦恼。

这个技术的名字,并不叫“模板”,而是叫“元编程”。

元(meta)无论在中文还是英文里,都是个很“抽象(abstract)”的词。因为它的本意就是“抽象”。元编程,也可以说就是“编程的抽象”。用更好理解的说法,元编程意味着你撰写一段程序A,程序A会运行后生成另外一个程序B,程序B才是真正实现功能的程序。那么这个时候程序A可以称作程序B的元程序,撰写程序A的过程,就称之为“元编程”。

回到我们的堆栈的例子。真正执行功能的,其实仍然是浮点的堆栈、整数的堆栈、各种你所需要的类型的堆栈。但是因为这些堆栈之间太相似了,仅仅有着些微的不同,我们为什么不能有一个将相似之处囊括起来,同时又能分别体现出不同之处的程序呢?很多语言都提供了这样的机会。C中的宏,C++中的模板,Python中的Duck Typing,广义上将都能够实现我们的思路。

我们的目的,是找出程序之间的相似性,进行“元编程”。而在C++中,元编程的手段,可以是宏,也可以是模板。

宏的例子姑且不论,我们来看一看模板:

template <typename T>
class Stack
{
public:
    void push(T v);
    T pop();
    Int Find(T x)
    {
        for(Int i = 0; i <= size; ++i)
        {
            if(data[i] == x) { return i; }
        }
    }
    // ... 其他代码 ...
};

typedef Stack<int>   StackInt;
typedef Stack<float> StackFloat;

通过模板,我们可以将形形色色的堆栈代码分为两个部分,一个部分是不变的接口,以及近乎相同的实现;另外一部分是元素的类型,它们是需要变化的。因此同函数类似,需要变化的部分,由模板参数来反应;不变的部分,则是模板内的代码。可以看到,使用模板的代码,要比不使用模板的代码简洁许多。

如果元编程中所有的变化的量(或者说元编程的参数),都是类型,那么这样的编程,我们有个特定的称呼,叫“泛型”。

但是你会问,模板的发明,仅仅是为了做和宏几乎一样的替换工作吗?可以说是,也可以说不是。一方面,很多时候模板就是为了替换类型,这个时候作用上其实和宏没什么区别。只是宏是基于文本的替换,被替换的文本本身没有任何语义。只有替换完成,编译器才能进行接下来的处理。而模板会在分析模板时以及实例化模板时时候都会进行检查,而且源代码中也能与调试符号一一对应,所以无论是编译时还是运行时,排错都相对简单。

但是模板也和宏有很大的不同,否则此文也就不能成立了。模板最大的不同在于它是“可以运算”的。我们来举一个例子,不过可能有点牵强。考虑我们要写一个向量逐分量乘法。只不过这个向量,它非常的大。所以为了保证速度,我们需要使用SIMD指令进行加速。假设我们有以下指令可以使用:

Int8,16: N/A
Int32  : VInt32Mul(int32x4, int32x4)
Int64  : VInt64Mul(int64x4, int64x4)
Float  : VInt64Mul(floatx2, floatx2)

所以对于Int8和Int16,我们需要提升到Int32,而Int32和Int64,各自使用自己的指令。所以我们需要实现下的逻辑:

for(v4a, v4b : vectorsA, vectorsB)
{
    if type is Int8, Int16
        VInt32Mul( ConvertToInt32(v4a), ConvertToInt32(v4b) )
    elif type is Int32
        VInt32Mul( v4a, v4b )
    elif type is Float
        ...
}

这里的问题就在于,如何根据 type 分别提供我们需要的实现?这里有两个难点。首先, if(type == xxx) {} 是不存在于C++中的。第二,即便存在根据 type 的分配方法,我们也不希望它在运行时branch,这样会变得很慢。我们希望它能按照类型直接就把代码编译好,就跟直接写的一样。

嗯,聪明你果然想到了,重载也可以解决这个问题。

GenericMul(int8x4,  int8x4);
GenericMul(int16x4, int16x4);
GenericMul(int32x4, int32x4);
GenericMul(int64x4, int64x4);
// 其它 Generic Mul ...

for(v4a, v4b : vectorsA, vectorsB)
{
    GenericMul(v4a, v4b);
}

这样不就可以了吗?

唔,你赢了,是这样没错。但是问题是,我这个平台是你可没见过,它叫 Deep Thought, 特别缺心眼儿,不光有 int8,还有更奇怪的 int9, int11,以及可以代表世间万物的 int42。你总不能为之提供所有的重载吧?这简直就像你枚举了所有程序的输入,并为之提供了对应的输出一样。

好吧,我承认这个例子还是太牵强了。不过相信我,在你阅读完第二章和第三章之后,你会将这些特性自如地运用到你的程序之中。你的程序将会变成体现模板“可运算”威力的最好例子。

2.2 模板世界的If-Then-Else:类模板的特化与偏特化

2.2.1 根据类型执行代码

前一节的示例提出了一个要求:需要做出根据类型执行不同代码。要达成这一目的,模板并不是唯一的途径。比如之前我们所说的重载。如果把眼界放宽一些,虚函数也是根据类型执行代码的例子。此外,在C语言时代,也会有一些技法来达到这个目的,比如下面这个例子,我们需要对两个浮点做加法, 或者对两个整数做乘法:

struct Variant
{
    union
    {
        int x;
        float y;
    } data;
    uint32 typeId;
};

Variant addFloatOrMulInt(Variant const* a, Variant const* b)
{
    Variant ret;
    assert(a->typeId == b->typeId);
    if (a->typeId == TYPE_INT)
    {
        ret.x = a->x * b->x;
    }
    else
    {
        ret.y = a->y + b->y;
    }
    return ret;
}

更常见的是 void*:

#define BIN_OP(type, a, op, b, result) (*(type *)(result)) = (*(type const *)(a)) op (*(type const*)(b))
void doDiv(void* out, void const* data0, void const* data1, DATA_TYPE type)
{
    if(type == TYPE_INT)
    {
        BIN_OP(int, data0, *, data1, out);
    }
    else
    {
        BIN_OP(float, data0, +, data1, out);
    }
}

在C++中比如在 Boost.Any 的实现中,运用了 typeid 来查询类型信息。和 typeid 同属于RTTI机制的 dynamic_cast,也经常会用来做类型判别的工作。我想你应该写过类似于下面的代码:

IAnimal* animal = GetAnimalFromSystem();

IDog* maybeDog = dynamic_cast<IDog*>(animal);
if(maybeDog)
{
    maybeDog->Wangwang();
}
ICat* maybeCat = dynamic_cast<ICat*>(animal);
if(maybeCat)
{
    maybeCat->Moemoe();
}

当然,在实际的工作中,我们建议把需要 dynamic_cast 后执行的代码,尽量变成虚函数。不过这个已经是另外一个问题了。我们看到,不管是哪种方法都很难避免 if 的存在。而且因为输入数据的类型是模糊的,经常需要强制地、没有任何检查的转换成某个类型,因此很容易出错。

但是模板与这些方法最大的区别并不在这里。模板无论其参数或者是类型,它都是一个编译期分派的办法。编译期就能确定的东西既可以做类型检查,编译器也能进行优化,砍掉任何不必要的代码执行路径。例如在上例中,

template <typename T> T addFloatOrMulInt(T a, T b);

// 迷之代码1:用于T是float的情况

// 迷之代码2:用于T是int时的情况

如果你运用了模板来实现,那么当传入两个不同类型的变量,或者不是 intfloat 变量,编译器就会提示错误。但是如果使用了我们前述的 Variant 来实现,编译器可就管不了那么多了。但是,成也编译期,败也编译期。最严重的“缺点”,就是你没办法根据用户输入或者别的什么在运行期间可能发生变化的量来决定它产生、或执行什么代码。比如下面的代码段,它是不成立的。


template <int i, int j>
int foo() { return i + j; }
int main()
{
    cin >> x >> y;
    return foo<x, y>();
}

这点限制也粉碎了妄图用模板来包办工厂(Factory)甚至是反射的梦想。尽管在《Modern C++ Design》中(别问我为什么老举这本书,因为《C++ Templates》和《Generic Programming》我只是囫囵吞枣读过,基本不记得了)大量运用模板来简化工厂方法;同时C++11和14中的一些机制如Variadic Template更是让这一问题的解决更加彻底。但无论如何,直到C++11/14,光靠模板你就是写不出依靠类名或者ID变量产生类型实例的代码。

所以说,从能力上来看,模板能做的事情都是编译期完成的。编译期完成的意思就是,当你编译一个程序的时候,所有的量就都已经确定了。比如下面的这个例子:

int a = 3, b = 5;
Variant aVar, bVar;
aVar.setInt(a);            // 我们新加上的方法,怎么实现的无所谓,大家明白意思就行了。
bVar.setInt(b);
Variant result = addFloatOrMulInt(aVar, bVar);

除非世界末日,否则这个例子里不管你怎么蹦跶,单看代码我们就能知道, aVarbVar 都一定会是整数。所以如果有合适的机制,编译器就能知道此处的 addFloatOrMulInt 中只需要执行 Int 路径上的代码,而且编译器在此处也能单独为 Int 路径生成代码,从而去掉那个不必要的 if

在模板代码中,这个“合适的机制”就是指“特化”和“部分特化(Partial Specialization)”,后者也叫“偏特化”。

2.2.2 特化

我的高中物理老师对我说过一句令我受用至今的话:把自己能做的事情做好。编写模板程序也是一样。当你试图用模板解决问题之前,先撇开那些复杂的语法要素,用最直观的方式表达你的需求:

// 这里是伪代码,意思一下

int|float addFloatOrMulInt(a, b)
{
    if(type is Int)
    {
        return a * b;
    }
    else if (type is Float)
    {
        return a + b;
    }
}

void foo()
{
    float a, b, c;
    c = addFloatOrMulInt(a, b);        // c = a + b;

    int x, y, z;
    z = addFloatOrMulInt(x, y);        // z = x * y;
}

因为这一节是讲类模板有关的特化和偏特化机制,所以我们不用普通的函数,而是用类的静态成员函数来做这个事情(这就是典型的没事找抽型):

// 这里仍然是伪代码,意思一下,too。
class AddFloatOrMulInt
{
    static int|float Do(a, b)
    {
        if(type is Int)
        {
            return a * b;
        }
        else if (type is Float)
        {
            return a + b;
        }
    }
};

void foo()
{
    float a, b, c;
    c = AddFloatOrMulInt::Do(a, b);        // c = a + b;

    int x, y, z;
    z = AddFloatOrMulInt::Do(x, y);        // z = x * y;
}

好,意思表达清楚了。我们先从调用方的角度,把这个形式改写一下:

void foo()
{
    float a, b, c;
    c = AddFloatOrMulInt<float>::Do(a, b);        // c = a + b;

    int x, y, z;
    z = AddFloatOrMulInt<int>::Do(x, y);        // z = x * y;
}

也许你不明白为什么要改写成现在这个样子。看不懂不怪你,怪我讲的不好。但是你别急,先看看这样改写以后能不能跟我们的目标接近一点。如果我们把 AddFloatOrMulInt<float>::Do 看作一个普通的函数,那么我们可以写两个实现出来:

float AddFloatOrMulInt<float>::Do(float a, float b)
{
    return a + b;
}

int AddFloatOrMulInt<int>::Do(int a, int b)
{
    return a * b;
}

void foo()
{
    float a, b, c;
    c = AddFloatOrMulInt<float>::Do(a, b);        // c = a + b;

    int x, y, z;
    z = AddFloatOrMulInt<int>::Do(x, y);        // z = x * y;
}

这样是不是就很开心了?我们更进一步,把 AddFloatOrMulInt<int>::Do 换成合法的类模板:

// 这个是给float用的。
template <typename T> class AddFloatOrMulInt
{
    T Do(T a, T b)
    {
        return a + b;
    }
};

// 这个是给int用的。
template <typename T> class AddFloatOrMulInt
{
    T Do(T a, T b)
    {
        return a * b;
    }
};

void foo()
{
    float a, b, c;

    // 嗯,我们需要 c = a + b;
    c = AddFloatOrMulInt<float>::Do(a, b);        
    // ... 觉得哪里不对劲 ...
    // ...
    // ...
    // ...
    // 啊!有两个AddFloatOrMulInt,class看起来一模一样,要怎么区分呢!
}

好吧,问题来了!如何要让两个内容不同,但是模板参数形式相同的类进行区分呢?特化!特化(specialization)是根据一个或多个特殊的整数或类型,给出模板实例化时的一个指定内容。我们先来看特化是怎么应用到这个问题上的。

// 首先,要写出模板的一般形式(原型)
template <typename T> class AddFloatOrMulInt
{
    static T Do(T a, T b)
    {
        // 在这个例子里面一般形式里面是什么内容不重要,因为用不上
        // 这里就随便给个0吧。
        return T(0);
    }
};

// 其次,我们要指定T是int时候的代码,这就是特化:
template <> class AddFloatOrMulInt<int>
{
public:
    static int Do(int a, int b) // 
    {
        return a * b;
    }
};

// 再次,我们要指定T是float时候的代码:
template <> class AddFloatOrMulInt<float>
{
public:
    static float Do(float a, float b)
    {
        return a + b;
    }
};

void foo()
{
    // 这里面就不写了
}

我们再把特化的形式拿出来一瞧:这货有点怪啊: template <> class AddFloatOrMulInt<int>。别急,我给你解释一下。

// 我们这个模板的基本形式是什么?
template <typename T> class AddFloatOrMulInt;

// 但是这个类,是给T是Int的时候用的,于是我们写作
class AddFloatOrMulInt<int>
// 当然,这里编译是通不过的。

// 但是它又不是个普通类,而是类模板的一个特化(特例)。
// 所以前面要加模板关键字template,
// 以及模板参数列表
template </* 这里要填什么? */> class AddFloatOrMulInt<int>;

// 最后,模板参数列表里面填什么?因为原型的T已经被int取代了。所以这里就不能也不需要放任何额外的参数了。
// 所以这里放空。
template <> class AddFloatOrMulInt<int>
{
    // ... 针对Int的实现 ... 
}

// Bingo!

哈,这样就好了。我们来做一个练习。我们有一些类型,然后你要用模板做一个对照表,让类型对应上一个数字。我先来做一个示范:


template <typename T> class TypeToID
{
public:
    static int const ID = -1;
};

template <> class TypeToID<uint8_t>
{
public:
    static int const ID = 0;
};

然后呢,你的任务就是,要所有无符号的整数类型的特化(其实就是uint8_tuint64_t啦),把所有的基本类型都赋予一个ID(当然是不一样的啦)。当你做完后呢,可以把类型所对应的ID打印出来,我仍然以 uint8_t 为例:

void PrintID()
{
    cout << "ID of uint8_t: " << TypeToID<uint8_t>::ID << endl;
}

嗯,看起来挺简单的,是吧。但是这里透露出了一个非常重要的信号,我希望你已经能察觉出来了: TypeToID 如同是一个函数。这个函数只能在编译期间执行。它输入一个类型,输出一个ID。

如果你体味到了这一点,那么恭喜你,你的模板元编程已经开悟了。

2.2.3 特化:一些其它问题

在上一节结束之后,你一定做了许多的练习。我们再来做三个练习。第一,给float一个ID;第二,给void*一个ID;第三,给任意类型的指针一个ID。先来做第一个:

// ...
// TypeToID 的模板“原型”
// ...

template <> class TypeToID<float>
{
  static int const ID = 0xF10A7;
};

嗯, 这个你已经了然于心了。那么void*呢?你想了想,这已经是一个复合类型了。不错你还是战战兢兢的写了下来:

template <> class TypeToID<void*>
{
  static int const ID = 0x401d;
};

void PrintID()
{
  cout << "ID of uint8_t: " << TypeToID<void*>::ID << endl;
}

遍译运行一下,对了。模板不过如此嘛。然后你觉得自己已经完全掌握了,并试图将所有C++类型都放到模板里面,开始了自我折磨的过程:

class ClassB {};

template <> class TypeToID<void ()>;            // 函数的TypeID
template <> class TypeToID<int[3]>;                // 数组的TypeID
template <> class TypeToID<int (int[3])>;        // 这是以数组为参数的函数的TypeID
template <> class TypeToID<
    int (ClassB::*[3])(void*, float[2])>;        // 我也不知道这是什么了,自己看着办吧。

甚至连 constvolatile 都能装进去

template <> class TypeToID<int const * volatile * const volatile>;

此时就很明白了,只要 <> 内填进去的是一个C++能解析的合法类型,模板都能让你特化。不过这个时候如果你一点都没有写错的话, PrintID 中只打印了我们提供了特化的类型的ID。那如果我们没有为之提供特化的类型呢?比如说double?OK,实践出真知,我们来尝试着运行一下:

void PrintID()
{
    cout << "ID of double: " << TypeToID<double>::ID << endl;
}

嗯,它输出的是-1。我们顺藤摸瓜会看到, TypeToID的类模板“原型”的ID是值就是-1。通过这个例子可以知道,当模板实例化时提供的模板参数不能匹配到任何的特化形式的时候,它就会去匹配类模板的“原型”形式。

不过这里有一个问题要厘清一下。和继承不同,类模板的“原型”和它的特化类在实现上是没有关系的,并不是在类模板中写了 ID 这个Member,那所有的特化就必须要加入 ID 这个Member,或者特化就自动有了这个成员。完全没这回事。我们把类模板改成以下形式,或许能看的更清楚一点:

template <typename T> class TypeToID
{
public:
    static int const NotID = -2;
};

template <> class TypeToID<float>
{
public:
    static int const ID = 1;
};

void PrintID()
{
    cout << "ID of float: " << TypeToID<float>::ID << endl;    // Print "1"
    cout << "NotID of float: " << TypeToID<float>::NotID << endl;    // Error! TypeToID<float>使用的特化的类,这个类的实现没有NotID这个成员。
    cout << "ID of double: " << TypeToID<double>::ID << endl;    // Error! TypeToID<double>是由模板类实例化出来的,它只有NotID,没有ID这个成员。
}

这样就明白了。类模板和类模板的特化的作用,仅仅是指导编译器选择哪个编译,但是特化之间、特化和它原型的类模板之间,是分别独立实现的。所以如果多个特化、或者特化和对应的类模板有着类似的内容,很不好意思,你得写上若干遍了。

第三个问题,是写一个模板匹配任意类型的指针。对于C语言来说,因为没有泛型的概念,因此它提供了无类型的指针void*。它的优点是,所有指针都能转换成它。它的缺点是,一旦转换称它后,你就再也不知道这个指针到底是指向float或者是int或者是struct了。

比如说copy

void copy(void* dst, void const* src, size_t elemSize, size_t elemCount, void (*copyElem)(void* dstElem, void const* srcElem))
{
    void const* reader = src;
    void const* writer = dst;
    for(size_t i = 0; i < elemCount; ++i)
    {
        copyElem(writer, reader);
        advancePointer(reader, elemSize);    // 把Reader指针往后移动一些字节
        advancePointer(writer, elemSize);
    }
}

为什么要提供copyElem,是因为可能有些struct需要深拷贝,所以得用特殊的copy函数。这个在C++98/03里面就体现为拷贝构造和赋值函数。

但是不管怎么搞,因为这个函数的参数只是void*而已,当你使用了错误的elemSize,或者传入了错误的copyElem,就必须要到运行的时候才有可能看出来。注意,这还只是有可能而已。

那么C++有了模板后,能否既能匹配任意类型的指针,同时又保留了类型信息呢?答案是显然的。至于怎么写,那就得充分发挥你的直觉了:

首先,我们需要一个typename T来指代“任意类型”这四个字:

template <typename T>

接下来,我们要写函数原型:

void copy(?? dest, ?? src, size_t elemCount);

这里的 ?? 要怎么写呢?既然我们有了模板类型参数T,那我们不如就按照经验,写 T* 看看。

template <typename T>
void copy(T* dst, T const* src, size_t elemCount);

编译一下,咦,居然通过了。看来这里的语法与我们以前学到的知识并没有什么不同。这也是语言设计最重要的一点原则:一致性。它可以让你辛辛苦苦体验到的规律不至于白费。

最后就是实现:

template <typename T>
void copy(T* dst, T const* src, size_t elemCount)
{
    for(size_t i = 0; i < elemCount; ++i)
    {
        dst[i] = src[i];
    }
}

是不是简洁了许多?你不需要再传入size;只要你有正确的赋值函数,也不需要提供定制的copy;也不用担心dst和src的类型不匹配了。

最后,我们把函数模板学到的东西,也应用到类模板里面:

template <typename T>                    // 嗯,需要一个T
class TypeToID<T*>                        // 我要对所有的指针类型特化,所以这里就写T*
{
public:
    static int const ID = 0x80000000;    // 用最高位表示它是一个指针
};

最后写个例子来测试一下,看看我们的 T* 能不能搞定 float*

void PrintID()
{
    cout << "ID of float*: " << TypeToID<float*>::ID << endl;
}

哈哈,大功告成。嗯,别急着高兴。待我问一个问题:你知道 TypeToID<float*> 后,这里的T是什么吗?换句话说,你知道下面这段代码打印的是什么吗?

// ...
// TypeToID 的其他代码,略过不表
// ...

template <typename T>                    // 嗯,需要一个T
class TypeToID<T*>                        // 我要对所有的指针类型特化,所以这里就写T*
{
public:
    typedef T         SameAsT;
    static int const ID = 0x80000000;    // 用最高位表示它是一个指针
};

void PrintID()
{
    cout << "ID of float*: " << TypeToID< TypeToID<float*>::SameAsT >::ID << endl;
}

别急着运行,你先猜。

------------------------- 这里是给勤于思考的码猴的分割线 -------------------------------

OK,猜出来了吗,T是float。为什么呢?因为你用 float * 匹配了 T *,所以 T 就对应 float 了。没想清楚的自己再多体会一下。

嗯,所以实际上,我们可以利用这个特性做一件事情:把指针类型的那个指针给“干掉”:

template <typename T>
class RemovePointer
{
    // 啥都不干,你要放一个不是指针的类型进来,我就让你死的难看。
};

template <typename T>
class RemovePointer<T*>    // 祖传牛皮藓,专治各类指针
{
public:
    typedef T Result;
};

void Foo()
{
    RemovePointer<float*>::Result x = 5.0f;        // 喏,用RemovePointer后,那个Result就是把float*的指针处理掉以后的结果:float啦。
    std::cout << x << std::endl;
}

OK,如果这个时候,我需要给 int* 提供一个更加特殊的特化,那么我还得都多提供一个:

// ...
// TypeToID 的其他代码,略过不表
// ...

template <typename T>                    // 嗯,需要一个T
class TypeToID<T*>                        // 我要对所有的指针类型特化,所以这里就写T*
{
public:
    typedef T         SameAsT;
    static int const ID = 0x80000000;    // 用最高位表示它是一个指针
};

template <>                                // 嗯,int* 已经是个具体的不能再具体的类型了,所以模板不需要额外的类型参数了
class TypeToID<int*>                    // 嗯,对int*的特化。在这里呢,要把int*整体看作一个类型。
{
public:
    static int const ID = 0x12345678;    // 给一个缺心眼的ID
};

void PrintID()
{
    cout << "ID of int*: " << TypeToID<int*>::ID << endl;
}

嗯,这个时候它会输出0x12345678的十进制(大概?)。 可能会有较真的人说,int* 去匹配 T 或者 T*,也是合法的。就和你说22岁以上能结婚,那24岁当然也能结婚一样。 那为什么 int* 就会找 int*float *因为没有合适的特化就去找 T*,更一般的就去找 T 呢?废话,有专门为你准备的东西的不用,人干事?这就是直觉。 但是呢,直觉对付更加复杂的问题还是没用的(也不是没用,主要是你没这个直觉了)。我们要把这个直觉,转换成合理的规则——即模板的匹配规则。 当然,这个匹配规则是对复杂问题用的,所以我们会到实在一眼看不出来的时候才会动用它。一开始我们只要把握:模板是从最特殊到最一般形式进行匹配就可以了。

2.3 即用即推导

2.3.1 视若无睹的语法错误

这一节我们将讲述模板一个非常重要的行为特点:那就是什么时候编译器会对模板进行推导,推导到什么程度。

这一知识,对于理解模板的编译期行为、以及修正模板编译错误都非常重要。

我们先来看一个例子:

template <typename T> struct X {};

template <typename T> struct Y
{
    typedef X<T> ReboundType;                        // 类型定义1
    typedef typename X<T>::MemberType MemberType;    // 类型定义2
    typedef UnknownType MemberType3;                // 类型定义3

    void foo()
    {
        X<T> instance0;
        typename X<T>::MemberType instance1;
        WTF instance2
        大王叫我来巡山 - + &
    }
};

把这段代码编译一下,类型定义3出错,其它的都没问题。不过到这里你应该会有几个问题:

  1. 不是struct X<T>的定义是空的吗?为什么在struct Y内的类型定义2使用了 X<T>::MemberType 编译器没有报错?
  2. 类型定义2中的typename是什么鬼?为什么类型定义1就不需要?
  3. 为什么类型定义3会导致编译错误?
  4. 为什么void foo()在MSVC下什么错误都没报?

这时我们就需要请出C++11标准 —— 中的某些概念了。这是我们到目前为止第一次参阅标准。我希望能尽量减少直接参阅标准的次数,因此即便是极为复杂的模板匹配决议我都暂时没有引入标准中的描述。 然而,Template引入的“双阶段名称查找(Two phase name lookup)”堪称是C++中最黑暗的角落 —— 这是LLVM的团队自己在博客上说的 —— 因此在这里,我们还是有必要去了解标准中是如何规定的。

2.3.2 名称查找:I am who I am

在C++标准中对于“名称查找(name lookup)”这个高大上的名词的诠释,主要集中出现在三处。第一处是3.4节,标题名就叫“Name Lookup”;第二处在10.2节,继承关系中的名称查找;第三处在14.6节,名称解析(name resolution)。

名称查找/名称解析,是编译器的基石。对编译原理稍有了解的人,都知道“符号表”的存在即重要意义。考虑一段最基本的C代码:

int a = 0;
int b;
b = (a + 1) * 2;
printf("Result: %d", b);

在这段代码中,所有出现的符号可以分为以下几类:

  • int:类型标识符,代表整型;
  • a,b,printf:变量名或函数名;
  • =,+,*:运算符;
  • ,,;,(,):分隔符;

那么,编译器怎么知道int就是整数类型,b=(a+1)*2中的ab就是整型变量呢?这就是名称查找/名称解析的作用:它告诉编译器,这个标识符(identifer)是在哪里被声明或定义的,它究竟是什么意思。

也正因为这个机制非常基础,所以它才会面临各种可能的情况,编译器也要想尽办法让它在大部分场合都表现的合理。比如我们常见的作用域规则,就是为了对付名称在不同代码块中传播、并且遇到重名要如何处理的问题。下面是一个最简单的、大家在语言入门过程中都会碰到的一个例子:

int a = 0;
void f() {
    int a = 0;
    a += 2;
    printf("Inside <a>: %d\n", a);
}
void g() {
    printf("Outside <a>: %d\n", a);
}
int main() {
    f();
    g();
}

/* ------------ Console Output -----------------
Inside <a>: 2
Outside <a>: 0
--------------- Console Output -------------- */

我想大家尽管不能处理所有名称查找中所遇到的问题,但是对一些常见的名称查找规则也有了充分的经验,可以解决一些常见的问题。 但是模板的引入,使得名称查找这一本来就不简单的基本问题变得更加复杂了。 考虑下面这个例子:

struct A  { int a; };
struct AB { int a, b; };
struct C  { int c; };

template <typename T> foo(T& v0, C& v1){
    v0.a = 1;
    v1.a = 2;
    v1.c = 3;
}

简单分析上述代码很容易得到以下结论:

  1. 函数foo中的变量v1已经确定是struct C的实例,所以,v1.a = 2;会导致编译错误,v1.c = 3;是正确的代码;
  2. 对于变量v0来说,这个问题就变得很微妙。如果v0struct A或者struct AB的实例,那么foo中的语句v0.a = 1;就是正确的。如果是struct C,那么这段代码就是错误的。

因此在模板定义的地方进行语义分析,并不能完全得出代码是正确或者错误的结论,只有到了实例化阶段,确定了模版参数的类型后,才知道这段代码正确与否。令人高兴的是,在这一问题上,我们和C++标准委员会的见地一致,说明我们的C++水平已经和Herb Sutter不分伯仲了。既然我们和Herb Sutter水平差不多,那凭什么人家就吃香喝辣?下面我们来选几条标准看看服不服:

14.6 名称解析(Name resolution)

1) 模板定义中能够出现以下三类名称:

  • 模板名称、或模板实现中所定义的名称;
  • 和模板参数有关的名称;
  • 模板定义所在的定义域内能看到的名称。

9) … 如果名字查找和模板参数有关,那么查找会延期到模板参数全都确定的时候。 …

10) 如果(模板定义内出现的)名字和模板参数无关,那么在模板定义处,就应该找得到这个名字的声明。…

14.6.2 依赖性名称(Dependent names)

1) …(模板定义中的)表达式和类型可能会依赖于模板参数,并且模板参数会影响到名称查找的作用域 … 如果表达式中有操作数依赖于模板参数,那么整个表达式都依赖于模板参数,名称查找延期到模板实例化时进行。并且定义时和实例化时的上下文都会参与名称查找。(依赖性)表达式可以分为类型依赖(类型指模板参数的类型)或值依赖。

14.6.2.2 类型依赖的表达式

2) 如果成员函数所属的类型是和模板参数有关的,那么这个成员函数中的this就认为是类型依赖的。

14.6.3 非依赖性名称(Non-dependent names)

1) 非依赖性名称在模板定义时使用通常的名称查找规则进行名称查找。

[Working Draft: Standard of Programming Language C++, N3337][1]

知道差距在哪了吗:人家会说黑话。什么时候咱们也会说黑话了,就是标准委员会成员了,反正懂得也不比他们少。不过黑话确实不太好懂 —— 怪我翻译不好的人,自己看原文,再说好懂了人家还靠什么吃饭 —— 我们来举一个例子:

int a;
struct B { int v; }
template <typename T> struct X {
    B b;                  // B 是第三类名字,b 是第一类
    T t;                  // T 是第二类
    X* anthor;            // X 这里代指 X<T>,第一类
    typedef int Y;        // int 是第三类
    Y y;                  // Y 是第一类
    C c;                  // C 什么都不是,编译错误。
    void foo() {
       b.v += y;          // b 是第一类,非依赖性名称
       b.v *= T::s_mem;   // T::s_mem 是第二类
                          // s_mem的作用域由T决定
                          // 依赖性名称,类型依赖
    }
};

所以,按照标准的意思,名称查找会在模板定义和实例化时各做一次,分别处理非依赖性名称和依赖性名称的查找。这就是“两阶段名称查找”这一名词的由来。只不过这个术语我也不知道是谁发明的,它并没有出现的标准上,但是频繁出现在StackOverflow和Blog上。

接下来,我们就来解决2.3.1节中留下的几个问题。

先看第四个问题。为什么MSVC中,模板函数的定义内不管填什么编译器都不报错?因为MSVC在分析模板中成员函数定义时没有做任何事情。至于为啥连“大王叫我来巡山”都能过得去,这是C++语法/语义分析的特殊性导致的。 C++是个非常复杂的语言,以至于它的编译器,不可能通过词法-语法-语义多趟分析清晰分割。因为它的语义将会直接干扰到语法:

void foo(){
    A<T> b;
}

在这段简短的代码中,就包含了两个歧义的可能,一是A是模板,于是A<T>是一个实例化的类型,b是变量,另外一种是比较表达式(Comparison Expression)的组合,((A < T) > b)

甚至词法分析也会受到语义的干扰,C++11中才明确被修正的vector<vector<int>>,就因为>>被误解为右移或流操作符,而导致某些编译器上的错误。因此,在语义没有确定之前,连语法都没有分析的价值。

大约是基于如此考量,为了偷懒,MSVC将包括所有模板成员函数的语法/语义分析工作都挪到了第二个Phase,于是乎连带着语法分析都送进了第二个阶段。符合标准么?显然不符合。

但是这里值得一提的是,MSVC的做法和标准相比,虽然投机取巧,但并非有弊无利。我们来先说一说坏处。考虑以下例子:

// ----------- X.h ------------

template <typename T> struct X {
      // 实现代码
};

// ---------- X.cpp -----------

// ... 一些代码 ...
X<int> xi; 
// ... 一些代码 ...
X<float> xf;
// ... 一些代码 ...

此时如果X中有一些与模板参数无关的错误,如果名称查找/语义分析在两个阶段完成,那么这些错误会很早、且唯一的被提示出来;但是如果一切都在实例化时处理,那么可能会导致不同的实例化过程提示同样的错误。而模板在运用过程中,往往会产生很多实例,此时便会大量报告同样的错误。

当然,MSVC并不会真的这么做。根据推测,最终他们是合并了相同的错误。因为即便对于模板参数相关的编译错误,也只能看到最后一次实例化的错误信息:

template <typename T> struct X {};

template <typename T> struct Y
{
    typedef X<T> ReboundType;                        // 类型定义1
    void foo()
    {
        X<T> instance0;
        X<T>::MemberType instance1;
        WTF instance2
    }
};

void poo(){
    Y<int>::foo();
    Y<float>::foo();
}

MSVC下和模板相关的错误只有一个:

error C2039: 'MemberType': is not a member of 'X<T>'
          with
          [
              T=float
          ]

然后是一些语法错误,比如MemberType不是一个合法的标识符之类的。这样甚至你会误以为int情况下模板的实力化是正确的。虽然在有了经验之后会发现这个问题挺荒唐的,但是仍然会让新手有困惑。

相比之下,更加遵守标准的Clang在错误提示上就要清晰许多:

error: unknown type name 'WTF'
    WTF instance2
    ^
error: expected ';' at end of declaration
    WTF instance2
                 ^
                 ;
error: no type named 'MemberType' in 'X<int>'
    typename X<T>::MemberType instance1;
    ~~~~~~~~~~~~~~~^~~~~~~~~~
    note: in instantiation of member function 'Y<int>::foo' requested here
        Y<int>::foo();
                ^
error: no type named 'MemberType' in 'X<float>'
    typename X<T>::MemberType instance1;
    ~~~~~~~~~~~~~~~^~~~~~~~~~
    note: in instantiation of member function 'Y<float>::foo' requested here
        Y<float>::foo();
                  ^
4 errors generated.

可以看到,Clang的提示和标准更加契合。它很好地区分了模板在定义和实例化时分别产生的错误。

另一个缺点也与之类似。因为没有足够的检查,如果你写的模板没有被实例化,那么很可能缺陷会一直存在于代码之中。特别是模板代码多在头文件。虽然不如接口那么重要,但也是属于被公开的部分,别人很可能会踩到坑上。缺陷一旦传播开修复起来就没那么容易了。

但是正如我前面所述,这个违背了标准的特性,并不是一无是处。首先,它可以完美的兼容标准。符合标准的、能够被正确编译的代码,一定能够被MSVC的方案所兼容。其次,它带来了一个非常有趣的特性,看下面这个例子:

struct A;
template <typename T> struct X {
    int v;
    void convertTo(A& a) {
       a.v = v; // 这里需要A的实现
    }
};

struct A { int v; };

void main() {
    X<int> x;
    x.foo(5);
}

这个例子在Clang中是错误的,因为:

error: variable has incomplete type 'A'
                        A a;
                          ^
    note: forward declaration of 'A'
     struct A;
            ^
1 error generated.

符合标准的写法需要将模板类的定义,和模板函数的定义分离开:

TODO 此处例子不够恰当,并且描述有歧义。需要在未来版本中修订。

struct A;
template <typename T> struct X {
    int v;
    void convertTo(A& a);
};

struct A { int v; };

template <typename T> void X<T>::convertTo(A& a) {
   a.v = v;
}

void main() {
    X<int> x;
    x.foo(5);
}

但是其实我们知道,foo要到实例化之后,才需要真正的做语义分析。在MSVC上,因为函数实现就是到模板实例化时才处理的,所以这个例子是完全正常工作的。因此在上面这个例子中,MSVC的实现要比标准更加易于写和维护,是不是有点写Java/C#那种声明实现都在同一处的清爽感觉了呢!

扩展阅读: [The Dreaded Two-Phase Name Lookup][2]

2.3.3 “多余的” typename 关键字

到了这里,2.3.1 中提到的四个问题,还有三个没有解决:

template <typename T> struct X {};

template <typename T> struct Y
{
    typedef X<T> ReboundType;                        // 这里为什么是正确的?
    typedef typename X<T>::MemberType MemberType2;    // 这里的typename是做什么的?
    typedef UnknownType MemberType3;                // 这里为什么会出错?
};

我们运用我们2.3.2节中学习到的标准,来对Y内部做一下分析:

template <typename T> struct Y
{
    // X可以查找到原型;
    // X<T>是一个依赖性名称,模板定义阶段并不管X<T>是不是正确的。
    typedef X<T> ReboundType;

    // X可以查找到原型;
    // X<T>是一个依赖性名称,X<T>::MemberType也是一个依赖性名称;
    // 所以模板声明时也不会管X模板里面有没有MemberType这回事。
    typedef typename X<T>::MemberType MemberType2;

    // UnknownType 不是一个依赖性名称
    // 而且这个名字在当前作用域中不存在,所以直接报错。
    typedef UnknownType MemberType3;                
};

下面,唯一的问题就是第二个:typename是做什么的?

对于用户来说,这其实是一个语法噪音。也就是说,其实就算没有它,语法上也说得过去。事实上,某些情况下MSVC的确会在标准需要的时候,不用写typename。但是标准中还是规定了形如 T::MemberType 这样的qualified id 在默认情况下不是一个类型,而是解释为T的一个成员变量MemberType,只有当typename修饰之后才能作为类型出现。

事实上,标准对typename的使用规定极为复杂,也算是整个模板中的难点之一。如果想了解所有的标准,需要阅读标准14.6节下2-7条,以及14.6.2.1第一条中对于current instantiation的解释。

简单来说,如果编译器能在出现的时候知道它的类型,那么就不需要typename,如果必须要到实例化的时候才能知道它是不是合法,那么定义的时候就把这个名称作为变量而不是类型。

在这里,我举几个例子帮助大家理解typename的用法,这几个例子已经足以涵盖日常使用[(预览)][3]:

struct A;
template <typename T> struct B;
template <typename T> struct X {
    typedef X<T> _A; // 编译器当然知道 X<T> 是一个类型。
    typedef X    _B; // X 等价于 X<T> 的缩写
    typedef T    _C; // T 不是一个类型还玩毛

    // !!!注意我要变形了!!!
    class Y {
        typedef X<T>     _D;          // X 的内部,既然外部高枕无忧,内部更不用说了
        typedef X<T>::Y  _E;          // 嗯,这里也没问题,编译器知道Y就是当前的类型,
                                      // 这里在VS2015上会有错,需要添加 typename,
                                      // Clang 上顺利通过。
        typedef typename X<T*>::Y _F; // 这个居然要加 typename!
                                      // 因为,X<T*>和X<T>不一样哦,
                                      // 它可能会在实例化的时候被别的偏特化给抢过去实现了。
    };

    typedef A _G;                   // 嗯,没问题,A在外面声明啦
    typedef B<T> _H;                // B<T>也是一个类型
    typedef typename B<T>::type _I; // 嗯,因为不知道B<T>::type的信息,
                                    // 所以需要typename
    typedef B<int>::type _J;        // B<int> 不依赖模板参数,
                                    // 所以编译器直接就实例化(instantiate)了
                                    // 但是这个时候,B并没有被实现,所以就出错了
};

2.4 本章小结

这一章是写作中最艰难的一章,中间停滞了将近一年。因为要说清楚C++模板中一些语法噪音和设计决议并不是一件轻松的事情。不过通过这一章的学习,我们知道了下面这几件事情:

  1. 部分特化/偏特化特化 相当于是模板实例化过程中的if-then-else。这使得我们根据不同类型,选择不同实现的需求得以实现;

  2. 在 2.3.3 一节我们插入了C++模板中最难理解的内容之一:名称查找。名称查找是语义分析的一个环节,模板内书写的 变量声明typedef类型名称 甚至 类模板中成员函数的实现 都要符合名称查找的规矩才不会出错;

  3. C++编译器对语义的分析的原则是“大胆假设,小心求证”:在能求证的地方尽量求证 —— 比如两段式名称查找的第一阶段;无法检查的地方假设你是正确的 —— 比如typedef typename A<T>::MemberType _X;在模板定义时因为T不明确不会轻易判定这个语句的死刑。

从下一章开始,我们将进入元编程环节。我们将使用大量的示例,一方面帮助巩固大家学到的模板知识,一方面也会引导大家使用函数式思维去解决常见的问题。

results matching ""

    No results matching ""