問題タブ [unordered-map]

unoreded_map サポートが gcc に追加されたのはいつですか?

RHEL 5.3 に同梱されている gcc 4.1.1 を使用しています。unoreded_map が欠落しているようです。手動で追加する方法はありますか？

皆さん、問題を解決するために動的計画法のアプローチを使用しています。アプローチの簡単な概要は次のとおりです。

1. 生成された各値は、25 個の一意のキーを使用して識別されます。
2. これらの 25 個のキーを使用して、boost::hash_combineを使用してハッシュ テーブルのシードを生成します。

3. として宣言されたハッシュテーブルに値を保存します

   boost::unordered_map<Key_Object, Data_Object, HashFunction> hashState;

4. アルゴリズムの時間プロファイリングを行ったところ、実行時間のほぼ95%がデータの取得/ハッシュ テーブルへの挿入に費やされていることがわかりました。

5. これらは私のハッシュテーブルの詳細でした

   hashState.size() 1880

   hashState.load_factor() 0.610588

   hashState.bucket_count() 3079

   hashState.max_size() 805306456

   hashState.max_load_factor() 1

   hashState.max_bucket_count() 805306457

次の2つの質問があります

1. ハッシュ テーブルの挿入/取得操作のパフォーマンスを向上させるためにできることはありますか?

2. C++ STL には、私の要件にも合う hash_multimap があります。ライブラリunordered_mapは、挿入/取得のパフォーマンスに関してhash_multimapとどのように比較されますか。

ドキュメントによると、aboost::thread::idは実行中のスレッドごとに一意であると見なすことができ、std::setandなどのコンテナで使用できますstd::map（<演算子はでオーバーライドされるためthread::id）。

thread::id私の問題は、のキーとして使用したいのですboost::unordered_mapが、キーが「ハッシュ可能」である必要があります（つまり、へのハッシュをサポートしているsize_t）。thread :: idの実装の詳細はすべて非表示になっているため、使用できるものはないと思います。

だから私の質問は-unordered_mapへのキーとしてthread::idを使用することは可能ですか？

「unordered_map」という名前に非常に混乱しています。名前は、キーがまったく順序付けられていないことを示唆しています。しかし、私はいつもハッシュ値で並べられていると思っていました。それとも間違っていますか (名前が順序付けられていないことを意味するため)?

または別の言い方をすると、これですか

と

と同じ

? （OK、正確ではありません。キー k1、k2 があり、k1 < k2 でも k2 < k1 でもない可能性があるため、STL はここで文句を言います。equal multimap-check を使用して上書きする必要があります。）

または、別の方法で: それらを反復するとき、キーリストがハッシュ値で順序付けられていると想定できますか?

プロジェクト euler の 14 番目の問題に関する投稿を書いているときに、VC9 と VC10 の動作の違いに遭遇しました。

次のコードは、VC9 では正常に実行されますが、VC10 では例外std::unordered_mapがスローされbad_allocます。奇妙なことは、例外から回復すると、将来の割り当てが成功することです (コンテナーのサイズは大きくなり続けます)。また、使用するboost::unordered_mapと、両方のコンパイラで正常に動作します。

実際のメモリ使用量に関しては、4GB RAM (使用中は 1.7) のマシンで実行しています。VC9 バージョンはタスクを完了する前に最大 810MB のメモリを取得し、VC10 バージョンは最大 658MB でクラッシュします。

これは VC10 のバグですか? 私は同じマシンで実行していますが、実行される作業量が同じである場合に、一方のバージョンでは一貫してメモリが不足し、もう一方のバージョンではメモリが不足する原因となるものは他にありますか?

_<編集>
いくつかの詳細情報:例外が最初に発生するのは、スタックの深さ 1 で 7,718,688 を計算するときです (メインから長さだけの再帰はありません)。その後、キャッシュに追加される番号ごとに発生するようです。キャッシュには、例外が発生する前に 16,777,217 個の要素が含まれていました (によるとcache.size())。興味深いのは、insert失敗した場合でもキャッシュ サイズが 1 ずつ大きくなるため、強力な例外保証を提供していないように見えることです (§23.2.1.11 に違反しています)。
_</編集>

コードは次のとおりです。

_<編集>
また、誰でもこの動作を再現できます。一度は消えた (そして再び現れた) ため、私の構成には何か特別なものがあるかもしれません。
_</編集>

テンプレート化された静的クラスを使用してリソース (画像、フォント、メッシュ データなど) の管理を処理するコードがいくつかあり、クライアント コードは次のようなことを実行できます。

「リソースタイプ」には、const std::string&.

getResource次のように実装されています。

table_tと定義されているtypedef typename boost::unordered_map< std::string, boost::shared_ptr<ResourceType> > table_t;

_resourcesタイプtable_tです。

問題は、（から発信された）boost::unordered_mapへの呼び出しでセグメンテーション違反が発生することです。ただし、代わりに、挿入操作 ( から発生) またはへの呼び出し(から発生) でsegfault を取得します。findfind_iteratorstd::map_Rb_tree_decrementfindstring::compare

この問題は、リソースが2回要求されたときにのみ発生します (失敗が発生した場合、fileName は有効です)。

これは両方で起こっているmapのでunordered_map、これを引き起こすにはどこかで奇妙なことをしているに違いないと思います。何かアイデアはありますか?

ありがとう。

編集：まだ問題がありますが、リソースが2回目にリクエストされたときにのみ発生するというのは間違っていました。ただし、リソースを取得するための最初の 2 つの呼び出しは成功し、セグメンテーション違反を引き起こしているのは 3 番目の呼び出しです (各呼び出しは別のリソースに対するものです)。

スタック トレースは次のとおりです。

unordered_list のキーとして string* を使用したいと思います。ポインター自体のハッシュは必要ありませんが、ポインターが指す文字列は必要です。

次のような構造体を作成する必要があることを理解しています。

それをハッシャーとしてマップテンプレートに送信しますが、方法がわかりません。

私はまだ、One-Of-A-Type コンテナーの問題に対する適切な解決策に取り組んでいますstd::map<std::type_info, boost::any>。残念ながら、std::type_infoは を定義していません。定義するのはoperator<不合理だと思います。

std::type_infoただし、オブジェクトのシングルトン アドレスを妥当な "ハッシュ" として単純に使用できるため、ハッシュ関数を定義することは合理的と思われます。std::type_infoしたがって、 astd::unordered_mapをキーとしてa に入れることができます。

C++11 はそのようなハッシュ関数を提供しますか? シングルトンのメモリアドレスを使用するstd::type_infoことは、ハッシュ戦略として不適切でしょうか?

Boost を使用した C++ プログラムで、キーが double のタプルである順序付けられていないマップを作成しようとしています。

マップの初期化は正常に完了しますが、キーと値を入力しようとすると、

次のエラー メッセージが表示されます。

これは、タプル キーのハッシュ関数を指定する必要があるためだと思います。どうやってやるの？

編集：

以下の提案に従って、次の実装を作成しました。

短くすることは可能ですか？

ハッシュテーブルから単一の値を格納および取得するには、複数のキー（int型）を使用する必要があります。複数のキーを使用して、単一のアイテムにインデックスを付けます。高速挿入が必要で、ハッシュテーブルを検索します。ちなみに、実装でBoostライブラリを使用することは許可されていません。

どうすればそれができますか？