ホーム < ゲームつくろー！ < クラス構築編

リンクリスト方式なスマートポインタ


　かなり前になりますが、マルペケではクラス構築編「スマートポインタテンプレートクラス」及び「改改・スマートポインタテンプレートクラス（交換サポート）」にてスマートポインタの概念と実装について説明してきました。概要を説明すると、スマートポインタというのはnewする事によって動的に確保したオブジェクトの自動解放をサポートしてくれます。これによりスマートポインタにnewしたオブジェクトを包む限りメモリリークは起きません（循環参照した場合は除きます）。詳しくは上記リンク先の記事を御覧ください。

　さて、スマートポインタの実装方法としてよく知られていてマルペケ謹製スマートポインタ（Dix::sp<T>）でも採用しているのが「参照カウンタ方式」によるスマートポインタです。これは同じnewしたオブジェクトポインタを参照している人の数を数える（参照数を共有する）事により、最後の一人がいなくなる時にだけdeleteする事で確実にオブジェクトを解放できる方法です。この方法は概念的にも分かりやすく、基本機能だけにしぼるなら実装もそれほど難しくありません。しかし実はこの方法、一つ大きな問題を抱えています。それは「参照カウンタの共有に伴なうnewの発生」です。

　空のスマートポインタを作る時、内部では共有カウンタの保存先となる数値型（int型等）をヒープから取る、すなわちnewが発生します。オリジナルなメモリアロケータ（メモリ管理者）を作成しているなら別ですが、標準のnewの動作速度は速くありません。それは要求されたサイズのメモリを確保するための検索や管理領域の確保に時間がかかるためです。もちろん、newの回数が少ない分にはあまり影響しませんが、これが毎フレーム何十万回ともなりますと、その速度は深刻なものになります。「毎フレーム何十万回にもなるの？」と思われるかもしれません。しかし、これは案外あっさりとなってしまいます。例えば、関数の引数にスマートポインタを渡すとしましょう。この時、値渡しをすると一度空のスマートポインタがローカルメモリに作られ、次に代入が行われます。newが1回発生するわけです。別の例で、クラスのメンバにスマートポインタが1つあるとすると、そのクラスのオブジェクトを作るだけでnewが発生します。関数の戻り値にスマートポインタを渡しても発生します。とにかくあらゆる所で参照カウンタ用のnewが発生する可能性があるわけです。

　newは遅い、とにかく遅い。そのため、可能な限りnewの発生回数を抑える必要があります。

　そこで「リンクリスト方式によるスマートポインタ」というのがあります。これは内部でnewが発生しません！この章ではそんなスマートポインタについて掘り下げてみます。



① リンクリスト方式なスマートポインタの理屈

　スマートポインタはnewされたオブジェクトを包みます。これは参照カウンタ方式でも、これから掘り下げるリンクリスト方式でも変わりません。異なるのは「同じオブジェクトを参照している人を認識する方法」です。先に説明したように、参照カウンタ方式は同じオブジェクトを参照している人の『数』を内部で共有する事で認識していました。

　一方リンクリスト方式では『数』ではなくて『お隣さん』として共有を認識します。リンクリスト方式なスマートポインタは、内部に同じスマートポインタの双方向リンクリストを持っています。そして共有がある場合は一方の手を相手に差し出し、相手からも手を貰う事でがっしりと握手します。これにより共有が実現します：

　共有が起こる度にこのリストの挿入を行えば、一本の長いリンクリストが出来ていきます。もちろん、共有から外れる時（＝スマートポインタが削除される時）はリンクリストから切り離せば良いだけです。最後の一人かどうかは、自分が消える時に両手に誰もいないかどうかで判定ができます。


　さて、この方式でどうして内部でnewが発生しないのでしょうか？双方向リンクの『手』の型は「スマートポインタのポインタ」です。そしてこれはヒープから取る必要はありません。相手の生ポインタをダイレクトに持ってしまっていいんです。「怖！」と思われるかもしれませんが、スマートポインタの性質がこれを可能にしてくれています。

　共有が発生した時、少なくともメモリのどこかに相手のスマートポインタの実体が存在します。つまりアドレスが割り振られているわけです。このアドレス先の人と手を結ぶ事で共有が実現します。そして、相手がいなくなる時にこの手は離されます。つまり、手がつながっている間は相手の存在が保証されているんです！スマートポインタをヒープに取ろうが小さな関数の中で一時的にスタック上に取ろうが、これは同じことです。相手のアドレスに実体が保証されているのであれば、生ポインタで持っても実質安全です。これにより、内部でnewをして共有先を確保する事がなくなるわけです。

