首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >std::unordered_map等式是否取决于插入顺序

问std::unordered_map等式是否取决于插入顺序
EN

Stack Overflow用户
提问于 2018-08-06 15:22:44
回答 3查看 5K关注 0票数 35

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

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2018-08-06 15:32:37

是的,在这种情况下,它们保证返回相等。具体措辞(取自N4659,§unord.req/12)是:

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

因此,只要一个键(和相关值)与另一个键相同(但可能以不同的排列顺序排列),它就会比较相等。

票数 33
EN

Stack Overflow用户

发布于 2018-08-06 15:33:46

来自[unord.red]/12

两个无序容器a和b比较相等,如果a.size() == b.size(),对于从a.equal_­range(Ea1)获得的每个等价密钥组[Ea1, Ea2),存在一个从b.equal_­range(Ea1)获得的等价密钥组[Eb1, Eb2),因此is_­permutation(Ea1, Ea2, Eb1, Eb2)返回true。..。

因此,只要键相同,大小相同,无论键的顺序如何,容器的比较都是相等的。

票数 14
EN

Stack Overflow用户

发布于 2018-08-06 15:36:02

下面是cppreference.com关于std:unordered_map,operator==,!=(std::unordered_map)的引号:

如果下列条件成立,两个无序集装箱lhs和rhs的含量是相等的:

  • lhs.size() == rhs.size()
  • 从lhs_eq1(Lhs_eq1)获得的每一组等效元素[rhs_eq1,lhs_eq1]在另一个容器[rhs_eq1,rhs_eq2)中有一组对应的等效元素,这些元素从rhs.equal_range(rhs_eq1)获得,具有以下性质:
    • 距离(lhs_eq1,lhs_eq2) == std::==(rhs_eq1,rhs_eq2)。
    • std::is_permutation(lhs_eq1,lhs_eq2,rhs_eq1) == == true。

​

请注意:

如果Key或T不是EqualityComparable,则行为未定义。 如果Hash和KeyEqual do (直到C++20)KeyEqual确实有(因为C++20)在lhs和rhs上没有相同的行为,或者如果operator== Key不是将分区细化为由KeyEqual引入的等效密钥组(也就是说,如果两个使用operator==比较相等的元素落入不同的分区),则行为也是未定义的。

最后,要考虑的是复杂性:

对operator==的调用与value_type上的N次调用成正比,对key_eq返回的谓词的调用与对hash_function返回的hasher的调用成比例,在最坏的情况下与N2成比例,其中N是容器的大小。

因此,如果两个无序映射具有相同的大小,并且在另一个容器中查找一个容器中的每个键,如果碰巧找到,则比较它们的值,则它们被认为是相同的。

票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/51710926

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档