在实践中，什么时候必须使用“std::unordered_map”而不是“std::map”？

Question

实际应用中，有什么情况std::unordered_map必须用 来代替std::map？

我知道它们之间的区别，比如内部实现、搜索元素的时间复杂度等等。

但我实在找不到确实std::unordered_map可以替代的情况std::map。

Answer 1

是的，例如，如果键类型没有合理的严格弱排序，但具有合理的相等性并且是可散列的。

std::set有序关联容器和上的键类型需要严格的弱顺序std::map。

Answer 2

我知道它们之间的区别，比如内部实现、搜索元素的时间复杂度

在这种情况下，您应该知道无序映射的平均渐近元素查找时间复杂度是恒定的，而有序映射的复杂度是对数的。这意味着容器有一定大小，此时使用无序映射时查找速度会更快。

但我真的找不到 std::unordered_map 确实不能被 std::map 替换的情况。

如果容器足够大，并且如果您无法承担有序映射查找的成本，那么您就不能选择替换更快的无序映射查找。

无法使用有序映射的另一种情况是不存在比较键的相对顺序的廉价函数。