我似乎找不到这方面的任何信息，所以我求助于 stackoverflow。 C++ 中 std::tr1::unordered_map 的迭代器效率如何？特别是与列表迭代器相比。制作一个包装类是否有意义，该包装类也将所有键保存在列表中以允许高效迭代(我的代码确实对 unordered_map 中的键使用了大量迭代)。对于那些会推荐 boost 的人，我不能使用它(无论出于何种原因)。
最佳答案
我没有检查 TR1，但 N3035(C++0x 草案)是这样说的:
All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized). Therefore, requirement tables for the iterators do not have a complexity column.
除了复杂性之外，该标准不会提供效率保证，因此您无法保证 list 和 unordered_map 的比较，除了它们'两者都是摊销常数时间(即，对容器进行完整迭代的线性时间)。
在实践中，我希望 unordered_map 迭代器至少在 list 附近，除非你的 hashmap 非常稀疏人口稠密。完整迭代的复杂度可能有一个 O(桶数)项。但是我从来没有看过一个针对 C++ 的 unordered_map 的实现，所以我不知道在简单的“链表数组”哈希表实现上会有什么修饰。如果你有一个“典型的”平台测试它，如果你试图编写在所有 C++ 实现上肯定是最快的代码，那么运气不好，你不能 ;-)
关于c++ - unordered_map 中迭代器的效率 (C++)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2499769/