C++中unordered_map和unordered_set的使用

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

// 插入函数：插入元素到容器
// 参数：待插入的值
// 返回：pair<迭代器,bool>
//      迭代器指向插入位置或已存在元素位置
//      bool为true表示插入成功,false表示已存在
pair<iterator,bool> 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<unordered_set>  // 无序集合容器
#include<unordered_map> // 无序映射容器  
#include<set>          // 有序集合容器
#include<iostream>
using namespace std;

int test_set2()
{
    const size_t n = 1000000;  // 测试数据量100万
    unordered_set<int> us;     // 声明无序集合
    set<int> s;                // 声明有序集合
    vector<int> 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;
}

// 插入函数
// 参数：要插入的键值对或元素值
// 返回：pair<迭代器,bool>组合
//      迭代器指向插入位置或已存在元素位置
//      bool表示是否插入成功(true插入成功,false表示已存在)
pair<iterator,bool> 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);

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

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

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

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

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

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

    private:
        // 底层哈希表对象
        // k: 键类型
        // pair<k,v>: 存储的值类型
        // mapkeyoft: 提取键的仿函数
        hash_bucket::hashtable<k, pair<k, v>, mapkeyoft> _ht;
    };
}

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

namespace bit
{
    // unordered_set类模板，实现无序集合
    // 特点：不重复、无序、只存储key
    template<class k>
    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<k, k, setkeyoft>::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<k, k, setkeyoft> _ht;
    };
}