C++ 模板沉思录(上)

语言: CN / TW / HK

:point_up_2:  Python猫 ” ,一个值得加星标的 公众号

花下猫语: 在我们读者群里,最近出现了比较多关于 C++ 的讨论,还兴起了一股学习 C++ 的风气。樱雨楼小姐姐对 C++ 的模板深有研究,系统地梳理成了一篇近 4 万字的文章!本文是上篇,分享给大家~

樱雨楼 | 原创作者

豌豆花下猫 | 编辑

0 论抽象——前言

故事要从一个看起来非常简单的功能开始:

请计算两个数的和。

如果你对Python很熟悉,你一定会觉得:“哇!这太简单了!”,然后写出以下代码:

def Plus(lhs, rhs):

    return lhs + rhs

那么,C语言又如何呢?你需要面对这样的问题:

/* 这里写什么?*/ Plus(/* 这里写什么?*/ lhs, /* 这里写什么?*/ rhs)
{
    return lhs + rhs;
}

也许你很快就能想到以下解法中的一些或全部:

  1. 硬编码为某个特定类型:

int Plus(int lhs, int rhs)
{
    return lhs + rhs;
}

显然,这不是一个好的方案。因为这样的Plus函数接口强行的要求两个实参以及返回值的类型都必须是int,或是能够发生隐式类型转换到int的类型。此时,如果实参并不是int类型,其结果往往就是错误的。请看以下示例:

int main()
{
    printf("%d\n", Plus(1, 2));          // 3,正确
    printf("%d\n", Plus(1.999, 2.999));  // 仍然是3!
}
  1. 针对不同类型,定义多个函数

int Plusi(int lhs, int rhs)
{
    return lhs + rhs;
}


long Plusl(long lhs, long rhs)
{
    return lhs + rhs;
}


double Plusd(double lhs, double rhs)
{
    return lhs + rhs;
}


// ...

这种方案的缺点也很明显:其使得代码写起来像“汇编语言”(movl,movq,...)。我们需要针对不同的类型调用不同名称的函数(是的,C语言也不支持函数重载),这太可怕了。

  1. 使用宏

#define Plus(lhs, rhs) (lhs + rhs)

这种方案似乎很不错,甚至“代码看上去和Python一样”。但正如许许多多的书籍都讨论过的那样,宏,不仅“抛弃”了类型,甚至“抛弃”了代码。是的,宏不是C语言代码,其只是交付于预处理器执行的“复制粘贴”的标记。一旦预处理完成,宏已然不再存在。可想而知,在功能变得复杂后,宏的缺点将会越来越大:代码晦涩,无法调试,“莫名其妙”的报错...

看到这里,也许你会觉得:“哇!C语言真烂!居然连这么简单的功能都无法实现!”。但请想一想,为什么会出现这些问题呢?让我们回到故事的起点:

请计算两个数的和。

仔细分析这句话:“请计算...的和”,意味着“加法”语义,这在C语言中可以通过“+”实现(也许你会联想到汇编语言中的加法实现);而“两个”,则意味着形参的数量是2(也许你会联想到汇编语言中的ESS、ESP、EBP等寄存器);那么,“数”,意味着什么语义?C语言中,具有“数”这一语义的类型有十几种:int、double、unsigned,等等,甚至char也具有“数”的语义。那么,“加法”和“+”,“两个”和“形参的数量是2”,以及“数”和int、double、unsigned等等之间的关系是什么?

是抽象。

高级语言的目的,就是对比其更加低级的语言进行抽象,从而使得我们能够实现更加高级的功能。抽象,是一种人类的高级思维活动,是一种充满着智慧的思维活动。汇编语言抽象了机器语言,而C语言则进一步抽象了汇编语言:其将汇编语言中的各种加法指令,抽象成了一个简单的加号;将各种寄存器操作,抽象成了形参和实参...抽象思维是如此的普遍与自然,以至于我们往往甚至忽略了这种思维的存在。

但是,C语言并没有针对类型进行抽象的能力,C语言不知道,也没有能力表达“int和double都是数字”这一语义。而这,直接导致了这个“看起来非常简单的功能”难以完美的实现。

针对类型的抽象是如此重要,以至于编程语言世界出现了与C语言这样的“静态类型语言”完全不一样的“动态类型语言”。正如开头所示,在Python这样的动态类型语言中,我们根本就不需要为每个变量提供类型,从而似乎“从根本上解决了问题”。但是,“出来混,迟早要还的”,这种看似完美的动态类型语言,牺牲的却是极大的运行时效率!我们不禁陷入了沉思:真的没有既不损失效率,又能对类型进行抽象的方案了吗?

正当我们一筹莫展,甚至感到些许绝望之时,C++的模板,为我们照亮了前行的道路。

1 新手村——模板基础

1.1 函数模板与类模板

模板,即C++中用以实现泛型编程思想的语法组分。模板是什么?一言以蔽之:类型也可以是“变量”的东西。这样的“东西”,在C++中有二:函数模板和类模板。

通过在普通的函数定义和类定义中前置template <...>,即可定义一个模板,让我们以上文中的Plus函数进行说明。请看以下示例:

此为函数模板:

