假设我们有std::unordered_multiset两个映射相同哈希值的值，c++ 标准是否有任何保证 find 将返回第一个插入的元素？
问问题
606 次
2 回答
3
有趣的问题。没有经常使用无序关联容器，所以我借此机会搜索了标准。这是我的解释： 23.2.5.6 说
“在支持等效键的容器中，具有等效键的元素在容器的迭代顺序中彼此相邻。因此，尽管未指定无序容器中元素的绝对顺序，但其元素被分组为等效键组这样每个组的所有元素都有等效的键。”
但随后继续
“无序容器上的变异操作应保持每个等效键组内元素的相对顺序，除非另有说明。”
23.2.5.9 然后声明
“对于 unordered_multiset 和 unordered_multimap，重新散列保留了等效元素的相对顺序。”
所以顺序似乎被保留了，因为 insert 并没有说它可能会改变等效键的顺序。但是，find 被指定为
“返回一个迭代器，该迭代器指向一个键等效于 k 的元素，如果不存在这样的元素，则返回 b.end()。”
因此，它没有定义它返回的等效键的哪个元素。严格来说，这可能会返回具有给定键的随机元素，并且仍然满足规范。鉴于 equal_range 定义为
返回一个范围，该范围包含所有具有等效于 k 的键的元素。
*equal_range(k).first可以完成这项工作并返回用键 k 插入的第一个元素。
于 2014-03-14T18:09:43.593 回答
1
我假设您的问题是关于两个键，它们不仅生成相同的哈希值，而且还使用提供给unordered_multiset. unordered_multiset::find将仅使用哈希值最初定位要在其中搜索的存储桶，但之后使用相等谓词完成搜索。
§23.2.5 [unord.req]表 103 - 无序关联容器要求
b.find(k)返回一个迭代器，该迭代器指向具有等效键的元素
k，或者b.end()如果不存在这样的元素。
find()对unordered_multi*容器没有额外的要求。这意味着不需要unordered_multiset::find将迭代器返回到第一个插入元素的实现。但是话又说回来，如果两个（或更多）键真的是等价的，你为什么要关心呢？
于 2014-03-14T18:10:16.023 回答