Searching std::unordered_set by hash value and predicate

Question

How can I search a std::unordered_set knowing hash value and having some predicate object? (The predicate determining equivalence by pred(x) && pred(y) meaning x == y.)

Answer 1

Well, you could ignore the hash value and iterate the entire unsorted_set testing the predicate. Not the ideal efficiency, since you'd prefer to only iterate one bucket, but it does what you ask.

Standard unordered_set has an interface begin(size_t) to get an iterator for a particular bucket (by number), and an interface bucket_count() to get the number of buckets.

Objects with a given hash are guaranteed to all appear in the same bucket, so iterating that bucket testing the predicate is sufficient for what you want to do.

I can't actually see anything in the standard to guarantee the correct bucket to iterate is hash_value % bucket_count(). There's a function to get the bucket for a given object, but not to get the bucket for a given hash value. Try it on your implementation, though: I think it's a reasonable guess, and I may just have failed to find the crucial restriction in the standard.

In summary, I think you want something like:

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

but I'm not sure.