|
C++ STL无序容器（哈希容器）是什么？
无序容器是 C++ 11 标准才正式引入到 STL 标准库中的，这意味着如果要使用该类容器，则必须选择支持 C++ 11 标准的编译器。
关联式容器一样，无序容器也使用键值对（pair 类型）的方式存储数据。不过，本教程将二者分开进行讲解，因为它们有本质上的不同：
关联式容器的底层实现采用的树存储结构，更确切的说是红黑树结构；
无序容器的底层实现采用的是哈希表的存储结构。
基于底层实现采用了不同的数据结构，因此和关联式容器相比，无序容器具有以下 2 个特点：
无序容器内部存储的键值对是无序的，各键值对的存储位置取决于该键值对中的键，
和关联式容器相比，无序容器擅长通过指定键查找对应的值（平均时间复杂度为 O(1)）；但对于使用迭代器遍历容器中存储的元素，无序容器的执行效率则不如关联式容器。
C++ STL无序容器种类
和关联式容器一样，无序容器只是一类容器的统称，其包含有 4 个具体容器，分别为 unordered_map、unordered_multimap、unordered_set 以及 unordered_multiset。
unordered_map
存储键值对 <key, value> 类型的元素，其中各个键值对键的值不允许重复，且该容器中存储的键值对是无序的。
unordered_multimap
和 unordered_map 唯一的区别在于，该容器允许存储多个键相同的键值对。
unordered_set
不再以键值对的形式存储数据，而是直接存储数据元素本身（当然也可以理解为，该容器存储的全部都是键 key 和值 value 相等的键值对，正因为它们相等，因此只存储 value 即可）。另外，该容器存储的元素不能重复，且容器内部存储的元素也是无序的。
unordered_multiset
和 unordered_set 唯一的区别在于，该容器允许存储值相同的元素。
也就是说，C++ 11 标准的 STL 中，在已提供有 4 种关联式容器的基础上，又新增了各自的“unordered”版本（无序版本、哈希版本），提高了查找指定元素的效率。
有读者可能会问，既然无序容器和之前所学的关联式容器类似，那么在实际使用中应该选哪种容器呢？总的来说，实际场景中如果涉及大量遍历容器的操作，建议首选关联式容器；反之，如果更多的操作是通过键获取对应的值，则应首选无序容器。
C++ STL无序容器底层实现原理（深度剖析）
http://c.biancheng.net/view/7235.html
当有新键值对存储到无序容器中时，整个存储过程分为如下几步：
将该键值对中键的值带入设计好的哈希函数，会得到一个哈希值（一个整数，用 H 表示）；
将 H 和无序容器拥有桶的数量 n 做整除运算（即 H % n），该结果即表示应将此键值对存储到的桶的编号；
建立一个新节点存储此键值对，同时将该节点链接到相应编号的桶上。
unordered_set 容器，可直译为“无序 set 容器”，即 unordered_set 容器和 set 容器很像，唯一的区别就在于 set 容器会自行对存储的数据进行排序，而 unordered_set 容器不会。
总的来说，unordered_set 容器具有以下几个特性：
不再以键值对的形式存储数据，而是直接存储数据的值；
容器内部存储的各个元素的值都互不相等，且不能被修改。
不会对内部存储的数据进行排序（这和该容器底层采用哈希表结构存储数据有关，可阅读《C++ STL无序容器底层实现原理》一文做详细了解）；
所谓“类似”，指的是 unordered_multiset 容器大部分的特性都和 unordered_set 容器相同，包括：
unordered_multiset 不以键值对的形式存储数据，而是直接存储数据的值；
该类型容器底层采用的也是哈希表存储结构（可阅读《C++ STL无序容器底层实现原理》一文做详细了解），它不会对内部存储的数据进行排序；
unordered_multiset 容器内部存储的元素，其值不能被修改。
和 unordered_set 容器不同的是，unordered_multiset 容器可以同时存储多个值相同的元素，且这些元素会存储到哈希表中同一个桶（本质就是链表）上。
读者可以这样认为，unordered_multiset 除了能存储相同值的元素外，它和 unordered_set 容器完全相同。
|