c++ - unordered_map (C++) 中迭代器的效率

Question

我似乎找不到任何关于此的信息，所以我求助于 stackoverflow。C++ 中 std::tr1::unordered_map 的迭代器效率如何？尤其是与列表迭代器相比。制作一个包装类是否有意义，该类还包含列表中的所有键以允许有效迭代（我的代码确实对 unordered_map 中的键使用了大量迭代）。对于那些会推荐 boost 的人，我不能使用它（无论出于何种原因）。

Answer 1

我还没有检查 TR1，但 N3035 (C++0x 草稿) 说：

迭代器的所有类别只需要在恒定时间内（摊销）对给定类别可实现的那些函数。因此，迭代器的需求表没有复杂度列。

除了复杂性之外，该标准不会提供效率保证，因此除了它们都是摊销的常数时间（即容器上完整迭代的线性时间）之外，您无法保证比较list和。unordered_map

在实践中，我希望unordered_map迭代器至少在 附近list，除非您的哈希图人口非常稀少。在完整迭代的复杂性中可能存在 O（桶数）项。但是我从来没有看过一个专门unordered_map针对 C++ 的实现，所以我不知道在简单的“链表数组”哈希表实现上会有什么装饰。如果你有一个“典型的”平台测试它，如果你正在尝试编写在所有 C++ 实现中绝对是最快的代码，那么运气不好，你不能;-)

Answer 2

不幸的是，除非您已经尝试过并衡量了结果，否则您无法确定某件事是否足够有效。我可以告诉你，标准库、TR1 和 Boost 类已经引起了很多关注。对于最常见的用例，它们可能会尽可能快。行走容器当然是一个常见的用例。

说了这么多，你需要问自己几个问题：

1. 表达我想要的最清晰的方式是什么？编写包装类可能会为您的代码增加不必要的复杂性。 先做对，再做快。

2. 我能负担得起额外的内存和时间来保持list与 的并行unordered_map吗？

3. 真的unordered_map是正确的数据结构吗？如果您最常见的用例是从头到尾遍历，那么您可能会更好，vector因为内存保证是连续的。

Answer 3

unordered_map 迭代器基本上只需要遍历哈希表的内部树结构。这只是意味着执行一些指针跟踪，因此应该非常有效。当然，如果您经常遍历 unordered_map，则可能一开始就使用了错误的数据结构。在任何情况下，这个问题的答案，就像所有性能问题一样，是让你为你的特定代码计时，看看它是否足够快。

Answer 4

这里的基准测试回答了https://stackoverflow.com/a/25027750/1085128 unordered_map 介于向量和映射之间以进行迭代。它比地图快得多。