問題タブ [unordered-map]

順序付けされていないマップ検索関数が bool 値を返すようにしたい場合、どうすればそれを行うことができますか?

ここに私のコードがあります。

他に何をする必要がありますか? boolを返すことは可能ですか? 私が見つけたこれに関するドキュメントはほとんどありません。

これは、 http://msdn.microsoft.com/en-us/library/bb982431.aspxから例を取得した場所です

私が実装したツリーデータ構造が占める正確なサイズをバイト単位で見つける必要があります。ノード構造は次のとおりです

私が行っているのは、 size(int)*2(word と count の場合) + map.bucket_count() * (sizeof(int) + sizeof(Node*)) で、ノードごとにこれを繰り返します。unordered_map のストレージの要素オーバーヘッドを無視している場合、これは正しい方法ですか?

また、私が正しければ、 map.bucket_count() は、事前に割り当てられたものを含め、現在割り当てられているバケットの数を示します。事前に割り当てられたバケットを無視する代わりに map.size() を使用する必要がありますか?

それとも、これらすべての代わりに、MemTrack などのツールを使用して使用メモリを見つけるほうがよいのでしょうか?

次のユーザー構造体があるとします。

そして、ユーザーレコードのコレクションを保存する必要があります（約10 ^ 5ユーザー、さらに大きく拡張できます）。unordered_setまたはunordered_mapとして保存すると、パフォーマンスが向上しますか？Unordered_setは技術的にはHashSetと同じであり、unordered_mapはHashMapと同じですよね？要素の数が増えると挿入と削除が非常に遅くなるため、通常のセット（順序付き）を使用することはできません。

また

挿入、削除、およびuserIdによる特定のユーザーオブジェクトへのアクセスに関して、非常に高速である必要があります。

unordered_map<float, unsigned short>C++ でハッシュ テーブルを実装するために を使用しています。

フロートをハッシュ テーブルのキーとして使用することは、ほとんどの状況で悪い考えであることはわかっています。それらを比較するとエラーが発生しやすくなるからです。ただし、このような状況では、大きなファイルから float を読み込んでおり、その精度は既知で一定です。

unordered_mapただし、衝突の頻度を推定するためにフロートをハッシュする方法の詳細を知りたいです。を作成するときに、デフォルトのハッシュ実装をオーバーライドしていませんunordered_map。ドキュメントによると、デフォルトのハッシュ関数はstd::hash<Key>. 私の場合はどれですかstd::hash<float>。しかし、ドキュメントを見ると、 「 、、、および組み込み整数型のstd::hashテンプレート引数」に対してのみ定義されています。char*const char*cropewrope

値をunordered_mapに追加するときに、値をハッシュするためにどの関数が呼び出されているか知っている人はいますか?

unordered_map- http://msdn.microsoft.com/en-us/library/bb982522.aspx

std::hash- http://www.sgi.com/tech/stl/hash.html#1

現在、C++ に Boost を使用しており、CRC32 を使用して順序付けされていないマップ (別名ハッシュ テーブル) を実装しようとしています。私の知る限りでは、文字列を初期キーとして取得し、それをハッシュして、バケットの数に収まるように別の操作を適用します。

私の状況では、事前に文字列キーをハッシュし (Boost で別の CRC 関数を使用)、その ID を使用してテーブルのインデックスを作成したいと考えています。私が助けを必要としている問題は、CRC32 ハッシュには 2^32 の潜在的な値があり、2^32 の要素を持つテーブルが必要になるとは思えないことです。この状況で私は何をすべきですか？

ここで助けてくれてありがとう！

基本的に、私はunordered_mapを持っていて、それにペアのセットを追加しようとしています...それらの約500,000。ペアを追加すると、挿入速度がだんだん遅くなり、最終的にすべて一緒に停止することに気づきました。なぜこれが起こるのか、またはこれを修正する方法について何か考えはありますか？

マップの定義：

