当前位置:

首页 > 编程开发 > C++中unordered_map和unordered_set的使用

C++中unordered_map和unordered_set的使用

无序集合(unordered_set)和无序映射(unordered_map)基于哈希表,增删查平均时间复杂度为常数。要求键必须可哈希且支持相等比较。迭代器为单向,遍历结果无序。在大多数应用场景下,其性能优于基于红黑树的有序集合(set)。注意哈希冲突可能导致最坏情况退化。

本文目录

    1. unordered_set系列的使用

    1.1 unordered_set和unordered_multiset参考文档

    参考文档

    C++中unordered_map和unordered_set的使用

    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;
        };
    }
    
    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发
    相关文章 更多
    n8n 2.49.0 与 3.3.0 预发布版如何保存和隔离工具调用记录?
    n8n 2.49.0 与 3.3.0 预发布版如何保存和隔离工具调用记录?

    n8n 2.49.0 与 3.3.0 预发布版对 AI Agent 作了三处调整。工具调用前的模型文本进入 Agent 历史,每条输入单独保存工具调用历史,一次对话中的每轮工具调用都写入聊天记忆。

    OpenBot v1.1.0-rc.2 的个人版请求需要哪些凭证?
    OpenBot v1.1.0-rc.2 的个人版请求需要哪些凭证?

    OpenBot v1.1.0-rc.2 的个人版请求需要能表明安装身份的凭证。桌面窗口沿用受信任入口建立的会话,程序可携带安装令牌,访问 /api/v2 时还可使用个人 API 密钥。过去直接发出的无凭证请求会被拒绝。

    llama.cpp b12469 的隐式矩阵乘法需要怎样的硬件能力?
    llama.cpp b12469 的隐式矩阵乘法需要怎样的硬件能力?

    llama.cpp b12469 的 Metal CONV_2D 增加隐式 GEMM。能否走新内核取决于设备是否支持 simdgroup 矩阵指令等实际分派条件。

    Google Gerrit Code Review 1.0.0 怎样查看补丁并处理外部审查内容?
    Google Gerrit Code Review 1.0.0 怎样查看补丁并处理外部审查内容?

    Google Gerrit Code Review 1.0.0 安装和只读查询示例,说明主机、工具权限、外部内容及评论投票的确认边界。

    llama.cpp b12466 的 SiLU 兼容范围扩大到哪里?
    llama.cpp b12466 的 SiLU 兼容范围扩大到哪里?

    llama.cpp b12466 调整了 OpenCL 的 SiLU 路径。新增的支持包括 f16,以及元素在内存中不连续的 f32 张量。

    llama.cpp b12468 的 WebGPU 时间步嵌入适用哪些项目?
    llama.cpp b12468 的 WebGPU 时间步嵌入适用哪些项目?

    llama.cpp b12468 的 WebGPU 变化集中在时间步嵌入。项目合并说明将 stable-diffusion.cpp 列作依赖该算子的下游项目示例。

    OpenCode PTY 0.6.0 哪些运行中的终端受协议 9 升级影响?
    OpenCode PTY 0.6.0 哪些运行中的终端受协议 9 升级影响?

    受影响的是旧协议守护进程承载的命令和持久终端。切换时旧实例会关闭,新服务在首次需要时再启动。

    llama.cpp b12465 的 SYCL 快速取模适用哪些路径?
    llama.cpp b12465 的 SYCL 快速取模适用哪些路径?

    llama.cpp b12465。llama.cpp b12465 的快速取模用在 SYCL 广播相关的索引运算。一次内核启动可复用同一组预计算值,前提是除数非零且能放入 32 位。

    Plannotator v0.28.67如何防止附件脚本切换线程和保存失败清空配置
    Plannotator v0.28.67如何防止附件脚本切换线程和保存失败清空配置

    Plannotator v0.28.67 让 HTML 附件脚本失去自行切换 Inbox 线程的能力,并在安全写入失败时保留 config.json 和 state.json。两项保护分别针对附件预览行为和本地配置文件。

    AG2 1.3.1沙箱、MCP Apps与A2UI兼容变化分别意味着什么
    AG2 1.3.1沙箱、MCP Apps与A2UI兼容变化分别意味着什么

    解释AG2 1.3.1的A2UI version与protocol_version差异、E2B和boxd后端、MCP Apps连接与独立缓存写入统计,提供只读包版本查询。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。