template <typename T>
T Plus(T lhs, T rhs)
{
    return lhs + rhs;
}


int main()
{
    cout << Plus(1, 2) << endl;          // 3,正确!
    cout << Plus(1.999, 2.999) << endl;  // 4.998,同样正确!
}

此为类模板:

template <typename T>
struct Plus
{
    T operator()(T lhs, T rhs)
    {
        return lhs + rhs;
    }
};


int main()
{
    cout << Plus<int>()(1, 2) << endl;             // 3,正确!
    cout << Plus<double>()(1.999, 2.999) << endl;  // 4.998,同样正确!
}

显然,模板的出现,使得我们轻而易举的就实现了类型抽象,并且没有(像动态类型语言那样)引入任何因为此种抽象带来的额外代价。

1.2 模板形参、模板实参与默认值

请看以下示例:

template <typename T>
struct Plus
{
    T operator()(T lhs, T rhs)
    {
        return lhs + rhs;
    }
};


int main()
{
    cout << Plus<int>()(1, 2) << endl;
    cout << Plus<double>()(1.999, 2.999) << endl;
}

上例中,typename T中的T,称为模板形参;而Plus<int>中的int,则称为模板实参。在这里,模板实参是一个类型。

事实上,模板的形参与实参既可以是类型,也可以是值,甚至可以是“模板的模板”;并且,模板形参也可以具有默认值(就和函数形参一样)。请看以下示例:

template <typename T, int N, template <typename U, typename = allocator<U>> class Container = vector>
class MyArray
{
    Container<T> __data[N];
};


int main()
{
    MyArray<int, 3> _;
}

上例中,我们声明了三个模板参数:

  1. typename T:一个普通的类型参数

  2. int N:一个整型参数

  3. template <typename U, typename = allocator<U>> class Container = vector:一个“模板的模板参数”

什么叫“模板的模板参数”?这里需要明确的是:模板、类型和值,是三个完全不一样的语法组分。模板能够“创造”类型,而类型能够“创造”值。请参考以下示例以进行辨析:

vector<int> v;

此例中,vector是一个模板,vector<int>是一个类型,而v是一个值。

所以,一个“模板的模板参数”,就是一个需要提供给其一个模板作为实参的参数。对于上文中的声明,Container是一个“模板的模板参数”,其需要接受一个模板作为实参 。需要怎样的模板呢?这个模板应具有两个模板形参,且第二形参具有默认值allocator<U>;同时,Container具有默认值vector,这正是一个符合要求的模板。这样,Container在类定义中,便可被当作一个模板使用(就像vector那样)。

1.3 特化与偏特化

模板,代表了一种泛化的语义。显然,既然有泛化语义,就应当有特化语义。特化,使得我们能为某些特定的类型专门提供一份特殊实现,以达到某些目的。

特化分为全特化与偏特化。所谓全特化,即一个“披着空空如也的template <>的普通函数或类”,我们还是以上文中的Plus函数为例:

// 不管T是什么类型,都将使用此定义...
template <typename T>
T Plus(T lhs, T rhs)
{
    return lhs + rhs;
}


// ...但是,当T为int时,将使用此定义
template <>  // 空空如也的template <>
int Plus(int lhs, int rhs)
{
    return lhs + rhs;
}


int main()
{
    Plus(1., 2.);  // 使用泛型版本
    Plus(1, 2);    // 使用特化版本
}

那么,偏特化又是什么呢?除了全特化以外的特化,都称为偏特化。这句话虽然简短,但意味深长,让我们来仔细分析一下:首先,“除了全特化以外的...”,代表了template关键词之后的“<>”不能为空,否则就是全特化,这显而易见;其次,“...的特化”,代表了偏特化也必须是一个特化。什么叫“是一个特化”呢?只要特化版本比泛型版本更特殊,那么此版本就是一个特化版本。请看以下示例:

// 泛化版本
template <typename T, typename U>
struct _ {};


// 这个版本的特殊之处在于:仅当两个类型一样的时候,才会且一定会使用此版本
template <typename T>
struct _<T, T> {};


// 这个版本的特殊之处在于:仅当两个类型都是指针的时候,才会且一定会使用此版本
template <typename T, typename U>
struct _<T *, U *> {};


// 这个版本“换汤不换药”,没有任何特别之处,所以不是一个特化,而是错误的重复定义
template <typename A, typename B>
struct _<A, B> {};

由此可见,“更特殊”是一个十分宽泛的语义,这赋予了模板极大的表意能力,我们将在下面的章节中不断的见到特化所带来的各种技巧。

1.4 惰性实例化

函数模板不是函数,而是一个可以生成函数的语法组分;同理,类模板也不是类,而是一个可以生成类的语法组分。我们称通过函数模板生成函数,或通过类模板生成类的过程为模板实例化。

模板实例化具有一个非常重要的特征:惰性。这种惰性主要体现在类模板上。请看以下示例:

template <typename T>
struct Test
{
    void Plus(const T &val)  { val + val; }
    void Minus(const T &val) { val - val; }
};


int main()
{
    Test<string>().Plus("abc");
    Test<int>().Minus(0);
}

