CPP知识积累

STL库

map和unordered_map的区别

数据结构

• map基于红黑树。红黑树是一种平衡二叉树的变体结构，左右子树高度差可能会大于一，但其平衡的代价要比平衡二叉树低。红黑树拥有自动排序的功能，因此map也就有了按键自动排序的功能，因此在map中的元素排列都是有序的。在map中，每一个元素都对应着一个红黑树的结点，所以实现对map的增删改查，也就是相当于对红黑树的操作。对于这些操作的复杂度都为O(logn)，复杂度即为红黑树的高度。
• unordered_map基于哈希表。散列表使得unordered_map的插入和查询速度接近于O(1)（在没有冲突的情况下），但是其内部元素的排列顺序是无序的。

元素顺序

• map按照key进行自动排序
• unordered_map无序

插入和查询的时间复杂度

• map基于红黑树，复杂度与树高相同，即O(logn)。
• unordered_map基于散列表，复杂度依赖于散列函数产生的冲突多少，但大多数情况下其复杂度接近于O(1)。

效率及其稳定性不同

• map的查找类似于平衡二叉树的查找，其性能十分稳定。空间效率接近100%。
• unordered_map的散列空间会存在部分未被使用的位置，所以其内存效率不是100%的。

使用场景

• map：
  • 元素需要有序；
  • 对于单次查询时间较为敏感，必须保持查询性能的稳定性，比如实时应用等等。
• unordered_map：
  • 要求查找速率快，且对单次查询性能要求不敏感。

总结

• 在需要元素有序性或者对单次查询性能要求较为敏感时，请使用map，其余情况下应使用unordered_map。
• 因此在需要使用字典结构进行算法编程的大部分情况下，都需要使用unordered_map而不是map。

关键字

auto关键字