cxx CRTP

六月 13, 2022 [c++] #c++

cxx CRTP

Curiously Recurring Template Pattern 的概念

C++ 通过类的继承与虚函数的动态绑定，实现了多态。这种特性，使得我们能够用基类的指针，访问子类的实例。例如我们可以实现一个名为 Animal 的基类，以及 Cat, Dog 等子类，并通过在子类中重载虚函数 jump，实现不同动物的跳跃动作。而后我们可以通过访问 Zoo 类的实例中存有 Animal 指针的数组，让动物园中所有的动物都跳一遍。

class Zoo {
 ...
 private:
    std::vector<shared_ptr<Animal>> animals;
 public:
    void () {
        for (auto animal : animals) {
            animal->jump();
        }
    }
 ...
}

在每次执行 animal->jump() 的时候，系统会检查 animal 指向的实例实际的类型，然后调用对应类型的 jump 函数。这一步骤需要通过查询虚函数表（vtable）来实现；由于实际 animal 指向对象的类型在运行时才确定（而不是在编译时就确定），所以这种方式称为动态绑定（或者运行时绑定）。

因为每次都需要查询虚函数表，所以动态绑定会降低程序的执行效率。为了兼顾多态与效率，有人提出了 Curiously Recurring Template Pattern 的概念。

通过模板实现静态绑定

把派生类作为基类的模板参数：父类是一个模板类，当子类继承父类时，传入的模板类型为子类本身（这样父类就可以调用子类的相关方法了（通过this））

为了在编译时绑定，我们就需要放弃 C++ 的虚函数机制，而只是在基类和子类中实现同名的函数；同时，为了在编译时确定类型，我们就需要将子类的名字在编译时提前传给基类。因此，我们需要用到 C++ 的模板。

#include <iostream>

using namespace std;

template<typename T>
class Base {
 public:
    void show () const {
        static_cast<const T*>(this)->show();
    }
};

class Derived: public Base<Derived> {
 public:
    // 这里子类中如果不定义 show; 则调用show时会递归的调用Base中的show，最后爆栈!!!!
    void show () const {
        cout << "Shown in Derived class." << endl;
    }
};

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

用在哪里？

现在我们考虑这样一个问题。

在使用虚函数的风格中，我们可以把 Cat , Dog... 等不同子类的指针，复制给基类的指针 Animal*，然后把基类的指针存入容器中（比如 vector<Animal*>）。但是，在 CRTP 中，我们就做不到这样了。这是因为同样是基类的指针 Animal<Cat>* 和 Animal<Dog>* 是两种完全不同的类型的指针。这样一来，我们就没法构造一个动物园了。

那么，CRTP 到底应该怎么用呢？我们不妨回过头来想一想，最初我们引入 CRTP 是为了什么。文章开头的第一段，我们提到多态是个很好的特性，但是动态绑定比较慢，因为要查虚函数表。而事实上，动态绑定慢，通常是因为多级继承；如果继承很短，那么查虚函数表的开销实际上也没多大。

在之前举出的例子里，我们运用 CRTP，完全消除了动态绑定；但与此同时，我们也在某种意义上损失了多态性。现在我们希望二者兼顾：保留多态性，同时降低多级继承带来的虚函数表查询开销。答案也很简单：让 CRTP 的模板类继承一个非模板的基类——这相当于这个非模板的基类会有多个平级的不同的子类。一个示例如下。

#include <iostream>
#include <vector>

using std::cout; using std::endl;
using std::vector;

class Animal {
 public:
    virtual void say () const = 0;
    virtual ~Animal() {}
};

template <typename T>
class Animal_CRTP: public Animal {
 public:
    void say() const override {
        static_cast<const T*>(this)->say();
    }
};

class Cat: public Animal_CRTP<Cat> {
 public:
    void say() const {
        cout << "Amimal_CRTP:\n";
        cout << "Meow~ I'm a cat." << endl;
    }
};

class Dog: public Animal_CRTP<Dog> {
 public:
    void say() const {
        cout << "Wang~ I'm a dog." << endl;
    }
};

