遍历所有元素时，std::unordered_map和std::map之间的性能差异是什么？

Question

我想用指针作为键来映射数据。我应该选择哪种容器，map还是unordered_map？在stackoverflow上有多个关于这个主题的问题，但没有一个覆盖当我们需要遍历所有键值对时的性能方面。

std::map<classKey* , classData*> myMap;
std::unordered_map<classKey* , classData*> myUnorderedMap;

for (auto & iter : myMap) { //loop1
    display(iter.second);
}

for (auto & iter : myUnorderedMap) { //loop2
    display(iter.second);
}

loop1和loop2哪个性能更好。

@RetiredNinja提供的基准测试结果。

当size = 10,000,000时，我们得到以下基准测试结果：

- nav_jan

---

有趣。一开始我不知道。不过我会把钱压在std::map上。你能否设置一些测试用例来进行分析吗？ - Bathsheba

请展示您如何进行基准测试。 - πάντα ῥεῖ

@MichaelChourdakis，OP询问的是性能问题，而不是时间复杂度方面的效率。 - Fureeish

不确定我是否正确使用了这个快速基准测试工具，但玩起来很有趣。http://quick-bench.com/sxQWkAg6tXRWsUCXIArv4NbjZ3E - Retired Ninja

Quick Bench非常出色；我（自认为）已经很好地利用它了。 - Lightness Races in Orbit

Answer 1

作为您所期望的，这在很大程度上取决于标准库数据结构的实际实现。因此，这个答案会比较理论化，不受任何一个实现的限制。

std::map在内部使用平衡二叉树。这就是为什么它具有O(log(n))的插入、删除和查找时间复杂度的原因。遍历它应该是线性的，因为你只需要进行深度优先遍历（这将需要O(log(n))内存，以堆栈空间的形式）。使用std::map进行迭代的好处是，您将按排序顺序遍历键，并且您将免费获得这个好处。

std::unordered_map 使用散列表进行实现。这使得插入、删除和查找的平均时间为常数。如果实现没有针对迭代进行优化，一个朴素的方法是遍历散列表中的每个桶。由于好的散列表（理论上）在50%的桶中恰好有一个元素，其余部分为零，因此该操作也将是线性的。然而，相同的线性操作在std::map中速度会更快，但需要更多的“墙钟时间”。为了解决这个问题，一些散列表实现保持所有元素的侧列表以进行快速迭代。如果出现这种情况，则在std::unordered_map上进行迭代将会更快，因为无法比迭代连续内存更快（仍然是线性时间，显然）。

在极小概率下，如果您确实需要优化到这个级别（而不仅仅是出于理论性能好奇），则您的代码其他地方可能存在更大的性能瓶颈。

所有这些都忽略了依赖指针值的奇怪性质，但那既非此处讨论重点。

进一步阅读的来源：

GCC标准库中map的实现

GCC标准库中unordered_map的实现

GCC标准库中unordered_map如何实现快速迭代

- JimPri

---

@πάνταῥεῖ 人类目前无法提供更好的实现来满足标准要求，再加上没有反对以这种方式实现结构的限制，这对我来说已经足够假设这个（或接近这个）实现。是的，标准并未涉及具体实现，但我们还能有什么呢？ - Fureeish

你最后的源代码说哈希映射保留了指向桶的迭代器（=指针）的链接列表。这根本不是连续的（2次间接寻址）。只有桶会是连续的。而且，地图也可以用节点做同样的事情。我真的很想看到一些测量结果作为答案。 - Quimby

一个std::map在内部使用平衡二叉树。这就是为什么它具有O(log(n))的插入、删除和查找时间复杂度。这是反过来的。通常使用树结构以满足标准的复杂性要求。(好吧，这些复杂性要求最初来自于树的属性。但标准不知道！) - Lightness Races in Orbit

迭代它应该是线性的，因为你只需要进行深度优先遍历（这将需要O(log(n))内存，以堆栈空间的形式）。 - 这不是std::map迭代器的工作方式。它们是外部迭代器，不能分配任何堆栈空间。增加树迭代器仅平均常数时间。 （遍历整个树仍然是线性的。）请参见此处：https://github.com/gcc-mirror/gcc/blob/41d6b10e96a1de98e90a7c0378437c3255814b16/libstdc%2B%2B-v3/src/c%2B%2B98/tree.cc - Sebastian Redl

我正在为“所有这些都忽略了指针值的奇怪性，但这不是重点”而苦恼。 - pcdangio