C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do it blows your whole leg off.

—— C++ 之父,Bjarne Stroustrup

C++ 是一门非常强大而复杂的语言,而模板(template)则是其“主打功能”之一。可以说,没有了模板,C++ 就不会是 C++,它不会有现在这样的灵活性和可拓展性,也不会像现在这样因为过于复杂而受人诟病。

本文将介绍 C++ 模板的一些较为少见但是非常强大的应用。为了读懂本文,你需要:

  • 有基础的编程知识和经验;
  • 能够看懂 C++ 代码;
  • 对于未知的事物充满好奇心。

如果你具备上面这些条件,那么就做好准备认识你所不知道的 template 吧!

从基础开始

为了照顾不太明白的读者,我们先很简单地讲一下什么是 C++ 的模板。已经了然于心的读者们可以选择再来复习一遍,或者跳过这一小节。

在传统的 C 语言中,不同的函数不能有相同的名字。这个规定其实非常好理解,因为很多时候函数操作会依赖于特定的类型。但我们也没法排除有一些不依赖于类型的通用算法,如果要为每种类型都定义一个名字不同的函数,再在每个函数里实现一遍算法,岂不是很麻烦?

于是 C++ 标准委员会(ISO C++ committee)就想,我们要在 C++ 里加入一个新功能,使得程序员可以写出不依赖于具体类型的泛型(generic)代码。这个新功能就是模板。在 C++ 中,我们可以通过如下语法定义一个模板函数:

template <class T>
T max(T a, T b) {
	if (a > b) return a;
	return b;
}

从函数名和函数的执行过程我们很容易推断出,它的作用就是找出并返回ab中的较大值。但是这个T是个什么玩意儿呢?

其实T是在代码第一行里定义的class T,它代表的是一个任意的类型。也就是说,这个函数接受两个类型相同的东西,并返回一个同样类型的东西。

既然有了模板函数,我们也可以弄出一个模板类:

template <int N, int M, typename T>
class Matrix {
private:
	T array[N][M];
public:
	Matrix();
	static Matrix identityMatrix();
	T &elementAtIndex(int x, int y) {
		return array[x][y];
	}
	const T &elementAtIndex(int x, int y) const {
		return array[x][y];
	}
} ;

注意到我们可以指定多个泛型的参数,而且这些参数还不一定得是T这样的类型参数——它还可以是非类型参数,如这里的整型N,甚至可以是嵌套的模板参数。

这些非常简单的例子可以让我们略微感受到模板的强大之处:只要类型T可以拷贝构造、定义了大于运算符,就可以套用这个函数。如果我们有心,可以用模板实现一整套泛型的算法,并提供简单的借口。设想一下,当我们要给自定义的类型排序的时候,不需要手写快排,而定义比较操作符,直接调用一个模板函数即可;当我们要使用某些数据结构的时候,直接把我们的类名告诉模板类即可。

事实上 C++ 的 STL 就是这样一个玩意儿。STL 的全称是 Standard Template Library,里面用模板实现了各种泛型的算法和数据结构。随叫随到,即写即用,从此无心造轮子,管他开不开 O2。

限于篇幅原因,模板的基础知识只能介绍到这。有关模板的更多知识,推荐大家阅读这个网页:https://isocpp.org/wiki/faq/templates

模板元编程

模板当然是个好东西,它非常之强大,可以完成原来写C代码时想都不敢想的功能。但问题也就在于它太强大了,就连当初设计模板的人也不知道它究竟有多么厉害。事实上,可以证明模板的这套语言本身就是图灵完备的,也就是说,光是使用模板,我们就可以在编译时完成一切计算。这就是所谓的模板元编程(template metaprogramming,TMP)。

从斐波那契谈起

如果要你用正常的 C++ 求斐波那契数列,你会怎么写?当然会是像下面这样:

const int N = 100;
int a[N + 1];
a[0] = 0, a[1] = 1;
for (int i = 2; i <= N; ++i)
	a[i] = a[i - 1] + a[i - 2];

或者是直接写递归的版本:

int fib(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fib(n - 1) + fib(n - 2);
}

其实我们可以用模板来做:

template <int N>
struct Fib {
	static const int value = Fib<N-1>::value + Fib<N-2>::value;
} ;

template <>
struct Fib<0> {
	static const int value = 0;
} ;

template <>
struct Fib<1> {
	static const int value = 1;
} ;

