Searching std::unordered_set by hash value and predicate
How ca开发者_StackOverflow社区n 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
.)
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.
精彩评论