在微不足道的键的情况下，使用 map 而不是 unordered_map 有什么优势吗？

Question

最近关于 unordered_map 在 C++ 中的讨论让我意识到我应该使用 unordered_map map 大多数 情况下，因为查找的效率 O(1) 与 O(log n) )。大多数时候我使用地图，我使用 int 或 std::string 作为键类型；因此，我对哈希函数的定义没有任何问题。我想得越多，我就越意识到我找不到任何理由使用 std::map 而不是 std::unordered_map 在具有简单类型的键的情况下-我查看了接口，并没有发现任何会影响我的代码的显着差异。

Hence the question: is there any real reason to use std::map over std::unordered_map in the case of simple types like int and std::string ?

我是从严格的编程角度提出的问题——我知道它没有被完全认为是标准的，而且它可能会给移植带来问题。

另外，我希望正确的答案之一可能是 “对于较小的数据集更有效”， 因为开销较小（这是真的吗？）——因此我想将问题限制在密钥是非平凡的（> 1 024）。

编辑： 呃，我忘记了明显的（感谢 GMan！）——是的，地图当然是有序的——我知道，并且正在寻找其他原因。

原文由 Kornel Kisielewicz 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

不要忘记 map 保持其元素有序。如果你不能放弃，显然你不能使用 unordered_map 。

要记住的其他一点是 unordered_map 通常会使用更多内存。 map 只有几个管家指针和每个对象的内存。相反， unordered_map 有一个大数组（在某些实现中可能会变得很大），然后为每个对象增加额外的内存。如果您需要内存感知， map 应该会更好，因为它缺少大数组。

因此，如果您需要纯粹的查找检索，我会说 unordered_map 是要走的路。但是总是有取舍的，如果你买不起，那么你就不能使用它。

仅从个人经验来看，我发现在主实体查找表中使用 unordered_map 而不是 map 时，性能有了巨大的提高（当然是测量的）。

另一方面，我发现重复插入和删除元素要慢得多。这对于相对静态的元素集合来说非常有用，但是如果您要进行大量的插入和删除，那么散列 + 分桶似乎会加起来。 （注意，这是经过多次迭代。）

原文由 GManNickG 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

通过使用无序映射，您可以声明代码中没有任何地方依赖被排序的映射。在某些情况下，此附加上下文信息可能有助于了解此映射在程序中的实际使用方式。清晰度可能更重要，因为性能是副作用。

当然，当您需要有序映射时，没有编译器会阻止您使用无序映射，但这不太可能很好地工作，以至于读者可能会认为这不仅仅是一个错误。

原文由 Audrius Meškauskas 发布，翻译遵循 CC BY-SA 4.0 许可协议