我们在Fib类里定义了一个静态的常量value,代表第N个斐波那契数的值。N = 0N = 1的两个模板特化是递归的边界条件,一般的情况则直接利用公式递归计算。整个计算过程都是在编译时完成的,而且由于模板的实例化机制,这个递归的过程还是记忆化的,即同一个斐波那契数不会被计算两次,计算的复杂度为 $O(N)$ 而非 $O(fibonacci(N))$ 。

如果我们要使用第10个斐波那契数列的值,只要用Fib<10>::value就可以了。值得一提的是,由于计算过程需要在编译时完成,模板中的参数必须得是编译时就知晓其值的常量。

另外,通常编译器会对模板的递归层数作限制,在clang编译器上默认是256层。可以使用-ftemplate-depth=N来将层数设为N,但太大的层数会使得编译器自己栈溢出……所以这玩意并没有什么○用。

但是这又有什么○用呢?

虽说是节省了运行时间,但必须在编译时确定所有数值,加之N还不能太大,感觉上并没有什么○用。

但TML可不光是编译时算数这么简单。下面将介绍两个TML在实际中的应用,请坐和放宽,准备打开新世界的大门。

CRTP

这个看上去超级高大上的缩写,全称其实是 Curiously Recurring Template Pattern1,直译过来就是“神奇递归模板模式”,一下就显得傻里傻气的了。

为什么叫这个名字呢?我们先来看一段代码:

template <class Derived>
struct Base {
	void polymorphism() {
		static_cast<Derived*>(this)->_poly();
	}
	static void static_poly() {
		Derived::_static_poly();
	}
	// Default implementation
	void _poly();
	static _static_poly();
} ;

struct Derived : public Base<Derived> {
	void _poly();
//	void _static_poly();
}

嗯,Base类是一个正常的模板类,虽然内容有点不明觉厉。但Derived类是什么鬼?为啥能把自己作为父类的模板参数?这岂不是“我依赖于我爸依赖于我”的状况 = = ?

然而这段代码是可以通过编译的合法代码。原因有二:

  • 虽然Base需要了解Derived的定义,但其不直接或间接包含Derived类的实例,也即其大小不依赖于Derived
  • 模板类会在被使用时实例化,而此时Base类与Derived类的定义均已知晓;就此段代码而言,编译器可以检验Derived类是否包含_poly()_static_poly()函数的定义,如果没有找到,则会在其父类Base<Derived>类中寻找。

一般人在第一次看到这个玄学一般的用法时都会目瞪口呆不知所措。先不要惊讶,我们来看看用这种写法能做什么:

无需 VTABLE 的编译时多态

C++ 实现多态的方法是将类内所有的虚(virtual)函数存在一个被称为VTABLE的数组中,在运行时调用一个虚函数时,实际调用表中指向的函数。这个方法有个缺点,就是必须维护这么一个表,从而产生额外开销(overhead)。

而利用 CRTP 则可以在实现多态的同时,省去这个表的开销。我们看上面那段代码,在Base类(下称基类)和Derived类(下称派生类)中都定义有_poly()(非虚)函数,理论上基类是访问不到派生类中的函数的。但是这里不一样,基类拥有额外的信息:派生类叫什么。所以基类在调用之前,将自己转换成了派生类。这个转换是可行的,因为事实上,自己本身就是自己的派生类(有点绕,感受一下)。这么一来,调用的就是派生类中的函数了。如果派生类中没有定义_poly()函数,则编译器会找到基类中的同名函数;如果定义了_poly()函数,则它会覆盖掉基类中的同名函数,故编译器会找到派生类中的函数。这样我们就在编译器实现了多态。

不过 CRTP 的这个多态并非真正的多态。如果我们有一个派生类的实例,通过 CRTP,基类中定义的函数可以调用派生类中重载的“虚”函数。但如果我们的派生类以基类指针的形式存在,我们则无法通过其访问到派生类的虚函数。后者被成为运行时多态,是 CRTP 力不能及的。

通用基类

有时候我们会遇到这样的问题:我们只有一个基类的指针,而我们要进行一次深拷贝,如下:

struct Base {};
struct Derived : public Base {};
struct AnotherDerived : public Base {};

void copy(Base *p) {
	Base *copy_p = new ???(*p);
}

于是我们懵逼了,这个???该填啥啊,写基类不对吧,写派生类也不知道是哪个啊,咋办?

一个解决方式定义一个名为clone()的虚函数,然后在每个派生类中重载:

struct Base {
	virtual Base *clone() const = 0;
} ;
struct Derived : public Base {
	virtual Derived *clone() const {
		return new Derived(*this);
	}
}
struct AnotherDerived : public Base {
	virtual AnotherDerived *clone() const {
		return new AnotherDerived(*this);
	}
}

