c++ - 通过哈希值和谓词搜索 std::unordered_set

Question

我如何搜索一个 std::unordered_set 知道散列值和一些谓词对象？ (由 pred(x) && pred(y) 决定等价的谓词意味着 x == y。)

Answer 1

好吧，您可以忽略散列值并迭代整个 unsorted_set 来测试谓词。这不是理想的效率，因为您更愿意只迭代一个桶，但它会按照您的要求进行。

标准 unordered_set 有一个接口(interface) begin(size_t) 来获取特定桶的迭代器(按数字)，还有一个接口(interface) bucket_count() 获取桶的数量。

具有给定散列的对象保证全部出现在同一个桶中，因此迭代该桶测试谓词足以满足您的需求。

我实际上在标准中看不到任何东西来保证迭代正确的桶是 hash_value % bucket_count()。有一个函数可以获取给定对象 的存储桶，但不能获取给定哈希值 的存储桶。不过，请在您的实现中尝试一下:我认为这是一个合理的猜测，我可能只是没能找到标准中的关键限制。

总而言之，我想你想要这样的东西:

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

但我不确定。