問題タブ [unordered-map]

次のような文字列でインデックス付けされた unordered_sets の順序付けられていないマップがある場合

このデータ構造の使用についていくつか質問がありました。セットへのポインターを使用したり、マップ値のインデックスを再作成したりすることなく、マップでインデックス付けされたセットに新しい値を挿入する方法はありますか?

2 番目の質問です。マップにインデックスを作成しようとすると、未解決の外部シンボル エラーが発生します。例として、

これが未解決のシンボルエラーを引き起こしている理由がわからないので、そこにあるガイダンスが役に立ちます.

前もって感謝します

編集: UseMap[character] を使用すると、未解決のシンボルエラーが発生します

エラーコードとソース例も追加

フルクラス

そして完全なエラーメッセージ:

エラー 52 エラー LNK2001: 未解決の外部シンボル "private: static class boost::unordered_map,class std::allocator >,class boost::unordered_set,class std::allocator >,struct boost::hash,class std::allocator > >,struct std::equal_to,class std::allocator > >,class std::allocator,class std::allocator > > >,struct boost::hash,class std::allocator > >,struct std::equal_to ,class std::allocator > >,class std::allocator,class std::allocator > const ,class boost::unordered_set,class std::allocator >,struct boost::hash,class std::allocator > >, struct std::equal_to,class std::allocator > >,class std::allocator,class std::allocator > > > > > > SingleUse::UseMap"(?UseMap@SingleUse@@0V?$unordered_map@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V?$unordered_set@V?$basic_string@ DU?$char_traits@D@std@@V?$allocator@D@2@@std@@U?$hash@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@ 2@@std@@@boost@@U?$equal_to@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@2@V?$allocator @V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@2@@boost@@U?$hash@V?$basic_string@DU?$char_traits @D@std@@V?$allocator@D@2@@std@@@4@U?$equal_to@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2 @@std@@@2@V?$allocator@U?$pair@$$CBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V? $unordered_set@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@U?$hash@V?$basic_string@DU?$char_traits@D@std@ @V?$allocator@D@2@@std@@@boost@@U?$equal_to@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@2@V?$allocator@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std @@@2@@boost@@@std@@@2@@boost@@A) G:\Documents\Programming Projects\KHMP\KHMP_Repo\KHMP\build\KHMP\KHMP\KHMPMain.obj

std::unordered_map大量のデータを保存するためにfromgnu+50xを使用しています。使用するスペースの合計を制限できるため、多数の要素にスペースを事前に割り当てたいと思います。

私がしたいのは電話です：

ここで、xは既知です。

std::unordered_mapこれをサポートしていません。std::unordered_map最終的には標準の一部になるので、可能であれば使用したいと思います。

その他の制約：

マップの信頼できるO（1）アクセスと変更が必要です。必要なハッシュ関数と比較関数はすでに非標準であり、いくらか高価です。O（log n）ミューテーション（と同様std::map）はコストがかかりすぎます。

->高価なハッシュと比較も、償却ベースの成長を非常に高価にします。追加の挿入ごとに、これらの関数からのO（n）演算が必要になります。これにより、指数関数的なストレージ要件にはO（n）の増加が必要になるため、アルゴリズムの実行時間に2次項が追加されます。

unordered_map次のように含まれる を 使用して#include <unordered_map> います。プログラムは次のようにコンパイルされます g++ Test.cc -std=gnu++0x -o test 。TR1 の を使用していますunordered_mapか、C++0x の を使用していますか。それともどちらも同じですか？

そのように宣言された std::set 値で unordered_map に挿入しようとしています:

データベースコンストラクターで、ファイルからデータを読み取り、unordered_map に挿入しようとしています

そして、両方でコードをコンパイルしようとしました:

と

しかし、エラーが発生しています：

また、さまざまな挿入方法を試しました。

と

同様のエラーが発生するだけです

なぜそれが機能しないのか、そしてこれを機能させるために何ができるのかを誰かが理解するのを手伝ってくれれば、とても感謝しています。

ありがとうございました。

私は現在、画像処理アルゴリズムを書いていますが、ある時点で、変換されたピクセルに関する統計情報を収集して、さらなる開発で従うべき方向についての洞察を得る必要がありました。収集する必要のある情報の種類は、次の形式でした。

