仮想関数を回避するテク [C++]

(追記 2022/06/22 22:35)

本記事の内容は Curiously recurring template pattern (CRTP) と呼ばれるものらしいです.より正確な情報や関連する情報を得たい場合は "Curiously recurring template pattern" や "CRTP C++" などと調べると良さそうです.

(追記終)

本文

競プロのライブラリを書いていると,継承されることを想定した基底クラスでデフォルトの動作を指定して,継承先で動作を微妙に変更したいことがあります (例えば平衡二分探索木において,添字アクセス・区間和取得・区間作用・反転などをサポートするかどうかで回転などにより木構造を変更した場合に更新すべき情報が変化します).

ベースのコードを書いた後はコピペして色んなバージョンを作ってもよいのですが,後でバグが発覚したり,インタフェースを変更したくなったときの修正箇所が多くて辛くなりがちです.

この問題への対処として仮想関数を用いる方法がありますが,私は使ったことがないのでここでは解説しません (できません).1 つ言えることとしては,仮想関数の呼び出しは通常の関数よりもオーバーヘッドが大きくなるということです.競プロライブラリにおいて速度は重要なので,これも避けたいです.

そこで,次のようなトリックを用います.

#include <iostream>

// Derived は base を継承することを想定
template <typename Derived>
struct Base {
    static void f() {
        // デフォルトの動作
        std::cout << "default f()" << std::endl;
    }
    static void g() {
        // デフォルトの動作
        std::cout << "default g()" << std::endl;
    }
    // 継承先の f() を呼ぶ関数
    static void call_f() {
        Derived::f();
    }
    // 継承先の g() を呼ぶ関数
    static void call_g() {
        Derived::g();
    }
};

// 全てデフォルトの動作をするクラス
struct Default : Base<Default> {};

// f の定義だけ上書きしたクラス
struct Derived : public Base<Derived> {
    using base_type = Base<Derived>;

    // f の定義を上書き
    static void f() {
        // デフォルトの動作を呼び出す (必要なければ呼ばなくても OK)
        base_type::f();
        // 差分の動作を記述
        std::cout << "extended" << std::endl;
    }
};

int main() {
    std::cout << "Default::call_f():" << std::endl;
    Default::call_f();
    std::cout << "Derived::call_f():" << std::endl;
    Derived::call_f();
    std::cout << "Default::call_g():" << std::endl;
    Default::call_g();
    std::cout << "Derived::call_g():" << std::endl;
    Derived::call_g();
    return 0;
}

このコードの実行結果は次のようになります ([C++] gcc 11.1.0 - Wandbox から確かめられます).

Default::call_f():
default f()
Derived::call_f():
default f()
extended
Default::call_g():
default g()
Derived::call_g():
default g()

何をやっているかですが,継承されることを想定した基底クラス Base を定義し,テンプレート引数に継承先のクラス Derived を与えるようにします.継承先で上書きされた関数を呼び出したい場合は Derived::f() のように書けばよいです.

継承先のクラス Derived では Base<Derived> を継承し,定義を上書きしたい関数のみを書きます.例えば上の例では,関数 f の定義を上書きすることで Derived::call_f() 内では Derived 内で定義した f が呼び出されてくれます.また,上書きする必要のない関数に関しては,何も書かなくてもよいです (Default::call_f()Derived::call_g() などの結果を見ると分かると思います).

使用例

私の赤黒木ライブラリはこのテクを使用して実装されています.継承先の各クラスは基底クラスに対して比較的差分を小さく抑えた実装になっていると思います.

おわりに

そこそこ面倒くさいので,もう少し簡単なやり方があったら教えて欲しい.C++に詳しい人いませんか.