問題タブ [unordered-set]

プレーンな (ツリーベースの) STL に対するアクセスを高速化するために、名前空間のunordered_setクラスを使用し始めました。しかし、boost() にスレッド ID への参照を格納したかったのですが、これらの識別子の API が非常に不透明であるため、そのハッシュを明確に取得できないことに気付きました。tr1mapboost::thread::id

驚くべきことに、boost はtr1(hashおよびを含むunordered_set) の一部を実装していますが、スレッド ID をハッシュできるハッシュ クラスを定義していません。

のドキュメントを見ると、boost::thread::idスレッド ID をストリームに出力できることがわかったので、ハッシュを行うための私の解決策は次のようなものでした。

つまり、シリアル化し、結果の文字列にハッシュを適用します。ただし、これは実際に STL を使用するよりも効率が悪いようmap<boost::thread::id>です。

だから、私の質問：これを行うためのより良い方法を見つけますか？hash<boost::thread::id>クラスの存在を強制しないのは、boost と tr1 の両方で明らかな矛盾ですか?

ありがとう。

残念ながら、私は自分で開発したプログラムに完全に取り組んでいません。最近、unordered_setへのポインターの単純な挿入から呼び出されたunordered_setの演算子でVisualStudioの致命的なエラーに気づきました。ローカルを確認した後、セットには2つの要素しかなく、最後の要素がNULLであることに気付きました（したがって、それがクラッシュしたと思います）。ここで質問に移ります。unordered_set（または他のSTLコンテナ）がその要素の1つとしてNULLポインタを（理論的に）取得するにはどうすればよいですか。プログラムはマルチスレッドですが、私のレビューによると、コードのその部分には1つのスレッドからのみアクセスする必要があります。ありがとう。

興味のある人のためにスタックとソースコードの一部を呼び出します： http：//privatepaste.com/c8e7f35a4e（PushToProcessedはオブジェクト自体から呼び出され、それ自体への参照を渡すため、NULLにすることはできません）

std::unordered_set を検索するにはどうすればよいですか? ハッシュ値を知り、述語オブジェクトを持っていますか? pred(x) && pred(y)(意味によって同等性を決定する述語x == y。)

boost::split の最初のパラメータとして boost::unordered_set を渡すことがコーシャかどうかは誰にもわかりませんか? libboost1.42-dev では、これにより問題が発生するようです。問題を引き起こす小さなサンプル プログラムを次に示します。test-split.cc と呼びます。

次に、次のコマンドを実行すると:

次のような valgrind で多くの苦情を受け取ります (タイミングによって異なるようですが、valgrind なしでコアダンプが表示されることもあります)。

これは Debian Squeeze ボックスです。関連するシステム情報は次のとおりです。

ただし、libboost1.42-dev を libboost1.40-dev にダウングレードすると、コードは正常に動作するようです。これはboost 1.42のバグですか、それともシーケンスを処理できないコンテナを渡すことでboost::splitを誤用していますか? ありがとう！

これはばかげた質問かもしれませんが、次のようになります。

単語の辞書を unordered_set ベースのハッシュ テーブルにハッシュしました。私のハッシュ関数は、同じ文字セットを含むすべての文字列が同じ値にハッシュされるという点で、意図的に「悪い」ものにされました。私は当初、通常のハッシュ関数の動作をオーバーライドし、各単語の文字の「頻度ヒストグラム」をハッシュ値として使用しようとしました (これは不可能だとわかりました :) ) が、スレッドの 1 つが 26-同じことを達成するためのビットビットマスク。これまでのところ、ハッシュ関数は問題なく動作します。

たとえば、私のスキームでは、CITIED と CITED は同じ値 1049144 にハッシュされます。私のアイデアは、文字セットが与えられた場合、そのセットの文字を含むすべての単語を見つけたいというものでした。

私が遭遇した動作を完全に説明できないため、ハッシュの概念を完全に理解していない (またはコードが明らかに間違っている) と推測しています:
文字列の文字で構成されるすべての単語を探すことにしました。 LIVEN」。私の出力（ハッシュキー付き）は次のとおりです：

CURTSEYED は一体どうやってそこに上陸したのですか? ご覧のとおり、残りの 3 つの単語とは異なるハッシュ値を持っています。ハッシュテーブルの理解/実装のどこに問題がありますか?

上記の出力を生成するコード:

My hash function :

Comparison function :