　副次効果として、リンクリスト方式のスマートポインタのコンストラクタは大変に軽いです。newされたオブジェクトへのポインタの代入以外はリンクリストの両手にNULLを入れるだけです。参照カウンタ方式の場合はここにカウンタ用のnewが発生します。その生成コスト差は雲泥です。

　では、リンクリスト方式のスマートポインタを実際に作ってみましょう。



② 双方向リストの挿入・切り離しが出来れば終わりです

　まず、このスマートポインタに必要なメンバから整理します。スマートポインタはnewされたオブジェクトを包むので、当然ですがそのオブジェクトへのポインタを格納する必要があります。次に、相手のスマートポインタへの双方向リストがあるので、スマートポインタのポインタを2つ持ちます。叩き台としてはこんな感じです：

template<class T>
class sp {
    T* ptr;              // newされたオブジェクトへのポインタ
    sp<T> *pre, *next;   // 双方向リンク
};

概念的には正しいのですが、これ、実はちょっと正解ではありません。と言うのも、双方向リンクに「オブジェクトの型」の情報は必要無いからです。ただ単にお隣にポインタがあるかどうかが分かれば良いだけなんです。そこで、親クラスを定義します：

// 双方向リンクな親クラス
class sp_base {
protected:
    sp_base *pre, *next;   // 双方向リンク

    // コンストラクタ
    sp_base() : pre(), next() {
    }
};

template<class T>
class sp : public sp_base {
    T* ptr;              // newされたオブジェクトへのポインタ
};

こうする事で、相手と手をつないだり話したりする仕事とオブジェクトの共有を分離できます。では、インターフェイス別に検討していきましょう。


○ コンストラクタ

　spクラスのコンストラクタは複数存在します。一番簡単な空のスマートポインタはこんな感じです：

template<class T>
class sp ; public sp_base {
public:
    sp(T* ptr = 0) : ptr(ptr) {
    }
};

　引数に渡されたnewしたオブジェクトへのポインタを内部に包みます。双方向リストはsp_baseクラスのコンストラクタが自動的にNULLに初期化してくれます。

　次に代入用のコピーコンストラクタですが、ここで相手とのリンク作業及び相手の持つオブジェクトとの共有が発生します：

template<class T>
class sp ; public sp_base {
public:
    sp(const sp<T> &src) {
        // 相手に加えてもらう
        src.join(*this);
        // 相手のオブジェクトポインタを共有
        ptr = src.getPtr();
    }
};

joinメソッドはsp_baseクラスが持っていて、引数に渡されたスマートポインタを自分のリストに加えます。実装はこうです：

class sp_base {
protected:
    sp_base *pre, *next;   // 双方向リンク

protected:
    // 自分のポインタを取得
    sp_base *getThis() {
        return this;
    }

    // 相手を自分のリストに加える
    void join(sp_base &src) {
        // まず相手に独立してもらう
        src.remove();

        sp_base* srcPtr = src.getThis();   // 相手のポインタ取得
        // 自分の隣にすでに誰かが繋がっていたら、その人のpreと自分のnextに相手を挟む
        if (next) {
            srcPtr->next = next;
            srcPtr->pre  = this;
            next->pre    = srcPtr;
            next         = srcPtr;
            return;
        }
       
        // 自分の隣は誰もいないのでそのまま繋げる
        next = srcPtr;
        srcPtr->pre = this;
    }
};

双方向リンクの接続は落ち着いてやれば簡単です。後は相手のオブジェクトポインタを共有すれば同型スマートポインタのコピーコンストラクタ終了です。

　代入にはもう一つアップキャスト代入があります。これは次のようにテンプレートで補います：

template<class T>
class sp ; public sp_base {
public:
    template<class T2>
    sp(const sp<T2> &src) {
        // 相手に加えてもらう
        src.join(*this);
        // 相手のオブジェクトポインタを共有（アップキャスト代入）
        ptr = src.getPtr();
    }
};

もしアップキャスト不可能な代入がソース内にあると、このコンストラクタでコンパイルエラーが出ます。



○ デストラクタ

　デストラクタが呼ばれるというのは自分がスコープから外れる直前です。これは自分自身がリンクリストから外れる事を意味します。この時、もし自分の両隣にすでに誰もいなければ、それは自分が最後の一人である事を示唆していますから、保持しているオブジェクトポインタをdeleteします。

　上の実装のremoveメソッドは正にその役を担っています：

