18:ハッシュを使って高速探索

　前回で特定のオブジェクトを探索する方法を紹介しましたが、頻繁に呼び出しが必要なオブジェクトをリストから逐一線形探索をしていたのであれば、その負荷は非常に大きなものになります。そこで、専用の「箱」に入れておくことで、特定のオブジェクトをすぐに取り出せるようにしましょう。
　ＳＴＬで用意されているmapクラスは、キーとそれ対応する要素を格納することができ、キー名により要素を素早く取り出すことができます。

　Visual C++をはじめとする一部のC++開発環境では「hash_map(もしくはunordered_map)」というクラスが用意されています。mapクラスとの大きな違いはキー名を元に探索するためのアルゴリズムの違いにあります。mapは二分木探索であるのに対し、hash_mapはハッシュアルゴリズムによって検索されます。この差は大変大きなもので、時にはhash_mapの方が２倍近く高速になることもあります。そのため、今回はhash_mapを使って解説しますが、利用できる関数は共通ですので、お使いの開発環境が対応していないようであれば、hash_mapをmapに置き換えてご覧下さい。

　hash_mapはＳＴＬの概念には沿っているものの、ＳＴＬ標準ではないため、宣言方法は開発環境によってまちまちです。なお、Visual C++の場合は以下のように記述します。ここでＳＴＬの文字列管理クラス「string」も併せて宣言されていますが、その理由は後ほど紹介。
hashmap.h
#include <string>
using namespace std;

#include <hash_map>
using namespace stdext;
　hash_mapクラスを「アイテムボックス」としてCGameObjectクラス内に宣言します。山括弧（<>）内の左側にはキーとする型、右側には要素とする型を入力します。下記のように、左側にstringを入れると、文字列に対応するオブジェクトの取得が可能となります。
itembox.h
class CGameObject
{
private:
    // アイテムボックスの宣言
    static hash_map<string, CGameObject*> itembox;
　アイテムボックスの管理を担う関数を用意します。
itembox2.h
class CGameObject
{
public:
    // オブジェクトを格納
    static void AppendItemBox(LPCSTR name, CGameObject *object);
    // 指定したキーに格納されているオブジェクトを取り除く
    // （実際に削除する場合はRemoveObject()を使うこと！）
    static void RemoveItemBox(LPCSTR name);
    // アイテムボックス内のデータをすべて取り除く
    static void ResetItemBox();
    // 指定した文字列に対応するオブジェクトを取得する
    static CGameObject* FindItemBox(LPCSTR name);
　用意したそれぞれの関数を実装します。まずは追加から。データを追加するには、make_pair関数を用いて作成されたデータでなくてはいけません。
insert.cpp
void CGameObject::AppendItemBox(LPCSTR name, CGameObject *object)
{
    itembox.insert(make_pair(name, object));
}
　続いて削除関数。eraseの引数にキーを指定すると、対応するデータが一覧から削除され、clear関数で、すべてのデータが削除されます。
remove.cpp
void CGameObject::RemoveItemBox(LPCSTR name)
{
    itembox.erase(name);
}

void CGameObject::ResetItemBox()
{
    itembox.clear();
}
　キーに対応する要素を取得する関数はfindで、対応するデータがあれば、その位置を示すイテレータが返されます。イテレータ内のfirstにはキー（この場合は文字列）、secondには要素（この場合はCGameObject*）が格納されています。もし、一覧に対応するデータが存在しない場合は、endイテレータが返されますので、このときはNULL値を返すようにしています。
find.cpp
CGameObject* CGameObject::FindItemBox(LPCSTR name)
{
    hash_map<string, CGameObject*>::iterator i;
    i = itembox.find(name);

    if(i == itembox.end()) return NULL;

    return i->second;
}
　オブジェクト管理にはこのアイテムボックスを有効に使っていきましょう。
←前の項目 次の項目→