C++ CRTP(Curiously Recurring Template Pattern)简介

C++ CRTP(Curiously Recurring Template Pattern)简介

By Z.H. Fu, X.Y. Xu

切问录 www.fuzihao.org

虚函数效率缺陷

在需要使用多态的场合中,我们采用虚函数来实现。具体来说,一般实现多态是采用如下虚函数的方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
struct Base{
virtual void eval() = 0;
};

struct Derived:public Base{
void eval(){
cout<<"in Derived.";
}
};

int main(){
Derived d;
Base* b = &d;
b->eval();
return 0;
}

这是一个最简单的继承的例子,在基类中定义一个纯虚函数,子类实现了这个函数,用基类指针指向子类并调用该函数时,可调用子类的函数。然而虚函数的实现机制是通过查询虚函数表(vtable),而这个过程需要耗费一定时间,如果是对效率要求较高的程序,则会受到影响。

CRTP(Curiously Recurring Template Pattern)

为了解决这个问题,我们引入CRTP(Curiously Recurring Template Pattern)的方式静态绑定模板,CRTP能在编译阶段静态决定“虚函数”的调用关系,其示例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
template<typename Derived>
struct Base{
void eval(){
static_cast<Derived&>(*this).eval();
}
};

struct Child:Base<Child>{
void eval(){
cout<<"eval in Child;"<<endl;
}
};

template<typename T>
void test(Base<T>& t){
t.eval();
}
int main(){
Child c;
test(c);
}

我们可以看到,静态绑定最直观的特征就是将子类作为模板类型传给基类,基类在相应的函数里通过static_cast,将this指针转化为子类类型,以此调用子类的相应函数。这种方式在编译阶段已经完成,不涉及运行时查询虚函数表,提高了程序效率。这种方法在Eigen库里得到了大量的使用,Eigen是一个线性代数库,其很多操作的实现采用了惰性求值(C++实现惰性求值)的手段,而惰性求值则要求所有的不同类型结果基于同一个基类,因此继承被大量采用,而Eigen是一个追求效率的库,因此用静态绑定代替了虚函数的使用。

参考文献

[1] https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Curiously_Recurring_Template_Pattern
[2] https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern
[3]C++实现惰性求值