C++11 スマートポインタの使い方・用途・サンプル

C++はガーベジコレクションがないので、動的にallocateしたオブジェクトは明示的にdeallocateしなければなりません。これを怠るとメモリリークなどもの問題が出てくるわけです。また逆に、オブジェクトを破棄したポインタを使いつづけるとnullポインタ、或いはダングリングポインタとしてエラーの原因になります。

C++において生来的ともいえるこれらの問題を解決しようというのがスマートポインタの機能です。簡単に言うと、ポインタのスコープに合わせてオブジェクトが勝手にdeallocate(deconstruct)されます。これによってオブジェクトとポインタの寿命が一致するのでメモリリーク、ダングリングポインタが防げます。

スマートポインタには何種類かあり、それぞれ異なる仕様・用途があります。以下、unique_ptr, shared_ptr, weak_ptr, auto_ptr(C++11以前)の説明をします。


1. unique_ptr

一番使われるのはunique_ptrでしょう。以上に述べたスマートポインタの特徴に加え、名の通り「指しているオブジェクトに対する唯一のポインタ」であることを保証します(低レベルで色々やれば崩せますが)。即ち、unique_ptrは他のスマートポインタからオブジェクトをコピーしたりアサインしたりすることが出来ません。

オブジェクトを他のポインタに割り当てたい場合はstd::moveを使う必要があります。これを使うと元のポインタはnullポインタになるので、やはり一つのポインタしかそれを指すことが出来ません。

以下のコードのように、いちいちdeleteなどしなくても使うことができます。

void unique_ptr_test() {
    cout << "----- unique_ptr test -----" << endl;
    std::unique_ptr<int> first(new int(1));
    std::unique_ptr<int> second(new int(2));

    // 関連して、nullptrも新しく加わった。0, NULLと区別される。
    std::unique_ptr<int> nullpo(nullptr);

    cout << "*first = " << *first << endl;
    cout << "*second = " << *second << endl;

//    std::unique_ptr<int> second = first; ERROR: コピーは出来ない。
//    second = first; ERROR: アサインも出来ない。

    // moveを用いることでオブジェクトをsecondに移すことが出来る。
    //　そのとき、firstはnullptrになるので注意。
    // つまり、unique_ptrを参照できるポインタは常に一つである。(定義より)
    second = std::move(first);
    cout << endl << "second = std::move(first);" << endl << endl;
    cout << "*fisrt = " << (first? "not null" : "null") << endl;
    cout << "*second = " << *second << endl << endl;

    cout << "nullpo is " << (nullpo? "not null" : "null") << endl;

    // unique_ptrはスコープの外に出るときにdeconstructorを呼ぶ。
    {
        std::unique_ptr<Foo> locale(new Foo());
    }
}

2. shared_ptr

unique_ptrの使いやすさの一つに「オブジェクトを指す唯一のポインタ」であることがあるでしょうが、逆にそうでない方が使いやすい場合もあるでしょう。複数のスマートポインタで同じオブジェクトを指したい時に使われるのがshared_ptrです。

shared_ptrはunique_ptrと異なり、コピー・アサインをすることができます。また、オブジェクトを指している複数のshared_ptrのうちの一つだけを初期化したい場合にreset()を呼ぶことで、そのオブジェクトを破棄せずに(それによって他のポインタがnullポインタにならずに)そのポインタだけをnullポインタにすることができます。

また、共有されているオブジェクトはshared_ptrの全てがスコープから外れた時に破棄されます。

void shared_ptr_test() {
    cout << "----- shared_ptr test -----" << endl;
    std::shared_ptr<Foo> first(new Foo());
    std::shared_ptr<Foo> copy = first;

    // copyがまだあるのでresetでもオブジェクトは持続される。
    // しかしfirstはnullポインタになる。
    first.reset();
    cout << "first = " << (first? "not null" : "null") << endl;
    cout << "copy = " << (first? "not null" : "null") << endl;

    // copyもreset()が呼ばれるとdestructor
    copy.reset();
}

