背景

最近在实现一个LSM键值对存储系统时遇到了一个问题：
LSM键值对存储系统的DELETE操作是通过插入特殊的符号~DELETE~实现的，然而对于不同的value类型（string、int…），需要定义不同的代表删除的符号。为了定义不同类型的删除符号，初步实现如下：

// 基模板类，提供value()方法获取删除符号，isDeleted()方法判断传入的值是否为删除符号
template<typename T>
struct DeleteMarker {
    static T value() {
        return T();  
    }

    static bool isDeleted(T value_) {
        return value_ == value();
    }
};

//对string的特化
template<>
struct DeleteMarker<std::string> {
    static std::string value() {
        return std::string("~DELETED~");
    }

    static bool isDeleted(std::string value_) {
        return value_ == value();
    }
};

//对int的特化
template<>
struct DeleteMarker<int> {
    static int value() {
        return 0;
    }

    static bool isDeleted(int value_) {
        return value_ == value();
    }
};

初步方法利用了一个模板类DeleteMarker，通过对DeleteMarker使用不同类型进行特化，从而决定不同类型的删除符号。然而，这样做弊端明显：每次特化时都需要重复写isDeleted()，代码冗余大。

查阅学习，发现CRTP技术可以解决这个问题，且不只能解决这个问题。

What is CRTP?

CRTP全称为Curiously Recurring Template Pattern，中文译为奇异递归模板模式，其最主要的内涵就是：把派生类作为基类的模板参数。

// 基类是一个模板类
template<class T>
class Base()
{...};

// 派生类继承基类，同时将自身作为基类的模板参数
class Derived : public Base<Derived>
{...};

通过CRTP模式，我们可以在派生类中修改基类的方法，从而不依赖虚函数实现多态，由于这样不存在虚函数的调用所以性能会更好。

运行时多态

利用CRTP实现运行时多态的基本结构：

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

class Derived1: public Base<Derived> {
    public:
    void gunc() {
        // Do something
    }
};

class Derived2: public Base<Derived> {
    public:
    void gunc() {
        // Do something
    }
};

由于基类知道继承它的类的信息，因此可以在其内部获得指向继派生类的指针，并用这个指针调用派生类的方法，从而实现了编译期的多态。
注意，由于我们为基类中的函数和派生类中的函数取了不同的名字func和gunc，因此此时func相当于纯虚函数，因为若不在派生类中实现gunc，编译无法通过。要使之只具有虚函数的性质而不具有纯虚函数的性质，只需将基类和派生类中的函数名设为一致。此时如果不在派生类中实现func，在对基类指针调用func时，由于该函数未在派生类内重写，没有触发函数隐藏机制（派生类重写基类的非虚函数时，对派生类对象调该函数会调派生类的函数，但是如果用指向该派生类对象的基类指针调该函数，会调基类的函数，不触发多态；如果不重写那么直接继承），会调用基类的func，从而导致无限循环。
然而我们发现，调用多态方法时却需要知道派生类的类型：

1
2
3

Derived1* d1 = new Derived1();
Base<Derived1>* b = d1;
b->func();

这岂不是失去了多态的意义？因此需要单独定义一辅助函数用于分发：

template<typename T>
void apply(Base<T>* b)
{
    b->func();
}

在调用时，

Derived1 d1;
Derived2 d2;
apply(d1);
apply(d2);

CRTP如何解决特化时只想重写某一部分函数的问题？

刚才介绍的是CRTP的主流用法即实现编译期多态，那么怎么搞能解决这个问题呢？
首先对于那些不想重写的函数，定义在一个新的基类中。这里将要用于特化DeleteMarker的T也要放在里面，不然基类搞不清楚。

template<typename Derived, typename T>
struct DeleteMarker_Base {
    static bool isDeleted(T value_) {
        return value_ == Derived::value();
    }
};

然后继承这个基类，得到原来的模板类。

template<typename T>
struct DeleteMarker: public DeleteMarker_Base<DeleteMarker<T>, T>
{
    static T value() {
        return T();
    }
};

对于不同的类型分别特化（以string为例）：

template<>
struct DeleteMarker<std::string> : public DeleteMarker_Base<DeleteMarker<std::string>, std::string>
{
    static std::string value() {
        return std::string("~DELETED~");
    }
};

此时调用DeleteMarker<std::string>从基类DeleteMarker_Base<DeleteMarker<std::string>, std::string>继承了isDeleted()方法，并且这个方法是用std::string特化的，搞定。

一定要这样吗？

不过这个方法也不是完美的，在特化新类型时参数显得相当繁杂。实际上，在特化时只想重写一部分函数，还有诸多解决方法。

运行时判断

template<typename T1, typename T2>
struct Base
{
    //other function
    //....
    void Func()
    {
        if(typeid(std::string) == typeid(T2))
        {
            cout<<"specialization function"<<endl;
        }
        else
        {
            cout << "primary function" << endl; 
        }
    }
};

成员函数的特化

template<typename T1, typename T2>
struct Base
{
    //other function
    //....
    template<typename T>
    void FuncImpl()
    {
        cout << "primary function" << endl; 
    }
    template<>
    void FuncImpl<string>()
    {
        cout << "specialization function" << endl; 
    }
    void Func()
    {
        FuncImpl<T2>();
    }
};

函数重载

template<typename T1, typename T2>
struct Base
{
    //other function
    //....
    template<typename T>
    void FuncImpl()
    {
        cout << "primary function" << endl; 
    }
    template<>
    void FuncImpl<string>()
    {
        cout << "specialization function" << endl; 
    }
    void Func()
    {
        FuncImpl<T2>();
    }
};

ref: 在C++泛型编程中如何只特化类的某个成员函数

Liu Yao's attic

CRTP（奇异递归模板模式） - 编译期多态

背景