迭代所有元素 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 我们得到以下基准结果：

Answer 1

正如您所料，这在很大程度上取决于标准库数据结构的实际实现。因此，这个答案将更具理论性，与任何一种实现的联系更少。

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

Astd::unordered_map在幕后使用哈希表。这允许您进行分摊的常量时间插入、删除和查找。如果实现没有针对迭代进行优化，一个简单的方法是迭代哈希表中的每个桶。由于一个好的哈希表（理论上）在 50% 的桶中恰好有一个元素，而在其余的桶中只有一个元素，因此该操作也将是线性的。但是，对于std::map. 为了解决这个问题，一些哈希表实现为快速迭代保留了所有元素的边列表。如果是这种情况，迭代 astd::unordered_map会更快，因为没有比在连续内存上迭代更好的了（尽管显然仍然是线性时间）。

在极不可能的情况下，您实际上需要优化到这个级别（而不仅仅是对理论上的性能感到好奇），您的代码中的其他地方可能会遇到更大的性能瓶颈。

所有这些都忽略了键控指针值的奇怪之处，但这既不存在也不存在。

进一步阅读的来源：

GCC std::map 实现

GCC std::unordered_map 实现

GCC std::unordered_map 如何实现快速迭代