STLのmapのKeyを工夫しよう

ホーム < ゲームつくろー！ < C++踏み込み編 < STLのmapのKeyを工夫しよう

その３ STLのmapのKeyを工夫しよう

　
　標準テンプレートライブラリ（STL）のmapはKeyによってそれに付随するオブジェクトを管理・検索します。内部では2分木検索を実施しているため、検索スピードは高速です。mapを使いこなすと、プログラムでの「検索」という部分が非常に楽になりますから、知らない人は是非使ってみてください。

① mapで出来ること

　mapで出来ることは非常に簡単です。このSTLでは、
　
　「Keyに対応する目的オブジェクトを引っ張り出す」

という仕事だけが出来ます。Keyというのは、オブジェクトを代表する「値」のようなものですが、Key自体がオブジェクトであってもかまいません。ただし、Keyと目的オブジェクトは常にペア(pair)である必要があります。

　図書館の膨大な本から目的の本を取り出したいとき、本棚すべてを見ていては気が遠くなります（線形検索）。そういう時に、本のありかを示すタグがあれば、検索は高速になります。タグに「生物/進化/ガラパゴス諸島の進化」とあれば、生物のコーナーの「進化」の本棚を見るだけで良いわけです。もっと場所を特定するタグを作成すれば、何の迷いも無く目的の本を探せるはずです。

　ゲーム製作でmapを使う場面は、目に見える形では少ないかもしれません。膨大な情報量を管理して引き出すゲームと言うのが少ないからです。しかし、目に見えない（プログラマしか知らない）部分では、色々と使われていると想像します。意外なところで使えたりするのがmapです。

② mapを簡単に使う

　なにはともあれmapという物を使ってみたいわけで、短いサンプルプログラムを示します。

#include <map>
#include <string>
using namespace std;

int main(int argc, char* argv[])
{
map<int, string> IntToStr;
map<int, string>::iterator it;

// pairオブジェクト
pair<int, string> p(0, "0");

// 格納
IntToStr.insert(p);

// 取り出し
it = IntToStr.find(0);
string str = (*it).second;

return 0;
}

　mapはテンプレートの型が最低2つ必要です。最初はKeyの型、2つめはオブジェクトの型です（フルに活用する時には4つ設定します）。STLでデータを探索する基本であるiteratorを次に作成します。これは当然ですが、mapの型と合わせなければなりません。mapにデータを格納する時には「pair」という非常に小さな構造体を用います。これは、2つのオブジェクトを保持するテンプレート構造体です。

template<class T, class U>
struct pair
{
typedef T first_type; // 型の名前を再定義
typedef U second_type
T first; // 1番目のオブジェクト
U second; // 2番目のオブジェクト

pair();
pair(const T& x, const U& y); // コンストラクタでペアを格納
template<class V, class W> // ペアのコピー（暗黙の型変換が可能）
pair(const pair<V, W>& pr);
};

　コンストラクタが3つありますが、3番目が見慣れない感じですね。これは、別の型情報のpairオブジェクトから値をコピーするために使います。これがないと、例えば、

pair<int, int> int_pair(100 ,200);
pair<double, double> double_pair( int_pair );

のような代入が出来なくなってしまい不便なのです。

　mapにデータを格納する時にはmap::insert関数を用います。ただpairオブジェクトを引数に渡すだけなので簡単です。値を取り出す時にはmap::find関数を使用します。これは引数に「Key」のみを渡します（Keyで検索ですから当然ですね）。もし指定のKeyがあれば、そのKeyに関連付けられている目的オブジェクトを指すpairオブジェクトのiteratorを返します。ここがポイントですね。目的オブジェクトはpair::secondに格納されているので、(*it).secondと値を取り出しています。

　mapの基本的な使い方は、実はこれだけなんです。非常に簡単で分かりやすいSTLだと思います。

③ mapを扱うときの注意

　このように簡単で便利なmapですが、いくつか注意点があります。まず、同じKeyは登録できません。また、格納されていないKeyで検索を行ったとき、iteratorとして戻ってくるのはmap::end関数の戻り値です。これは空っぽ（不定ポインタ）なので、たぐるとメモリ保護違反となります。つまり、「Keyがあるはず」というチェックの無いプログラムを書くのは危険です（上のプログラムはそれを無視しています）。

　Keyがあるかないかはiteratorがmap::end関数の戻り値と同値であるかを調べれば良いので、

if(it != IntToStr.end())
string str = (*it).second;

と条件文を付ければOKです。