上例中,Minus函数显然是不适用于string类型的。也就是说,Test类对于string类型而言,并不是“100%完美的”。当遇到这种情况时,C++的做法十分宽松:不完美?不要紧,只要不调用那些“不完美的函数”就行了。在编译器层面,编译器只会实例化真的被使用的函数,并对其进行语法检查,而根本不会在意那些根本没有被用到的函数。也就是说,在上例中,编译器实际上只实例化出了两个函数:string版本的Plus,以及int版本的Minus。

在这里,“懒惰即美德”占了上风。

1.5 依赖型名称

在C++中,“::”表达“取得”语义。显然,“::”既可以取得一个值,也可以取得一个类型。这在非模板场景下是没有任何问题的,并不会引起接下来即将将要讨论的“取得的是一个类型还是一个值”的语义混淆,因为编译器知道“::”左边的语法组分的定义。但在模板中,如果“::”左边的语法组分并不是一个确切类型,而是一个模板参数的话,语义将不再是确定的。请看以下示例:

struct A { typedef int TypeOrValue; };
struct B { static constexpr int TypeOrValue = 0; };


template <typename T>
struct C
{
    T::TypeOrValue;  // 这是什么?
};

上例中,如果T是A,则T::TypeOrValue是一个类型;而如果T是B,则T::TypeOrValue是一个数。我们称这种含有模板参数的,无法立即确定语义的名称为“依赖型名称”。所谓“依赖”,意即此名称的确切语义依赖于模板参数的实际类型。

对于依赖型名称,C++规定:默认情况下,编译器应认为依赖型名称不是一个类型;如果需要编译器将依赖型名称视为一个类型,则需要前置typename关键词。请看以下示例以进行辨析:

T::TypeOrValue * N;           // T::TypeOrValue是一个值,这是一个乘法表达式
typename T::TypeOrValue * N;  // typename T::TypeOrValue是一个类型,声明了一个这样类型的指针

1.6 可变参数模板

可变参数模板是C++11引入的一个极为重要的语法。这里对其进行简要介绍。

可变参数模板表达了“参数数量,以及每个参数的类型都未知且各不相同”这一语义。如果我们希望实现一个简单的print函数,其能够传入任意数量,且类型互不相同的参数,并依次打印这些参数值,此时就需要使用可变参数模板。

可变参数模板的语法由以下组分构成:

  1. typename...:声明一个可变参数模板形参

  2. sizeof...:获取参数包内参数的数量

  3. Pattern...:以某一模式展开参数包

接下来,我们就基于可变参数模板,实现这一print函数。请看以下示例:

// 递归终点
void print() {}


// 分解出一个val + 剩下的所有val
// 相当于:void print(const T &val, const Types1 &Args1, const Types2 &Args2, const Types3 &Args3, ...)
template <typename T, typename... Types>
void print(const T &val, const Types &... Args)
{
    // 每次打印一个val
    cout << val << endl;

    // 相当于:print(Args1, Args2, Args3, ...);
    // 递归地继续分解...
    print(Args...);
}


int main()
{
    print(1, 2., '3', "4");
}

上例中,我们实现了一对重载的print函数。第一个print函数是一个空函数,其将在“Args...”是空的时候被调用,以作为递归终点;而第二个print函数接受一个val以及余下的所有val作为参数,其将打印val,并使用余下的所有val继续递归调用自己。不难发现,第二版本的print函数具有不断打印并分解Args的能力,直到Args被完全分解。

2 平淡无奇却暗藏玄机的语法——sizeof与SFINAE

2.1 sizeof

“sizeof?这有什么可讨论的?”也许你会想。只要你学过C语言,那么对此必不陌生。那么为什么我们还需要为sizeof这一“平淡无奇”的语法单独安排一节来讨论呢?这是因为sizeof有两个对于泛型编程而言极为重要的特性:

  1. sizeof的求值结果是编译期常量(从而可以作为模板实参使用)

  2. 在任何情况下,sizeof都不会引发对其参数的求值或类似行为(如函数调用,甚至函数定义!等),因为并不需要

上述第一点很好理解,因为sizeof所考察的是类型,而类型(当然也包含其所占用的内存大小),一定是一个编译期就知道的量(因为C++作为一门静态类型语言,任何的类型都绝不会延迟到运行时才知道,这是动态类型语言才具有的特性),故sizeof的结果是一个编译期常量也就不足为奇了。

上述第二点意味深长。利用此特性,我们可以实现出一些非常特殊的功能。请看下一节。

2.2 稻草人函数

让我们以一个问题引出这一节的内容:

如何实现:判定类型A是否能够基于隐式类型转换转为B类型?

乍看之下,这是个十分棘手的问题。此时我们应当思考的是:如何引导(请注意“引导”一词的含义)编译器,在A到B的隐式类型转换可行时,走第一条路,否则,走第二条路?

请看以下示例:

template <typename A, typename B>
class IsCastable
{
private:

    // 定义两个内存大小不一样的类型,作为“布尔值”
    typedef char __True;
    typedef struct { char _[2]; } __False;


    // 稻草人函数
    static A __A();


    // 只要A到B的隐式类型转换可用,重载确定的结果就是此函数...
    static __True __Test(B);