class sp_base {
protected:
    sp_base *pre, *next;   // 双方向リンク

protected:
    // リンクリストから外れる
    bool remove() {
        if (!pre && !next)
            return true; // 最後の一人でした
        if (pre)
            pre->next = next;
        if (next)
            next->pre = pre;
        pre = next = 0;
        return false;  // 仲間がまだいました
    }
template<class T>
class sp ; public sp_base {
public:
    ~sp() {
        // リンクリストから外れる
        if (remove())
            // 最後の一人でした
            delete ptr;
    }
};



○ 比較演算子その他

　スマートポインタとして後必要な演算子としては、

　　・ 同一ポインタか？（比較演算子 ==、!=）
　　・ NULLか？（NULLとの比較演算子 ==、 !=）
　　・ スマートポインタの代入（代入演算子 =）
　　・ NULLの代入（NULLの代入演算子 = ）
　　・ ポインタへの参照（アロー演算子 ->）
　　・ ポインタの値を取得（参照演算子 *）

このくらいでしょうか。それぞれ小粒ですがこんな感じです：

template<class T>
class sp ; public sp_base {
public:
    // 比較演算子
    bool operator ==(const sp<T> &src) { return (ptr == src.getPtr()); }
    bool operator !=(const sp<T> &src) { return (ptr != src.getPtr()); }
    bool operator ==(const int &) { return ptr == 0; }
    bool operator !=(const int &) { return ptr != 0; }
    operator int() {return ptr ? 1 : 0;}   // ※if文での判定などで使います。単項演算子もカバーするよ

    // 代入演算子
    sp<T> &operator =(const sp<T> &src) {
        // 独立します
        if (remove())
            delete ptr;
        // 相手に加えてもらう
        src.join(*this);
        // 相手のオブジェクトポインタを共有
        ptr = src.getPtr();
        return *this;
    }
    template<class T2>
    sp<T> &operator =(const sp<T2> &src) {
        // 独立します
        if (remove())
            delete ptr;
       // 相手に加えてもらう
        ((sp<T>*)&src)->join(*this);
        // 相手のオブジェクトポインタを共有（アップキャスト代入）
        ptr = src.getPtr();
        return *this;
    }
    sp<T> &operator =(const int &) {
        // 独立してNULL化します
        if (remove())
            delete ptr;
        ptr = 0;
    }

    // 参照
    T* operator ->() { return ptr; }
    const T* operator ->() const { return ptr; }
    T &operator *() { return *ptr;}
    const T &operator *() const { return *ptr; }
};

　参照演算子については注意が必要です。ptrがNULLの場合があるためです。何も考えずに参照するとメモリ保護違反で落ちます。つまりスマートポインタと言えどもNULLチェックは必要であるという事です。



③ 落とし穴回避：自分自身の代入はリンクしない

　参照カウンタ方式にしろリンクリスト方式にしろ、スマートポインタには幾つか落とし穴があります。基本的には「自己参照はやばい」です。リンクリスト方式のスマートポインタでは自分自身の分身を自分にリンクしてしまうとやばいです。

　なぜやばくなるか？例えばまだリンクしていないスマートポインタオブジェクトOがあるとします。これにO自身を代入しようとすると、最初にOは自分自身が他人になるので自分の保持しているポインタが解放できるかをチェックします。今の場合は誰もリンクしていないので解放してしまいます。そして「もう解放してしまった自分自身」を代入します。この結果、ダングリングしたオブジェクトを指すポインタを保持する人ができてしまいます。

　リンクリスト中に自分自身がいる場合は問題ありません。例えばABCD-O-EFGとある所にOを追加する場合、Oはまず自分自身をリストから外してからリストに加わります。結果としてO意外に加わる時にはその右側に位置が移るだけです。しかし、Oに追加しようとすると外れてしまう段階でOが独立してしまうため、上のリンクしていないスマートポインタオブジェクトへの代入と同じことになってしまいます。

　文章だけだとよく分からないと思いますが(^-^;、兎にも角にも自分自身への代入は残念な結果になります。これを防ぐには、代入時に自分自身であるかどうかをチェックするだけです。自分自身だったら何もしない、ただそれだけです。でも、それが大変に重要になります。実装上で自分自身への代入が起こるのは代入演算子を使った時です：

// コピーオペレータ
sp<T> &operator =(sp<T> &src) {
    // 相手が別人の時のみリンクする
    if (src.getThis() != this) {
        selfDelete();
        src.join(*this);
        ptr = src.getPtr();
    }
    return *this;
}



　以上の実装を踏まえたリンクリスト方式のスマートポインタはツール編に公開致します。