　格納するときに同じKeyがある場合、map::insert関数はpair<Key, bool>という戻り値のsecond変数にfalseを返してきます。よって、

if( !IntToStr.insert(p).second )
// 格納できなかった時の処理;

とすることで、格納出来ない場合の処理を行わせることができます。

③ 決め手はKeyの大小等号

　mapオブジェクトの中では、Keyを頼りに格納と検索を行っています。格納方法は2分木です。よって、Keyによる大小の比較が成されています。また、検索にヒットしたかどうかは「==」演算子を用いています。さて、Keyはオブジェクトでもなれると先述しました。ということは、オブジェクトの比較演算子を再定義すると、とても面白い検索も可能になるのです。

　ここで1つかなりに実用的と思われる例でオブジェクトの大小によるmapの扱いを紹介します。以下の図をご覧ください。

符号無し整数の数直線があって、(Sn, En)という線分に区切るとします。線分は重なることが出来ないとして、次のようなアクセスをしたいと考えます。

指定の線分をクリックすると、それに関連する目的オブジェクトにアクセスできるようにするわけです。こういうツールは非常に応用範囲の広いものです。

　mapで言うと、線分は「Key」にあたります。ただし、Keyには開始点(Sn)と終了点(En)がありますから、すでにオブジェクトです。そこでまず、区間をあらわすCIntervalクラスを作成し、大小等号の演算子を再定義します。目的のオブジェクトは何でも良いので、今回は単なる数字にしておきます。

　2つの区間（CInterval）の大小は簡単ですね。

class CInterval
{
protected:
unsigned int m_S;
unsigned int m_E;

public:
CInterval(){m_S=0; m_E=0;}
CInterval(unsigned int s, unsigned int e){m_S=s; m_E=e;}
unsigned int GetEnd() const
{ return m_E;}
unsigned int GetStart() const
{ return m_S; }

public:
// オペレータ定義
bool operator <(const CInterval &Obj) cosnt
{
if(m_E <= Obj.GetStart())
return true;
return false;
}

bool operator >(const CInterval &Obj) const
{
if(m_S >= Obj.GetEnd())
return true;
return false;
}
};

整数なので、境界線が重なるのは許容します。よって<=や>=を使っているわけです。
　最大のポイントは等号処理です。線分が重なったら保存しないでほしいわけですから、「線分が重なったら等しい」というふうに「==」演算子を書き換えます。

bool operator ==(const CInterval &Obj) const
{
if(m_E <= Obj.GetStart() || Obj.GetEnd() <= m_S)
return false;
return true;
}

ちなみに、演算子の関数の後の「const」を入れないと「オーバーロードされた演算子が無い」というエラーが出ますので忘れずに。これで、重なりの無い線分を並べる事が出来ます。実際にやってみましょう。

int main(int argc, char* argv[])
{
map<CInterval, int> IntToStr;
map<CInterval, int>::iterator it;

// pairオブジェクト
pair<CInterval, int> p[5];
p[0].first = CInterval( 0, 10);
p[1].first = CInterval(10, 20);
p[2].first = CInterval(17, 30); // 重なる
p[3].first = CInterval(40, 50);
p[4].first = CInterval(30, 45); // 重なる

// 出力
for(int i=0; i<5; i++)
printf("[%d] : %d\n", i, IntToStr.insert(p[i]).second);

return 0;
}

線分を5つ作成してpairオブジェクトの配列にいれ、それを順番にmapに挿入していきます。しかし、p[2]とp[4]は重なってしまいますから、同一キーとなりmapに入れる事が出来ません。出力結果は次の通りです。

[0] : 1
[1] : 1
[2] : 0
[3] : 1
[4] : 0

うまくいってますね。

　実を言うと、同様のことをSTLのSetでも行うことが出来ます。mapとの違いは、mapがKeyと目的オブジェクトが異なっていたのに対して、SetはKeyも目的オブジェクトも同じという点です。mapの場合、区間が目的オブジェクトへのハッシュになっているという不思議な状態を実現できます。

④ Keyの変更

　mapはKeyを頼りに内部で2分木に分類してくれています。よって、Keyを変更する事は原則出来ません。変更する方法もあるのですが、その場合再構築を必要とします。上の区間の例だと、区間を変更する事は良くあるでしょうから、実はちょっとまずいわけです。パフォーマンスを求めるときには抜本的な見直しが必要ですが、そうでない場合、一度削除を行ってから再登録するのが簡単でしょう。削除も登録も時間にしてO(logn)レベルですから、そう気にする部分でもありません。