    // ...否则,重载确定的结果才是此函数(“...”参数的重载确定优先级低于其他一切可行的重载版本)
    static __False __Test(...);


public:

    // 根据重载确定的结果,就能够判定出隐式类型转换是否能够发生
    static constexpr bool Value = sizeof(__Test(__A())) == sizeof(__True);
};

上例比较复杂,我们依次进行讨论。

首先,我们声明了两个大小不同的类型,作为假想的“布尔值”。也许你会有疑问,这里为什么不使用int或double之类的类型作为False?这是由于C语言并未规定“int、double必须比char大”,故为了“强行满足标准”(你完全可以认为这是某种“教条主义或形式主义”),这里采用了“两个char一定比一个char大一倍”这一简单道理,定义了False。

然后,我们声明了一个所谓的“稻草人函数”,这个看似毫无意义的函数甚至没有函数体(因为并不需要,且接下来的两个函数也没有函数体,与此函数同理)。这个函数唯一的目的就是“获得”一个A类型的值“给sizeof看”。由于sizeof的不求值特性,此函数也就不需要(我们也无法提供)函数体了。那么,为什么不直接使用形如“T()”这样的写法,而需要声明一个“稻草人函数”呢?我想,不用我说你就已经明白原因了:这是因为并不是所有的T都具有默认构造函数,而如果T没有默认构造函数,那么“T()”就是错误的。

接下来是最关键的部分,我们声明了一对重载函数,这两个函数的区别有二:

  1. 返回值不同,一个是sizeof的结果为1的值,而另一个是sizeof的结果为2的值

  2. 形参不同,一个是B,一个是“...”

也就是说,如果我们给这一对重载函数传入一个A类型的值时,由于“...”参数的重载确定优先级低于其他一切可行的重载版本,只要A到B的隐式类型转换能够发生,重载确定的结果就一定是调用第一个版本的函数,返回值为__True;否则,只有当A到B的隐式类型转换真的不可行时,编译器才会“被迫”选择那个编译器“最不喜欢的版本”,从而使得返回值为__False。返回值的不同,就能够直接体现在sizeof的结果不同上。所以,只需要判定sizeof(__Test(__A()))是多少,就能够达到我们最终的目的了。下面请看使用示例:

int main()
{
    cout << IsCastable<int, double>::Value << endl;  // true
    cout << IsCastable<int, string>::Value << endl;  // false
}

可以看出,输出结果完全符合我们的预期。

2.3 SFINAE

SFINAE(Substitution Failure Is Not An Error,替换失败并非错误)是一个高级模板技巧。首先,让我们来分析这一拗口的词语:“替换失败并非错误”。

什么是“替换”?这里的替换,实际上指的正是模板实例化;也就是说,当模板实例化失败时,编译器并不认为这是一个错误。这句话看上去似乎莫名其妙,也许你会有疑问:那怎么样才认为是一个错误?我们又为什么要讨论一个“错误的东西”呢?让我们以一个问题引出这一技巧的意义:

如何判定一个类型是否是一个类类型?

“哇!这个问题似乎比上一个问题更难啊!”也许你会这么想。不过有了上一个问题的铺垫,这里我们依然要思考的是:一个类类型,有什么独一无二的东西是非类类型所没有的?(这样我们似乎就能让编译器在“喜欢和不喜欢”之间做出抉择)

也许你将恍然大悟:类的成员指针。

请看以下示例:

template <typename T>
class IsClass
{
private:

    // 定义两个内存大小不一样的类型,作为“布尔值”
    typedef char __True;
    typedef struct { char _[2]; } __False;


    // 仅当T是一个类类型时,“int T::*”才是存在的,从而这个泛型函数的实例化才是可行的
    // 否则,就将触发SFINAE
    template <typename U>
    static __True __Test(int U::*);


    // 仅当触发SFINAE时,编译器才会“被迫”选择这个版本
    template <typename U>
    static __False __Test(...);


public:

    // 根据重载确定的结果,就能够判定出T是否为类类型
    static constexpr bool Value = sizeof(__Test<T>(0)) == sizeof(__True);
};

同样,我们首先定义了两个内存大小一定不一样的类型,作为假想的“布尔值”。然后,我们声明了两个重载模板,其分别以两个“布尔值”作为返回值。这里的关键在于,重载模板的参数,一个是类成员指针,另一个是“...”。显然,当编译器拿到一个T,并准备生成一个“T::*”时,仅当T是一个类类型时,这一生成才是正确的,合乎语法的;否则,这个函数签名将根本无法被生成出来,从而进一步的使得编译器“被迫”选择那个“最不喜欢的版本”进行调用(而不是认为这个“根本无法被生成出来”的模板是一个错误)。所以,通过sizeof对__Test的返回值大小进行判定,就能够达到我们最终的目的了。下面请看使用示例:

int main()
{
    cout << IsClass<double>::Value << endl;  // false
    cout << IsClass<string>::Value << endl;  // true
}

可以看出,输出结果完全符合我们的预期。

2.4 本章后记

