【STL十一】无序容器（哈希容器）—— unordered_map、unordered_set

• 简介
  除了序列式容器和关联式容器之外，C++ 11 标准库又引入了一类容器，即无序容器。无序容器，又称无序关联式容器、或者哈希容器。

和关联式容器一样，此类容器存储的也是键值对元素；不同之处在于，关联式容器默认情况下会对存储的元素做升序排序，而无序关联式容器不会。
和其它类容器相比，无序关联式容器擅长通过指定键查找对应的值，而遍历容器中存储元素的效率不如关联式容器。

一、简介

无序容器包含有 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 唯一的区别在于，该容器允许存储值相同的元素。

1、关联容器和无序容器不同

和关联式容器一样，无序容器也使用键值对（pair 类型）的方式存储数据。不过，它们有本质上的不同：

• 关联式容器的底层实现采用的树存储结构，更确切的说是红黑树结构；
• 无序容器的底层实现采用的是哈希表的存储结构。

2、无序容器特点

基于底层实现采用了不同的数据结构，因此和关联式容器相比，无序容器具有以下 2 个特点：

• 无序容器内部存储的键值对是无序的，各键值对的存储位置取决于该键值对中的键，
• 和关联式容器相比，无序容器擅长通过指定键查找对应的值（平均时间复杂度为O(1)）；但对于使用迭代器遍历容器中存储的元素，无序容器的执行效率则不如关联式容器。

二、头文件

#include <unordered_map>
#include <unordered_set>

三、模板类

unordered_map 容器模板的定义如下所示：

template < class Key,                        //键值对中键的类型
           class T,                          //键值对中值的类型
           class Hash = hash<Key>,           //容器内部存储键值对所用的哈希函数
           class Pred = equal_to<Key>,       //判断各个键值对键相同的规则
           class Alloc = allocator< pair<const Key,T> >  // 指定分配器对象的类型
           > class unordered_map;

四、无序容器的内部结构

1、管理桶

• 每一个位置，我们把其叫做一个桶。
• 通过哈希函数映射时可能好几个值，映射到一个桶。
• 如果桶的数量小的时候，可能会出现挂篮在的现象。（即一个桶下有好几个篮子——存储的对象）。这样我们找某个值时，先找到对应的桶，然在桶里再找我们桶内存储的值。
• 管理桶：无序容器的性能依赖于哈希函数的质量和桶的数量大小

2、内部结构

中间黑色的代表桶

• unordered_map 、unordered_multimap
• unordered_set、unordered_multiset
  

五、unordered_map成员函数

1、迭代器

成员函数	功能
begin()	同array容器
end()	同array容器
rbegin()	同array容器)
rend()	同array容器)
cbegin()	同array容器
cend()	同array容器
crbegin()	同array容器)
crend()	同array容器)

2、元素访问

成员函数	功能
operator[]	同array容器
at(n)	同array容器
front()	同array容器
back()	同array容器
data()	同array容器

3、容量

成员函数	功能
size()	同array容器
max_size()	同array容器
empty()	同array容器
reserve	同vector容器
capacity	同vector容器
shrink_to_fit	同vector容器

4、修改操作

成员函数	功能
clear()	同vector容器
insert()	同vector容器
insert_or_assign(C++17)	同map容器
emplace()	同vector容器
emplace_hint()	同map容器
try_emplace(C++17)	同map容器
erase()	同vector容器
push_back()	同vector容器
emplace_back()	同vector容器
pop_back()	同vector容器
push_front()	同vector容器
emplace_front()	同vector容器
pop_front()	同vector容器
resize()	同vector容器
swap()	同vector容器
extract(C++17)	从另一容器释出结点
merge(C++17)	从另一容器接合结点

5、操作

成员函数	功能
merge()	list容器
splice()	list容器
remove(val)	list容器
remove_if()	list容器
reverse()	list容器
unique()	list容器
sort()	list容器

5、查找

成员函数	功能
count(key)	同map容器
find(key)	同map容器
contains (C++20)	同map容器
equal_range(key)	同map容器
lower_bound(key)	同map容器
upper_bound(key)	同map容器

6、桶接口

