c++中map、multimap、unordered_map、unordered_multimap的区别

羽林君 2021-12-20 23:17

前言:

c++的各种容器使用的时候很方便,但是如果作为一个初学者,看到一堆库要记住也是很头疼的,而且很多库名称会很相似,所以我们要很好的使用这些库的时候,我们需要了解清楚它们底层实现的原理,这样我们使用中就更加得心应手。

今天给大家分享一下mapmultimapunordered_mapunordered_multimap,看上去是不是很相似,今天就来描述几者的区别。

作者:良知犹存

转载授权以及围观:欢迎关注微信公众号:羽林君

或者添加作者个人微信:become_me


几种容器的初步介绍:

map简介

map是STL的一个关联容器,map 容器中所有的元素都会根据元素对应的键值来排序,而键值key 是唯一值,并不会出现同样的键值key,也就是说假设已经有一个键值key 存在map 里,当同样的键值key 再insert 资料时,新的资料就会覆盖掉原本key 的资料。

map 的实作方式通常是用红黑树(red-black tree)实作的,这样它可以保证可以在O(log n)时间内完成搜寻、插入、删除,n为元素的数目。

常用函数

函数名作用
begin返回一个指向集合中第一个元素的迭代器
end返回指向末尾的迭代器
empty如果set为空,则返回true
size返回集合中元素的数量
insert在集合中插入元素
erase从集合中擦除元素
swap交换集合的内容
clear删除集合中的所有元素
emplace构造新元素并将其插入到集合中
find搜索具有给定键的元素
count获取与给定键匹配的元素数

注意: 这里map的键值 key是不可以重复的,在实际使用中,如果用map[key] = xxx,其中key已经存在的情况下,key对应的元素会被覆盖掉,如果是用insert方式进行覆盖则会失败。

下面代码里面用到了 first和second

map.first:第一个称为(key)键值
map.second:第二个称为(key)键值对应的数值(value)

#include 
#include 
using namespace std;
int main()
{
    std::map studentMap = {
    {1, "Tom"},
    {7, "Mali"},
    {15, "John"}};

    for(auto i:studentMap2)
    {
        cout<" "
            <        cout<    }
    std::pair::iterator, bool> retPair;
    retPair = studentMap.insert(std::pair(15, "Bob"));  
    
    for(auto i:studentMap)
    {
        cout<" "
            <        cout<    }   


    studentMap[15] = "Lily";

    for(auto i:studentMap)
    {
        cout<" "
            <        cout<    }    
    
    cout<    studentMap.erase(15);
    for(auto i:studentMap)
    {
        cout<" "
            <        cout<    }    
}

输出结果如图所示:

multimap简介

multimaps是关联式容器,它按照特定的顺序,存储由key和value映射成的键值对,其中多个键值对之间的key是可以重复的,multimap在底层用二叉搜索树(红黑树)来实现。

在内部,multimap中的元素总是通过其内部比较对象,按照指定的特定严格弱排序标准对key进行排序的。和map最大的区别,multimap中的key是可以重复的。

常用函数参照map函数使用

#include 
#include 
using namespace std;
int main()
{
    std::multimap studentMap2 = {
    {"first""Tom"},
    {"second""Mali"},
    {"third""John"}};    


    studentMap2.insert(std::pair("first""Bob"));  
    
    cout<< "output:"<    for (std::multimap::iterator it = studentMap2.begin(); it != studentMap2.end(); it++) {
        std::cout << (*it).first << ", " << (*it).second << "\n";
    }
    std::cout << studentMap2.count("first") <
}

以上代码可以进行debug 进行查看,一个键值对应多个元素,对应数据排列的情况如下:

冲突的元素会使用元素链接的方式保存。


注意:multimap中没有重载operator[]操作。

所以我们无法使用 multimap[key]进行访问数据,是因为multimap的key可以对应多个数据,所以下标访问是没有意义的。


unordered_map简介

unordered_map 内部实现了一个哈希表(也叫散列表,通过把关键码值映射到Hash表中一个位置来访问记录,查找的时间复杂度可达到O(1),其在海量数据处理中有着广泛应用)。因此,其元素的排列顺序是无序的。容器中每个元素都是 key/value,每个 key 仅可出现一次