sizeof,作为一个C语言的“入门级”语法,其“永不求值”的特性往往被我们所忽略。本章中,我们充分利用了sizeof的这种“永不求值”的特性,做了很多“表面工程”,仅仅是为了“给sizeof看”;同理,SFINAE技术似乎也只是在“找编译器的麻烦,拿编译器寻开心”。但正是这些“表面工程、找麻烦、寻开心”,让我们得以实现了一些非常不可思议的功能。

3 类型萃取器——Type Traits

Traits,中文翻译为“特性”,Type Traits,即为“类型的特性”。这是个十分奇怪的翻译,故很多书籍对这个词选择不译,也有书籍将其翻译为“类型萃取器”,十分生动形象。

Type Traits的定义较为模糊,其大致代表了这样的一系列技术:通过一个类型T,取得另一个基于T进行加工后的类型,或对T基于某一标准进行分类,得到分类结果。

本章中,我们以几个经典的Type Traits应用,来见识一番此技术的精妙。

3.1 为T“添加星号”

第一个例子较为简单:我们需要得到T的指针类型,即:得到“T *”。此时,只需要将“T *”通过typedef变为Type Traits类的结果即可。请看以下示例:

template <typename T>
struct AddStar { typedef T *Type; };


template <typename T>
struct AddStar<T *> { typedef T *Type; };


int main()
{
    cout << typeid(AddStar<int>::Type).name() << endl;    // int *
    cout << typeid(AddStar<int *>::Type).name() << endl;  // int *
}

这段代码十分简单,但似乎我们写了两遍“一模一样”的代码?认真观察和思考即可发现:特化版本是为了防止一个已经是指针的类型发生“升级”而存在的。如果T已经是一个指针类型,则Type就是T本身,否则,Type才是“T *”。

3.2 为T“去除星号”

上一节,我们实现了一个能够为T“添加星号”的Traits,这一节,我们将实现一个功能与之相反的Traits:为T“去除星号”。

“简单!”也许你会想,并很快给出了以下实现:

template <typename T>
struct RemoveStar { typedef T Type; };


template <typename T>
struct RemoveStar<T *> { typedef T Type; };


int main()
{
    cout << typeid(RemoveStar<int>::Type).name() << endl;    // int
    cout << typeid(RemoveStar<int *>::Type).name() << endl;  // int
}

似乎完成了?不幸的是,这一实现并不完美。请看以下示例:

int main()
{
    cout << typeid(RemoveStar<int **>::Type).name() << endl;  // int *,哦不!
}

可以看到,我们的上述实现只能去除一个星号,当传入一个多级指针时,并不能得到我们想要的结果。

这该如何是好?我们不禁想到:如果能够实现一个“while循环”,就能去除所有的星号了。虽然模板没有while循环,但我们知道:递归正是循环的等价形式。请看以下示例:

// 递归终点,此时T真的不是指针了
template <typename T>
struct RemoveStar { typedef T Type; };


// 当T是指针时,Type应该是T本身(已经去除了一个星号)继续RemoveStar的结果
template <typename T>
struct RemoveStar<T *> { typedef typename RemoveStar<T>::Type Type; };

上述实现中,当发现T选择了特化版本(即T本身是指针时),就会递归地对T进行去星号,直到T不再选择特化版本,从而抵达递归终点为止。这样,就能在面对多级指针时,也能够得到正确的Type。下面请看使用示例:

int main()
{
    cout << typeid(RemoveStar<int **********>::Type).name() << endl;  // int
}

可以看出,输出结果完全符合我们的预期。

显然,使用这样的Traits是具有潜在的较大代价的。例如上例中,为了去除一个十级指针的星号,编译器竟然需要实例化出11个类!但好在这一切均发生在编译期,对运行效率不会产生任何影响。

3.3 寻找“最强大类型”

让我们继续讨论前言中的Plus函数,以引出本节所要讨论的话题。目前我们给出的“最好实现”如下:

template <typename T>
T Plus(T lhs, T rhs)
{
    return lhs + rhs;
}


int main()
{
    cout << Plus(1, 2) << endl;  // 3,正确!
}

但是,只要在上述代码中添加一个“.”,就立即发生了问题:

int main()
{
    cout << Plus(1, 2.) << endl;  // 二义性错误!T应该是int还是double?
}

上例中,由于Plus模板只使用了单一的一个模板参数,故要求两个实参的类型必须一致,否则,编译器就不知道T应该是什么类型,从而引发二义性错误。但显然,任何的两种“数”之间都应该是可以做加法的,所以不难想到,我们应该使用两个而不是一个模板参数,分别作为lhs与rhs的类型,但是,我们立即就遇到了新的问题。请看以下示例:

template <typename T1, typename T2>
/* 这里应该写什么?*/ Plus(T1 lhs, T2 rhs)
{
    return lhs + rhs;
}

应该写T1?还是T2?显然都不对。我们应该寻求一种方法,其能够获取到T1与T2之间的“更强大类型”,并将此“更强大类型”作为返回值。进一步的,我们可以以此为基础,实现出一个能够获取到任意数量的类型之中的“最强大类型”的方法。

应该怎么做呢?事实上,这个问题的解决方案,确实是难以想到的。请看以下示例:

template <typename A, typename B>
class StrongerType
{
private:

    // 稻草人函数
    static A __A();
    static B __B();


public:

