C++ STL无序关联式容器
C++ STL无序关联式容器教程
除了 序列式容器 和 关联式容器 之外，C++ 11 标准库又引入了一类容器，即无序关联式容器。无序关联式容器，又称哈希容器。
和关联式容器一样，此类容器存储的也是键值对元素；不同之处在于，关联式容器默认情况下会对存储的元素做升序排序，而无序关联式容器不会。
和其它类容器相比，无序关联式容器擅长通过指定键查找对应的值，而遍历容器中存储元素的效率不如关联式容器。
STL关联式容器详解
说明
无序容器是 C++ 11 标准才正式引入到 STL 标准库中的，这意味着如果要使用该类容器，则必须选择支持 C++ 11 标准的编译器。
和关联式容器一样，无序容器也使用键值对，即 pair 类型 的方式存储数据。不过，它们有本质上的不同：关联式容器的底层实现采用的树存储结构，更确切的说是红黑树结构；无序容器的底层实现采用的是哈希表的存储结构。
C++ STL 底层采用哈希表实现无序容器时，会将所有数据存储到一整块连续的内存空间中，并且当数据存储位置发生冲突时，解决方法选用的是“链地址法”（又称“开链法”）。
特点
基于底层实现采用了不同的数据结构，因此和关联式容器相比，无序容器具有以下 2 个特点：
- 无序容器内部存储的键值对是无序的，各键值对的存储位置取决于该键值对中的键。
- 和关联式容器相比，无序容器擅长通过指定键查找对应的值（平均时间复杂度为 O(1)）；但对于使用迭代器遍历容器中存储的元素，无序容器的执行效率则不如关联式容器。
分类
| 无序容器 | 功能 |
|---|---|
| unordered_map | 存储键值对 <key, value> 类型的元素，其中各个键值对键的值不允许重复，且该容器中存储的键值对是无序的。 |
| unordered_multimap | 和 unordered_map 唯一的区别在于，该容器允许存储多个键相同的键值对。 |
| unordered_set | 不再以键值对的形式存储数据，而是直接存储数据元素本身（当然也可以理解为，该容器存储的全部都是键 key 和值 value 相等的键值对，正因为它们相等，因此只存储 value 即可）。另外，该容器存储的元素不能重复，且容器内部存储的元素也是无序的。 |
| unordered_multiset | 和 unordered_set 唯一的区别在于，该容器允许存储值相同的元素。 |
技术细节
C++ 11 标准的 STL 中，在已提供有 4 种关联式容器的基础上，又新增了各自的 “unordered” 版本（无序版本、哈希版本），提高了查找指定元素的效率。
总的来说，实际场景中如果涉及大量遍历容器的操作，建议首选关联式容器；反之，如果更多的操作是通过键获取对应的值，则应首选无序容器。
案例
无序关联式容器使用
使用 unordered_map 无序关联式容器
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
cout << "嗨客网(www.haicoder.net)\n" << endl;
unordered_map<string, string> unMap{{"name","haicoder"},{"url","www.haicoder.net"}};
for (auto iter = unMap.begin(); iter != unMap.end(); ++iter)
{
cout << iter->first << " " << iter->second << endl;
}
return 0;
}
编译后，我们直接运行生成的二进制文件 a.out，如下图所示：
我们定义了一个无序关联式容器 unordered_map，并存入了两个元素，接着，我们使用迭代器访问了其中的所有元素。
C++ STL无序关联式容器总结
除了序列式容器和关联式容器之外，C++ 11 标准库又引入了一类容器，即无序关联式容器。无序关联式容器，又称哈希容器。
和关联式容器一样，此类容器存储的也是键值对元素；不同之处在于，关联式容器默认情况下会对存储的元素做升序排序，而无序关联式容器不会。
和其它类容器相比，无序关联式容器擅长通过指定键查找对应的值，而遍历容器中存储元素的效率不如关联式容器。
