問題タブ [unordered-set]

Windowsコードをクロスプラットフォームビューに書き直す必要があります。次に例を示します。

すべてのコードに_Ptrイテレータのメンバーがありますが、ドキュメントで見つけることができません。Visual Studio（stlの実装）で動作すると思います。それを置き換える方法はありますか？そして、何_Myvalですか？

UPD：

そして行のエラーit->aabb：

エラー：'* it.std :: __ detail :: _ Hashtable_iterator <_Value、__constant_iterators、__cache> :: operator-> with _Value = qdt :: QuadTreeOccupant *、bool __constant_iterators = true、bool _cache=のメンバー'aabb'のリクエストfalse、std :: _detail :: _ Hashtable_iterator <_Value、__constant_iterators、__cache> :: pointer = qdt :: QuadTreeOccupant * const *'、これは非クラスタイプ' qdt :: QuadTreeOccupant * const'</ p>

言い換えると、2つunordered_map、またはunordered_set、まったく同じコンテンツと同じハッシュ関数でオブジェクトを埋めた場合、それらを反復処理すると、キーと値のペアの同じシーケンスが得られますか？

もしそうなら、これが成り立つための条件は何ですか（例えば、同じハッシュ関数、同じキー、必ずしも同じ値ではありません）。

rehashこれは、順序付けられていない連想コンテナー内の関数の事後条件として標準で見つかりました。

投稿: a.bucket_count() > a.size() / a.max_load_factor()およびa.bucket_count() >= n. (n はコンテナー内のバケットの数です)

上記の条件のいずれかがすべての実装で満たされたときに、自動再ハッシュがトリガーされることを意味するために上記を使用できますか? または、実装はいつ再ハッシュするかを自由に決定でき、上記はrehash関数のみに関係しますか?

ここで my_type が満たさなければならない要件はどれですか? (std::hash の特殊化に加えて)

2 つの が与えられた場合std::set、単純に両方のセットを同時に反復処理して要素を比較することができ、線形の複雑さが得られます。std::unordered_set要素は任意の順序で格納される可能性があるため、これは s では機能しません。では、どのくらいの費用がかかりa == bますstd::unordered_setか?

unordered_set から「要素を 1 つ削除」する機能が欲しいです。

ただし、erase(begin()) を使用して実装すると、非常に遅くなります。(これは g++-4.5.3 にあります。begin() はより多くの空のハッシュ バケットをトラバースする必要があるのでしょうか?)

驚くべきタイミングで以下のサンプル コードを参照してください。

より効率的な「1つの要素を削除する」を実装する他の方法はありますか? (イテレータを無効にする他の介入セット操作を許可したい。)

アプリケーションのブーストと標準の unordered_set を使用しようとしています。目的は、場所、つまりこのセット内の特定の要素のインデックスを見つけることです。結果には微妙な違いがあります。この簡単なプログラムに従って、boost の要素が反転されます。問題はどこだ？

シンプルな「what-if」コード:

ブーストで私は得る

そして、標準の unordered_set を使用すると、取得しています

私は両方をコンパイルします

かなり大規模なプロジェクトでは unordered_set を使用する必要があり、それを正しく使用していることを確認するために、小さな例を試してみました。

コンパイルすると、次のようになります。

私のハッシュ関数が表示されていないようですが、「ハッシュ」がデフォルトの関数名だと思いました。ハッシュを正しく定義しましたか? それとも、別のハッシュ クラスを 2 番目のテンプレート引数として明示的に宣言する必要がありますか?

どうやら、厳密にブール値ではないものunordered_set::eraseをunordered_set::count返します（論理的には、実際の型については話していません）。

リンクされたページは、消去の3番目のバージョンを読み取ります。

キー値キーを持つ要素を削除します

これには、特定のキーを持つ要素が複数存在する可能性があることを示唆するトーンがあります。これについては明確に述べていませんが、多くのように聞こえます。
さて、セットのポイントは、順序付けられていないものであっても、各要素を1回持つことです。

標準ライブラリはbool型の存在を認識し、それをのようなブール値に使用しますunordered_set::empty()。それで、上記の場合に戻ることのポイントは何size_typeですか？ハッシュの衝突にもかかわらず、コンテナは異なるキーを持つ要素を区別する必要がありますよね？それでも信頼できますか？

一般的な文字列を格納して検索できる必要があります。文字列の内容についてはよくわかりません.2/3より少し多いのは人間の言葉で、残りはUUIDまたは数字/文字の組み合わせに近いものです. 特定のグループ化は一定であることを知っています（つまり、人間の言葉が含まれている場合はすべて人間の言葉になり、UUID が含まれている場合はすべてのコンテンツが UUID になります）。

最高の平均検索率を得るために、このデータをマップまたはハッシュマップのどちらに配置するかを決定する必要があります。入力形式についてほとんど知らない場合、文字列の適切で効率的なハッシュを作成できるとは思わないため、O(log n) ランタイムでマップすると言う傾向があります。どちらが良いかについての考えはありますか？

編集：重要な側面を1つ忘れていました。文字列の長さがわからないので、長い文字列ではメモリ使用量が大きくなりすぎるのではないかと心配しています。ハッシュ方式を使用した場合、X 文字の後にハッシュが文字単位でハッシュされないような処理を行って、メモリの消費量が膨大になるのを回避します。

私が本当に欲しいのは、バケットの（ログN）検索を提供できるように、順序付けられた方法でソートされた「バケット」に複数の値を保持するハッシュマップの実装です。しかし、それはstardrd C++には存在しないと思いますし、ゼロから書く価値はありません。

pps。データはほぼ静的です。たまにリストに追加する必要がありますが、それはまれであり、書き込み時間が遅いことを喜んで受け入れます。私は検索時間だけを気にします。