unordered_map 特点就是搜寻效率高,利用键值与哈希函数(hash function)计算出哈希值而快速的查找到对应的元素,时间复杂度为常数级别O(1), 而额外空间复杂度则要高出许多。unordered_map 与map 的使用方法基本上一样,都是key/value 之间的映射,只是他们内部采用的资料结构不一样。所以对于需要高效率查询的情况可以使用unordered_map 容器。而如果对记忆体消耗比较敏感或者资料存放要求排序的话则可以用map 容器。

常用函数参照map函数使用

#include 
#include 
using namespace std;
int main()
{
   std::unordered_map < std::string , int > studentUMap3 = { 
        { "Tom" , 1 }, 
        { "Ann" , 4 }, 
        { "Job" , 2 } 
    };

   studentUMap3.insert(std::pair("Job", 5));  
    

    cout<< "output:"<    for (auto it = studentUMap3.begin(); it != studentUMap3.end(); it++) {
        std::cout << (*it).first << ", " << (*it).second << "\n";
    }

    cout<    studentUMap3["Job"] = 3;
    for (auto it = studentUMap3.begin(); it != studentUMap3.end(); it++) {
        std::cout << (*it).first << ", " << (*it).second << "\n";
    }
}

unordered_map用法和map基本一致,但是考虑的访问的速度有要求的情况下,我们优先使用,unordered_map;要是考虑到空间大小对程序影响的时候,我们优先使用map。

unordered_multimap简介

unordered_multimap 是一个封装哈希表的无序容器。容器中每个元素都是 key/value,每个 key 可重复出现

同map和unordered_map区别一样,multimap通过key访问单个元素的速度通常也比unordered_multimap容器慢。常用函数参照map函数使用

#include 
#include 
using namespace std;
int main()
{
   std::unordered_multimap < int , int > studentUMap4;
    studentUMap4.insert(std::pair(1, 333));
    studentUMap4.insert(std::pair(3, 555));
    studentUMap4.insert(std::pair(5, 666));


   studentUMap4.insert(std::pair(5, 5));  
    

    cout<< "output:"<    for (auto it = studentUMap4.begin(); it != studentUMap4.end(); it++) {
        std::cout << (*it).first << ", " << (*it).second << "\n";
    }

    std::cout <<"count:"<< studentUMap4.count(5) <    std::cout <<"size: "<< studentUMap4.size() <    std::cout <<"empty?"<< studentUMap4.empty()<<"\n" <

    std::unordered_multimap < int , int >studentUMap5;
    studentUMap5.swap(studentUMap4);
    std::cout <<"count:"<< studentUMap4.count(5) <    std::cout <<"size: "<< studentUMap4.size() <    std::cout <<"empty?"<< studentUMap4.empty()<<"\n" <

    std::cout <<"count:" <"\n" <

    studentUMap5.clear();
    std::cout <<"size: " <    std::cout <<"empty?"<}

重复元素对应的debug显示

代码执行输出显示

区别介绍

首先这几个容器都是关联容器,其中无论是有序关联容器还是有序关联容器都是基于(set:集合 key  map:映射表  [key : value])

来自wiki

关联容器是指C++标准模板库中的一套类模板,实现了有序关联数组。可用于存放任意数据类型的元素。C++标准中定义的关联容器有:set, map, multiset, multimap。

关联容器类似于C++中的无序关联容器。差别为:

  • 关联容器是红黑树实现,无序关联容器是哈希表实现。
  • 关联容器保证按键值有序遍历,因此可以做范围查找,而无序关联容器不可以。
  • 关联支持一些导航类的>>操作,如求出给定键最邻近的键,最大键、最小键操作。
  • 关联容器的迭代器不会失效,除非所指元素被删除。
  • 无序关联容器的iterator在修改元素时可能会失>>效。所以对关联容器的遍历与修改在一定程度上可并行
  • 哈希表查找时候要算hash,这个最坏时间复杂度是O(key的长度);基于比较的有序关联容器通常只使用>头几个字符进行比较

关联容器不支持顺序容器的位置相关的操作,例如 push_front 或 push_back 操作。原因是关联容器中>的元素是根据关键字来存储的,这些操作对于关联容器没有意义。

关联容器也不支持构造函数或插入操作这些接收一个元素值和一个数量值的操作。

因为map和multimap unordered_map和unordered_multimap两两区分时候,从底层实现来说,区别不是很大,所以我们先进行map与multimap的区别,再进行map和unordered_map区别比较。其他的类比即可。

最直观的区别:

map和unordered_map;//key不允许重复,是单重映射表
multimap和unordered_multimap;//key允许重复,是多重映射表

实现机制的区别:

