meryngii.neta

今日も新たな"ネタ"を求めて。

Curiously Recurring Template Pattern (CRTP) と Policy-based design

この記事はEEIC Advent Calender 2016の12月22日分として書かれた.

CRTPとは

C++でのジェネリックプログラミングで広く知られたパターンとして, Curiously Recurring Template Pattern (CRTP) というものがある. この名前は実態から大分かけ離れているので, CRTPが何たるかを要約しておくと次のようになる. 「基底クラスに派生クラスの型を与えると, 基底クラスから派生クラスを触ることができる.」 基本的にはそれだけのことである. それだけのことなのだが, なかなかに興味深い性質を持っているのでわざわざ名前が付いている.

template <typename Derived>
class base {
    // ...
};

class derived
    : public base<derived>
{
    // ...
};

CRTPという名前に「なってしまった」理由は, 1995年にJames O. Coplienという人物が同名の論文として発表したことによる. Coplien自身はCRTPのテクニックを発明したわけではなく, 複数のプログラマが独自に再発明しているのを見て これがある種のパターンではないかと気付いた,ということらしい. わざわざ「私が名付けるのは避けたい」とまで言っていることから, まさかこんな名前で広まるとは思っていなかったのだろう.

Curiously recurring template pattern - Wikipedia

ジェネリックプログラミングを実践しているプログラマの多くは, CRTPが何となく便利だとは認識していても, 「なぜ便利なのか」を認識していないかもしれない. Coplienの論文には,「何のためにCRTPを使うのか」が一言で明確に示されている.

That is, we encode the circular dependency directly using inheritance in one direction and templates in the other.

C++では継承によってクラス間の依存関係を表すことができるが, それは単方向の依存関係に限定される. 双方向な依存関係,すなわち循環依存をクラス間で表現する手法がCRTPであり, 片方を継承,もう片方をテンプレート引数として表現することで, 循環依存が発生しているクラスをコンポーネントに分解することが可能になる, というわけである.

「CRTPは静的多態性をうんたら」とかそういう論調のサイトをよく見かけるのだが, 12年前にCryolite先生が書いているように, 私もその説明には今ひとつ納得がいっていない. どちらかというと,CRTPはもっと一般的な手法で, 多態性の表現として使うのは応用の一種に過ぎない,という風に思っている. 循環依存が生じるパターンだったらおよそ何でも役に立つはずなのだ. 一応,オブジェクト指向の理論的枠組みでは CRTPのことを"F-Bounded Polymorphism"と呼ぶらしいが, 元論文がパッと見た感じ意味不明だったので誰か解読したら教えて欲しい.

細かい理屈は置いておいて,実用例を見ると理解が早くてよい. CRTPを活用した有名なライブラリとして, Boostのiterator_facade というテンプレートクラスを見てみる.

template <
    class Derived
  , class Value
  , class CategoryOrTraversal
  , class Reference  = Value&
  , class Difference = ptrdiff_t
>
class iterator_facade;

iterator_facadeは,自作イテレータを実装する際に要求される 各種関数を自動生成してくれるライブラリである. イテレータを定義するには, 似たような演算子を大量に定義する必要があって, そういう演算子を一つ一つ手で実装するのは時間の無駄である. しかし,だからといってイテレータという抽象化がダメだというわけではない. イテレータとして本来必要な機能はせいぜい「移動する」「デリファレンス」「比較する」ぐらいしかないので, それらの実装だけはコンテナごとに別々にしてインターフェイス部分を共通化することでイテレータを簡単に作れるようになるはずだ, というアイディアに基づくのがiterator_facadeである.

class int_iterator
    : public boost::iterator_facade<
        int_iterator,
        int,
        std::output_iterator_tag,
        int
    >
{
public:
    explicit int_iterator(int x) noexcept : x_{x} { }
    
private:
    friend boost::iterator_core_access;
    
    // 最低限の機能だけ実装する
    void increment() noexcept {
        ++this->x_;
    }
    int dereference() const noexcept {
        return this->x_;
    }
    bool equal(const int_iterator& other) const noexcept {
        return this->x_ == other.x_;
    }
    
    int x_;
};

