C++:奇异递归模板模式(CRTP)

奇异递归模板(Curiously Recurring Template Pattern,CRTP)正如其名,是一种递归式利用c++模板的设计模式,更一般地被称作F-bound polymorphism,是我最近在开发数学库的时候听闻的一种惯用法。

What is CRTP?

CRTP的代码很简单,可以用如下的代码演示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename Child> struct Base {
void interface() { static_cast<Child *>(this)->implementation(); }
};

struct Derived : Base<Derived> {
void implementation() { cerr << "Derived implementation\n"; }
};

template <typename ChildType> struct VectorBase {
ChildType &underlying() { return static_cast<ChildType &>(*this); }
inline ChildType &operator+=(const ChildType &rhs) {
this->underlying() = this->underlying() + rhs;
return this->underlying();
}
};

父类接收一个子类作为模板参数,子类在实现的时候将自身传入(递归),父类利用这个模板参数将自身静态转换为子类的引用后调用子类的函数。

可以发现,CRTP本质就是静态多态,即:在编译期实现的同名函数不同行为,在Base类中设置好的interface函数可以根据子类的implementation函数的实现不同来产生不同的行为。听起来是不是和虚函数很像?其实上面这段代码的实现效果和下面的虚函数实现版本代码很像:

1
2
3
4
5
6
7
struct VBase {
void interface() {}
virtual void implementation() { cout << "VBase" << endl; }
};
struct VDerived : public VBase {
void implementation() override { cout << "VDerived" << endl; }
};

Why CRTP?

既然和虚函数实现的效果是一致的,并且在模板技术已经相当成熟的当下(如C++20中已经可以使用的concept),为什么还要使用CRTP?简单列举一个例子,比如我要实现一个数学库,如果使用运行时多态来实现向量类Vector,那么代码结构大致如下:

1
2
3
4
5
6
7
8
template<typename Type, unsigned Len>
struct VectorBase{
virtual void someFunction(){...}
...
};
struct Vector3: VectorBase<float, 3>{
virtual void someFunction() override {...}
};

需要注意的是,运行时多态是有开销的,熟悉c++虚函数的人应该就能明白,如果我调用一个虚函数,需要查询对象头部的虚函数表来得到实际函数地址,这个寻址的开销对于一个数学库而言是非常巨大的。而如果使用静态多态,则可以使用如下的代码来实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename ChildType> struct VectorBase {
ChildType &underlying() { return static_cast<ChildType &>(*this); }
inline ChildType &operator+=(const ChildType &rhs) {
this->underlying() = this->underlying() + rhs;
return this->underlying();
}
};
struct Vec3f : public VectorBase<Vec3f> {
float x{}, y{}, z{};
Vec3f() = default;
Vec3f(float x, float y, float z) : x(x), y(y), z(z) {}
};

inline Vec3f operator+(const Vec3f &lhs, const Vec3f &rhs) {
Vec3f result;
result.x = lhs.x + rhs.x;
result.y = lhs.y + rhs.y;
result.z = lhs.z + rhs.z;
return result;
}

可以看到,静态多态虽然导致代码复用度相较于运行时多态降低了很多,但是相较于完全手搓,我们可以利用子类实现的operator+来通过CRTP自动添加operator+=,相当于是做到了运行效率与开发效率的相对平衡。

Summary

CRTP在80年代被提出,但是至今仍然被广泛使用,虽然今天运行时多态已经相当成熟,但是我们仍然希望能在运行效率和开发效率之间做到平衡,这时CRTP就成为了我们的不二之选:拥有多态的代码复用性的同时可以除去动态多态的runtime开销。

本文相关代码在crtp.cpp

参考资料

作者

Carbene Hu

发布于

2022-07-14

更新于

2022-08-05

许可协议

评论