中山企业网站的建设,Wordpress媒体库途径,网站图片移动怎么做的,健康企业建设我们要开始学习map和set的使用#xff0c;虽然使用更加复杂#xff0c;但是STL整体的设计#xff0c;本身就具有很强的前瞻性和延续性#xff0c;比如说迭代器等#xff0c;我们顺着文档来看。这也是除了vector之外最重要的容器#xff0c;当然还有unordered_map 和 unor…我们要开始学习map和set的使用虽然使用更加复杂但是STL整体的设计本身就具有很强的前瞻性和延续性比如说迭代器等我们顺着文档来看。这也是除了vector之外最重要的容器当然还有unordered_map 和 unord_set其实这几个也是C里面用的最多的。
Set学习
模版参数
这里的set呢它只有一个模版参数可就是T然后还有一个比较器默认是小于它给一个比较器呢就是为了有些地方默认的operator 重载的比较不符合你的要求假设你用的是指针但是指针是按地址比较大小当这个T是一个指针的时候但是你不想按地址比较大小那么原生的行为不符合怎么办那你是不是就可以传仿函数呀去控制里面的比较规则呀。在下面就是空间配置器它是负责申请内存。
insert() 我们看到函数参数中有一个value_type类型但是不知道这个是什么类型。我们先写一个最简单来看看。 》set s;set 没有push() 线性表、链表、队列等都是线性结构才会有push()接口 。后面非线性结构的都是insert()接口了。我们随便插入一些数据s.insert(4)s.insert(5)…我们插入5个值。然后我们定义一个迭代器set::iterator it s.begin()这个set呢它是一个双向迭代器它底层用了特殊的算法迭代是走的另一种非递归后面也会讲不用像我们在前面的二叉树OJ那里用栈模拟但是它这里非递归有前提的前提就是它要有三叉链它的逻辑底层是有parent成员变量的反正我们先不管后面我们才讨论底层。 》然后我们while循环遍历while(it ! s.end())cout *it it然后我们看到走出来就是有序的其实它不仅仅是有序的它是在有序的情况下还加了一些东西如果值已经有了它还会不会插入不会了所以严格来说它不是排序而是一个排序➕去重 》它这块支持迭代器是不是有普通迭代器支持可读可写还有const迭代器只读。然后它还有反向迭代器就不演示了。 》它既然支持迭代器那么就会支持范围for。其实范围for和我们迭代器在底层上是一样的只是在上层看来有些区别。 》我们发现const迭代器和普通迭代器都是不支持修改的 虽然一个叫iteratro一个叫const iterator但是底层都是用的一个const_iterator来实现的。 》另外重载的两个insert()函数用的很少。平时也很少用在某一个位置插入这个接口价值很小。 》insert()不会有迭代器失效的问题不像顺序表挪动数据会影响相对关系它的erase()是会有迭代器失效的问题。
void test_set1()
{setint s;s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(1);s.insert(3);s.insert(2);s.insert(1);// 排序 去重 setint::iterator it s.begin();while (it ! s.end()){//*it 10;cout *it ;it;}cout endl;for (auto e : s){cout e ;}cout endl;
}empty()/size()/max_size()
erase()/find()—两个是要配合的 erase()函数主要有两种一种是在某个位置删除另外一种是删除某一个具体的值。第三种删除特定的区间这个用的很少。 》这块要玩删除的话就得配合find()函数。我们前面插入了很多值我们随便set::iterator it find(2)一个值那么我们**怎么判断是找到还是没找到呢**如果元素被找到了是会返回value值对应的迭代器查找失败就会返回end()迭代器。是不是就是if(pos ! s.end())就是找到了呀。 》我们来对比一下set自带的find()和算法里面的find()有什么区别呢 set::iterator it find(20) 和 pos find(s.begin()s,end()20),算法里面的find能不能行呢是行的。它们的区别很大数据量小还好数据量大就会差别很大。set的find()的效率是logN而算法的查找效率是O(N)因为算法的是暴力查找。这个算法的find()查找不是给set用的而是给像vector它们用的。
void test_set2()
{setint s;s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(1);s.insert(3);s.insert(2);s.insert(1);setint::iterator pos s.find(20); // O(logN)if (pos ! s.end()){cout set.find找到了 endl}pos find(s.begin(), s.end(), 2); // O(N)if (pos ! s.end()){cout find找到了 endl;}
}》如果我们要erase了呢我想将我从键盘中输入的值erase()掉通过find()查找我们输入的值再去erase(迭代器)。当erase()成功之后对应的位置就不能访问了已经是失效了。我们可以通过查找进行持续的删除。我们还可以直接传参数去删除即erase(3)也就是你可以理解成这个erase(3)相当于调用了find()➕erase(迭代器)。 》前面第一种是先是找到了再去删除它们会有什么区别呢第二种用法如果没有找到直接去删除是不会报错的而你第一种调用了find()没有找到你还是去删除是会报错的。 》size_type erase(value)是会返回一个size_type类型的数据他为什么不用bool类型呢是因为它和另外讲的东西契合起来。我们能够看到删除成功是返回1删除失败是会返回0为什么是返回这个而不是返回bool呢因为待会儿我们还要学另外一个版本另外一个版本是允许冗余的。
void test_set3()
{setint s;s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(1);s.insert(3);s.insert(2);s.insert(1);cout s.erase(3) endl;cout s.erase(30) endl;for (auto e : s){cout e ;}cout endl;setint::iterator pos s.find(3);if (pos ! s.end())s.erase(pos);for (auto e : s){cout e ;}cout endl;/*int x;while (cin x){setint::iterator pos s.find(x);if (pos ! s.end()){s.erase(pos);cout 删除 x 成功 endl;}else{cout x 不在set中 endl;}for (auto e : s){cout e ;}cout endl;}*/if (s.count(5)){cout 5在 endl;}if (s.find(5) ! s.end()){cout 5在 endl;}
}swap()
swap()就跟我们以前讲的一样比如说你要交换两个set的对象用算法的swap()直接交换是深拷贝是树的拷贝代价很大所以set自己有一个swap()它们交换指针代价小很多。
count() count()函数这个设计是和一个版本对应起来的就是你给我一个值我看一下这个值在我set里面有几个在这里的set而言无非就是1个和0个。但是待会儿还有一个对称的版本。我们说了有些场景可能需要的不是排序➕去重而只是排序那么它们就设计了multile版本它是多样性的意思它是允许冗余的它们的接口设计都是保持的一致。 》count()函数有一个非常有意义的点就是判断在不在比用find()方便。比如说我要判断一个值在还是不在用count()是不是就很方便呀比如说我要count(3)if(s.count(3))看一下这个3在不在在的话是会返回1不在的话是会返回0。如果用find()的话就没那么方便了吗要这样if(s.find(3) ! s.end())是不是相对来说不太方便了。
lower_bound()函数 lower_bound()是干嘛呢比如lower_bound(30)是帮你去找 30的值的迭代器但是它在这儿又有一点问题lower_bound()和upper_bound()的返回值还有点不一样。我们试验一下。 》你看set::iterator lowIt s.lower_bound(3)如果有3它会返回3位置的迭代器没有就返回 3的值我们插入的值里面是有3的所以返回的是3 的迭代器。如果是set::iterator lowIt s.lower_bound(6)我们插入里面没有6那它会返回什么呢返回的是7的迭代器。 》它什么情况下比较有用么比如说要求删除 x的所有值那么你就不用遍历去删除了这里的lower_bound()函数就可以帮干这件事情怎么删除呢不要忘了我们的erase()是支持迭代器区间的删除那么erase()左区间可以给个lowIt变量右区间可以给end()相当于是左闭右开【即erase(lowIts.end())
void test_set4()
{setint s;s.insert(4);s.insert(5);s.insert(1);s.insert(3);s.insert(2);s.insert(7);s.insert(9);// 返回 val得位置迭代器 3返回3位置 6 返回7位置/*setint::iterator lowIt s.lower_bound(3); 存在lowIt s.lower_bound(6); 不存在*/for (auto e : s){cout e ;}cout endl;// 要求删除x的所有值int x;cin x;setint::iterator lowIt s.lower_bound(x);s.erase(lowIt, s.end());for (auto e : s){cout e ;}cout endl;
}upper_bound() 比如upper_bound(60)如果有60的话它是不回返回60而是返回 60的值我们来验证一下。这里我们比如说是set::iterator upIt s.upper_bound(5)我们传一个5然后再来一个set::iterator upIt s.upper_bound(6)我们传的是6这两个区别就是一个值在我们插入的里面一个是不存在。我们来看看结果我传的是5有5它返回5了吗答案是不会的它返回的是7我传的是6它返回的是7。所以这里的upper_bound()它要找的不是 的值它是返回 x位置的迭代器。 》所以upper_bound和lower_bound一个是返回 一个是返回 。其实他们**两个可以配合起来并配合ease()贯彻“左闭右开【”。**比如说要删除 x [] y的区间是不是就可以将这两个配合起来使用了呀。比如auto leftIt s.lower_bound(x)auto rightIt s.upper_bound(y)erase(letfItrightIt)所以它会删除【xy】
void test_set5()
{setint s;s.insert(4);s.insert(5);s.insert(1);s.insert(3);s.insert(2);s.insert(7);s.insert(9);for (auto e : s){cout e ;}cout endl;// 返回x位置的迭代器 -》 都是返回 7位置的迭代器//setint::iterator upIt s.upper_bound(5); // 存在//upIt s.upper_bound(6); // 不存在// 删除x y的区间 删除 [x,y]int x, y;cin x y;auto leftIt s.lower_bound(x); // [auto rightIt s.upper_bound(y); // )s.erase(leftIt, rightIt);for (auto e : s){cout e ;}cout endl;
}讲讲multiset版本
multiset它是允许键值冗余的它的用法和set一样的但就是要记一下它的名字比如mutilset mS它是排序不去重。 》真正有区别的就是count()函数比如说你要统计一个值s.count(1)set版本那边的count没有给bool类型的返回值而是给int类型返回值这其实是为保证接口的设计一致。其实set不需要count是个bool就行了但是为了和multiset保持一致返回值类型也是int。 》同样的set版本里面的erase()函数的返回值不是bool而是size_type也是为了和multiset里面的erase()设计保持一致可以返回删除了几个对应的值。 》还有一个区别就是这里的find()函数比如我这里有多个同样的值那么我auto pos s.find(3)会返回哪个3的迭代器呢那么这里就可以做一件事情它会返回中序的第一个可以由while(pos ! s.end())cout *pos pos验证。我们以后讲了搜索树会知道插入的时候树是会旋转的所以同样的值插入在左边还是右边都不影响。
void test_set6()
{multisetint s;s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(1);s.insert(3);s.insert(2);s.insert(1);s.insert(3);s.insert(3);s.insert(3);s.insert(3);// 排序 setint::iterator it s.begin();while (it ! s.end()){//*it 10;cout *it ;it;}cout endl;for (auto e : s){cout e ;}cout endl;cout s.count(1) endl;cout s.erase(1) endl;for (auto e : s){cout e ;}cout endl;// 多个x的话find返回中序第一个xauto pos s.find(3);while (pos ! s.end()){cout *pos ;pos;}cout endl;
}看一下题目
题一
两个数组的交集找交集怎么找呢是不是可以考虑这样你也有我也有的就是交集。 》最简单的方案就是将其中一个数组放进set里面我直接去你里面找是不是太慢了。我们可以遍历将值inser()插入进set里面。然后继续遍历另一个数组在我们的set里面找对应的值那其中是不是就可以用count()函数而不必调用find()函数呀然后存在的话就将值插入到我们另一个开辟的数组里面。但是这里有可能过不去为什么呢因为在我们开辟的vector来存交集的值会有重复因为交集是隐形的要求你去重的。 》那你的另一个数组是不是也用set来去重一下呀。但是这个算法不够高效因为假设你set里面有n个元素那么每调用一次count()的时间复杂度是logN那么总的时间复杂度是不是N*logN。 》还有一个优化算法这个优化算法在很多找交集都能有效。找并集的话只需要一个set就行了。现在来说一个交集/差集的优化算法这个算法不一定要set但是set用在这里刚刚好。 》我们inset()到set之后是不是就相当于有序了呀有了排序就好说。如果你要求并集的话只要放到一个set里面就行了它是可以去重的。那么交集和差集怎么搞呢有些地方需要同步同步数据的话就要找交和差集。 》两个数组已经是有序了的然后分别有一个指针先是指向各自的开始。交集的话两个相比较的话1.小的2.相等的就是交集同时3.有一个结束就结束了。这个优化之后就变成了时间复杂度是2N了。 》这个算法除了可以找交集还可以找差集。1.相比较小的就是差集小的2.相等的话同时3.一个走到头了另一个剩下的是不是也属于差集了。 》差集和交集在服务器和你网盘需要同步的时候是有用到的。比如你有一个服务器文件夹和一个本地文件夹你要将本地文件同步到服务器文件里面相当于备份嘛那是不是一方删除另一方也会删除你添加的另一方是不是也要添加呀。
map
首先map数据结构里面呢有一个Key和Value。它里面有一个valuse_type类型它里面不是把数据分开存储的不像我们前面讲的自己写的搜索树里面单独分开定一个key和value而map它是将key和value是放在一个结构里面的这个结构是在C里面被定义成pair类型pair就是一对一对的意思在map这里呢叫做键值对。
insert() 》我们先用map来存一个字典的例子map的insert()插入的一个值是value_type类型的value_type其实就是pair类型的数据。pair类型呢有两个参数第一个参数叫做first第二个参数叫做second。 》如果我们想插入的话mapstring, stringdictdict.insert(pairstringstring(“sort”“排序”))这是第一种匿名对象的一种传参数用起来比正常的要舒服很多。第二种正常点是这样的pairstringstringkv(“insert”“插入”)dict.insert(kv)还有第三种方式用起来更爽用到make_pairmake_pair就是制造一个pair对象即dict.insert(make_pair(“left”左边)) 》前面第一、第二种都是借用的pair的构造函数来进行。第三种make_pair是一个函数模版它的优势是不用声明参数让它自动推导。第四种还能这么写dict.insert({“right”右边})虽然知道可以这么写但是目前还是不太清楚为什么这个涉及到C11点类型转换C11再讲。 》map的遍历mapstringstring::iterator it dict.begin()我们也说过如果你清楚的情况下可以用auto让它自己推导。while(it ! dict.end())coyt it it**发现不支持it**。有没有人想过你直接分别单独用变量表示key和value不就好了嘛为什么要封装一个pair这个地方就能看出来为什么要搞一个pair了。这个map的迭代器和链表的迭代器有些相似它用自定义类型去封装封装节点只不过在map这里是一个树的节点那么解引用是不是去调用operator呀那C是否支持一个函数返回两个值呢这里it本质是it-operator()它是不是要返回节点里面的数据呀对于set还好set里面只有一个key但是map这里是一个key和value那C是否支持一次返回两个值呢不支持是吧但是你这里用到了模拟解引用的行为那就要返回节点如果你这里分别单独用变量表示key和value就没办法搞了所以我把key和value给你打包成一个结构数据这个结构数据就叫做pait类型所以operator返回的是节点数据这个节点数据是一个pair类型。 》但是你这类型pair支不支持流呢即cout it吗答案是不支持。有同学说我们来支持一下就可以了但是支持的话是不是就要改库里面的代码呀那么我们换一种方法玩。你不是一个结构嘛那么我们就是cout (*it).first “:” (*it).second endl但是在这种地方你的迭代器是不是指针的行为呀那你还用解引用*吗不会而是用迭代器重载的-运算符来用*即cout it-first “:” it-second endl 》那这里的范围forfor(const auto kv : dict)kv其实是返回的*解引用后的pair数据类型用kv.first()和kv.second()来访问。
void test_map1()
{mapstring, string dict;// pair构造函数dict.insert(pairstring, string(sort, 排序));pairstring, string kv(insert, 插入);dict.insert(kv);// make_pairauto ret1 dict.insert(make_pair(left, 左边));auto ret2 dict.insert(make_pair(left, 剩余));dict[operator] 重载; // 插入修改dict[left] 左边、剩余; // 修改dict[erase]; // 插入cout dict[left] endl; // 查找// C11 再讲//dict.insert({ right, 右边 });// 遍历//mapstring, string::iterator it dict.begin();auto it dict.begin();while (it ! dict.end()){//cout *it ; // it-operator*()//cout (*it).first : (*it).second endl;cout it-first : it-second endl;it;}cout endl;for (const auto kv : dict){cout kv.first : kv.second endl;}
}//mapped_type operator[] (const key_type k)
//{
// pairiterator,bool ret insert(make_pair(k, mapped_type()));
//
// //return (*(ret.first)).second;
// return ret.first-second;
//}那你现在统计水果出现的次数是不是就很方便了呀先构建一颗map树mapstringint countMapfor(aoto str : arr)是不是就可以先调用map的find()函数auto it countMap.find(str)如果水果没有插入到我们的树里面那么我们就构建一个pairstringint即countMap.insert(make_pair(str1))如果已经存在了就it-second;
void test_map2()
{string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };// 17:08继续/*mapstring, int countMap;for (auto str : arr){mapstring, int::iterator it countMap.find(str);if (it ! countMap.end()){it-second;}else{countMap.insert(make_pair(str, 1));}}*///mapstring, int countMap;//for (auto str : arr)//{// //pairmapstring, int::iterator, bool ret countMap.insert(make_pair(str, 1));// auto ret countMap.insert(make_pair(str, 1));// if (ret.second false)// {// ret.first-second;// }//}mapstring, int countMap;for (auto str : arr){countMap[str];}for (const auto kv : countMap){cout kv.first : kv.second endl;}
}int main()
{//test_set6();test_map1();return 0;
}其实map这里最重要的就是刚刚讲的那么刚刚上面讲的呢还有优化的空间这个优化的空间是要帮我们去搞后面的事情。
mapstring, int countMap;for (auto str : arr){mapstring, int::iterator it countMap.find(str);if (it ! countMap.end()){it-second;}else{countMap.insert(make_pair(str, 1));}}这个代码其实是可以改进优化的。find()这里有这么一个问题我去find()是不是一直去找不在的话是不是我就相当于从根找到尾了呀没有的话我就得去插入插入是不是又得去找一次那是不是重复了呀find()找一次没找到后insert又找了一次。其实不优化也无关痛痒但是这里讲优化是为下面做铺垫为下面的玩法做铺垫。 》所以这里就可以用insert()来做一件事情正常的呢insert()的返回值是一个pair类型的数据pair的first数据被设置成为一个iterator迭代器这个迭代器指向两种可能要么指向新插入的元素插入成功要么指向与key相等的元素插入不成功。意味着是这样的我insert()返回的pair类型的数据first是一个迭代器这个迭代器呢一定是指向一个位置的要么是你新插入元素的迭代器要么是没有插入成功因为反冗余的嘛那么itreator就是已经有了的元素的迭代器。那么pair的second数据类型是一个bool如果是新插入的那就是true如果已经有相等的了就是flase。也就是说它插入成功或者失败是会返回bool值的。我insert()返回的pair的迭代器不管你是插入成功还是失败都会返回一个元素的位置那么就可以利用起来。 》就拿上面统计水果个树来说如果水果已经存在map里面了还会插入吗不会。**这个待会儿对我们理解[]的使用非常重要 。**它insert()返回的pair类型的值非常有意义和我们待会儿要讲的“【】”有很大关系。我们插入atuo ret1 dict.insert((“left”左边))和auto ret2 dict.insert((“left”剩余))按理来说第一次插入的left是成功的ret1的second数据是truefirst数据是新插入元素的迭代器第二次插入leftret2的second数据是flase然后ret2的first数据和ret2一样的。 》我们就可以进行对上面代码改进不需要再调用find()函数了就调用insert()就行。我们不管有没有插入都调用insert()函数即pairmapstringint::iteratorbool ret countMap.insert(make_pair(str1))写简单一点就是auto ret countMap.insert(make_pairstr1)有两种情况插入成功我用不用管我不管也就是第一次出现那么返回的pair的second是一个true插入失败说明水果已经有了那么insert()是不是同时充当了find()的作用因为它把对应的元素的迭代器也给我了。 if(ret.second false)那就是插入失败已经有该水果了所以ret.first-second
mapstring, int countMap;for (auto str : arr){pairmapstring, int::iterator, bool ret countMap.insert(make_pair(str, 1));auto ret countMap.insert(make_pair(str, 1));if (ret.second false){ret.first-second;}}operator[]
》其实我们统计也不会用这个方法这个方法太憋屈了我们**讲这个真正的目的是为了玩“【】”**这个重载运算符而且C里面的map非常喜欢用“【】”如果说map的话我们重点学习的就是这个“【】”重载运算符。我们统计次数怎么统计我先写好
mapstring, int countMap;for (auto str : arr){countMap[str];}
此书成功统计出来没有毛病这个“【】”很绝。一句代码统计完次数就用了operator []这么一个重载运算符。 》operator[]返回值是一个mapped_type类型。我们想想我们什么时候重载过operator[]了我们在vector、string的时候重载了operator[]但是这里map支持随机访问吗并不支持目的也不是。 》其实这里map的operator[]已经改变了[]的意义了它不是随机访问它的参数也不是下标。它的参数是key返回值是value的引用。 》那么这里怎么做到一句话就统计了此书呢insert()都没有了吗我们来看看源码实现 这个代码能把人看崩掉我们简化一下代码我们先提取出(this-insert(make_pair(Kmapped_type()))).first这一串其实是谁呢实际上就是调用了insert()嘛。 》insert的返回值是不是pairmap::iteratorbool类型数据呀即pairmap::iteratorbool ret insert(make_pair(Kmapped_type()))然后它取了ret的first数据first是个什么呢不就是指向节点的迭代器嘛。 》所以一开始的代码就可以理解成
pairmap::iteratorbool ret insert(make_pair(Kmapped_type()))
return (*(ret.first)).second;》其实这个也绕了一点其实等价于
pairmap::iteratorbool ret insert(make_pair(Kmapped_type()))
return (ret.first)-second;我们在“【】”里面给的是key值有两种情况1.Key在map对象中2.Key不在map对象中。这里是精华很多面试中都会考这里。 》第一种Key在map对象中我们要进行插入make_pair(kmapped_type())中的mapped_type()是个啥我们先来看看mapped_type是谁是不是T类型就是Value的类型呀也就是第二个模版参数的类型第一个模版参数的类型是key的类型K嘛。那么mapped_type()是不是用Value类型进行构造的匿名对象呀 》也就是说你来了一个Key我不管你在不在我先insert(0。假设第一种情况Key是存在的那么插入失败那么insert()也就会插入失败那么你pairmap::iteratorbool ret insert(make_pair(Kmapped_type()))中的ret的second数据bool类型就是flasefirst数据就是Key所在节点的迭代器。然后return (*(ret.first)).second可能早期没有支持“-”这个符号所以我们现在支持就这样写ret.first-second------这个是不是就是节点的Value值呀。并且不要忘了**我operator[]的返回值是Value的引用引用的作用是1.减少拷贝2.支持修改** 》所以此时operato[]的作用有两层1.查找K对应的Value2.修改K对应的Value值。 》第一种情况插入失败insert()完全没有起作用它反而充当的是查找的作用。它这里的operator[]返回值只用的是insert()返回值的first即返回节点的迭代器。插入成功还是失败无所谓呀为什么呢如果Key在map对象中肯定插入失败嘛 》第二种情况如果Key不在对象中那么insert()是不是插入成功operator[]的返回值是不是节点的迭代器中的Value值的引用呀这个值一开始是匿名构造的对象上面有说如果Value是stirng类型就是空串如果是int类型就是0如果是指针类型就是空nullptr。我返回的Value值的引用那也就意味着充当着 插入 和 修改两层作用你可以修改也可以不修改。 》我们再来分析一下我们写的代码
countMap[str];水果要是第一次出现那会先插入插入的时候节点的个数是intt类型它内部会匿名构造int类型对象就是0但是operator[]会返回这个int的引用我们在外面用了所以0会如果水果已经有了它们operator[]不会插入成功它会返回水果所在节点的Value值的引用然后Value值。 》我们再从另外一个角度我们知道这个之后呢有些人插入字典就不会像我们一开始那样写了而是这样写
auto ret1 dict.insert(make_pair(left, 左边));
auto ret2 dict.insert(make_pair(left, 剩余));
dict[operator] 重载; // 插入修改
dict[left] 左边、剩余; // 查找 修改
dict[erase]; // 插入
cout dict[left] endl; // 查找所以operator[]是一个多元化功能map的其他函数参考set就行了。
multimap
它和map不同的是它是允许冗余的它是可以插入Key相同的键值对的哪怕你的Value值相同也是可以的其他的东西和map其实是一样的。
multimapstringstring dict
dict.insert(make_pair(left“左边”))
dict.insert(make_pair(left“剩余”))》相比map multimap使用函数接口最大的区别是什么multimap不支持operator[]为什么呢如果对于map你给一个Key我是不是要么有要么没有有的话我就返回对应的Value没有的话我好可以插入。但是mutiple有多个Key的时候那么Key是不是面临一对多的关系呀所以不支持operator []也是情理之中的。
题目前K个高频单词
这个题目是一个统计次数➕topK的问题。我们不管三七二十一先把各个单词出现的次数统计出来当然可以用map来帮我们做KV映射mapstring, int countMap然后将words遍历一遍就可以得到各个单词出现的次数。 》接下来就是TopK的问题了。我们以前应该是讲过如果建堆来解决我们是不是要建小堆来解决是吧但是我们不考虑用堆来解决其实优先级也就是堆因为优先级队列就是用堆来封装的。因为如果用堆的话选出K个之后还需要进行排队。 》我们的mapstring, int它所插入的值是按照string来进行排序的但是我们要的是按int来进行排序。sort()能对map进行排序吗答案是不能因为sort()要求的是随机迭代器map显然不满足。那我们是不是要将map里面的值放到vector里面然后就可以用sort()来进行排序了呀当然vector存放的元素类型就是pairstring, int了呀即vrctorpairstring, int vSort 》当然也可以不放pair类型而是vectormapstring, int::iterator v这和我们放pairstring, int有什么区别呢这种方案行不行呢 大家想想待会儿用sort()是不是必然要自己控制比较方式呀如果要自己控制比较方式的话你放pair我要写仿函数我放迭代器你是不是也得控制比较方式呀。大家想一想我在vector里面放迭代器iterator后能不能访问到里面的Key和Value是可以的。但是区别在哪里呢如果你放的是pairstring, int你待会儿得拷贝把map里面的每一个数据都拷贝到pair里面而我iterator迭代器就是一个指针所以针对于拷贝的代价我们还是选择迭代器iterator比较好。 》由于迭代器写出来很长我们先typedef一下typedef mapstring, int::iterator countIrer然后我们就是遍历map将每一个节点的iterator都插入到vector里面。 》接下来就是用到sort()函数进行排序了。 sort(v.begin(), v.end())这个时候能不能支持排序呢是不能支持到因为vector的迭代器v.begin()解引用之后是map节点的迭代器那么它支持排序吗不支持。不支持怎么办我们是不是得写一个仿函数来控制排序使其支持呀。 》所以我们来写一个仿函数struct IteCompare{}在其里面支持一个bool operator() (countIter ite1, countIter ite2)这里是支持迭代器进行比较。大家想清楚因为vector里面的每一个数据是迭代器我们将vector的迭代器传给sortsort解引用*是map节点pair的迭代器所以是迭代器比较那么迭代器比较要用仿函数来控制比较并使其能支持比较所以我们写了bool operator() (countIter ite1, countIter ite2)然后函数体内写return ite1-second ite2-second;然后我们的仿函数就完成了。 》接下来就是将仿函数一并传给sort()即sort(v.beginv.end()IterCompare)记住IterCompare是类型我们应该传一个对象给sort()所以是用到匿名对象IteComapre()即sort(v.beginv.end()IterCompare()) 》然后我们排序好了我们还得取出前K个是不是还得再来一个vector ret然后将排完序后的vector循环K次呀并且将值push_bacnk()进我们的ret里面。 》但是光光这样还是不能提交成功因为我们的选出来的K个words单词顺序不对因为如果单词出现的次数相同的话还得进行ASICC码排序将出现次数相同的单词进行排序。 》按道理一开始我们的countMap是按string的大小也就是按照Key去排序的进行将每一个节点插入的所以一开始就是将按string将words排序好了然后紧接着我们再遍历将每一个节点的迭代器放入vector了呀此时也是按照words的string来进行排序的但是我们后面用了sort()之后sort()是一个不稳定的排序它会将我们原来的words正确顺序给打乱的。所以你sort()完之后选出来了K个但是words的顺序你还得再排一次除非你用一个稳定的排序。 》在sort()文档里面它有告诉你它sort()是一个不稳定排序它提供了一个stable_sort()是能够保证稳定性的。所以我们将sort()换成stable_sort()试一下能不能通过是能通过的。 》或者还有方法你如果提前考虑到了这点的话你可以在仿函数阶段也将words的顺序也控制好即(ite1-second ite2-second || ite1-second ite2-second ite1-first ite2-first)所以我认为次数大的肯定大如果次数相等再比较words来进行排序。这样就可以调用sort()了。这不是改变sort()的稳定性而是改变了比较的规则。但是会有一些性能的影响。 》我们还有别的方法如果要排序除了用sort()是不是map本身也支持排序呀只不过一开始是对string来排序的我再定义一个mapint, string sortMap那么就是遍历一遍countMap然后sortMap.insert(make_pair(kv.secondkv.string))就是将K和V调个位置但是map会进行去重所以我们还得用mutilmap才行即mutilmapint, string sortMap然后我们再去sortMap里面去取元素就行了即for()循环K次然后ret.push_back(it-second) it。但是取出来K个之后它是按升序来的显然不符合我们的要求此时我们的map、mutilmap都是支持自己定义比较方式的这不就体现出来了吗所以我们在定义sortMap的时候还得传入另外一个参数mutilmapint, string, greater sortMap要传入一个greater来进行控制比较方式。 》最靠谱的还是sort或者srable_sort因为如果用map的太依赖其底层的实现了。
