C++ 中的 map 与 hash_map
我对 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.
相关文章