    // 3目运算符表达式的类型就是“更强大类型”
    typedef decltype(true ? __A() : __B()) Type;
};


int main()
{
    cout << typeid(StrongerType<int, char>::Type).name() << endl;    // int
    cout << typeid(StrongerType<int, double>::Type).name() << endl;  // double
}

上例中,我们首先定义了两个“稻草人函数”,用以分别“获取”类型为A或B的值“给decltype看”。然后,我们使用了decltype探测三目运算符表达式的类型,不难发现,decltype也具有sizeof的“不对表达式进行求值”的特性。由于三目运算符表达式从理论上可能返回两个值中的任意一个,故表达式的类型就是我们所寻求的“更强大类型”。随后的用例也证实了这一点。

有了获取两个类型之间的“更强大类型”的Traits以后,我们不难想到:N个类型之中的“最强大类型”,就是N - 1个类型之中的“最强大类型”与第N个类型之间的“更强大类型”。请看以下示例:

// 原型
// 通过typename StrongerType<Types...>::Type获取Types...中的“最强大类型”
template <typename... Types>
class StrongerType;


// 只有一个类型
template <typename T>
class StrongerType<T>
{
    // 我自己就是“最强大的”
    typedef T Type;
};


// 只有两个类型
template <typename A, typename B>
class StrongerType<A, B>
{
private:

    // 稻草人函数
    static A __A();
    static B __B();


public:

    // 3目运算符表达式的类型就是“更强大类型”
    typedef decltype(true ? __A() : __B()) Type;
};


// 不止两个类型
template <typename T, typename... Types>
class StrongerType<T, Types...>
{
public:

    // T和typename StrongerType<Types...>::Type之间的“更强大类型”就是“最强大类型”
    typedef typename StrongerType<T, typename StrongerType<Types...>::Type>::Type Type;
};


int main()
{
    cout << typeid(StrongerType<char, int>::Type).name() << endl;          // int
    cout << typeid(StrongerType<int, double>::Type).name() << endl;        // double
    cout << typeid(StrongerType<char, int, double>::Type).name() << endl;  // double
}

通过递归,我们使得所有的类型共同参与了“打擂台”,这里的“擂台”,就是我们已经实现了的StrongerType的双类型版本,而“打擂台的最后大赢家”,则正是我们所寻求的“最强大类型”。

有了StrongerType这一Traits后,我们就可以实现上文中的双类型版本的Plus函数了。请看以下示例:

// Plus函数的返回值应该是T1与T2之间的“更强大类型”
template <typename T1, typename T2>
typename StrongerType<T1, T2>::Type Plus(T1 lhs, T2 rhs)
{
    return lhs + rhs;
}


int main()
{
    Plus(1, 2.);  // 完美!
}

至此,我们“终于”实现了一个最完美的Plus函数。

3.4 本章后记

本章所实现的三个小工具,都是STL的type_traits库的一部分。值得一提的是我们最后实现的获取“最强大类型”的工具:这一工具所解决的问题,实际上是一个非常经典的问题,其多次出现在多部著作中。由于decltype(以及可变参数模板)是C++11的产物,故很多较老的书籍对此问题给出了“无解”的结论,或只能给出一些较为牵强的解决方案。

4 “压榨”编译器——编译期计算

值也能成为模板参数的一部分,而模板参数是编译期常量,这二者的结合使得通过模板进行(较复杂的)编译期计算成为了可能。由于编译器本就不是“计算器”,故标题中使用了“压榨”一词,以表达此技术的“高昂的编译期代价”以及“较大的局限性”的特点;同时,合理的利用编译期计算技术,能够极大地提高程序的效率,故“压榨”也有“压榨性能”之意。

本章中,我们以一小一大两个示例,来讨论编译期计算这一巧妙技术的应用。

4.1 编译期计算阶乘

编译期计算阶乘是编译期计算技术的经典案例,许多书籍对此均有讨论(往往作为“模板元编程”一章的首个案例)。那么首先,让我们来看看一个普通的阶乘函数的实现:

int Factorial(int N)
{
    return N == 1 ? 1 : N * Factorial(N - 1);
}

这个实现很简单,这里就不对其进行详细讨论了。下面,我们来看看如何将这个函数“翻译”为一个编译期就进行计算并得到结果的“函数”。请看以下示例:

// 递归起点
template <int N>
struct Factorial
{
    static constexpr int Value = N * Factorial<N - 1>::Value;
};


// 递归终点
template <>
struct Factorial<1>
{
    static constexpr int Value = 1;
};


int main()
{
    cout << Factorial<4>::Value;  // 编译期就能获得结果
}

观察上述代码,不难总结出我们的“翻译”规则:

  1. 形参N(运行时值)变为了模板参数N(编译期值)

  2. “N == 1”这样的“if语句”变为了模板特化

  3. 递归变为了创造一个新的模板(Factorial<N - 1>),这也意味着循环也可以通过此种方式实现

  4. “return”变为了一个static constexpr变量

上述四点“翻译”规则几乎就是编译期计算的全部技巧了!接下来,就让我们以一个更复杂的例子来继续讨论这一技术的精彩之处:编译期分数的实现。

4.2 编译期分数