成员函数	功能
begin()	同array容器
end()	同array容器
cbegin()	同array容器
cend()	同array容器
bucket_count	正在使用的桶的数目。
max_bucket_count()	容器容纳的最多的桶的数量
bucket_size(n)	第n个桶中有多少个元素
bucket(key)	关键字为k的元素在哪个桶种

7、哈希策略

成员函数	功能
load_factor	每个桶的平均元素数量，返回float值
max_load_factor	试图维护的平均桶大小，返回float值，会在需要时添加新的桶，以使得load_facotr < max_load_factor
rehash(n)	重组存储，使得bucket_count >=n, 且bucket_count > size/max_load_factor
reserve(n)	重组存储，使得可以保存n个元素且不必rehash。

六、demo

1、构造函数、emplace、find、迭代器

• 返回值
  指向键等于 key 的元素的迭代器。若找不到这种元素，则返回尾后（见 end() ）迭代器。

#include <iostream>
#include <string>       // string
#include<unordered_map>

using namespace std;
int main() {
    // 调用构造函数 1，也就是默认构造函数
    unordered_map <string, string> umap{
        {"小b","家在西安"},
        {"小a","家在北京"},
        {"小d","没有家"},
    };

    umap.emplace("小c","家在濮阳" );

    cout << "i can find 小c：" << endl;
    auto ite = umap.find("小c");
    cout << ite->first << "=" << ite->second << endl << endl;

    //使用迭代器输出 umap 容器存储的所有键值对
    for (auto iter = umap.begin(); iter != umap.end(); ++iter) {
        cout << iter->first << " " << iter->second << endl;
    }
    return 0;
}

输出

i can find 小c：
小c=家在濮阳


小b 家在西安
小a 家在北京
小d 没有家
小c 家在濮阳

2、桶接口bucket_count、max_bucket_count、bucket_size、bucket

#include <iostream>
#include <string>       // string
#include<unordered_map>

using namespace std;
int main() {
    // 调用构造函数 1，也就是默认构造函数
    unordered_map <string, string> umap{
        {"小b","家在西安"},
        {"小c","家在濮阳"},
        {"小a","家在北京"},
        {"小d","没有家"},
    };

    //获取键为 小c的键值对所在的范围
    auto pair = umap.equal_range("小c");
    //输出 pair 范围内的每个键值对的键的值
    for (auto iter = pair.first; iter != pair.second; ++iter) {
        cout << iter->first << "="<<iter->second;
    }
    cout << endl;
    
    auto bc = umap.bucket_count();
    cout << "bucket_count = " << bc << endl;

    auto bcm = umap.max_bucket_count();
    cout << "max_bucket_count = " << bcm << endl;

    auto szie = umap.bucket_size(3);
    cout << "bucket_size(3) = " << szie << endl;

    auto pos = umap.bucket("小c");
    cout << "bucket(\"小c\") = " << pos << endl;

    return 0;
}

输出

小c=家在濮阳
bucket_count = 8
max_bucket_count = 1152921504606846975
bucket_size(3) = 1
bucket(“小c”) = 3

七、unordered_multimap

和 unordered_map 容器一样，unordered_multimap 容器也以键值对的形式存储数据，且底层也采用哈希表结构存储各个键值对。两者唯一的不同之处在于，unordered_multimap 容器可以存储多个键相等的键值对，而 unordered_map 容器不行。

无序容器中存储的各个键值对，都会哈希存到各个桶（本质为链表）中。而对于 unordered_multimap 容器来说，其存储的所有键值对中，键相等的键值对会被哈希到同一个桶中存储。

• unordered_multimap 容器模板的定义如下所示：

template < class Key,      //键（key）的类型
           class T,        //值（value）的类型
           class Hash = hash<Key>,  //底层存储键值对时采用的哈希函数
           class Pred = equal_to<Key>,  //判断各个键值对的键相等的规则
           class Alloc = allocator< pair<const Key,T> > // 指定分配器对象的类型
           > class unordered_multimap;

• demo

#include <iostream>
#include <string>       // string
#include<unordered_map>
using namespace std;
int main() {
    // 调用构造函数 1，也就是默认构造函数
    unordered_multimap <string, string> ummap{
        {"小b","家在西安"},
        {"小c","家在濮阳"},
        {"小a","家在北京"},
        {"小d","没有家"},
        {"小d","也没有家"},
    };

    //输出 ummap容器中存储键为 'b' 的键值对的数量
    cout << ummap.count("小d") << endl;

    for (auto iter = ummap.begin(); iter != ummap.end(); ++iter) {
        cout << iter->first << " " << iter->second << endl;
        cout << "ummap.bucket(iter->first) = " << ummap.bucket(iter->first)<<endl;
    }

    cout << "ummap.bucket_count() = " << ummap.bucket_count();

    return 0;
}