3. weak_ptr

 weak_ptrはshared_ptrをサポートするスマートポインタです。
weak_ptrはshared_ptrが指しているオブジェクトを同様に指すことが出来ます。しかし、先ほどshared_ptrの指すオブジェクトは、「shared_ptrの全てがスコープから外れたら破棄される」とありましたが、つまりweak_ptrが指していても、shared_ptrが全てなくなれば破棄される、ということです。

ではweak_ptrは何に使われるのかというと、 shared_ptrを用いてオブジェクトを破棄して新しいオブジェクトをconstructしたり、という流れの中で使われます。つまり、weak_ptrでshared_ptrのオブジェクトを参照しておき、それからshared_ptrで新しいオブジェクトをallocateすると、weak_ptrはNullを指すことになります。使ってみるとこれが便利な場合が結構あります。

void weak_ptr_test() {
    cout << "----- weak_ptr test -----" << endl;


    // 通常のポインタはDangling pointerとなるリスクがある。
    // 例えばここでrefはdangling pointerである。
    int* ptr = new int(10);
    int* ref = ptr;
    delete ptr;

    // それに対して、
    // weak_ptrは対象のオブジェクトがdeallocateされたかをexpired(), lock()で確認することが出来る。

    std::shared_ptr<int> sptr;
    // takes ownership of pointer
    sptr.reset(new int(10));

    // weak1は*sptrを参照はするが、保持はしない。
    std::weak_ptr<int> weak1 = sptr;

    // 前のオブジェクトを破棄し、新しいオブジェクトを作る。
    // ここでweak1がshared_ptrなら一緒に5を指すことになるが、ここではweak_ptrなので参照オブジェクトがなくなる。
    sptr.reset(new int(5));

    // 5を指すweak_ptr
    std::weak_ptr<int> weak2 = sptr;


    // weak1の指していたオブジェクトがdeallocateされたかはlock()で確認することが出来る。
    if ( auto tmp = weak1.lock() ) {
        std::cout << "weak1.lock() = " << *tmp << '\n';
    } else {
        std::cout << "weak1 is expired\n";
    }

    if ( auto tmp = weak2.lock() ) {
        std::cout << "weak2.lock() = " << *tmp << '\n';
    } else {
        std::cout << "weak2 is expired\n";
    }

}

4. auto_ptr (C++11以前)

 auto_ptrはレガシーです。簡単に言うならunique_ptrの下位互換です。C++11以前からあるので(これを発展させたものが今まで説明してきたスマートポインタら)、C++11を使いたくない事情がある場合に代用として使えます。基本的に使い方はunique_ptrと同じです。ただ隠蔽構造がやや不完全で、例えば以下のコードだとy = xでunique_ptrのy = std::move(x)に当たり、ここでxはnullポインタになるので、なかなか注意が必要な構造をしています。

void auto_ptr_test() {
    cout << "----- auto_ptr test -----" << endl;
    auto_ptr<int> x(new int(5));
    auto_ptr<int> y;

    y = x;

    cout << "x is " << (x.get() ? "not null" : "null") << endl; // Print NULL
    cout << "y is " << (y.get() ? "not null" : "null") << endl; // Print non-NULL address i
}

スマートポインタは通常のポインタと比べてそんなに遅くないそうです(アセンブリにして追加一行程度とのこと)。特にパフォーマンスが求められていない部分のコードは手軽く使っていけるようです。

Zobrist Hashing

Zobrist Hashingは将棋やチェスなどで用いられる、状態をハッシュ値に落とし込む方法です。

というのも将棋やチェスのような状態のハッシュ値を計算する場合、n進数や辞書順によるハッシュ関数では状態空間に対してハッシュ値を不偏的に散らすことはなかなか難しいです。そこでZobrist Hashingは乱数とXORを使って不偏性を作り出します。


