unordered_map

写在前面：

unordered_map总结
unordered_map和map的比较

unordered_map：

无序映射是关联容器，用于存储由键值和映射值组合而成的元素，并允许基于键快速检索各个元素。
在unordered_map中，键值通常用于唯一标识元素，而映射值是与该键关联的内容的对象。键和映射值的类型可能不同。
在内部，unordered_map中的元素没有按照它们的键值或映射值的任何顺序排序，而是根据它们的散列值组织成桶以允许通过它们的键值直接快速访问单个元素（具有常数平均时间复杂度）。

unordered_map容器比映射容器更快地通过它们的键来访问各个元素，尽管它们通过其元素的子集进行范围迭代通常效率较低。

无序映射实现直接访问操作符（operator []），该操作符允许使用其键值作为参数直接访问映射值。

容器中的迭代器至少是前向迭代器。

关键词：无序的 快速的检索 达到的是更快的访问 但是子集的范围迭代效率低

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

• 1
• 2
• 3
• 4
• 5
• 6

unordered_map容器的迭代器指向这个value_type的元素。 因此，对于一个称为它的迭代器来说，它指向映射的一个元素，它的键和映射值可以分别用下面的方法访问：

unordered_map<Key,T>::iterator it;
(*it).first;             // the key value (of type Key)
(*it).second;            // the mapped value (of type T)
(*it);                   // the "element value" (of type pair<const Key,T>) 

• 1
• 2
• 3
• 4

其他的具体的成员变量和成员函数可以看：文档

如果在使用map的时候不需要使得元素之间有序那么直接使用undered_map就可以了否则标准库当中的map底层是以红黑树的数据结构实现的，支持的搜索，插入，删除都是O(logn)的时间复杂度。

map和unordered_map的比较

map：

优点：
有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
map底层是以红黑树的数据结构实现的，支持的搜索，插入，删除都是O(logn)的时间复杂度。

缺点：
空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间

unordered_map：

优点： 因为内部实现了哈希表，因此其查找速度非常的快
缺点： 哈希表的建立比较耗费时间
适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map