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

素颜马尾好姑娘i 2022-05-25 08:13 550阅读 0赞

*  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)。