C++ 中的 map 与 hash_map [英] map vs. hash_map in C++

问题描述

我对 C++ 中的 hash_map 和 map 有疑问.我知道 map 在 STL 中，但 hash_map 不是标准.两者有什么区别?

I have a question with hash_map and map in C++. I understand that map is in STL, but hash_map is not a standard. What's the difference between the two?

推荐答案

它们以非常不同的方式实现.

They are implemented in very different ways.

hash_map(TR1 和 Boost 中的 unordered_map；使用这些代替)使用哈希表，其中键被哈希到表中的一个槽，值存储在与该键关联的列表.

hash_map (unordered_map in TR1 and Boost; use those instead) use a hash table where the key is hashed to a slot in the table and the value is stored in a list tied to that key.

map 实现为平衡二叉搜索树(通常是红/黑树).

map is implemented as a balanced binary search tree (usually a red/black tree).

unordered_map 应该在访问集合的已知元素时提供稍微更好的性能，但是 map 将具有其他有用的特性(例如，它以排序顺序存储，这允许从头到尾遍历).unordered_map 在插入和删除时会比 map 更快.​​

An unordered_map should give slightly better performance for accessing known elements of the collection, but a map will have additional useful characteristics (e.g. it is stored in sorted order, which allows traversal from start to finish). unordered_map will be faster on insert and delete than a map.

这篇关于C++ 中的 map 与 hash_map的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！