.Net HashSet のように機能するデータ構造を使用したいので、次のようにデフォルトのハッシュ メソッドとカスタム比較子で unordered_set を使用しようとしました。

問題は、HashtSet を使用して (メソッドを使用して) 特定のキーを見つけようとしたときに、それを使用して追加したfindばかりです。insertHashSet::end()

何が問題なのか説明していただけますか？VS2010でVC++を使用しています

unordered_setのコンストラクターを見てきました。ハッシュバケットの数を設定せずに、カスタムアロケータインスタンスを使用してunordered_setを構築することはできませんか？カスタムアロケータが必要であり、型にはデフォルト値の定義がないため、実装の詳細をいじりたくありません。MSDNは、コンストラクターに対して3つのオーバーロードしか提供しませんが、どれもひどく有用ではありません。

編集：聖なるがらくた。std :: hashの私のSTL実装は、カスタムアロケータタイプの文字列に特化していません-明示的なtypedefs std::stringとstd::wstringのみを実行できます。つまり、ランダムな文字列をハッシュしようとしたくないのは理解できますが、カスタムアロケータがあるからですか？これは私をうんざりさせます。

問題を解決しますが、冗長な構造とコピーですか？Ewwwww。

unordered_setプロジェクトで使用したいのですが。

ただし、そのドキュメントは不完全であるか、単なる技術的なリファレンスであり、例はありません。

誰かがそれを扱うオンラインリソースへのリンクを提供できますか？本も歓迎します、できれば無料です。グーグル検索は何の価値も返しませんでした。

ありがとう！

この質問はこれに関連して おり、より正確にはこの質問に対する回答に関連しています。

ここに行きます：私はunsignedintsのC++ / TR1 unordered_setを持ってUいます（大まかなカーディナリティ100-50000、大まかな値の範囲0から10 ^ 6）。カーディナリティを考えると、ランダムであるが一意ののメンバーをNできるだけ早く反復したいと思います。の一般的な値はありませんが、小さい場合は高速に動作するはずです。NUNN

より詳細には、ここでの「ランダム性」の概念は、2つの呼び出しが多少異なるサブセットを生成する必要があるということです。異なるほど良いですが、これはそれほど重要ではありません。たとえば、ブロックの開始インデックスがランダムである限り、のNメンバーの連続（またはラップアラウンド連続）ブロックに満足します。U同じコストで非連続的である方が良いですが、主な関心事は速度です。U穏やかに変化しますが、呼び出し間で常に変化します（呼び出し間で挿入/消去される要素は約0〜10個）。

私がどこまで来たか：

1. 簡単なアプローチ：次のよう
   なランダムなインデックスを選択します。イテレータを取得し、を使用して時間を進めてから、サブセットに対して実際のループを開始します。利点：簡単です。短所：++の無駄。i(i+N-1) < |U|itU.begin()iit++

2. バケットアプローチ（そしてこれは上記のリンクから「新しく」派生しました）：上記のように選択し、 -番目の要素が含まれているバケットを見つけ、local_iterator
   を 取得し、の-番目の要素に到達するまで進みます。それ以降は、時間を増やし続けます。バケットの最後に到達した場合は、次のバケットの最初から続行します。もっとランダムにしたい場合は、完全にランダムに選んでバケツを包み込むことができます。ibilitU.begin(b)litlit++iUlitNliti

私の未解決の質問：

1. 上記のポイント2の場合、 -番目Uの要素を見つけたら、どういうわけかイテレータを入れることができないのは本当ですか？iこれにより、バケット境界の制御などが不要になります。初心者の私にとって、標準のフォワードイテレータが5番目のアイテムでトラバースを続行する方法を知っている必要があることは認識できないようですが、U自分で5番目のアイテムiを見つけたときは上記のポイント2以外をi通過できないようにする必要があります。U
2. 他に何ができますか？もっと賢い/もっとランダムなものを知っていますか？可能であれば、バケットサイズやハッシュ関数などの手動制御には関与したくありません。これは少し頭がおかしいからです。

2d ベクトルを行ごとにハッシュ テーブルにプッシュし、後でハッシュ テーブル内の行 (ベクトル) を検索して、それを見つけられるようにしたいと考えています。私は何かをしたい

セットにベクトルを挿入して検索する方法がわかりません。だから誰かが私を導くことができれば、それは役に立ちます。ありがとう

アップデート：

std::set私が使用することにしたハッシュテーブルではないことに気付いたので、unordered_mapこれに要素を挿入して検索するにはどうすればよいですか: