C++中unordered_map和unordered_set的使用

1. unordered_set系列的使用

1.1 unordered_set和unordered_multiset参考文档

参考文档

1.2 unordered_set类的介绍

unordered_set的声明中，Key就是底层关键字的类型。默认情况下，它要求Key支持转换为整型——如果Key本身不支持，或者你想按自己的逻辑来，完全可以自己实现一个将Key转为整型的仿函数，传给第二个模板参数。同样地，unordered_set默认要求Key支持比较相等，如果不符合要求，也可以自己实现比较相等的仿函数传给第三个参数。至于底层存储数据的内存，是从空间配置器申请的，有需要的话可以自己实现内存池，传给第四个参数。

当然，绝大多数情况下，我们根本不需要动后三个模板参数。unordered_set底层是用哈希桶实现的，增删查的平均效率是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)。下面这段代码展示了常见的接口函数。

// 插入函数
// 参数：要插入的键值对或元素值
// 返回：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;
    };
}