C++ STL unordered_map和map的使用和性能分析

• unordered_map是C++ Boost库中的内容，这里的unordered翻译成“无序”。但它并不是完全的“无序”的概念，而是散列式的存储方式。
• unordered库提供了两个散列映射类，unordered_map和unordered_multimap。
• 它们用散列表代替了二叉树的实现，模板参数多了散列计算函数，比较谓词使用equal_to<>。
  看到这里，我们就应该明白，比起map/multimap，unordered_map和unordered_mutimap在查找元素的时候，速度不是一般的快。
  它们的查找速率是==常数级==的，而==map/multimap是基于二叉树实现的，所以查找是O(log n)的复杂度==。

unordered_map属于关联式容器，采用std::pair保存key-value形式的数据。用法与map一致。特别的是，STL中的map因为是==有序==的二叉树存储，所以对key值需要有大小的判断，当使用内置类型时，无需重载operator < ；但是用用户==自定义类型的话，就需要重载啦==！ unoredered_map全程使用不需要比较元素的key值的大小，但是，对于元素的==要有判断，又因为需要使用hash映射，所以，对于非内部类型，需要程序员为其定义这二者的内容，对于内部类型，就不需要了。

• unordered库使用“桶”来存储元素，散列值相同的被存储在一个桶里。当散列容器中有大量数据时，同一个桶里的数据也会增多，造成访问冲突，降低性能。为了提高散列容器的性能，unordered库会在插入元素是自动增加桶的数量，不需要用户指定。但是，用户也可以在构造函数或者rehash()函数中，指定最小的桶的数量。

map, set, multimap, and multiset

• 上述四种容器采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:

• 插入: O(logN)

• 查看:O(logN)

• 删除:O(logN)

hash_map, hash_set, hash_multimap, and hash_multiset

• 上述四种容器采用哈希表实现，不同操作的时间复杂度为：

• 插入:O(1)，最坏情况O(N)。

• 查看:O(1)，最坏情况O(N)。

• 删除:O(1)，最坏情况O(N)。