1. C++ unordered_set系列容器使用详解

1.1 unordered_set与unordered_multiset参考文档指引

官方参考文档

1.2 unordered_set容器类介绍

在unordered_set的声明中，Key代表底层关键字的类型。默认情况下，该类型必须支持转换为整型——如果Key本身不满足该条件，或者您希望按照自定义逻辑处理，完全可以自行实现一个将Key转换为整型的仿函数，并将其作为第二个模板参数传入。同理，unordered_set默认要求Key支持相等比较运算符，若不符合要求，你也可以自定义比较相等的仿函数并传给第三个参数。至于底层存储数据的内存，默认由空间配置器分配，若有特殊需求，可以自行实现内存池，并作为第四个参数传入。

当然，在绝大多数实际开发场景中，我们完全不需要修改后三个模板参数。unordered_set底层基于哈希桶（hash bucket）实现，其增删查操作的平均时间复杂度为O(1)，但迭代器遍历不再保证有序——为了与set区分，因此命名为unordered_set。此前我们已经学习过set容器的使用方法，set与unordered_set在功能上高度相似，仅因底层数据结构不同而产生一些性能与使用上的差异。本节将重点讨论这些差异。

// unordered_set模板声明：一个不保证元素顺序的集合容器
template < 
    class Key,     // 键与值的类型(因为是集合，键就是值)
                   // 例如：unordered_set, unordered_set
    
    class Hash = hash,    // 哈希函数对象类型,用于计算元素的哈希值
                              // 默认使用标准库的hash
    
    class Pred = equal_to,    // 判断两个键是否相等的函数对象类型
                                   // 默认使用标准库的equal_to
    
    class Alloc = allocator   // 内存分配器类型
                                   // 默认使用标准分配器allocator
> 
class unordered_set;

1.3 unordered_set与set的使用差异对比

查阅文档可以发现，unordered_set的增删查操作接口与set完全一致，使用方法完全相同，此处不再重复演示。它们之间的主要差异集中体现在以下三个方面。

第一个差异：对Key类型的要求不同。 set要求Key必须支持小于比较（因为底层是红黑树，需要排序），而unordered_set要求Key必须支持转换为整型并支持相等比较。要深刻理解这两点，需要结合哈希表的底层实现原理——这本质上是哈希表本身对键类型的要求。

第二个差异：迭代器类型与遍历结果不同。 set的iterator是双向迭代器，而unordered_set是单向迭代器。更重要的是，set底层采用红黑树，中序遍历可以保证有序，因此set迭代器遍历的结果是“有序且去重”；而unordered_set底层采用哈希表，迭代器遍历的结果是“无序且去重”。

第三个差异：性能表现不同。 总体而言，在大多数应用场景下，unordered_set的增删查改操作速度更快。红黑树的增删查改时间复杂度为O(log n)，而哈希表的平均时间复杂度为O(1)。下面的代码通过实际测试直观对比了两者的性能差异。

// 插入函数：插入元素到容器
// 参数：待插入的值
// 返回：pair<迭代器,bool>
//      迭代器指向插入位置或已存在元素位置
//      bool为true表示插入成功,false表示已存在
pair insert(const value_type& val);

// 删除函数：删除指定key的元素
// 参数：要删除的key
// 返回：删除的元素个数(0表示元素不存在,1表示删除成功)
size_type erase(const key_type& k);

// 查找函数：查找指定key的元素
// 参数：要查找的key
// 返回：指向找到元素的迭代器,未找到返回end()
iterator find(const key_type& k);

#include  // 无序集合容器
#include // 无序映射容器  
#include          // 有序集合容器
#include
using namespace std;

int test_set2()
{
    const size_t N = 1000000;  // 测试数据量100万
    unordered_set us;     // 声明无序集合
    set s;                // 声明有序集合
    vector v;             // 存储测试数据的vector
    v.reserve(N);              // 预留空间,避免动态扩容
    srand(time(0));            // 随机种子
    
    // 生成测试数据
    for (size_t i = 0; i < N; ++i)
    {
        //v.push_back(rand());     // N较大时重复值较多
        v.push_back(rand()+i);     // 加上i使重复值较少
        //v.push_back(i);          // 完全有序无重复
    }

    // 测试set的插入性能
    size_t begin1 = clock();
    for (auto e : v)
    {
        s.insert(e);
    }
    size_t end1 = clock();
    cout << "set insert:" << end1 - begin1 << endl;

    // 测试unordered_set的插入性能
    size_t begin2 = clock();
    us.reserve(N);             // 预留空间,避免rehash
    for (auto e : v)
    {
        us.insert(e);  
    }
    size_t end2 = clock();
    cout << "unordered_set insert:" << end2 - begin2 << endl;

    // 测试set的查找性能
    int m1 = 0;                // 记录查找成功次数
    size_t begin3 = clock();
    for (auto e : v)
    {
        auto ret = s.find(e);
        if (ret != s.end())    // 找到元素
        {
            ++m1;
        }
    }
    size_t end3 = clock();
    cout << "set find:" << end3 - begin3 << "->" << m1 << endl;

    // 测试unordered_set的查找性能
    int m2 = 0;                // 记录查找成功次数
    size_t begin4 = clock();
    for (auto e : v)
    {
        auto ret = us.find(e);
        if (ret != us.end())   // 找到元素
        {
            ++m2;
        }
    }
    size_t end4 = clock();
    cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl;

    // 输出实际插入数据量(因为有重复值,所以小于N)
    cout << "插入数据个数：" << s.size() << endl;
    cout << "插入数据个数：" << us.size() << endl << endl;

    // 测试set的删除性能
    size_t begin5 = clock();
    for (auto e : v)
    {
        s.erase(e);
    }
    size_t end5 = clock();
    cout << "set erase:" << end5 - begin5 << endl;

    // 测试unordered_set的删除性能
    size_t begin6 = clock();
    for (auto e : v)
    {
        us.erase(e);
    }
    size_t end6 = clock();
    cout << "unordered_set erase:" << end6 - begin6 << endl << endl;

    return 0;
}