WikipediaのZobrist Hashingの擬似コードを引用します。

   constant indices
       white_pawn := 1
       white_rook := 2
       # etc.
       black_king := 12
   
   function init_zobrist():
       # fill a table of random numbers/bitstrings
       table := a 2-d array of size 64×12
       for i from 1 to 64:  # loop over the board, represented as a linear array
           for j from 1 to 12:      # loop over the pieces
               table[i][j] = random_bitstring()
   
   function hash(board):
       h := 0
       for i from 1 to 64:      # loop over the board positions
           if board[i] != empty:
               j := the piece at board[i], as listed in the constant indices, above
               h := h XOR table[i][j]
       return h

(Wikipediaより: http://en.wikipedia.org/wiki/Zobrist_hashing)


・init_zobrist
まず下準備として、予めパズルの各マスに対してランダムビットstringを定義する。
例えば将棋なら、
７六に歩がある状態を 0100 0111 のように定義する。
７七に角がある状態を 1001 1100...
のように全てのマスの、全てのありうる状態に対するキーの値をテーブルに保存する。（以後テーブル値とする。）


・hash(board)
全てのマスの状態に対して定義されたテーブル値をビット毎のXORでかけていく。


さて、このZobrist Hashingの特徴を見ていきましょう。

・まず、Zobrist HashingはPerfect Hashingである保証は全くありません。盤が違う状態でも同じハッシュ値になり得ます。簡単な例だと
0000 XOR 0011 = 0011
0100 XOR 0111 = 0011
ですので。

・そこから一歩進んで、このハッシュ関数は同じフレームワークの中でビット長を変えることでハッシュの重複度を変化させることが出来ます。つまり、ビットを長くするほど違う盤の状態が同じハッシュ値を持つ割合(確率)を小さくさせることが出来ます。これは当然計算速度とメモリ量のトレードオフになります。

・n進数や辞書順によるハッシュ関数と比較して、盤の状態に対して偏りのないハッシュ値が得られることが多い。Bitwise XORなのでハッシュ値のビットストリングの各桁は、全てのマスの状態の関数なので、全てのマスのテーブル値を参照した結果の値といえる。ただしここで注意しなければならないのは、必ず偏りがないハッシュになるとは限らないということです。それは状態空間の性質にもよりますし、乱数の揺れにも依存します。



天才的な発想ですよね。どの位実用されているのかはよく知らないのですが、こういうアイディアの出せる人間になりたいものですね。




C++で簡単なサンプルを実装をしたものが以下のコードです。

/*
 * zobrist.cc
 *
 * Short sample to test Zobrist hashing.
 * Zobrist hashing is a hash function construction for abstract board games.
 *
 *
 *  Created on: Jun 10, 2014
 *      Author: Yuu Jinnai
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define INDICES 16
#define SIZE 32

void initZobrist(int* table);
void initRandomBoard(int* board);
int hash(int* board);

int* table;

int main() {

 srand(time(NULL));
 table = new int[SIZE*INDICES];
 initZobrist(table);

 int* board = new int[SIZE];
 for (int i = 0; i < 10; ++i) {
  initRandomBoard(board);
  printf("hash(board) = %d\n\n", hash(board));
 }

}

void initZobrist(int* table) {
 for (int i = 0; i < SIZE; ++i) {
  for (int j = 0; j < INDICES; ++j) {
   table[i+SIZE*j] = rand();
   printf("table[%d][%d] = %d\n", i, j, table[i+SIZE*j]);
  }
 }
}

void initRandomBoard(int* board) {
 for (int i = 0; i < SIZE; ++i) {
   board[i] = rand() % INDICES;
   printf("%d ", board[i]);
 }
 printf("\n");
}

int hash(int* board) {
 int h = 0;
 for (int i = 0; i < SIZE; ++i) {
  h = (h ^ table[i+SIZE*board[i]]);
 }
 return h;
}