C++ map和unordered_map的区别

unordered_map 类模板和 map 类模板都是描述了这么一个对象：它是由 std::pair<const Key, value> 组成的可变长容器；

这个容器中每个元素存储两个对象，也就是 key - value 对。

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>::templaterebind<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排序)