ハッシュ関数-私の場合、pair.first == pair.secondについて心配する必要がないことに注意してください。したがって、このハッシュ関数で十分だと思います。間違っている場合は修正してください。

unordered_mapに値を追加する方法...約200,000〜500,000ペアを追加しようとしています：

編集：私は実際に50,000,000ペア近くを追加しています...ちょうどテストを実行しました...

EDIT2：

フリーズする前の出力例。ここで、countはマップ内のエントリの数です。マップを再ハッシュしようとしていると思いますが、なぜそれが失敗してコンピューターがフリーズするのかわかりません。

チェックパーティクル：87500カウント：35430415負荷率：0.988477

チェックパーティクル：87600カウント：35470808負荷率：0.989652

チェックパーティクル：87700カウント：35511049負荷率：0.990818

チェックパーティクル：87800カウント：35555974負荷率：0.992073

チェックパーティクル：87900カウント：35595646負荷率：0.993163

チェックパーティクル：88000カウント：35642165負荷率：0.994427

チェックパーティクル：88100カウント：35679608負荷率：0.995434

チェックパーティクル：88200カウント：35721223負荷率：0.996563

チェックパーティクル：88300カウント：35760313負荷率：0.997616

チェックパーティクル：88400カウント：35799621負荷率：0.9987

チェックパーティクル：88500カウント：35833445負荷率：0.999649

私はこのコードを書きます：

実行時に、行でエラーが発生します

test3.exeの0x00411eddで未処理の例外：0xC0000005：アクセス違反の読み取り場所0x00000004。 "

Visual StudioExpress2008とBoost1_47_0を使用しています。

これは私の完全なコードです：

をキーとする C++ の順序付きおよび順序なしの連想コンテナーを考えてみましょうdouble。

NaN有効なキー タイプですか?

順序付けられたコンテナーでは、厳密な弱い順序付けが尊重されないため、「いいえ」と言う必要があります。

順序付けられていないコンテナでは、わかりません。

GCC 4.6.2 では次のようになります。

順序付けされたマップについては、次のようになります。

順序付けられていないマップの場合、次のようになります。

したがって、順序付けされたマップでは、すべての NaN が同じように扱われます。これは私が予想することですが、NaN は要件に違反しているように見えました。ただし、順序付けされていないマップの場合、要素を再度取得することはできず、すべての NaN が異なります。これも私が期待するものではありません。

規格はこの問題について何か言う必要がありますか?

更新:以下の優れた回答のおかげで、 NaN が含まれているときに何か他std::mapのものを挿入すると壊れることに注意してください。

(他の言語が連想コンテナー内の浮動小数点キーをどのように処理するかについて、コメントをいただければ幸いです。)

stl unordered_mapを使用していますが、countメソッドを機能させることができないようです。これは私のプログラムです：

unordered_mapのドキュメントにはunordered_map::count(const Key& k)、キーを持つ要素の数が返されると記載されていますk。したがって、ここでの出力はであると予想しますが3、実際の出力は1です。なんで？

でユーザー定義のキータイプをサポートstd::unordered_set<Key>するには、ハッシュファンクターstd::unordered_map<Key, Value> を提供する必要があります。operator==(Key, Key)

コンパイラやライブラリに付属している型のように、型のデフォルトのハッシュstd::unordered_set<X>だけ を使用して記述する方が便利です。相談後X

• C++標準ドラフトN3242§20.8.12 [unord.hash]および§17.6.3.4[hash.requirements]、
• Boost.Unordered
• g ++include\c++\4.7.0\bits\functional_hash.h
• VC10include\xfunctional
• StackOverflowのさまざまな関連質問

専門化することは可能のようですstd::hash<X>::operator()：

C ++ 11のコンパイラサポートはまだ実験的です---私はClangを試しませんでした---、これらは私の質問です：

1. そのような特殊化を名前空間に追加することは合法stdですか？私はそれについて複雑な気持ちを持っています。

2. std::hash<X>::operator()C ++ 11標準に準拠しているバージョンはどれですか？

3. それを行うためのポータブルな方法はありますか？