私がしたことは、変換された画像を開いて反復処理し、必要な値を保存しstd::unordered_mapて、次の署名を付けることでした。

ループ内:

また、カスタム ハッシュ関数も作成します (これは完璧なハッシュ関数でした: 256^2 x R + 256 x G + B- したがって、バケットとハッシュテーブルのレイアウトに関係なく (妥当な範囲で) 衝突は最小限に抑えられるはずです)。

私が気づいたのは、挿入が悲惨なほど遅いということでした! - 11 回目以降、挿入速度が約 100 倍に低下しました。大量の衝突がありました！画像内の複製された色の数は非常に少ないにもかかわらず。

その後、コード内で発生する可能性のある障害を排除したいと考え、unordered_mapint などのプリミティブ キー型で STL ハッシュ関数を使用してベンチマークを開始しました。

ベンチマークのコードは次のとおりです。

... そして、これが外側のループの最初の 20 回の反復の結果です (int 型のキーには STL のハッシュ関数のみを使用):

この場合、衝突の数が多すぎませんか? STL ライブラリは一般的に高品質ですが、単純な int ベースのキー サウンドには 639/640 と 640/1280 が少なくとも奇妙に聞こえます。それとも、私は何か間違ったことをしていますか？

そして、これは私のハッシュ関数でした（理論的には、衝突はまったくないはずですが、数値は非常に近かったです）：

こ、これはもうおかしくない…

私はこのハッシュ関数を書きました：

理論的には、衝突率は 100% になるはずですよね? しかし、結果は次のとおりです。

なんで？

環境: MSVS2010

unordered_mapキーで並べ替えるにはどうすればよいですか？unordered_mapキーでソートして印刷する必要があります。

私は勉強していて、それを理解することはできません。コンパイラは、型unordered_mapが宣言されていないというエラーをスローします。

Visual C++ 2008 Express Edition を使用しています。

私はこれらの C++ ライブラリの多くに慣れていないので、私の質問が素朴であると感じた場合はご容赦ください。

それぞれ約 160 MB (それぞれ約 700000 行) の 2 つの大きなテキスト ファイルがあります。file1 に表示されるすべての重複行を file2 から削除する必要があります。これを実現するために、32 文字の文字列をキーとして unordered_map を使用することにしました。32 文字の文字列は、各行の最初の 32 文字です (これは行を一意に識別するのに十分です)。

とにかく、基本的には最初のファイルを調べて、各行の 32 文字の部分文字列を unordered_map にプッシュするだけです。次に、2 番目のファイルを調べて、file2 の行が unordered_map に存在するかどうかを確認します。存在しない場合は、行全体を新しいテキスト ファイルに書き込みます。

これは、小さなファイル (それぞれ 40 MB) では問題なく機能しますが、この 160 MB のファイルでは、ハッシュテーブルに挿入するのに非常に時間がかかります (file2 を見始める前に)。約 260,000 回の挿入で..停止したか、非常に遅くなったようです。メモリの限界に達した可能性はありますか? もしそうなら、誰かがこれを計算する方法を説明できますか? そうでない場合、それを高速化するために他にできることはありますか? カスタムハッシュ関数を選択したり、最適化に役立ついくつかのパラメータを指定したりしますか?

ハッシュ テーブルへのキー オブジェクト ペアは (string, int) で、文字列の長さは常に 32 文字で、int は重複を処理するために使用するカウントです。12 GB RAM を搭載した 64 ビット Windows 7 OS を実行しています。

どんな助けでも大歓迎です..みんなありがとう!!

unordered_map のカスタム アロケータに関していくつか問題があります。大規模なデータセットがあり、文字列をキーとしてハッシュする必要があります。そのため、カスタム メモリ アロケータを提供すると速度が最適化されることがわかりました。しかし、どうすればそれを行うことができますか？（SOを確認しましたが、カスタムハッシュ関数などに関連するものはいくつかありますが、カスタムアロケーターの使用に関するものは何も見つかりませんでした）

unordered_map::size() は何を返しますか? それは、最長の制御されたシーケンスだと言います。私はそれが何を意味するのか混乱しました。それはバケット自体の数ですか、それとも何か他のものですか?

どうもありがとう