問題タブ [unordered-set]

私は後押しするのが初めてです。boost::unorder_set を実装しようとしています。コードは次のとおりです。

次のエラーが表示されます。

実装の何が問題になっていますか? 事前にサンクス。

順序付けられていないセットがどのように機能するかを誰か説明できますか? セットの仕組みもよくわかりません。私の主な質問は、検索機能の効率です。

たとえば、これのビッグ O 実行時間の合計は?

ブーストの unordered_set を使用するコードがあります

unix の下で gcc を使用してコンパイルし、正常に動作します。mingw32 (gmake 3.8.1) でクロスコンパイルしようとすると、次のメッセージが表示されます。

私には、テンプレート関連の問題のように思えます。助言がありますか？

ありがとう、マティア

[編集]

レキシカルキャストなど、他のブースト機能が利用可能です

次のコードを検討してください

問題は、なぜ s2 のサイズが 1 ではなく 2 なのかということです。ハッシュ関数と関係があるに違いないと確信しています。ブーストドキュメントを見て、ハッシュ関数をいじってみましたが、うまくいきませんでした。

アイデア？

非常に長いリストをディスクから unordered_set にロードしています。文字列のセットを使用すると、非常に高速です。約 7 MB のテスト リストが約 1 秒でロードされます。ただし、一連の char ポインターを使用すると、約 2.1 分かかります。

文字列バージョンのコードは次のとおりです。

char* バージョンのコードは次のとおりです。

「new(mem)」は、カスタム メモリ マネージャーを使用しているため、大きなメモリ ブロックを割り当てて、C 文字列などの小さなオブジェクトに割り当てることができます。ただし、これを通常の「新規」でテストしたところ、結果は同じでした。また、メモリマネージャーを他のツールで問題なく使用しました。

アドレスではなく実際の c 文字列に基づいて挿入および検索ハッシュを作成するには、2 つの構造体が必要です。unordered_deref は、スタック オーバーフローで実際にここで見つけました。

最終的には、数ギガバイトのファイルをロードする必要があります。これが、私がカスタム メモリ マネージャーを使用している理由ですが、この恐ろしい速度低下が受け入れられない理由でもあります。何か案は？

とは

環境：Visual Studio 2010 Professional

TL; DR

今日は使い方を探していましたstd::tr1::unordered_set。前回の使い方std::mapを聞いたので、自分で調べてみることにしました。

私はグーグルで検索しましたが、ほとんどの結果から、ハッシュを実行するための構造体があることがわかりました。道は少し複雑に見えたので、探し続けて、ようやく別のアプローチに出くわしました。

実装する必要があります

と

結果のコードは質問の終わり近くにあります。

==問題なくおなじみです。size_tおなじみです。しかし、何operator size_tですか？

equals効果的hashCodeなJavaに従って一緒にオーバーライドする必要があるJavaのようです。しかし、特に名前が。の場合はわかりませんsize_t。

結果のコードは次のとおりです。完全なプログラムは正常に動作し、正しい出力を生成します。

もうちょっと：

いいえ

コンパイルできません：

でもない

しかし、私が見ているように、関数はを返しますint。エラーコードは次のとおりです。

std::unordered_map<tuple<int, int>, string>箱から出してすぐに動作しないのはなぜですか? のハッシュ関数を定義しなければならないのは面倒ですtuple<int, int>。

タプルをキーとして順序付けされていないマップを構築する(Matthieu M.) は、これを自動化する方法を示していますboost::tuple。可変個引数テンプレートを使用せずに c++0x タプルに対してこれを行う方法はありますか?

確かにこれは標準にあるはずです:(

を使用したいのですがboost::unordered_map<key,value>、keyはstd::set<int>です。整数のセットは組み込み型ではないため、独自のハッシュ関数を提供する必要があると想定しました（つまり、boostのhash_rangeを使用することを考えていました）。

しかし、今私はこのようなハッシュマップを初期化しようとしましたが、ハッシュ関数も等式述語も提供していませんでした-そしてgccは文句を言いませんでした。ここで何が起きてるの？Boostは、STLコンテナをすべて単独でハッシュするのに十分賢いですか？これは、カスタムハッシュ関数を使用した場合よりも遅くなりますか？使用するのはboost::hash_rangeどうですか？

前もって感謝します。

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

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

また

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

次のような unordered_set があります。

次に、その unordered_set 内の要素の約 85% を消去する別の関数を実行しました。(消去される要素は、この関数のロジックに依存しますが、すべての要素が最初に順番に挿入されたので問題ではありません)。

unordered_set のいくつかの要素を消去した後、その unordered_set にまだ残っている最後の要素を出力したいと思います。たとえば、要素 9997、9998、9999、および 10000 が消去されているため、このセットに残っている最大の要素は 9996 です。これを行う方法は?
基本セットを使用する場合、次のことができます。

セットにはreverse_iteratorとrbegin()がありますが、これはunordered_setには存在しません。基本セットを作成しなかった理由は、要素サイズを 10^8 まで拡大する必要があるためです。通常のセット (赤黒木に基づく) を使用すると、実際にパフォーマンスが低下します (特に、挿入と削除を扱う場合)。これどうやってするの？最終的に残った unordered_set をベクターにコピーすることはできますが、もちろん時間がかかります。よりスマートな方法を使用してこれを達成するにはどうすればよいですか? 次のようなこともできないことに気付きました：