map和unordered_map的区别:内部实现机理不同

  • map :map内部实现了一个红黑树(红黑树是非严格平衡二叉搜索树,而AVL是严格平衡二叉搜索树),红黑树具有自动排序的功能,因此map内部的所有元素都是有序的,红黑树的每一个节点都代表着map的一个元素。因此,对于map进行的查找、删除,添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树 (又名儿茶查找树、二叉排序树–特点就是左子树上所有节点的键值都小于根节点的键值,右子树所有节点的键值都大于根结点的键值)存储的,使用中序遍历可将键值按照从小到大遍历出来。map和multimap的区别在于,map不允许相同key值存在,multimap则允许相同的key值存在。

  • unordered_map :unordered_map内部实现了一个哈希表 (也叫散列表,通过把关键码值映射到Hash表中一个位置来访问记录,查找的时间复杂度可达到O(1),其在海量数据处理中有着广泛应用)。因此,其元素的排列顺序都是无序的。unordered_map 和 unordered_multimap 都是基于哈希表实现的,而且冲突策略采用的是链地址法。

使用的角度

空间占用率和效率上

unorder_map占用的内存更加高一点,unorder_map内部采用hash表,map内部采用的是红黑树,内存占有率的问题转化成hash表 VS 红黑树,还是unorder_map内存要高一点.

但是unorder_map采用哈希表搜索,搜寻效率高,利用键值与哈希函数(hash function)计算出哈希值而快速的查找到对应的元素,时间复杂度为常数级别O(1)

在关键字类型的元素没有明显的序的情况下,或者在某些应用中,维护元素有序的代价非常高昂,采用无序容器代替map来说效果会好。

结语

这就是我对mapmultimapunordered_mapunordered_multimap几者的分享,有机会可以给大家一起分享一下set, multisetunordered_set, unordered_multiset的使用与区别。如果大家有更好的想法和需求,也欢迎大家加我好友交流分享哈。


作者:良知犹存,白天努力工作,晚上原创公号号主。公众号内容除了技术还有些人生感悟,一个认真输出内容的职场老司机,也是一个技术之外丰富生活的人,摄影、音乐 and 篮球。关注我,与我一起同行。

                              ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧  END  ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧

推荐阅读

【1】在球场上我向人民币玩家低了头

【2】Linux开发coredump文件分析实战分享

【3】CPU中的程序是怎么运行起来的 必读

【4】cartographer环境建立以及建图测试

【5】设计模式之简单工厂模式、工厂模式、抽象工厂模式的对比

本公众号全部原创干货已整理成一个目录,回复[ 资源 ]即可获得。


