宜兰县网站建设_网站建设公司_CSS_seo优化

前言：在上一篇文章中，我们介绍了二叉搜索树这种树形结构，它与之前学过的序列式容器有所不同。本文将重点讲解基于二叉搜索树实现的另外一个容器：map。它的底层实现也采用了平衡二叉搜索树。

一、map的认识

1.1 map的基本概念

map:
是一种键值对（key-value）容器，每个元素包含一个唯一的键（key）和对应的值（value）。键用于排序和唯一标识元素，值存储与键关联的数据。

map的特点：

• 有序性：元素按键的升序自动排序。
• 唯一性：每个键在map中只能出现一次。(不含重复数据)
• 操作复杂度：插入、删除和查找操作的平均时间复杂度为 O(log n)。

二、map的使用

1、map模板参数介绍：

关于map的声明有以下一些注意事项：

• 第一个模板参数：key，Key就是map底层关键字的类型。
• 第二个模板参数：T(V)，T(V)是map底层value的类型。
• 第三个模板参数：比较器，set默认要求Key支持小于较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数。
• 第三个模板参数：空间配置器，一般情况下不需要传。

2、pair的介绍

• pair是C++标准库中的一个模板类，用于存储两个不同类型的值，通常用于键值对的表示。其定义在头文件中，基本形式为std::pair<T1, T2>。T1就是key，T2就是value。
• map是C++标准库中的关联容器，用于存储键值对（key-value pairs），且键唯一。其定义在

map与pair的联系：

map的每个元素本质上是一个pair对象，具体为std::pair<const Key, T(Value)>。键（Key）被声明为const以确保不可修改，只有(value)才能被修改。

为什么要有pair？

从数据访问的角度，在前面的二叉搜索树实现的过程中，我们通常是将key和value放在一个结点里面，要访问结点里面key或value只能通过这个结点去访问，但是如果我们结点里存的是一个pair那么拿到一个pair就能同时得到key和value的值，这样可以明确的表示这两个数据的关联性，避免键和值单独管理。也有利于数据的访问。

2.1map的构造和迭代器

对于map的构造我们关注以下几个接口即可：

代码示例：

#include<iostream>#include<map>usingnamespacestd;voidtest_map1(){//无参默认构造map<string,string>dict;//初始化列表构造map<string,string>dict1={{"left","左边"},{"right","右边"},{"sort","排序"}};//拷贝构造map<string,string>dict2(dict1);//迭代器区间构造map<string,string>dict3(dict1.begin(),dict1.end());}

2、map的迭代器

map的迭代器是一个双向迭代器，所以map支持正向和反向迭代遍历，默认按照key的升序顺序遍历，这是因为其底层采用二叉搜索树结构，迭代器遍历遵循中序遍历方式。由于支持迭代器，map自然也支持范围for。需要注意的是：map允许修改value数据，但禁止修改key数据，因为修改关键字会破坏底层搜索树的结构。

代码示例：

#include<iostream>#include<map>usingnamespacestd;voidtest_map2(){//初始化列表构造map<string,string>dict1={{"left","左边"},{"right","右边"},{"sort","排序"}};//正向遍历for(auto&e:dict1){cout<<e.first<<":"<<e.second<<" ";}cout<<endl;//反向迭代autoit=dict1.rbegin();while(it!=dict1.rend()){//map中的key是不能被修改的 只有value能被修改//(*it).first = "xxx";//key不能被修改！！！//(*it).second = "xxxx";cout<<(*it).first<<":"<<(*it).second<<" ";//cout << it->first << ":" << it->second<< " ";it++;}cout<<endl;for(auto&[k,v]:dict){cout<<k<<":"<<v<<endl;}// 结构化绑定 C++14/17auto[x,y]=kv1;auto&[x1,y1]=kv1;x1+='x';x+='k';}

2.2 map的增删查操作

1、插入数据

map的插入接口主要掌握以下几个接口：

代码示例：

#include<iostream>#include<map>usingnamespacestd;voidtest_map3(){//map底层其实存的是pair(键值对)pair<string,string>kv1("left","左边");pair<string,string>kv2("right","右边");pair<string,string>kv3("sort","排序");pair<string,string>kv4("const","常量");map<string,string>dict={kv1,kv2,kv3,kv4};dict.insert({"left","哈哈"});//若键'left'已经存在则插入失败dict.insert(pair<string,string>("sort","排序"));//插入一个pairdict.insert(make_pair("hello","你好"));//插入还可以使用make_pairdict.insert({"people","人"});//隐式类型转化//列表插入autopos=dict.begin();dict.insert(pos,{"English","英文"});vector<pair<string,string>>v={{"k1","v1"},{"k2","v2"},{"k3","v3"}};//迭代器区间插入dict.insert(v.begin(),v.end());for(constauto&e:dict){cout<<e.first<<":"<<e.second<<" ";}cout<<endl;}

2、find/count和erase

代码示例：