int main()
{
    std::for_each(int_iterator{1}, int_iterator{5},
        [] (int x) { std::cout << x << " "; });
    
    // Output: 1 2 3 4 
}

iterator_facadeのドキュメント には,「なぜポリシーオブジェクトではなくCRTPが選択されたのか」について書いてある. ポリシーオブジェクトがなんなのかがこの文書だけでは釈然としなかったが, CRTP以外のやり方という文脈から察して, おそらく継承関係を逆にしたりコンポジションにしたりしたラッパのことを指しているのだと思う.

template <typename Iterator, /*...*/>
class iterator_facade : public Iterator { /*...*/ };

こういうラッパではなくあえてiterator_facadeでCRTPが使われている理由には,次の3つが挙げられている.

  • ラッパの生成やコピーにオーバーヘッドがかかる.
    • C++の規格上,空の基底クラスにはEmpty Base Optimization (EBO) が効いて,空間コストが必ず除去されることが保証される.
    • 現実的には,メンバを追加しない空の派生クラスでもオブジェクトのレイアウトが変わらない状況がほとんどな気はする.
  • 利用者がコンストラクタをカスタマイズできない.
    • これはそこそこ本質的な問題であろう.C++11だとInheriting Constructorsでマシになるが,根本的には解決していない.
  • パラメタライズされたイテレータ(例えばfoo_iterator<T>のようにTでパラメタライズされたもの)を作る時, (Template AliasesのないC++03以前では)foo_iterator_generator<T>::typeのように型生成テンプレートを経由する必要がある.
    • イテレータにはoperator++などが返す型が必ず同一でなければならないという規約があるので,ラッパだったとしても必ずiterator_facade<...>という型として扱わなければならない.
    • C++11だとTemplate Aliasesがあるのでこの手間はなくなった.しかし,最終的にユーザに見える型がiterator_facade<...>になってしまうことに変わりはない.

そもそものところ, 新しいイテレータを作る時にfoo_iteratorではなくて iterator_facade<...>という型になり, ユーザに内部の実装詳細であるはずのiterator_facadeが見えているということがおかしい. あくまで「イテレータインターフェイスを自動実装するクラス」を利用した「新しいイテレータクラス」を提供するわけで, ラッパというやり方は自然な依存関係の表現とは言い難いわけだ. しかし,実際のところインターフェイスを定義するために 最終的な派生クラスの型が要るから,それをテンプレート引数として 注入するのがCRTPの役割である,といえる.

興味深いこととして, CRTPには実行時のオーバーヘッドが全くない(ゼロオーバーヘッド抽象化)ので, iterator_facadeを使うかどうかについて性能面で悩む必要が全くない. 逆に言えば,CRTPを使う動機には「性能が絶対要件である」という前提が欠かせない. 性能がどうでもよいのなら,実際のところ仮想関数で何とかなる場合が多いからだ. こういった考え方こそC++らしいもので, それ故にCRTPはC++のライブラリ設計で頻出の手法になっている.

ちなみに,iterator_facadeも現在C++標準に提案されているらしい(採用されたわけではない). Ranges TSを精力的に開発しているEric Nieblerが著者の一人のようである.

Iterator Facade Library Proposal for Ranges

テンプレート引数地獄

必ずしもCRTPに限らないが, テンプレートをフル活用したプログラムにありがちな問題として, 「テンプレート引数の数が増えまくる」というものがある. 再びiterator_facadeを例に考えると, 後ろ2個のテンプレート引数にはデフォルト値があるので, 利用者からは最低限3個の引数を指定すればよい,ということになっているが, テンプレート引数が5個であることに変わりはない. このことは, ライブラリを利用する立場だとコンパイル時・リンク時・デバッグ時に表面化する. 例えば,上のコードでoperator++の実体は

boost::iterators::detail::iterator_facade_base<int_iterator, int,
    std::__1::output_iterator_tag, int, long, false, false>::operator++()