int main()
{
    test_set2();    // 执行性能测试
    return 0;
}

1.4 unordered_map与map的使用差异分析

类似地，unordered_map的增删查改操作与map完全一致，用法不再赘述。它们之间的差异同样集中在三个方面：

对Key的要求不同。 map要求Key支持小于比较，而unordered_map要求Key支持转换为整型并支持相等比较——这同样是哈希表底层实现的要求。

迭代器差异。 map的iterator是双向迭代器，unordered_map是单向迭代器。map底层采用红黑树，中序遍历保证有序，因此map迭代器遍历的结果是Key有序且去重；而unordered_map底层采用哈希表，遍历结果是Key无序且去重。

性能差异。 在大多数场景下，unordered_map的增删查改速度更快，红黑树时间复杂度为O(log n)，哈希表平均为O(1)。下面的代码展示了unordered_map常见的接口函数。

// 插入函数
// 参数：要插入的键值对或元素值
// 返回：pair<迭代器,bool>组合
//      迭代器指向插入位置或已存在元素位置
//      bool表示是否插入成功(true插入成功,false表示已存在)
pair insert(const value_type& val);

// 删除函数
// 参数：要删除元素的key
// 返回：实际删除的元素个数
//      对于set/map返回0(不存在)或1(删除成功)
size_type erase(const key_type& k);

// 查找函数
// 参数：要查找的key
// 返回：指向找到元素的迭代器
//      如果没找到返回end()迭代器
iterator find(const key_type& k);

// map中的[]运算符重载
// 参数：关键字key
// 返回：key对应的value的引用
// 特点：如果key不存在则自动插入,value默认初始化
mapped_type& operator[](const key_type& k);

1.5 unordered_multimap与unordered_multiset

unordered_multimap和unordered_multiset与multimap/multiset功能完全类似，支持Key重复（冗余）。它们之间的差异同样体现在三个方面：对Key的要求不同、迭代器类型及遍历顺序不同、性能表现不同。

1.6 UnOrderedMap.h代码实现解析

UnOrderedMap.h

#pragma once  // 防止头文件被重复包含
#include"HashTable.h"  // 引入哈希表的实现

namespace bit
{
    // unordered_map类模板，实现键值对的无序映射
    template
    class unordered_map
    {
        // 仿函数类，用于从pair中提取key值
        struct MapKeyOfT
        {
            // 重载()运算符，返回pair中的first成员(键值)
            const K& operator()(const pair& kv)
            {
                return kv.first;
            }
        };

    public:
        // 使用类型别名简化迭代器类型的书写
        // 注意这里的模板参数：
        // K: 键类型
        // pair: 实际存储的值类型(键值对)
        // MapKeyOfT: 提取键的仿函数
        typedef typename hash_bucket::HashTable, MapKeyOfT>::iterator iterator;

        // 返回容器的起始迭代器
        iterator begin()
        {
            return _ht.begin();
        }

        // 返回容器的结束迭代器
        iterator end()
        {
            return _ht.end();
        }

        // 插入键值对
        // 参数kv: 要插入的键值对
        // 返回值: 插入是否成功
        bool insert(const pair& kv)
        {
            return _ht.Insert(kv);
        }

    private:
        // 底层哈希表对象
        // K: 键类型
        // pair: 存储的值类型
        // MapKeyOfT: 提取键的仿函数
        hash_bucket::HashTable, MapKeyOfT> _ht;
    };
}

1.7 UnOrderedSet.h代码实现详解

UnOrderedSet.h

#pragma once  // 防止头文件被重复包含
#include"HashTable.h"  // 引入哈希表的实现

namespace bit
{
    // unordered_set类模板，实现无序集合
    // 特点：不重复、无序、只存储key
    template
    class unordered_set
    {
        // 仿函数类，用于返回key值本身
        // 因为set只存储key，所以key和value是同一个值
        struct SetKeyOfT
        {
            // 重载()运算符，直接返回key
            const K& operator()(const K& key)
            {
                return key;
            }
        };

    public:
        // 使用类型别名简化迭代器类型的书写
        // 注意这里的模板参数：
        // K: 键类型
        // K: 值类型(与键相同)
        // SetKeyOfT: 提取键的仿函数
        typedef typename hash_bucket::HashTable::iterator iterator;

        // 返回容器的起始迭代器
        iterator begin()
        {
            return _ht.begin();
        }

        // 返回容器的结束迭代器
        iterator end()
        {
            return _ht.end();
        }

        // 插入元素
        // 参数key: 要插入的值
        // 返回值: 插入是否成功（如果元素已存在则返回false）
        bool insert(const K& key)
        {
            return _ht.Insert(key);
        }

    private:
        // 底层哈希表对象
        // K: 键类型
        // K: 值类型(与键相同)
        // SetKeyOfT: 提取键的仿函数
        hash_bucket::HashTable _ht;
    };
}