[解決済み] C++のSTLでバイナリサーチツリーを実装？

質問

ご存知ですか？ C++ STL が含まれています。 バイナリサーチツリー(BST) の実装が必要なのか、それとも自分でBSTオブジェクトを作成した方がいいのか？

STLにBSTの実装がない場合、利用できるライブラリはありますか？

私の目標 は、目的のレコードをできるだけ早く見つけることができるようにすることです。私はレコードのリスト（数千は超えないはず）を持っており、私はそのリストの中でフレーム単位（コンピュータゲームです）の検索を行います。私は、私の関心のあるレコードの識別子としてunsigned intを使用しています。どのような方法であれ、最も速い方法が私にとって最も効果的でしょう。

どのように解決するのですか？

必要なのは、あるデータをあるキーで検索する方法です。キーは unsigned int このように、いくつかの可能性があります。もちろん std::map :

typedef std::map<unsigned int, record_t> my_records;

しかし、それ以外の可能性もあります。例えば、かなり高い確率で ハッシュマップはさらに高速になります バイナリツリーよりも ハッシュマップは unordered_map は、C++では C++11 コンパイラやstd libですでにサポートされている可能性があります (コンパイラのバージョンとドキュメントを確認してください)。これらは、最初に C++TR1 ( std::tr1::unordered_map )

キーが密接に分散している場合は、単純な 配列 で、そのキーをインデックスとして使用します。速さに関して言えば、配列へのインデックスに勝るものはないでしょう。しかし、キーの分布があまりにランダムだと、多くのスペースを浪費することになります。

としてレコードを保存する場合 ポインター また、データをキーでソートしてベクターに保存することもできます。

typedef std::vector< std::pair<unsigned int, record_t*> > my_records;

より良いデータローカリティのため、おそらくプロセッサキャッシュと相性が良く、シンプルな std::vector 理論的には他のデータ構造が有利になるはずですが、多くの場合、他のデータ構造よりも良いパフォーマンスを発揮します。その弱点は、中間に挿入したり、削除したりすることです。しかし、この場合、32ビットシステムでは、2*32ビットPODのエントリを移動する必要があり、実装では、メモリ移動のためのCPU intrinsicsを呼び出して実行する可能性があります。