这份代码可以正常运作,但显得十分不优美:每个类里都得写一遍,这样不仅有大量重复代码,还容易出错。

我们来分析一下为什么需要这样写,问题似乎在于,我的基类不知道我到底是啥,所以我需要在派生类里定义虚函数。这不就是 CRTP 解决的问题吗?我们把代码改成下面这样2

struct Base {
	virtual Base *clone() const = 0;
};

template <class Derived>
struct BaseCRTP : public Base {
	virtual Base *clone() const {
		return new Derived(static_cast<Derived const &>(*this));
	}
}

struct Derived : public BaseCRTP<Derived> {};

假设我们有一个Derived类的实例,在经历了一些事情之后,它变成了Base类的指针。现在我们通过这个指针调用clone()函数,通过虚函数的机制,我们会找到BaseCRTP<Derived>类的clone()函数。此时我们已经知道了派生类的名字,也就可以完成深拷贝了。

如果分析一下背后的原因,我们会发现,每次定义一个派生类,编译器都会实例化一份BaseCRTP出来。所以并没有什么神奇的,其实只是编译器帮我们生成了我们本应手写的代码而已。CRTP 的其他应用,比如实例计数器,也都是基于这个原理。

SFINAE

又是一个高大上的缩写,不急,我们先把它展开了:全称为 Substitution failure is not an error3。这都不是一个词组了,而是一句话:替换失败不被视为编译错误。当替换失败时,编译器不报错,而只是将这个模板从待选的重载函数集中移除,不考虑失败的这一个模板而已。

在实例化一个模板时,编译器需要把模板参数中的东西替换为实际的类型或值,然而替换是可能失败的,比如下面这个例子:

template <class T>
void defined_foo(typename T::foo) {}

template <class T>
void defined_foo(T) {}

struct Foo {
	typedef int foo;
} ;

这里我们定义了两个版本的defined_foo(),接受不同的参数。typename关键字是为了消除歧义,告诉编译器T::foo绝壁是个类型名。由于是模板函数,编译器得做类型替换,这里就可能出现替换失败的情况,比如:

defined_foo<Foo>(0);
defined_foo<int>(0);

第一行,Foo类中有foo类型,所以在第一个模板中替换成功,而在第二个模板中替换失败;第二行,int类型显然不包含别的类型,所以在第一个模板中替换失败,而在第二个模板中替换成功。这两个情况中,都是恰有一个重载的模板替换成功,都不会报错。

看上去是非常自然而且简单的做法吧?你绝对想不到可以用这玩意儿做什么:

编译时自省

先说说什么是自省。子曰:“见贤思齐焉,见不贤而内自省也”,不过这和我们要讲的自省没有半毛钱关系。

所谓自省,其实就是程序自己知道自己的情况。比如在 Python 中,程序可以在运行时查看自己的代码,获取某个类的名称、成员,甚至是实时增减成员。对于 C++ 这种强类型语言来说,这显然不现实。但通过 SFINAE,我们可以实现一定程度上的自省。

上面的那个例子,其实就是某种自省。我们可以在编译时判断一个类是否满足某种条件,从而调用不同的函数。在 STL 中,有一个神秘的头文件叫<type_traits>(C++11 的新特性),其中包含了很多判断类型的类型的东西,如is_arrayis_class等。这些东西其实是用 SFINAE 实现的模板类,其中包含一个名为value的成员,代表判断的值是真是假。

这么说可能有些玄,我们来看一个具体的、真实存在的例子:

boost::enable_if

先上代码再解释:

template<bool Cond, class T = void>
struct enable_if_c
{ typedef T type; };

template<class T>
struct enable_if_c<false, T> {};

template<class Cond, class T = void>
struct enable_if : enable_if_c<Cond::value, T> {};

// === 我是分割线 ===
template<class T>
typename enable_if<is_floating_point<T>, T>::type
  frobnicate(T t) {}

is_floating_point也是<type_traits>里的东西,其作用正如其名。enable_if的实现是,如果第一个参数的条件为true,那么其中会包含一个type类型,为第二个参数的类型;否则不会有这个类型。拿分割线下的函数举例,如果第一个参数的条件,即T是浮点类型,为false,那么在使用这个函数时就会产生替换错误。所以enable_if的作用可以理解为限制模板所能够接受的类型。

不过这个写法有点丑陋,毕竟返回类型这么长;所以另一个常见的写法是添加一个虚设的(dummy)参数,并在参数里实现 SFINAE4