分数,由分子和分母组成。有了上一节的铺垫,我们不难发现:分数正是一个可以使用编译期计算技术的极佳场合。所以首先,我们需要实现一个编译期分数类。编译期分数类的实现非常简单,我们只需要通过一个“构造函数”将模板参数保留下来,作为静态数据成员即可。请看以下示例:

template <long long __Numerator, long long __Denominator>
struct Fraction
{
    // “构造函数”
    static constexpr long long Numerator   = __Numerator;
    static constexpr long long Denominator = __Denominator;


    // 将编译期分数转为编译期浮点数
    template <typename T = double>
    static constexpr T Eval() { return static_cast<T>(Numerator) / static_cast<T>(Denominator); }
};


int main()
{
    // 1/2
    typedef Fraction<1, 2> OneTwo;

    // 0.5
    cout << OneTwo::Eval<>();
}

由使用示例可见:编译期分数的“实例化”只需要一个typedef即可;并且,我们也能通过一个编译期分数得到一个编译期浮点数。

让我们继续讨论下一个问题:如何实现约分和通分?

显然,约分和通分需要“求得两个数的最大公约数和最小公倍数”的算法。所以,我们首先来看看这两个算法的“普通”实现:

// 求得两个数的最大公约数
long long GreatestCommonDivisor(long long lhs, long long rhs)
{
    return rhs == 0 ? lhs : GreatestCommonDivisor(rhs, lhs % rhs);
}


// 求得两个数的最小公倍数
long long LeastCommonMultiple(long long lhs, long long rhs)
{
    return lhs * rhs / GreatestCommonDivisor(lhs, rhs);
}

根据上一节的“翻译规则”,我们不难翻译出以下代码:

// 对应于“return rhs == 0 ? ... : GreatestCommonDivisor(rhs, lhs % rhs)”部分
template <long long LHS, long long RHS>
struct __GreatestCommonDivisor
{
    static constexpr long long __Value = __GreatestCommonDivisor<RHS, LHS % RHS>::__Value;
};


// 对应于“return rhs == 0 ? lhs : ...”部分
template <long long LHS>
struct __GreatestCommonDivisor<LHS, 0>
{
    static constexpr long long __Value = LHS;
};


// 对应于“return lhs * rhs / GreatestCommonDivisor(lhs, rhs)”部分
template <long long LHS, long long RHS>
struct __LeastCommonMultiple
{
    static constexpr long long __Value = LHS * RHS /
        __GreatestCommonDivisor<LHS, RHS>::__Value;
};

有了上面的这两个工具,我们就能够实现出通分和约分了。首先,我们可以改进一开始的Fraction类,在“构造函数”中加入“自动约分”功能。请看以下示例:

template <long long __Numerator, long long __Denominator>
struct Fraction
{
    // 具有“自动约分”功能的“构造函数”
    static constexpr long long Numerator = __Numerator /
        __GreatestCommonDivisor<__Numerator, __Denominator>::__Value;

    static constexpr long long Denominator = __Denominator /
        __GreatestCommonDivisor<__Numerator, __Denominator>::__Value;
};


int main()
{
    // 2/4 => 1/2
    typedef Fraction<2, 4> OneTwo;
}

可以看出,我们只需在“构造函数”中添加对分子、分母同时除以其最大公约数的运算,就能够实现“自动约分”了。

接下来,我们来实现分数的四则运算功能。显然,分数的四则运算的结果还是一个分数,故我们只需要通过using,将“四则运算模板”与“等价的结果分数模板”连接起来即可实现。请看以下示例:

// FractionAdd其实就是一个特殊的编译期分数模板
template <typename LHS, typename RHS>
using FractionAdd = Fraction<

    // 将通分后的分子相加
    LHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__LValue +
    RHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__RValue,

    // 通分后的分母
    __LeastCommonMultiple<LHS::Denominator, RHS::Denominator>::__Value

    // 自动约分
>;


// FractionMinus其实也是一个特殊的编译期分数模板
template <typename LHS, typename RHS>
using FractionMinus = Fraction<

    // 将通分后的分子相减
    LHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__LValue -
    RHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__RValue,

    // 通分后的分母
    __LeastCommonMultiple<LHS::Denominator, RHS::Denominator>::__Value

    // 自动约分
>;


// FractionMultiply其实也是一个特殊的编译期分数模板
template <typename LHS, typename RHS>
using FractionMultiply = Fraction<

    // 分子与分子相乘
    LHS::Numerator * RHS::Numerator,

    // 分母与分母相乘
    LHS::Denominator * RHS::Denominator

    // 自动约分
>;


// FractionDivide其实也是一个特殊的编译期分数模板
template <typename LHS, typename RHS>
using FractionDivide = Fraction<

    // 分子与分母相乘
    LHS::Numerator * RHS::Denominator,

    // 分母与分子相乘
    LHS::Denominator * RHS::Numerator

    // 自动约分
>;