という名前である. int_iteratorの利用者からみて, longだのfalseだのの情報は明らかにいらないし, デバッグ中に見たい情報ではない. 残念ながらこれでもまだ単純すぎる例で, さらに少し複雑なコードになると画面が埋め尽くされるほどの型情報が コマンドを叩く度にわらわらと出て来る. 特にデバッグ中に見たいのは型情報よりも変数の値であって, そういう冗長な型情報は端的にいってデバッグの邪魔である.

ライブラリを開発する側もつらい. 例えば,iterator_facadeのコードを少し引用すると,こんな感じのがあちらこちらにある.

#  define BOOST_ITERATOR_FACADE_INTEROP_HEAD_IMPL(prefix, op, result_type, enabler)       \
    template <                                                              \
        class Derived1, class V1, class TC1, class Reference1, class Difference1 \
      , class Derived2, class V2, class TC2, class Reference2, class Difference2 \
    >                                                                       \
    prefix typename mpl::apply2<result_type,Derived1,Derived2>::type \
    operator op(                                                            \
        iterator_facade<Derived1, V1, TC1, Reference1, Difference1> const& lhs   \
      , iterator_facade<Derived2, V2, TC2, Reference2, Difference2> const& rhs)

Boostのコードはプリプロセッサの闇魔術で色々圧縮されているものの, 「テンプレート引数が多すぎる」という本質的な問題は 残されたままである. 例えば,iterator_facadeのテンプレート引数にもう一つ新規に追加するとしたら?…… ヘッダ中のあちらこちらを直さなければいけないだろうし, 苦痛以外の何者でもない.

テンプレート引数の羅列は順序に依存している ということも問題である. 例えばiterator_facadeに与えるテンプレート引数のどれかを交換すれば, おびただしい数のコンパイルエラーになること間違い無しである. 『C++の設計と進化』には,C++の設計過程で順序依存をなくす工夫が なされていることがあちこちに書いてある. 順序依存は可能な限り避けるべきであり, そして推奨されるプログラミングパターンに含まれているべきでもない.

循環参照との戦い

そもそもなぜValueだのCategoryOrTraversal だのといった型を渡さなければならないのか? どうせDerivedを渡しているのだから,Derivedの中で型を定義してしまえば, 基底クラスはそのメンバを参照できるはずじゃないか, と思うのは自然な発想である.

template <typename Derived>
class iterator_facade
{
public:
    Derived& operator += (typename Derived::difference_type n); // エラー
    // ...
};

しかし,残念ながら,C++の言語仕様上このコードはコンパイルできない. Derivedがincomplete typeとかそういうエラーが出るだろう. なぜかというと,派生クラスのメンバにアクセスするためには, 基底クラスのメンバの型やシグネチャ*1が確定していないといけないからである. すなわち,基底クラスのメンバ関数シグネチャが 派生クラスのメンバに依存するようなコードは,そもそも書けない. そのため,CRTPが活躍できるのは,あくまで 「基底クラス内のメンバ関数の"実装"が派生クラスに依存している」 という状況に限られている.

よく知られた回避策は2つある.

  • 基底クラスのテンプレート引数を増やす.
  • メンバテンプレートや戻り値型推論を活用することで,型の依存関係を逆向きに変える.

1番目の解決策は先ほどまで述べた通りである. 2番目の解決策だと,例えばこんな感じになる.

template <typename Derived>
class iterator_facade
{
public:
    template <typename Difference>
    Derived& operator += (Difference n);
    // ...
};

この場合だとなんとかうまくいくのだが, 一般にはこれでは対処しきれない場合が存在する. 最も単純な例としては,

template <typename Derived>
class foo
{
    typename Derived::value_type val_;
};

というように,基底クラス内で依存型を実体化しなければならない場合に起きる. こういうコードは普通にあり得るので, 2番目の解決策は即座に限界を迎える. また,そもそもメンバテンプレートでなかった単純なメンバ関数が, 依存性解決のためだけにテンプレートになって複雑性が増大しているのも問題である. こうしてテンプレート引数が増えると, 同じようにデバッグ時などに困るだけである.