羽林君 某嵌入式程序猿分享技术、生活、人生云云文字。如有诗云:去年今日此门中,人面桃花相映红。人面不知何处去,桃花依旧笑春风。
评论
  • 故障现象一辆2017款东风风神AX7车,搭载DFMA14T发动机,累计行驶里程约为13.7万km。该车冷起动后怠速运转正常,热机后怠速运转不稳,组合仪表上的发动机转速表指针上下轻微抖动。 故障诊断 用故障检测仪检测,发动机控制单元中无故障代码存储;读取发动机数据流,发现进气歧管绝对压力波动明显,有时能达到69 kPa,明显偏高,推断可能的原因有:进气系统漏气;进气歧管绝对压力传感器信号失真;发动机机械故障。首先从节气门处打烟雾,没有发现进气管周围有漏气的地方;接着拔下进气管上的两个真空
    虹科Pico汽车示波器 2025-01-08 16:51 113浏览
  • 「他明明跟我同梯进来,为什么就是升得比我快?」许多人都有这样的疑问:明明就战绩也不比隔壁同事差,升迁之路却比别人苦。其实,之间的差异就在于「领导力」。並非必须当管理者才需要「领导力」,而是散发领导力特质的人,才更容易被晓明。许多领导力和特质,都可以通过努力和学习获得,因此就算不是天生的领导者,也能成为一个具备领导魅力的人,进而被老板看见,向你伸出升迁的橘子枝。领导力是什么?领导力是一种能力或特质,甚至可以说是一种「影响力」。好的领导者通常具备影响和鼓励他人的能力,并导引他们朝着共同的目标和愿景前
    优思学院 2025-01-08 14:54 96浏览
  • 在过去十年中,自动驾驶和高级驾驶辅助系统(AD/ADAS)软件与硬件的快速发展对多传感器数据采集的设计需求提出了更高的要求。然而,目前仍缺乏能够高质量集成多传感器数据采集的解决方案。康谋ADTF正是应运而生,它提供了一个广受认可和广泛引用的软件框架,包含模块化的标准化应用程序和工具,旨在为ADAS功能的开发提供一站式体验。一、ADTF的关键之处!无论是奥迪、大众、宝马还是梅赛德斯-奔驰:他们都依赖我们不断发展的ADTF来开发智能驾驶辅助解决方案,直至实现自动驾驶的目标。从新功能的最初构思到批量生
    康谋 2025-01-09 10:04 93浏览
  • 光伏逆变器是一种高效的能量转换设备,它能够将光伏太阳能板(PV)产生的不稳定的直流电压转换成与市电频率同步的交流电。这种转换后的电能不仅可以回馈至商用输电网络,还能供独立电网系统使用。光伏逆变器在商业光伏储能电站和家庭独立储能系统等应用领域中得到了广泛的应用。光耦合器,以其高速信号传输、出色的共模抑制比以及单向信号传输和光电隔离的特性,在光伏逆变器中扮演着至关重要的角色。它确保了系统的安全隔离、干扰的有效隔离以及通信信号的精准传输。光耦合器的使用不仅提高了系统的稳定性和安全性,而且由于其低功耗的
    晶台光耦 2025-01-09 09:58 79浏览
  • 根据环洋市场咨询(Global Info Research)项目团队最新调研,预计2030年全球中空长航时无人机产值达到9009百万美元,2024-2030年期间年复合增长率CAGR为8.0%。 环洋市场咨询机构出版了的【全球中空长航时无人机行业总体规模、主要厂商及IPO上市调研报告,2025-2031】研究全球中空长航时无人机总体规模,包括产量、产值、消费量、主要生产地区、主要生产商及市场份额,同时分析中空长航时无人机市场主要驱动因素、阻碍因素、市场机遇、挑战、新产品发布等。报告从中空长航时
    GIRtina 2025-01-09 10:35 95浏览
  • 本文介绍编译Android13 ROOT权限固件的方法,触觉智能RK3562开发板演示,搭载4核A53处理器,主频高达2.0GHz;内置独立1Tops算力NPU,可应用于物联网网关、平板电脑、智能家居、教育电子、工业显示与控制等行业。关闭selinux修改此文件("+"号为修改内容)device/rockchip/common/BoardConfig.mkBOARD_BOOT_HEADER_VERSION ?= 2BOARD_MKBOOTIMG_ARGS :=BOARD_PREBUILT_DTB
    Industio_触觉智能 2025-01-08 00:06 118浏览
  • 1月7日-10日,2025年国际消费电子产品展览会(CES 2025)盛大举行,广和通发布Fibocom AI Stack,赋智千行百业端侧应用。Fibocom AI Stack提供集高性能模组、AI工具链、高性能推理引擎、海量模型、支持与服务一体化的端侧AI解决方案,帮助智能设备快速实现AI能力商用。为适应不同端侧场景的应用,AI Stack具备海量端侧AI模型及行业端侧模型,基于不同等级算力的芯片平台或模组,Fibocom AI Stack可将TensorFlow、PyTorch、ONNX、
    物吾悟小通 2025-01-08 18:17 84浏览
  • 在智能网联汽车中,各种通信技术如2G/3G/4G/5G、GNSS(全球导航卫星系统)、V2X(车联网通信)等在行业内被广泛使用。这些技术让汽车能够实现紧急呼叫、在线娱乐、导航等多种功能。EMC测试就是为了确保在复杂电磁环境下,汽车的通信系统仍然可以正常工作,保护驾乘者的安全。参考《QCT-基于LTE-V2X直连通信的车载信息交互系统技术要求及试验方法-1》标准10.5电磁兼容试验方法,下面将会从整车功能层面为大家解读V2X整车电磁兼容试验的过程。测试过程揭秘1. 设备准备为了进行电磁兼容试验,技
    北汇信息 2025-01-09 11:24 97浏览
  • 一个真正的质量工程师(QE)必须将一件产品设计的“意图”与系统的可制造性、可服务性以及资源在现实中实现设计和产品的能力结合起来。所以,可以说,这确实是一种工程学科。我们常开玩笑说,质量工程师是工程领域里的「侦探」、「警察」或「律师」,守护神是"墨菲”,信奉的哲学就是「墨菲定律」。(注:墨菲定律是一种启发性原则,常被表述为:任何可能出错的事情最终都会出错。)做质量工程师的,有时会不受欢迎,也会被忽视,甚至可能遭遇主动或被动的阻碍,而一旦出了问题,责任往往就落在质量工程师的头上。虽然质量工程师并不负
    优思学院 2025-01-09 11:48 114浏览
  •  在全球能源结构加速向清洁、可再生方向转型的今天,风力发电作为一种绿色能源,已成为各国新能源发展的重要组成部分。然而,风力发电系统在复杂的环境中长时间运行,对系统的安全性、稳定性和抗干扰能力提出了极高要求。光耦(光电耦合器)作为一种电气隔离与信号传输器件,凭借其优秀的隔离保护性能和信号传输能力,已成为风力发电系统中不可或缺的关键组件。 风力发电系统对隔离与控制的需求风力发电系统中,包括发电机、变流器、变压器和控制系统等多个部分,通常工作在高压、大功率的环境中。光耦在这里扮演了
    晶台光耦 2025-01-08 16:03 88浏览
  • 职场是人生的重要战场,既是谋生之地,也是实现个人价值的平台。然而,有些思维方式却会悄无声息地拖住你的后腿,让你原地踏步甚至退步。今天,我们就来聊聊职场中最忌讳的五种思维方式,看看自己有没有中招。1. 固步自封的思维在职场中,最可怕的事情莫过于自满于现状,拒绝学习和改变。世界在不断变化,行业的趋势、技术的革新都在要求我们与时俱进。如果你总觉得自己的方法最优,或者害怕尝试新事物,那就很容易被淘汰。与其等待机会找上门,不如主动出击,保持学习和探索的心态。加入优思学院,可以帮助你快速提升自己,与行业前沿
    优思学院 2025-01-09 15:48 98浏览
  • 村田是目前全球量产硅电容的领先企业,其在2016年收购了法国IPDiA头部硅电容器公司,并于2023年6月宣布投资约100亿日元将硅电容产能提升两倍。以下内容主要来自村田官网信息整理,村田高密度硅电容器采用半导体MOS工艺开发,并使用3D结构来大幅增加电极表面,因此在给定的占位面积内增加了静电容量。村田的硅技术以嵌入非结晶基板的单片结构为基础(单层MIM和多层MIM—MIM是指金属 / 绝缘体/ 金属) 村田硅电容采用先进3D拓扑结构在100um内,使开发的有效静电容量面积相当于80个
    知白 2025-01-07 15:02 169浏览
  • 在当前人工智能(AI)与物联网(IoT)的快速发展趋势下,各行各业的数字转型与自动化进程正以惊人的速度持续进行。如今企业在设计与营运技术系统时所面临的挑战不仅是技术本身,更包含硬件设施、第三方软件及配件等复杂的外部因素。然而这些系统往往讲究更精密的设计与高稳定性,哪怕是任何一个小小的问题,都可能对整体业务运作造成严重影响。 POS应用环境与客户需求以本次分享的客户个案为例,该客户是一家全球领先的信息技术服务与数字解决方案提供商,遭遇到一个由他们所开发的POS机(Point of Sal
    百佳泰测试实验室 2025-01-09 17:35 101浏览
  • By Toradex 秦海1). 简介嵌入式平台设备基于Yocto Linux 在开发后期量产前期,为了安全以及提高启动速度等考虑,希望将 ARM 处理器平台的 Debug Console 输出关闭,本文就基于 NXP i.MX8MP ARM 处理器平台来演示相关流程。 本文所示例的平台来自于 Toradex Verdin i.MX8MP 嵌入式平台。  2. 准备a). Verdin i.MX8MP ARM核心版配合Dahlia载板并
    hai.qin_651820742 2025-01-07 14:52 131浏览
  • HDMI 2.2 规格将至,开启视听新境界2025年1月6日,HDMI Forum, Inc. 宣布即将发布HDMI规范2.2版本。新HDMI规范为规模庞大的 HDMI 生态系统带来更多选择,为创建、分发和体验理想的终端用户效果提供更先进的解决方案。新技术为电视、电影和游戏工作室等内容制作商在当前和未来提供更高质量的选择,同时实现多种分发平台。96Gbps的更高带宽和新一代 HDMI 固定比率速率传输(Fixed Rate Link)技术为各种设备应用提供更优质的音频和视频。终端用户显示器能以最
    百佳泰测试实验室 2025-01-09 17:33 107浏览
我要评论
0
点击右上角,分享到朋友圈 我知道啦
请使用浏览器分享功能 我知道啦