int main () {
    vector<Animal*> zoo;
    zoo.push_back(new Cat());
    zoo.push_back(new Dog());
    // 这里并不会调用Animal_CRTP 的say函数
    for (vector<Animal*>::const_iterator iter{zoo.begin()}; iter != zoo.end(); ++iter) {
        (*iter)->say();
    }
    for (vector<Animal*>::iterator iter{zoo.begin()}; iter != zoo.end(); ++iter) {
        delete (*iter);
    }
    return 0;
}

应用

IComparable

我们常常在Java和C的更加强大。

#include<iostream>
using namespace std;
template<typename T>
class IComparable
{
public:
    bool less(const IComparable<T>& b) const {
        return this->lessImpl(b);
    }
    bool greater(const IComparable<T>& b) const {
        return b.less(*this);
    }
    bool notLess(const IComparable<T>& b) const {
        return !this->less(b);
    }
    bool notGreater(const IComparable<T>& b) const {
        return !this->greater(b);
    }
    bool equal(const IComparable<T>& b) const {
        return !this->less(b) && !this->greater(b);
    }
    bool notEqual(const IComparable<T>& b) const {
        return !this->equal(b);
    }
private:
    bool lessImpl(const IComparable<T>& b) const {
        return true;
    }
}; // Need Derived to override lessImpl().
class A : public IComparable<A>
{
public:
    A(int num):N(num){}
    bool lessImpl(const A& b){
        return N < b.N;
    }
private:
    int N;
};
class B : public IComparable<B>
{
public:
    B(int num1, int num2):N1(num1), N2(num2){}
    bool lessImpl(const B& b){
        return N1 < b.N1 || N2 < b.N2;
    }
private:
    int N1, N2;
};
int main(){
    //cout << alphabeta;
    A a(5), b(10);
    cout << a.less(b) << endl; // OK
    B c(5, 10), d(5, 0);
    cout << c.greater(d) <<endl; // OK
}

这段代码里，我首先定义了一个接口IComparable，然后定义了一系列的比较函数，它们都直接或间接地使用了lessImpl()方法，而定义了派生类A和B之后，在类中覆盖lessImpl() 方法，并使用CRTP技术，获得IComparable所带有的比较函数，这样，A和B就可以进行比较操作了。

对于这个例子，可以发现：生成这些操作完全是在编译期完成的，在运行期只是普通的比较，且没有任何空间开销，虽然IComparable是空类，或者说是接口，但它是被继承的可以借助EBO, 优化空间，变为0空间开销。派生类只要写lessImpl()方法，就可以获得所有比较功能，这也是CRTP最显著的特点：

基类能够在不直接知道派生类类型的情况下，为派生类提供功能，且无任何的运行时开销。

Counter

#include<iostream>
using namespace std;
template<typename T>
class Counter
{
public:
    static size_t get(){
        return Count;   
    }
    Counter(){
        add(1);
    }
    Counter(const Counter& other){
        add(1);
    }
    ~Counter(){
        add(-1);
    }
private:
    static int Count;
    static void add(int n){
        Count += n;
    }
};
template<typename T>
int Counter<T>::Count = 0;
class A : public Counter<A>
{};
class B : public Counter<B>
{};
int main(){
    // Counter<A>::add(1);  [Error] 'static void Counter<T>::add(int) [with T = A]' is private
    A a1;
    cout << "A : " << Counter<A>::get() << endl;
    {
        B b1;
        cout << "B : " << Counter<B>::get() << endl;
        {
            A a2;
            cout << "A : " << Counter<A>::get() << endl;
        }
        cout << "A : " << Counter<A>::get() << endl;
    }
    cout << "B : " << Counter<B>::get() << endl;
}

对象构造肯定会调用构造函数，析构时也会调用析构函数，我们只要在构造函数和析构函数中添加计数的代码，再让其他类继承。 在继承Counter时，Counter的模板参数就是派生类，同时就会实例化类模板，创建一个特定为派生类提供的计数器。 构造函数将会在派生类被构造时隐式调用，从而实现了计数。

enable_shared_from_this

我们看C++标准库中，最为经典的就是enable_shared_from_this<T>。 为了实现从类中传出一个安全的shared_ptr<T>来包装this指针，并且只能对现有的类做极小的修改，对实际使用没有影响。 使用CRTP是最好的选择。通过继承enable_shared_from_this<T>，它可以自动生成派生类的传出this的方法。

