問題タブ [unordered-map]

私は最近、boost とそれがコンテナーであることに関心を持ち始めたばかりであり、web と stackoverflow で、boost::unordered_map が大きなコレクションの最速のコンテナーであるという記事をいくつか読みました。したがって、私はこのクラス State を持っています。これはコンテナー内で一意でなければならず (重複はありません)、コンテナーには数十億ではないにしても数百万の状態が存在します。そのため、サイズを小さくし、計算をできるだけ少なくするように最適化しようとしています。以前はboost::ptr_vectorを使用していましたが、stackoverflowで読んだように、ベクターはオブジェクトがそれほど多くない場合にのみ有効です。私の場合、状態はロボットからの感覚運動情報を記述するため、膨大な量の状態が存在する可能性があるため、高速検索が最優先事項です。ブーストのドキュメントに従うunordered_map については、高速化するためにできることが 2 つあります。hash_function を使用し、等値演算子を使用して、hash_function に基づいて状態を比較します。そこで、ステート情報を取り込み、boost::hash_combine を使用して std::size_t ハッシュ値を作成するプライベート hash() 関数を実装しました。operator== は、基本的に状態のハッシュ値を比較します。そう：

• std::size_t は、数十億の可能性のある hash_function の組み合わせをカバーするのに十分ですか? 状態の重複を避けるために、hash_values を使用するつもりです。

• state_map を作成するとき、State* またはハッシュ値をキーとして使用する必要がありますか? すなわち:boost::unordered_map<State*,std::size_t> state_map; または boost::unordered_map<std::size_t,State*> state_map;

• boost::unordered_map::iterator = state_map.find() を使用したルックアップ時間は、boost::ptr_vector を通過して各反復子のキー値を比較するよりも高速ですか?

• 最後に、このような順序付けられていないマップを最適化して速度と高速ルックアップを実現する方法に関するヒントやコツを教えていただければ幸いです。

編集:私はかなりの数の答えを見てきました.1つはブーストを使用せずにC ++ 0X、もう1つはunordered_setを使用しないことですが、正直に言うと、boost::unordered_setがハッシュ関数でどのように使用されるかをまだ知りたいです. ブーストのドキュメントに従って実装しましたが、順序付きセットでブーストのハッシュ関数を使用する方法がまだわかりません。

値10で最初に作成した要素を削除したい次のコードがあります。イテレーターの設定と消去に問題があります。それはどのように行われますか？

アプリケーションに静的なunordered_mapsがいくつかあり、起動時に初期化できるようにしたいと考えています。それらはクラスの一部ではありません。私の初期設定では、ヘッダーとソースファイルは次のとおりでした。

そしてソースファイル：

ただし、これを実行しようとした後、マップでルックアップを実行しようとすると（つまり、Game :: Elements :: NameElementMap [std :: string（ "Air"）]）、常に空の文字列が返され、その使用でのサイズが返されます。コンテキストは0です。

初期化をヘッダーファイルに移動してみました（つまり、ヘッダーファイルに

しかし、コンパイラーはデフォルトのコンストラクターがないことについて不平を言いました。私は何が間違っているのですか？

前もって感謝します

イテレータを使用して多層unordered_mapに整数を出力しようとしていますが、問題が発生しています。エラーはコードの下にあります。

以下のエラー：

VS2010C++のインデックスに最大3,000,000個のdouble値を格納したいと思います。unsigned int私はstd::tr1:unordered_map<unsigned int, double>この目的のためにを使用します。残念ながら、値番号2 ^ 21を格納しようとすると、例外がスローされます（2 ^ 21-1のスペースしかない場合、つまり、一部のインデックスでは20ビットしか使用できない場合があります）。値を保存する前に試しましたrehashが、どちらも機能しませんでした。

最後に、私はいくつかの非常に基本的なテストプログラムに行き着きました（少しでも異なる動作を示しましたが、とにかく）：

私がチェックしたいくつかのケース：

1）まったく再ハッシュしない場合、プログラムはi == 32000（最終的には2 ^ 15）に従って出力された後、長い休憩を取り、その後i == 262000（2 ^ 18）に進みます。そこでは永久に保持されます（100％のCPU負荷で、メモリは増加しません）。

2）を実行するrehash(1000)と、i == 65000（2 ^ 16）になり、永久に保持されます（CPU負荷は100％、メモリは増加しません）。

3）を実行するrehash(3000000)と、ループは正常に終了しますが、プログラムは終了しません。つまり、明らかにデストラクタに問題があります。

そこで何が起こっているのか、そしてさらに重要なのは、それについて何をすべきかということです。

助けてくれて本当にありがとうございます！

unordered_mapそれで、私はSTLから新しく標準化されたもので遊んでいました。私が持っているコードはこのようなものです。 unordered_map を作成し、それを埋めて、出力するだけです:

ただし、取得する出力は次のように並べられています。

しかし、地図を注文してもらうために代価を払いたくありません! それが unordered_map を使用している理由です...ここで何が起こっているのですか?

追記：私はgcc version 4.3.4 20090804 (release) 1 (GCC)このように使用してコンパイルしていますg++ -std=c++0X maptest.cpp

まず、C ++で[]演算子をunordered_mapと組み合わせてルックアップに使用すると、find（）メソッドの呼び出しがラップされるのか、それとも[]演算子をfind（）よりも速く使用するのかを明確にできますか？

次に、次のコードでは、キーがunordered_mapにまだ含まれていないmap[key] = value場合に、[]演算子を使用して作成されたデフォルト値を置き換えるために、行を介して2回目のルックアップを実行していると思われます。キーがありません。

それは本当です。もしそうなら、（おそらくポインタなどを使用して）どのような場合でも（おそらく値を配置する場所のアドレスを格納する/値を読み取ることによって）1回のルックアップのみを実行する方法があります。それでも同じ機能を実現しますか？もしそうなら、明らかにこれは有用な効率改善になるでしょう。

変更されたコードの抜粋は次のとおりです。

次のプログラムでは、unordered_mapO（1）の検索/挿入時間を必要としたという理由だけで、現在使用しています。でも今は注文したかったです。毎回ソートするのは非常に非効率的です。私の選択肢は何ですか？私はそれhash_mapが仕事をすることを読みました、しかし私が読んだ記事は私が理解するのに非常に混乱するかかなり複雑です。挿入/検索の複雑さは何hash_mapですか？それは本当に順序付けられていますか？もしそうなら、それはC ++ 0xで定義されていますか？どうすればそれを実装できますか？そうでない場合、他に何を使用できますか？ありがとう。

編集：

以前使ってstd::mapいたのですが、アイテムがたくさんあります（百万単位）。それで、アイテムの数が非常に多い場合でも、map注文したい場合は、皆さんがお勧めしますか？

デフォルトunordered_mapで使用されるビットハッシュは何ですか? 関数は を返します。16 ビットのハッシュ関数を使用するということですか?C++0xstd::hashsize_tunordered_map

これはおそらくばかげた質問だと思いますが、確認したかったので、この情報をすぐに見つけることができませんでした。

順序付けされていないマップでのfind（）のパフォーマンス特性は何ですか？通常のルックアップと同じくらい速い/ほぼ同じくらい速いですか？

つまり

対。

ここRows::NameRowMapで、は文字列インデックスをintにマッピングする順序付けられていないマップです。

私の場合、キーが事前に存在するかどうかはわかりません。そのため、最初の解決策の方が安全だと思われましたが、存在を保証できれば、2番目のケースの方が高速です（追加のチェックを無視します）。 ？もしそうなら、なぜですか？重要な場合は、1.46ブーストの実装を使用しています