2014年5月1日木曜日

C++: std::map の lower_bound と upper_bound // mapに対してある値の近傍2点の値を取り出したいのです。

assimpのスケルタルアニメーションデータのロードに際して、アニメーションのキーフレーム情報{時刻、変形データ}群について、そのシーケンスからさっくりと、ある指定時刻の前後のキーフレーム情報を取得したいな、と。

そこで単純にキーフレーム情報を std::vector に入れて置いて片っ端からトラバースという手っ取り早いかもしれない実装、ではなくて、少しでも効率良くある指定時刻の前後のキーフレーム情報を探索したいな、と。

キーフレームの時刻情報は単純に比較可能で重複していないので std::map を使って事実上の二分木で探索したら効果的です。効果的ですが、いわばファジーな検索をしたいのです。

mapに対してある値の近傍2点の値を取り出したいのです。

そこで使えそうなのがstd::mapの lower_bound, upper_bound, equal_range メンバー関数たち。少し罠に掛かりかけましたが、それは後にするとして、コードと実行結果の例です。

code:

upper_bound を使って「より大きい」キーのイテレーターを探してその値を取り出して、それから1つ前にイテレーターを戻して「以下」の値も取り出しています。

掛かりかけた罠は lower_bound は「以上」であって「以下」ではないという点なのでした。 lower_bound と upper_bound で「以下」と「より大きい」が取れたら楽かしら、と思ってやってみて、あ、なんか違う、と仕様確認して上記実装になったのでした(╹◡╹)


参考:

0 件のコメント:

コメントを投稿