asp网站代码 部分封装,中山网站建设文化价格,网站建设技术外文,哪个网站可以做1040在了解map之前#xff0c;我们先看看两个场景#xff0c;通过这两个场景的对比#xff0c;让我们知道为什么要存在存储双关键字的容器 场景一#xff1a;判断一堆字符串中#xff0c;某一个字符串是否出现过
在没学set容器之前#xff0c;我们只能想到把这一堆字符串存到… 在了解map之前我们先看看两个场景通过这两个场景的对比让我们知道为什么要存在存储双关键字的容器 场景一判断一堆字符串中某一个字符串是否出现过
在没学set容器之前我们只能想到把这一堆字符串存到一个字符型数组里面从前往后遍历每一个字符判断某一个字符串是否出现过这个时间复杂度是ON级别的如果我们学过set的话我们就可以把这一堆字符串存到set容器里面判断某一字符串是否出现过的时候直接调用里面的count接口就可以了时间复杂度是OlogN级别的所以我们用set特解决场景一问题的时候时间复杂是更优的
场景二找出一堆字符串中某一个字符串出现的次数
如果找的是次数那么set容器就用不了了set容器存储的是单关键字而且里面是不能有重复元素的大家可能想到有multiset它可以存储重复的元素因此要判断某一个字符串出现的次数直接调用multiset里面的count不就完了吗其实还有一个问题如果这一堆字符串中所有的字符全都长一样比如有10,000个字符串里面的每个字符都是a当我想找“aa”这个字符串出现的次数的时候用multiset来解决的话是要遍历整个红黑树一遍的要全部把它扫描一遍才能统计出a次数此时它的时间复杂度是ON级别的那和数组存储没有任何的差别所以我们想判断某一个字符串出现的次数是不能用set容器的
此时存储双关键字的map就登场了它可以做到存储双关键字它把两个关键词绑定在一起存到红黑树里面的比如在这个问题里面我想统计某一个字符串出现的字数map绑定的两个关键字可以设置成第一个是string第二个是int它的意思是把字符串和出现的次数绑定在一起放进红黑树里面的一个一个节点中也就是说红黑树的节点存的是一个结构体结构体的第一个关键字是字符串第二个是字符串出现的次数此时在查找某一个字符串出现的次数的时候直接在这个红黑中找出对应的字符串拿到它出现的次数就可以了至于如何解决这样的一个问题我们学完map的方式之后在一起编写代码
map / multimap map 与 multimap 的区别 map 不能存相同元素 multimap 可以存相同的元素其余的使⽤⽅式完全⼀致。因此这⾥只练习使⽤ map 。 map 与 set 的区别 set ⾥⾯存的是⼀个单独的关键字也就是存⼀个 int 、 char 、 double 或者 string 。⽽ map ⾥⾯存的是⼀个 pairkey, value k-v 模型不仅有⼀个关键字还会有⼀个与关键字绑定的值⽐较⽅式是按照 key 的值来⽐较。 也就是中序遍历的结果是按照第一个关键字的的大小来做比较的可以这样理解红⿊树⾥⾯⼀个⼀个的结点都是⼀个结构体⾥⾯有两个元素分别是 key 和 value 。插⼊、删除和查找的过程中⽐较的是 key 的值。 ⽐如我们可以在 map 中 存 int, int 来统计数字出现的次数 存 string, int 来统计字符串出现的次数 存 string, string 表⽰⼀个字符串变成另⼀个字符串 甚⾄存 int, vectorint 来表⽰⼀个数后⾯跟了若⼲个数......可以用来存储树就是一个根结点后面跟了一堆孩子int表示根vectorint存它的一堆孩子但用map存储树的效率不高因为查找的时间复杂是OlogN后面我们在学习哈希表的时候可以给大家演示一下如何用这个东西存储树因为用哈希表来存储这样的形式查找是很快的 1 创建 map
#include iostream
#include vector
#include map
using namespace std;
int main()
{ mapint, int mp1; mapint, string mp2; mapstring, int mp3; mapint, vectorint mp4; // 甚⾄可以挂⼀个 vectorreturn 0;
}
2 size / empty
size 求红⿊树的⼤⼩。时间复杂度 O(1) 。empty 判断红⿊树是否为空。时间复杂度 O(1) 。
3 begin / end
迭代器可以使⽤范围 for 遍历整个红⿊树。遍历是按照中序遍历的顺序因此是⼀个有序的序列。
4 insert
向红⿊树中插⼊⼀个元素。这⾥需要插⼊⼀个 pair可以⽤ {} 形式。⽐如 mp.insert({1, 2}) 。时间复杂度 O(log N) 。
5 operator []
重载 [] 使得 map 可以像数组⼀样使⽤。这是 map 最好⽤的接⼝有了这个重载map 的使⽤就变得特别轻松不⽤写很多冗余的代码。它的底层其实就是调⽤了 insert 函数并且会返回 val 的引⽤。我们⽬前就先学会使⽤即可。
6 erase
删除⼀个元素。时间复杂度 O(log N) 。
7 find / count
find 查找⼀个元素返回的是迭代器。时间复杂度 O(log N) 。count 查询元素出现的次数⼀般⽤来判断当前元素是否在红⿊树中。时间复杂度O(log N) 。
8 lower_bound / upper_bound
lower_bound ⼤于等于 x 的最⼩元素返回的是迭代器。时间复杂度 O(log N) 。upper_bound ⼤于 x 的最⼩元素返回的是迭代器。时间复杂度 O(log N) 。
代码
#include iostream
#include map
#include string
using namespace std;//传引用使得mp不需要拷贝
void print(mapstring, int mp)
{//避免拷贝//双关键字用auto提取出来的是一个pair类型所以打印要用first、secondfor (auto p : mp){cout p.first p.second endl;}
}void test1()
{mapstring, int mp;//插入mp.insert({ 张三, 1 });mp.insert({ 李四, 2 });mp.insert({ 王五, 3 });print(mp); //打印出来的结果按第一个关键字作比较后面的关键字只起到绑定作用//李四 2//王五 3//张三 1//operator[] 可以让 map 像数组一样使用int a[2] { 1,2 };a[1] 4;cout a[1] endl; //4cout mp[张三] endl; //1mp[张三] 110;cout mp[张三] endl; //110// 注意事项operator[] 有可能会向 map 中插入本不想插入的元素if (mp[赵六] 4) cout yes;else cout no endl; //no//虽然我们只是想判断赵六存不存在但是一旦调用了[]就把赵六插入进来了// [] 里面的内容如果不存在 map 中会先插入然后再拿值// 插入的时候第一个关键字就是 [] 里面的内容第二个关键字是一个默认值print(mp);//李四 2//王五 3//张三 110//赵六 0//这样的逻辑去写就没有插入张飞从mp.count(张飞)这句话就断掉了//后面的语句没有执行了此时打印张飞是不存在map里的if (mp.count(张飞) mp[赵六] 4) cout yes endl;else cout no endl; //noprint(mp);cout endl;//李四 2//王五 3//张三 110//赵六 0//删除mp.erase(张三);print(mp);cout endl;//李四 2//王五 3//赵六 0//auto x mp.lower_bound(李四);mapstring, int::iterator x mp.lower_bound(李四);cout x-first x-second endl; //李四x mp.upper_bound(李四);cout x-first x-second endl; //王五
}// 统计一堆字符串中每一个字符串出现的次数
void fun()
{string s;mapstring, int mp; // 字符串字符串出现的次数for (int i 1; i 5; i){cin s;mp[s]; // 体现了 operator 的强大s字符串不存在会先插入 }print(mp);//输入//sdf//aa//dd//aa//dd//输出//aa 2//dd 2//sdf 1
}int main()
{test1();//fun();return 0;
}
