c++ - ハッシュ値と述語による std::unordered_set の検索

Question

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

Answer 1

ハッシュ値を無視してunsorted_set、述語のテスト全体を繰り返すことができます。1 つのバケットのみを反復したいので、理想的な効率ではありませんが、要求どおりに実行されます。

Standardunordered_setにはbegin(size_t)、特定のバケットの反復子を (番号で) 取得するためのインターフェイスと、bucket_count()バケットの数を取得するためのインターフェイスがあります。

特定のハッシュを持つオブジェクトはすべて同じバケットに表示されることが保証されているため、述語をテストするバケットを反復するだけで十分です。

反復する正しいバケットがhash_value % bucket_count(). 特定のオブジェクトのバケットを取得する関数がありますが、特定のハッシュ値のバケットを取得する関数はありません。ただし、実装で試してみてください。これは妥当な推測であり、標準の重大な制限を見つけられなかった可能性があります。

要約すると、次のようなものが必要だと思います。

size_t bucket = hash_value % myset.bucket_count();
find_if(myset.begin(bucket), myset.end(bucket), pred);

確信はないけど。