こういう状況に何度も直面した後,私は次のような考えに至った. シグネチャを確定させるための型情報は, CRTPを積極的に活用する上でやむを得ず必要になるので, それらは事前に与える以外の解決策がない. そして,そのための最も単純で使いやすい手法は, 「CRTPに使うためのDerivedもまとめて」丸ごと一つのテンプレート引数として与える, というものである.

template <typename P>
class iterator_facade
{
    using derived_type      = typename P::derived_type;
    using value_type        = typename P::value_type;
    using category_type     = typename P::category_type;
    using reference_type    = typename P::reference_type;
    using difference_type   = typename P::difference_type;
    
public:
    // ...
};

先ほどまでDerivedというテンプレート引数を与えていた代わりに, 派生クラス自身ではない型にderived_typeというメンバを持たせることで, テンプレート引数に陽に現れない形で間接的にCRTPを実現する. そして,シグネチャを確定させるための情報も一緒にその型に持たせてしまう. たったこれだけの変更だけで, テンプレート引数が増大する問題を回避しながら, CRTPも活用できるようになるのである.

ところで,Pとは何だろうか? これはまさしく次に解説する ポリシー (Policy) そのものであるといえる.

CRTPとPolicy-based design

ポリシーを使った設計それ自体は,何ら新しいことではない. 2001年に出版された『Modern C++ Design』(略称MC++D) *2 という本には, ポリシーを使ってスマートポインタを構成するといった, 当時としては相当先進的なジェネリックプログラミングのスタイルが示されている. しかし,そうはいっても,MC++Dが出版されて既に15年以上経っているわけで, ポリシーが新規の概念かというとそういうことはない.

template <
    typename T,
    template <class> class OwnershipPolicy,
    class CoversionPolicy,
    template <class> class CheckingPolicy,
    template <class> class StoragePolicy
>
class SmartPtr;

このスマートポインタは, ポリシーを切り替えるだけで参照カウント方式や 暗黙変換の方式などを変更することができる. 様々なスマートポインタに共通の処理だけがSmartPtrに実装されていて, 例えばアトミック変数で参照カウントを制御するといった詳細は ポリシーに分離されている.

MC++Dで解説された「ポリシー」と この記事で述べている「ポリシー」が 一つ決定的に違っているのは,ポリシーとして テンプレートクラスではなくただのクラスを用いていることである *3. テンプレートクラスを受け取る形式は, 上の例だと利用者がTを指定する必要が無いという利点があるが, しかしテンプレート引数が増える問題は解消できていない. 実際のところ,利用者は既にTの実体を知っているわけだから, ポリシーとして与える際にTを知っている前提で型を定義することに それほど手間がかかるわけではないのだ.

PolicyとTraits

C++11の標準ライブラリにType Traits (型特性)があるので, Traitsは比較的知られている概念だと思う. 型同士の相関を考えるという性質上, TraitsとPolicyはよく似ているので紛らわしいが, 違いについて下のように解説がある.

What is the difference between a trait and a policy?

Traitsとは要するに「既存の型から情報を引き出す」操作, Policyは逆に「情報をクラスに入れ込む」操作であるといえる. この解説の例ではstd::allocator<T> がPolicyの例として挙げられている. アロケータはコンテナに「入れ込む」形になっているわけで, よくよく考えてみるとSTLの中にもポリシーは使われている.

ポリシーの合成,入れ子

ポリシーを型として実装した場合, 直交したポリシーを合成するのは非常に簡単で, 多重継承を使えばよい. 以下の例だと,アロケーションとロガーを別々のポリシーとして定義し, それらを一つにまとめている.

template <typename Policy>
struct my_list_base
{
    using derived_type = typename Policy::derived_type;
    using value_type = typename Policy::value_type;
    
    struct elem {
        elem* next;
        value_type val;
    };
    
public:
    void add(const value_type& val) {
        const auto ptr =
            static_cast<elem*>(
                Policy::allocate(sizeof(elem))
            );
        
        ptr->next = head_;
        ptr->val = val;
        head_ = ptr;
        
        Policy::add_log("added element");
    }
    
    void traverse() {
        for (auto cur = head_; cur != nullptr; cur = cur->next) {
            this->derived().on_traverse(cur->val);
            Policy::add_log("traversing...");
        }
    }
    
protected:
    my_list_base() : head_{} {}
    
private:
    derived_type& derived() noexcept {
        return static_cast<derived_type&>(*this);
    }
    
    elem* head_;
};

struct my_allocation_policy {
    static void* allocate(std::size_t size);
    static void deallocate(void*);
};
struct my_logging_policy {
    static void add_log(const char*);
};

template <typename T>
class my_list;

template <typename T>
struct my_list_policy
    : my_allocation_policy
    , my_logging_policy
{
    using derived_type = my_list<T>;
    using value_type = T;
};

template <typename T>
class my_list
    : public my_list_base<my_list_policy<T>>
{
private:
    friend my_list_base<my_list_policy<T>>;
    
    void on_traverse(T val) {
        std::cout << ++count_ << " " << val << std::endl;
    }
    
    std::size_t count_ = 0;
};

このパターンをより複雑なものに一般化した場合, ポリシーを前提に階層的なクラス設計を行う際に, 基底クラスに近づくにつれて「ポリシーが大きくなっていくような」ものになる. 例として,侵入型参照カウンタintrusive_ptrの実装について考えてみる.

template <typename T>
class my_intrusive_ptr {
    // ...
};

template <typename Policy>
class ref_counted_base
{
private:
    using derived_type = typename Policy::derived_type;
    using ref_count_type = typename Policy::ref_count_type;
    
    friend my_intrusive_ptr<derived_type>;
    
    void acquire_ref() {
        Policy::increment(ref_count_);
    }
    void release_ref() {
        if (Policy::decrement(ref_count_) == 1) {
            delete &derived(); // thisをdeleteするアグレッシブさ
        }
    }
    
    derived_type& derived() noexcept {
        return static_cast<derived_type&>(*this);
    }
    
    ref_count_type ref_count_{1};
};

template <typename Policy>
struct atomic_ref_counted_policy
    : Policy
{
    using ref_count_type = std::atomic<std::size_t>;
    
    static void increment(ref_count_type& count) {
        count.fetch_add(1, std::memory_order_seq_cst);
    }
    static std::size_t decrement(ref_count_type& count) {
        return count.fetch_sub(1, std::memory_order_seq_cst);
    }
};

template <typename Policy>
class atomic_ref_counted_base
    : public ref_counted_base<atomic_ref_counted_policy<Policy>>
{
    // ...
};

class my_class;

struct my_class_policy {
    using derived_type = my_class;
};

class my_class
    : public atomic_ref_counted_base<my_class_policy>
{
    // ...
};

この例だと,継承の真ん中にある atomic_ref_counted_baseは,元あるポリシーを拡張して, ref_count_typeといった新しいメンバを導入している. 大したコード量でないのでありがたみが分かりにくいが, アトミック変数という実装詳細を後回しにして, ref_counted_baseには「侵入型参照カウントを実装するとしたらこうなる」というコード片を CRTPを駆使して括り出せている,ということが分かる. そして,atomic変数を使うことを確定させた時, 実装すべきはincrementといったより細分化された部品だけになっている.

循環依存の関係にあるわけだから, 継承が一段深くなる度にポリシーは逆方向に継承されていくのは自然であるといえよう. あるいは,継承関係が逆転することは, 「制御の反転」 の一形態と見ることもできる. ただし,あまりこういう複雑な継承関係を組み合わせすぎると意味不明になるので, やりすぎない程度にすることも大事である.

ここまでを俯瞰してみると, ポリシーというのは「そのクラス専用の名前空間のようなものを定義している」 と考えることもできる. 言い換えると,クラスが依存するコンテキストを限定することができ, 依存関係を最小化できる. そして,C++のクラスあるいは型というのは, ほとんど何でもできると言って良いぐらい色んな物を持てるから, 受け取る型が一つでも表現能力の面で困ることがない.

  • 普通の関数 (staticメンバ関数)
  • 普通の値(constexpr or 変数)
  • 変数メンバ
  • メンバ関数
  • 型(typedef または 入れ子クラス)
  • テンプレートクラス(メンバテンプレートクラス または テンプレートエイリアス

そんなわけで,型を一つポンと渡すことでポリシーを表現するやり方は, シンプルな割に表現力も問題がないので便利だと思う.

CRTP共通基底クラス

CRTPでは大抵の場合,derived()メンバを定義するのだが, ポリシーが必ずderived_typeという型を持つとしたら, この作業も共通化してしまえる. まあ実際のところ無くても大して問題ではないが,コードの重複は少し減らせる.

template <typename Policy>
class crtp_base
{
protected:
    using derived_type = typename Policy::derived_type;
    
    derived_type& derived() noexcept {
        return static_cast<derived_type&>(*this);
    }
    const derived_type& derived() const noexcept {
        return static_cast<const derived_type&>(*this);
    }
};

動的なダウンキャストについては, Boostにはpolymorphic_downcastという小粒なライブラリと同じ手法を使えばチェックできる. その動きを簡単に説明すると,デバッグ時にはdynamic_castを使って, リリース時にはstatic_castを使う,というものである. 但し,ポリモーフィックでない型(=仮想関数が無いクラス)の場合は コンパイル時に怒られるので,仮想デストラクタを強制的に付けてRTTIが動くようにする必要がある.

    #ifdef ENABLE_POLYMORPHIC_CAST
    virtual ~crtp_base() = default;
    #endif

    derived_type& derived() noexcept {
        #ifdef ENABLE_POLYMORPHIC_CAST
            auto p = dynamic_cast<derived_type*>(this);
            if (!p) {
                throw std::bad_cast{};
            }
            return *p;
        #else
            return static_cast<derived_type&>(*this);
        #endif
    }

例えばこんなミスを自動検出できる.

template <typename Policy>
struct printer_base : crtp_base<Policy> {
    void print() {
        std::cout << this->derived().x << std::endl;
    }
};

struct int_wrapper;
struct double_wrapper;

struct int_wrapper_policy {
    using derived_type = double_wrapper; // Broken
};
struct int_wrapper : printer_base<int_wrapper_policy> {
    int x = 123;
};
struct double_wrapper_policy {
    using derived_type = double_wrapper;
};
struct double_wrapper : printer_base<int_wrapper_policy> { // Broken, too
    double x = 123.456;
};

void f() {
    int_wrapper w;
    w.print();
    // int_wrapper -> printer_base<int_wrapper_policy> -> double_wrapper
}

デバッグ時とリリース時でオブジェクトのレイアウトが変わってしまうのは深刻な問題なので, 普遍的に役立つかというと微妙ではある. 上で示しているように必要なときだけ#ifdefで有効にするか, ポリモーフィックな型だけをメタプログラミングで判定して チェックしたりといった使い方になるだろうか.

ポリシーでプロトタイピング

ここまでを踏まえて,最後により汎用的なプログラミングスタイルについて述べる. ポリシーの利用用途は上のような特殊なライブラリに限られたものではなく, ほとんど何にでも使える. ポリシーを使うと,C++のような静的型付け言語であっても トップダウンに素早くプロトタイピングすることが可能である.

ものすごく単純な例だが, 入力が少しずつ入ってくるタイプのtokenizer (カンマなどで文字列を切断するやつ)について考えてみる. まず何も考えずにクラスの名前を決める.

template <typename Policy>
class tokenizer_base
    : public crtp_base<Policy>
{
    // ???
};

まず文字を受け取る関数が要るだろうから, addみたいな関数を追加する. となると,引数には文字を受け取るだろうから, character_typeみたいな型をポリシーに要求する.

template <typename Policy>
class tokenizer_base
    : public crtp_base<Policy>
{
    using character_type = typename Policy::character_type;
    
public:
    void add(character_type ch) {
        // ???
    }
};

新しい文字が来たら,デリミタ(切り分ける文字)かそうでないかのどっちかで, デリミタじゃなかったら単にバッファに溜めるみたいな処理になるはずである. デリミタかどうかの判断は派生クラスに丸投げして,バッファの型も追加する.

template <typename Policy>
class tokenizer_base
    : public crtp_base<Policy>
{
    using character_type = typename Policy::character_type;
    using token_buffer_type = typename Policy::token_buffer_type;
    
public:
    void add(character_type ch) {
        auto& self = this->derived();
        
        if (self.is_delimiter(ch)) {
            // ???
        } else {
            // ???
        }
    }
    
private:
    token_buffer_type buf_;
};

バッファは「文字を追加できる何か」だから とりあえずvectorみたいなやつと考えることにして, トークンができた後の処理は派生クラスに丸投げすることにする. あとバッファがたまったままだと困るので,finishみたいなやつも加える.

template <typename Policy>
class tokenizer_base
    : public crtp_base<Policy>
{
    using character_type = typename Policy::character_type;
    using token_buffer_type = typename Policy::token_buffer_type;
    
public:
    void add(character_type ch) {
        auto& self = this->derived();
        
        if (self.is_delimiter(ch)) {
            self.on_new_token(buf_);
            buf_.clear();
        } else {
            buf_.push_back(ch);
        }
    }
    
    void finish() {
        this->derived().on_new_token(buf_);
    }
    
private:
    token_buffer_type buf_;
};

ポイントは,「ここでコンパイルにかけてしまう」ことである. まだvectorを使うとか何も言っていないわけだが, プロトタイピングをしている時は最終的な型がどうなるのか分からないので, 型が確定していないのも当たり前だ. しかし,テンプレートのコードだから型を確定させなくてもこれだけでコンパイルはできる. C++コンパイルエラー地獄でよく知られている言語であるので, C++プログラマコンパイラと仲良くなる方法を知るべきであり, その一つがシンタクスエラーなど単純なエラーを早い段階で潰しておくことである.

このクラスを実際に使うとなったら,実際にポリシーの実体と派生クラスを作る. この時初めてテンプレートが実体化されて, シンタクスよりも具体的なエラーが出てくるようになる.

class char_tokenizer;

struct char_tokenizer_policy
{
    using derived_type = char_tokenizer;
    using character_type = char;
    using token_buffer_type = std::vector<char>;
};

class char_tokenizer
    : public tokenizer_base<char_tokenizer_policy>
{
public:
    void show_all() {
        for (const auto& token : tokens_) {
            std::cout << token << std::endl;
        }
    }
    void set_delimiter(char delim) {
        delim_ = delim;
    }
    
private:
    friend tokenizer_base<char_tokenizer_policy>;
    
    bool is_delimiter(char c) {
        return c == delim_;
    }
    
    void on_new_token(const std::vector<char>& v) {
        tokens_.emplace_back(std::begin(v), std::end(v));
    }
    
    char delim_ = ',';
    std::vector<std::string> tokens_;
};

このような順番で考えていくと, 自然とtokenizer_baseから実装詳細が抜き取られ, 逐次的にトークン処理をする際に最低限必要なものだけが書かれていることが分かる. 必要に応じて基底クラスと派生クラスの仕様をすり合わせていくと, 分離されたモジュールとしていい具合に整備されてくるはずである. そして何より大事なのが,こういう抽象化はオーバーヘッドなしに行える, ということである.

まとめ

  • CRTPはモジュール間の循環依存問題を解消する.
  • テンプレート引数が増えるテクニックは望ましくない.
  • CRTPとポリシーを組み合わせるパターンは極めて有用である.
  • テンプレートのコンパイルエラーに負けない強い心を持つ.

明日のEEIC Advent Calendarは@nobi_sannです.

*1:私としては経験的には何に依存しているのか予想できるのだが,規格上の厳密な依存の範囲はよく知らない.Coplienの論文だと"structure"と呼ばれていた.

*2:Modern C++ Designは現在ではあまりModernではないが,ジェネリックプログラミングの歴史において重要な一冊である.

*3:さらにもう一つの別のやり方として,private継承を用いるものもある.