template <class T>
T frobnicate(T t, typename enable_if<is_floating_point<T>, T>::type * = 0) {}

type_traits

整个<type_traits>库过于庞大,以个人之力无法看穿,只能挑选一些浅薄的所见所得与大家分享。下面的代码均来自<type_traits>库,为了便于阅读,删去了一部分不影响理解的内容。

首先,我们需要两个类true_typefalse_type,用来区分结果。这两个类中应当定义value,类型为bool,值分别为truefalse

然后,我们要考虑 cv 修饰符(constvolatile)的问题,它们不应影响我们对类型的判断。remove_cv的作用是去除类型中的 cv 修饰符,它的实现如下:

// remove_const
template <class _Tp> struct remove_const {typedef _Tp type;};
template <class _Tp> struct remove_const<const _Tp> {typedef _Tp type;};

// remove_volatile
// ...

// remove_cv
template <class _Tp> struct remove_cv {
	typedef typename remove_volatile<typename remove_const<_Tp>::type>::type type;
};

这里利用模板的匹配功能,获得了类型去掉 cv 修饰符后的名字,并记在了remove_cv::type中。

接下来就可以判断了。先看一个简单的,is_null_pointer

template <class _Tp> struct __is_nullptr_t_impl : public false_type {};
template <> struct __is_nullptr_t_impl<nullptr_t> : public true_type {};

template <class _Tp> struct _LIBCPP_TYPE_VIS_ONLY is_null_pointer
    : public __is_nullptr_t_impl<typename remove_cv<_Tp>::type> {};

nullptr_t是 C++11 中加入的空指针类型。这个判断很简单,不用多说。

下面则是一个特别玄的判断:is_base_of,判断B是否是D的基类。由于<type_traits>中的代码过于复杂,下面给出的代码是 StackOverflow 上一个问题里5的简化版代码:

typedef char (&yes)[1];
typedef char (&no)[2];

template <class B, class D>
struct Host {
	operator B*() const;
	operator D*();
} ;

template <class B, class D>
struct is_base_of {
	template <class T> 
	  static yes test(D*, T);
	static no test(B*, int);
	
	static const bool value = sizeof(test(Host<B,D>(), int())) == sizeof(yes);
} ;

我们把true_typefalse_type改成了yesno,通过其内存大小来判断类型;这个并不重要。

要理解这段代码的原理,首先我们需要知道 C++ 标准中,有多个可选函数时会优先选择哪方:

  • 原则1:如果两个函数参数类型相同,而 cv 修饰符不同,则优先选择与传入参数 cv 修饰符匹配的一方;
  • 原则2:如果原则1无法区分,且两个类型转换函数返回类型不同,则优先选择与目标参数匹配的一方;
  • 原则3:如果原则2无法区分,优先选择非模板函数。

现在我们来分析一下代码的原理。Host的两个类型转换函数的原型分别为

  • B *(Host<B, D> const &)
  • D *(Host<B, D> &)

假设BD的基类,那么D *可以转换为B *,反则不行。对于第一个test函数,可选的转换函数只有第二个;而对于第二个test函数,两个转换函数都可选,根据原则1,编译器会第二个选择转换函数(因为默认的传入参数为*this,为非const类型)。此时第一个test函数的目标类型与转换函数的返回类型匹配,而第二个的不匹配,根据原则2,编译器会选择第一个test函数,故得到yes

假设B不是D的基类,那么D *不可以转换为B *,反之或许可以。对于第二个test函数,可选的转换函数只有第一个;对于第一个test函数,可选的转换函数有第二个,也可能有第一个,但一定会选择第二个。此时根据原则3,编译器会选择第二个test函数,故得到no

总结

写了这么多,其实也只涉及了模板的冰山一角。由此可见这一功能的强大与复杂,也不难理解为何模板一直处于争论的中心,甚至有这么一个笑话:“Java 程序员聚在一起谈面向对象和设计模式,C++ 程序员聚在一起谈模板和语言规范到底是怎么回事”,嘲笑的就是 C++ 令人咂舌的复杂程度。

但一码归一码,C++ 还是一门被广泛使用的语言,因此适当的了解还是必要的。而本文中提到的用法,可能大家没有见过,但在工程中的确是普遍存在的。就拿 CRTP 来说,Boost 库的文法分析库 Spirit、计算几何库 CGAL 的整个核心中都使用了 CRTP;而 SFINAE 更是已经进入了 C++ 标准。即便自己不会写出这样的代码,至少在见到的时候也应该明白是在干什么;退一步讲,把这篇文章当成是普通的科普文章,图个乐呵也好。

参考文献