voidtest_map4(){string arr[]={"苹果","香蕉","梨","草莓","香蕉","梨","苹果","梨","苹果"};map<string,int>m;for(auto&str:arr){//map<string, int>::iterator it = m.find(str);autoit=m.find(str);if(it!=m.end()){//找到了 就加加it->second++;}else{//没找到就插入m.insert({str,1});}}for(auto&e:m){cout<<e.first<<":"<<e.second<<" ";}cout<<endl;string arr2[]={"苹果","香蕉","梨","草莓","香蕉","梨","苹果","梨","苹果"};map<string,int>m2;//使用count也可以代替findfor(auto&e:arr){if(m2.count(e)){//如果元素已经存在 ++该key对应的value值即可m2[e]++;//operator[]的使用会在后面介绍}else{//没找到就插入m2.insert({e,1});}}for(auto&e:m2){cout<<e.first<<":"<<e.second<<" ";}cout<<endl;//删除一个指定的keym.erase("草莓");for(auto&e:m){cout<<e.first<<":"<<e.second<<" ";}cout<<endl;//删除一个迭代器位置的key 注意key被删除了那么value也跟着直接被删除了！！！autopos=m.find("香蕉");if(pos!=m.end()){m.erase(pos);}for(auto&e:m){cout<<e.first<<":"<<e.second<<" ";}cout<<endl;//删除一段迭代器区间的keym2.erase(m2.begin(),m2.end());}

运行结果：

3、lower_bound和upper_bound的使用

lower_bound：返回指向第一个不小于给定键的元素的迭代器。如果键不存在，返回指向第一个大于该键的元素。
upper_bound：返回指向第一个大于给定键的元素的迭代器。

代码示例：

#include<iostream>#include<map>usingnamespacestd;voidtest_map5(){map<int,string>m={{1,"a"},{2,"b"},{3,"c"},{5,"e"},{4,"d"},{6,"f"}};autopos1=m.lower_bound(2);autopos2=m.upper_bound(4);while(pos1!=pos2){cout<<pos1->first<<":"<<pos1->second<<" ";pos1++;}cout<<endl;autopos3=m.lower_bound(2);//可以删除这段区间的值 注意不能再用上面的pos1了因为pos已经改变了m.erase(pos3,pos2);for(auto&e:m){cout<<e.first<<":"<<e.second<<" ";}cout<<endl;}

运行结果：

4、map的operator[]的使用

访问或插入元素：当使用map[key]时，若key已存在，返回对应的值（value）的引用；若key不存在，则自动插入一个key到map中，其值通过默认构造函数初始化，并返回该值的引用。
非const限定：只能用于非const的map对象，因为可能修改map内容(修改某个key对应的value)。

代码示例：

#include<iostream>#include<map>usingnamespacestd;voidtest_map6(){map<string,string>dict={{"left","左边"},{"right","右边"},{"insert","插入"},{"string","字符串"}};//=======================================================================// 1、如果k不在map中，insert会插⼊k和mapped_type默认值，同时[]返回结点中存储//mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊+修改功能//2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的//迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找+修改的功能//=======================================================================dict["set"];// 插入一个空字符，string的无参构造不传参构造出一个空字符串dict["set"]="集合";// 修改dict["string"]="xxxx";// 修改dict["begin"]="开始";// 插入+修改//cout << dict["set"] << endl; // 查找string arr[]={"苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉"};map<string,int>countMap;for(auto&str:arr){//直接使用operator[] 如果key在那么就对key的value++ 如果key不在那就直接插入countMap[str]++;}//结构化绑定for(auto&[k,v]:countMap){cout<<k<<":"<<v<<endl;}}

值得注意的是：在之前讲插入的时候，insert的参数为value_type类型，而value_typde在map中被typedef为了一个pair，而insert的返回值又是一个pair，注意这两个pair其实是不一样的！！！⼀个是map底层红黑树节点中存的pair<key, T>，另⼀个是insert返回值pair<iterator,bool>下面画图分析：

说明：

1. 如果key已经在map中，插入失败，则返回⼀个pair<iterator,bool>对象，返回pair对象first是key所在结点的迭代器，second是false。
2. 如果key不在在map中，插入成功，则返回⼀个pair<iterator,bool>对象，返回pair对象first是新插⼊key所在结点的迭代器，second是true。
3. 也就是说无论插入成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器。那么也就意味着insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以用来实现operator[]。

2.4multimap的使用

map：存储键值对（key-value），每个键唯一，不允许重复键。底层通常实现为红黑树，保证元素有序（按键排序）。
multimap：允许重复键，多个键可以关联不同值。同样基于红黑树实现，保持有序性。其它的特性均与map一样。

值得注意的是：由于multimap支持数据重复，所以multimap就不⽀持[]，因为⽀持key冗余，[]就只能支持插入了，不能⽀持修改，没有意义。

代码示例：

#include<iostream>#include<map>usingnamespacestd;voidtest_multimap(){multimap<string,string>dict={{"left","左边"},{"right","右边"},{"insert","插入"},{"string","字符串"}};//插入相同的keydict.insert({"apple","苹果"});dict.insert({"apple","haha"});dict.insert({"apple","hehe"});dict.insert({"string","xxxx"});dict.erase("apple");//删除指定的key相应的value也会被直接删除autopos=dict.find("string");if(pos!=dict.end()){dict.erase(pos);}for(auto&e:dict){cout<<e.first<<":"<<e.second<<" ";}cout<<endl;}

三、总结

map 和 multimap 对比总结