std :: unordered_map相等是否依赖于插入顺序

Question

std :: unordered_map相等是否依赖于插入顺序

如果std::unordered_map使用相同的(非相等的)键值对创建两个容器,但以不同的顺序插入(因此容器包含相同的元素,但可能在不同的顺序中),容器保证是相等的,根据等于运算符(operator==).我假设容器元素的哈希码和相等运算符满足其实现的所有必需约束.

Answer 1

Jer*_*fin 30

是的,他们保证在这种情况下返回平等.具体措辞(来自N4659,§[unord.req]/12)是:

两个无序容器a和b比较相等,如果a.size() == b.size()和,对于每一个等效密钥组[Ea1, Ea2)从获得的a.equal_range(Ea1),存在的等效密钥组[Eb1, Eb2)从获得的b.equal_range(Ea1),使得is_permutation(Ea1, Ea2, Eb1, Eb2)返回true.

因此,只要一个中的键(和相关值)与另一个相同(但可能以不同的置换顺序),它将比较相等.

@Ant:无序容器是哈希表,所以它们从在同一个桶中散列到相同值的所有键开始.我希望他们实际上使用`std :: is_permutation`来检查同一个桶中的密钥.[可以是O(n)](https://codereview.stackexchange.com/questions/86241/is-permutation-on-sequence-containers-in-on-complexity-follow-up). (3认同)
@hgm-红黑树？这个问题涉及无序映射，而不是（有序）映射。 (2认同)

Answer 2

Nat*_*ica 13

来自[unord.red]/12

两个无序容器a和b比较相等,如果a.size() == b.size()和,对于每一个等效密钥组[Ea1, Ea2)从获得的a.equal_range(Ea1),存在的等效密钥组[Eb1, Eb2)从获得的b.equal_range(Ea1),使得is_permutation(Ea1, Ea2, Eb1, Eb2)返回true.[...]

因此,只要密钥相同且大小相同,无论密钥的顺序如何,容器都将相等.

归档时间：	7 年，2 月前
查看次数：	2069 次
最近记录：	6 年，7 月前