#include <memory>
#include <iostream>
struct Good: std::enable_shared_from_this<Good> // 注意：继承
{
    std::shared_ptr<Good> getptr() {
        return shared_from_this();
    }
};
struct Bad
{
    // 错误写法：用不安全的表达式试图获得 this 的 shared_ptr 对象
    std::shared_ptr<Bad> getptr() {
        return std::shared_ptr<Bad>(this);
    }
    ~Bad() { std::cout << "Bad::~Bad() called\n"; }
};
int main()
{
    // 正确的示例：两个 shared_ptr 对象将会共享同一对象
    std::shared_ptr<Good> gp1 = std::make_shared<Good>();
    std::shared_ptr<Good> gp2 = gp1->getptr();
    std::cout << "gp2.use_count() = " << gp2.use_count() << '\n';
    // 错误的使用示例：调用 shared_from_this 但其没有被 std::shared_ptr 占有
    try {
        Good not_so_good;
        std::shared_ptr<Good> gp1 = not_so_good.getptr();
    } catch(std::bad_weak_ptr& e) {
        // C++17 前为未定义行为； C++17 起抛出 std::bad_weak_ptr 异常
        std::cout << e.what() << '\n';    
    }
    // 错误的示例，每个 shared_ptr 都认为自己是对象仅有的所有者
    std::shared_ptr<Bad> bp1 = std::make_shared<Bad>();
    std::shared_ptr<Bad> bp2 = bp1->getptr();
    std::cout << "bp2.use_count() = " << bp2.use_count() << '\n';
} // UB ： Bad 对象将会被删除两次

还有就是C++20中的view_interface，其派生类可以变成一个范围，还可以使用各种范围适配器。

由于ranges库还没有完全完成，暂无示例。

LLVM/MLIR

LLVM中大量使用了CRTP技术，如下随便截取一段代码：

amespace mlir {
class Operation final
    : public llvm::ilist_node_with_parent<Operation, Block>,
      private llvm::TrailingObjects<Operation, BlockOperand, Region,
                                    detail::OperandStorage> {
public:
    /// ...

MLIR中极其重要的数据结构之一mlir::Operation的声明处，可以看到它继承自一个模板基类。我们调到这个基类的地方：

template <typename NodeTy, typename ParentTy, class... Options>
class ilist_node_with_parent : public ilist_node<NodeTy, Options...> {
protected:
  ilist_node_with_parent() = default;
 
private:
  /// Forward to NodeTy::getParent().
  ///
  /// Note: do not use the name "getParent()".  We want a compile error
  /// (instead of recursion) when the subclass fails to implement \a
  /// getParent().
  const ParentTy *getNodeParent() const {
    return static_cast<const NodeTy *>(this)->getParent();
  }

可以看到，在getNodeParent()接口中同样存在static_cast。整个开源项目中这样的用法数不胜数。

CRTP的意义

有人喜欢称CRTP为静态多态，不完全正确。我们把CRTP和Interface做个比较，CRTP是通过模板参数获得派生类的类型，并为每个派生类都生成了一个基类， 每个派生类继承CRTP类都要将自身的类型传给基类，就发生了模板实例化，本质上并没有一个基类（接口）对多个派生类（实现）。

而对于Interface，Interface本身不知道派生类的类型，但是它有固定的方法规定，参数个数，类型，返回值，都是确定的，并且每个方法都是通过按照vtable调用的，都是指针。 这样就能真正的做到一个基类（接口）对多个派生类（实现）。

将CRTP作为快速扩展类的手段，基类可以获得到派生类的类型，提供各种操作，比普通的继承更加灵活。但CRTP基类并不会单独使用，只是作为一个模板的功能。

链接

https://zhuanlan.zhihu.com/p/137879448 https://zhuanlan.zhihu.com/p/136258767

索引
cxx CRTP
Curiously Recurring Template Pattern 的概念
通过模板实现静态绑定
用在哪里？
应用
- IComparable
- Counter
- enable_shared_from_this
- LLVM/MLIR
CRTP的意义
链接