• 输出

2
小b 家在西安
ummap.bucket(iter->first) = 0
小c 家在濮阳
ummap.bucket(iter->first) = 3
小a 家在北京
ummap.bucket(iter->first) = 1
小d 没有家
ummap.bucket(iter->first) = 2
小d 也没有家
ummap.bucket(iter->first) = 2
ummap.bucket_count() = 8

八、unordered_set

unordered_set 容器具有以下几个特性：

• 不再以键值对的形式存储数据，而是直接存储数据的值；
• 容器内部存储的各个元素的值都互不相等，且不能被修改。
• 不会对内部存储的数据进行排序（这和该容器底层采用哈希表结构存储数据有关，可阅读《C++ STL无序容器底层实现原理》一文做详细了解）；

对于 unordered_set 容器不以键值对的形式存储数据，读者也可以这样认为，即 unordered_set 存储的都是键和值相等的键值对，为了节省存储空间，该类容器在实际存储时选择只存储每个键值对的值。

• unordered_set 容器的类模板定义如下：

template < class Key,            //容器中存储元素的类型
           class Hash = hash<Key>,    //确定元素存储位置所用的哈希函数
           class Pred = equal_to<Key>,   //判断各个元素是否相等所用的函数
           class Alloc = allocator<Key>   //指定分配器对象的类型
           > class unordered_set;

• demo

#include <iostream>
#include <string>       // string
#include<unordered_set>
using namespace std;
int main() {
    unordered_set<string> uset{
        "小b",
        "小c",
        "小a",
        "小d",
    };

    auto ite = uset.insert("小e");
    cout << *(ite.first) << " " << ite.second << endl;

    unordered_set<string> set2;
    set2.insert(uset.begin(), uset.end());

    for (auto iter = set2.begin(); iter != set2.end(); ++iter) {
        cout << *iter << endl;
    }

    return 0;
}

• 输出

小e 1
小b
小c
小a
小d
小e

九、unordered_multiset。

unordered_multiset 容器大部分的特性都和 unordered_set 容器相同，包括：

• unordered_multiset 不以键值对的形式存储数据，而是直接存储数据的值；
• 该类型容器底层采用的也是哈希表存储结构，它不会对内部存储的数据进行排序；
• unordered_multiset 容器内部存储的元素，其值不能被修改。

和 unordered_set 容器不同的是，unordered_multiset 容器可以同时存储多个值相同的元素，且这些元素会存储到哈希表中同一个桶（本质就是链表）上。
读者可以这样认为，unordered_multiset 除了能存储相同值的元素外，它和 unordered_set 容器完全相同。

• unordered_multiset 容器类模板的定义如下：

template < class Key,            //容器中存储元素的类型
           class Hash = hash<Key>,    //确定元素存储位置所用的哈希函数
           class Pred = equal_to<Key>,   //判断各个元素是否相等所用的函数
           class Alloc = allocator<Key>   //指定分配器对象的类型
           > class unordered_multiset;

• demo

#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
    std::unordered_multiset<int> umset{ 1,2,2,2,3,4,5 };
    cout << "multiset size = " << umset.size() << endl;
    cout << "multiset count(2) =" << umset.count(2) << endl;

    //删除容器中所有值为 2 的元素
    int num = umset.erase(2);
    cout << "删除了 " << num << " 个元素 2" << endl;
    //输出容器中存储的所有元素
    for (auto iter = umset.begin(); iter != umset.end(); ++iter) {
        cout << *iter << " ";
    }

    cout << "umset.bucket_count() = "<< umset.bucket_count();
    return 0;
}

• 输出

multiset size = 7
multiset count(2) =3
删除了 3 个元素 2
1 3 4 5 umset.bucket_count() = 8

参考：
1、C++ STL 容器库 中文文档
2、STL教程：C++ STL快速入门
3、https://www.apiref.com/cpp-zh/cpp/header.html
4、https://en.cppreference.com/w/cpp/container