C++中的unordered_map和map区别1. unordered_map 2. map

1.

unordered_map

在头文件上，引入

<unordered_map>

来使用它。对于

unordered_map

而言，最大的特点在于内部实现上，使用到了哈希表（散列表、

hash_table

）来进行映射存储，它的模板类声明及其参数如下：

/**
 * 程序来自STL源码 bits/unordered_map.h
 */
template<typename _Key,  // key 类型 
        typename _Tp,    // value 类型
        typename _Hash = hash <_Key>,     // 哈希函数
        typename _Pred = equal_to <_Key>, // 用于比较两者是否相同的函数
        typename _Alloc = allocator <std::pair<const _Key, _Tp>>> // 分配器，描述了容器在内存管理上的细节，不应该自己来处理，除非写自己的容器
class unordered_map {
};           

在

unordered_map

内部，使用的

Hash Table

对数据进行组织，通过把键值

key

映射到

hash

表中的一个位置进行访问，根据

hash

函数的特点，

unordered_map

对于元素查找的时间复杂度可以达到

O(1)

，但是，它的元素排列是无序的。具体例子如下：

int main() {
    using namespace std;
    // 首先创建一个无序 map，它的 key 使用 int 类型，value 使用 string 类型
    unordered_map<int, string> unorderedMap;    
   
    // 三种插入新元素的方法，“茴”字有三种写法~
    unorderedMap.insert(make_pair(0, "Alice")); 
    unorderedMap[1] = "Bob";
    unorderedMap.insert(unordered_map<int, string>::value_type(2, "Candy"));
 
    // 对内部元素挨个输出
    for (auto iter = unorderedMap.begin(); iter != unorderedMap.end(); iter++) {
        cout << iter->first << " - " << iter->second << endl;
        /*
         * >: 输出如下，可以得知它们在 key 的排序上并没有顺序
         * 2 - Candy
         * 0 - Alice
         * 1 - Bob
         */
    }
}           

unordered_map

由于建立了哈希表，所以它在最开始建立的时候比较耗时间，但是它查询速度快呀~，一般情况下用

unordered_map

是没有问题的。

2.

map

对于

map

而言，首先在头文件上，引用

<map>

进来，然后使用。它的类模板声明以及部分函数声明如下：

/**
 * 程序来自C++源码 bits/stl_map.h
 */
template<typename _Key,  // key 类型
        typename _Tp,    // value 类型
        typename _Compare = std::less<_Key>, // 用于比较两个元素的比较函数
        typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > // 分配器，同样的描述了容器在内存管理上的细节，不应该自己来处理，除非写自己的容器
class map {
private:
    /// 将一个红黑树转换成 [multi]map.
    typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
    rebind<value_type>::other _Pair_alloc_type;

    typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
    key_compare, _Pair_alloc_type> _Rep_type;
};           

map

的内部，使用了红黑树（

red-black tree

）来组织数据，因此默认的就已经实现了数据的排序。从下面例子中可以看出，它默认实现了在

key

上排序实现递增：

int main() {
    map<int, string> mapper;
    mapper.insert(make_pair(0, "Alice"));
    mapper[1] = "Bob";
    mapper.insert(map<int, string>::value_type(2, "Candy"));
    for (auto &iter : mapper) {
        cout << iter.first << " - " << iter.second << endl;
        /*
         * >: 输出如下，很明显的，它们在 key 的排序上是递增排列的
         * 0 - Alice
         * 1 - Bob
         * 2 - Candy
         */
    }
}           

不过，在存储上

map

却比较占用空间，因为在红黑树中，每一个节点都要额外保存父节点和子节点的连接，因此使得每一个节点都占用较大空间来维护红黑树性质。

3. 总结

两种数据结构特点如下表格~

unordered_map	map
查找	快，Average： O(1) ，Worst Case： O(n)	恒定的 log(n)
插入	和上面一样	log(n) + 平衡二叉树所用时间
删除	还和上面一样	log(n)
是否排序	不排序	排序
实现方法	哈希表	红黑树
适用于	查找操作频率高	要求结果有序（按 key 排序）