C++のstd::mapのキーに、自分で定義した構造体やクラスを使うことができます。
その際、std::mapはデータを2分木で格納しているため、キーになる構造体やクラスに、比較演算子 < を定義してあげる必要があります。
自分で作った構造体やクラスだと、二つ提示されてもどっちが大きいとか小さいとかわからないもんね!
というわけで、以下は、intとchar[100]をもった構造体をキーとしたい場合のサンプル。
/** * @struct intStringKey_t * @brief This struct is int-string key for map */ struct intStringKey_t{ int intKey; char stringKey[100]; bool operator < (const intStringKey_t& rhs ) const { if (intKey_t < rhs.intKey_t) { return true; } if (intKey_t > rhs.intKey_t) { return false; } if ((strcmp(stringKey, rhs.stringKey)) < 0) { return true; } if ((strcmp(stringKey, rhs.stringKey)) > 0) { return false; } return false; } };// intStringKey_t;
こんな感じで構造体を定義すれば、この構造体をstd::mapのキーとして使えます。
もちろん、比較演算子の処理の中身はこの限りではありません。
さて、std::mapのキーとして構造体を使おうとして、一度落とし穴にハマりました。
その時のコードはこんな感じ
/** * @struct intStrKey_t * @brief This struct can NOT be used as int-string key for map */ struct intStrKey_t{ int intKey; char strKey[100]; bool operator < (const intStrKey_t&rhs ) const { if (intKey < rhs.intKey) { return true; } else if (intKey == rhs.intKey) { if (strcmp(strKey, rhs.strKey)) { return true; } else { return false; } } else { return false; } } };// intStrKey_t;
パッと見、よさそうな感じがしませんか??
でも、この定義だと、二つのintが等しいときの処理が、charが等しかったらfalseを返して、等しくなかったらtrueを返す、となってます。
つまり、strcmpの結果が-1でも1でもtrueを返しちゃってるわけです。
となると、二分木の探索に支障が出てくるわけですね。。。
わかってみるとなんてことないのですが、このバグの厄介なところは、mapにデータを一つ格納しただけでは特に問題が顕在化しなかったのです。
二つ目のデータを格納してみたら、格納したはずなのに取り出せない!という事態になりました。
しかも、三つ目のデータを格納してみたら、それはちゃんと取り出せる。。。
最初は、mapにデータが格納できたりできなかったりする、あるいは取り出せたり取り出せなかったりする、というその不安定な感じから、mapを扱ってるコードの近くで、メモリでも破壊しちゃってるのかな、と思ったりもしたのですが、周辺のコードをよく読んでみても、そんな気配もなく…。
実は構造体(比較演算子 <)の定義がおかしいと気が付くのに、ちょっと時間がかかりました。
もし同じような現象で悩んでる人がこのエントリを見つけてくれたら嬉しいなぁ。