int main()
{
    // 1/2
    typedef Fraction<1, 2> OneTwo;

    // 2/3
    typedef Fraction<2, 3> TwoThree;

    // 2/3 + 1/2 => 7/6
    typedef FractionAdd<TwoThree, OneTwo> TwoThreeAddOneTwo;

    // 2/3 - 1/2 => 1/6
    typedef FractionMinus<TwoThree, OneTwo> TwoThreeMinusOneTwo;

    // 2/3 * 1/2 => 1/3
    typedef FractionMultiply<TwoThree, OneTwo> TwoThreeMultiplyOneTwo;

    // 2/3 / 1/2 => 4/3
    typedef FractionDivide<TwoThree, OneTwo> TwoThreeDivideOneTwo;
}

由此可见,所谓的四则运算,实际上就是一个针对Fraction的using(模板不能使用typedef,只能使用using)罢了。

最后,我们实现分数的比大小功能。这非常简单:只需要先对分母通分,再对分子进行比大小即可。而比大小的结果,就是“比大小模板”的一个数据成员。请看以下示例:

// 这六个模板都进行“先通分,再比较”运算,唯一的区别就在于比较操作符的不同

// “operator==”
template <typename LHS, typename RHS>
struct FractionEqual
{
    static constexpr bool Value =
        LHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__LValue ==
        RHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__RValue;
};


// “operator!=”
template <typename LHS, typename RHS>
struct FractionNotEqual
{
    static constexpr bool Value =
        LHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__LValue !=
        RHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__RValue;
};


// “operator<”
template <typename LHS, typename RHS>
struct FractionLess
{
    static constexpr bool Value =
        LHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__LValue <
        RHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__RValue;
};


// “operator<=”
template <typename LHS, typename RHS>
struct FractionLessEqual
{
    static constexpr bool Value =
        LHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__LValue <=
        RHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__RValue;
};


// “operator>”
template <typename LHS, typename RHS>
struct FractionGreater
{
    static constexpr bool Value =
        LHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__LValue >
        RHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__RValue;
};


// “operato>=”
template <typename LHS, typename RHS>
struct FractionGreaterEqual
{
    static constexpr bool Value =
        LHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__LValue >=
        RHS::Numerator * __CommonPoints<LHS::Denominator, RHS::Denominator>::__RValue;
};


int main()
{
    // 1/2
    typedef Fraction<1, 2> OneTwo;

    // 2/3
    typedef Fraction<2, 3> TwoThree;

    // 1/2 == 2/3 => false
    cout << FractionEqual<OneTwo, TwoThree>::Value << endl;

    // 1/2 != 2/3 => true
    cout << FractionNotEqual<OneTwo, TwoThree>::Value << endl;

    // 1/2 < 2/3 => true
    cout << FractionLess<OneTwo, TwoThree>::Value << endl;

    // 1/2 <= 2/3 => true
    cout << FractionLessEqual<OneTwo, TwoThree>::Value << endl;

    // 1/2 > 2/3 => false
    cout << FractionGreater<OneTwo, TwoThree>::Value << endl;

    // 1/2 >= 2/3 => false
    cout << FractionGreaterEqual<OneTwo, TwoThree>::Value << endl;
}

至此,编译期分数的全部功能就都实现完毕了。不难发现,在编译期分数的使用过程中,我们全程使用的都是typedef,并没有真正的构造任何一个分数,一切计算都已经在编译期完成了。

4.3 本章后记

读完本章,也许你会恍然大悟:“哦!原来模板也能够表达形参、if、while、return等语义!”,进而,也许你会有疑问:“那既然这样,岂不是所有的计算函数都能换成编译期计算了?”。

很可惜,答案是否定的。

我们通过对编译期计算这一技术的优缺点进行总结,从而回答这个问题。编译期计算的目的,是为了完全消除运行时代价,从而在高性能计算场合极大的提高效率;但此技术的缺点也是很多且很明显的:首先,仅仅为了进行一次编译期计算,就有可能进行很多次的模板实例化(比如,为了计算10的阶乘,就要实例化出10个Factorial类),这是一种极大的潜在的编译期代价;其次,并不是任何类型的值都能作为模板参数,如浮点数(虽然我们可以使用编译期分数间接的规避这一限制)、以及任何的类类型值等均不可以,这就使得编译期计算的应用几乎被限定在只需要使用整型和布尔类型的场合中;最后,“递归实例化”在所有的编译器中都是有最大深度限制的(不过幸运的是,在现代编译器中,允许的最大深度其实是比较大的)。但即使如此,由于编译期计算技术使得我们可以进行“抢跑”,在程序还未开始运行时,就计算出各种复杂的结果,从而极大的提升程序的效率,故此技术当然也是瑕不掩瑜的。

注:本文中的部分程序已完整实现于本文作者的Github上,列举如下:

  1. 编译期分数:https://github.com/yingyulou/Fraction

  2. print函数:https://github.com/yingyulou/pprint

  3. Tuple:https://github.com/yingyulou/Tuple

  4. 表达式模板:https://github.com/yingyulou/ExprTmpl

本篇完,敬请期待下篇

作者:樱雨楼,毕业于生物信息学专业,是一枚 Python/C++/Perl 开发,R 语言黑粉,Github 勾搭  https://github.com/yingyulou

猫注: 本文所有赞赏,归樱雨楼小姐姐所有,鼓励优质原创,支持好文章!

:point_up_2:  扫码赞赏她

分享到: