说完了set 和multiset,现在我们要说另外两种重要的关联容器,就是map和multimap。
嗯,这时我们先回顾一下pair模板。这个map和multimap里面放着的东西 它不能是基本类型的变量,它必须是pair模板类的对象。
嗯,那也就是说,map和multimap里面放着的东西一定是个对象,而且对象一定是只有first和second的
这两个成员变量。而且,multimap和map都是按照first的成员变量
来把这些元素进行从小到大排序的。当然,什么叫大小,你可以自己定义啊。
我们来看看map的这个multimap 它的定义,啊,是这样。
嗯,第一个类型参数key ,实际上就是代表了multimap里面元素的first的成员变量的类型。
第二而类型参数T,就是元素的second的成员变量的类型。第三个
类型参数Pred确审值是lesskey, 就规定了
比大小的规则。那第四个类型参数,那个我们不管它,就用确审值就行了。然后再multimap的里面呢
嗯,typedef了一个value type的这样一个类型。嗯,它是一个pair类型,pair<const key.T>
嗯,那就是一个value type呢它有两个成员变量。嗯,first的成员变量呢是T类型的。
而且是const的了。那second的成员变量呢,是T类型的。那在map和multimap里面
我们往往把元素的first 的成员变量,呃,称为这个关键字。
那这样的话multimap和map之中的元素啊,都是由关键字和词组成,啊。
First的成员变量叫关键字,Second的成员变来那个叫值。它每个元素都是一个pair对象。
关键字的类型是key ,那multimap的中他是允许有多个元素的关键字,
也就是与first的成员变量相同的,然后元素按照first的成员变量从小到大排序。
那确审的情况下呢,当然是用less Key定义什么叫小。
我们下面看一个具体程序的例子。呃,我们使用multimap #include <map>的这个头文件。然后这里面
typedef了一个类型,叫mmid,这个类型是一个muiltimap的
容器。type的first的成员变量,整型的。
然後,second的成员变量呢,是double型的。然后,这个
关键字也就是first的成员变量,比大小的规则是了less int,那归根到底就是用小1号去比大小啦。
呃,这就是我们定义出来的一种Multimap的容器类的这种类型mmid。
然后,这里定义了一个这个pairs这样一个容器。然后,在这里呢调用pairs.count成员函数算里面有多少个
呃,元素的关键字的值等于15 。啊,这里说的等于也不使用等等号。
而是说x小于y,y小于x同时不成立,就算等于。
这里面算有多少个元素的关键字是等于15,那当然没有,对吧?因为一开始pairs就是空的。所以说,
呃,这第一行的输出呢,就应该是,嗯,0。对,第一行输出是0。然後接下来呢,我们调用
这个multimap 的insert成员函数。就往里头去插入一个元素,那我们知道
要插入的元素必定是一个pair模板类的对象。所以我们在这个参数这块要生成一个
pair模板类的对象。怎么生成呢?呃,看这种写法,这个东西是什么呀?是在
mmid这个类里面定义的valuetype这种类型。那
在这个multimap的这个定义里面有这样一条语句,
typedef pair <const key.T> value
type。那,呃, 那么也就是说这个 mmid
value type是个什么样的
东西呢?那当然就是把这个key替换成
这个int的这个T替换成double以后,得到的这样的一个pair 模板类这种类型。
呃,那这个是一个类型的名字,而后面呢()里面有给出了参数。这个参数当然就是
构造函数的参数,于是这里面的整个表达式就是一个临时的这个
对象。这个对象所属的类型是,呃,mmid value type.
归根到底就是这个pair、呃,int、double。好,现在在这里就生成了一个
这样的一个pair对象。这个pair对象的first的成员对象是int型的,嗯,它的值是15
。然後, second的成员变量呢,是double型的,它的值是27。
然后就把这个对象插到这pairs里面去了,那实际上就是这个对象的副本被插进去了。
呃,接下来再插入另外一个对象,是15 ,99.3。呃,multimap只允许有两个元素。
它们的first的成员变量相同的,所以我们接下来算。这时候有多少个元素first的成员变量值是15啦!
呃,这个时候当然算起来就两个,所以就会输出2,2,第二行的是2。
呃,然后在接下去又插入了这个30,101.1、10,22.2。嗯,然後,嗯,就不停的全部
进行几次插入。然后我们在这里呢,呃,用一个
迭代器i来遍历整个的这个,呃,
这个multiset的容器pairs。然后呢,对每一个迭代器i我们输出它指向的的那个
元素的first的成员变量,和second的成员变量。然后我们发现,呃,这个循环,啊
这个循环输出的结果在这儿,啊。嗯,那这个结果有什么规律呢?啊,我们看到他们的first 的成员变量,
就是一个整型的关键字它是从小到大排序的。这个小的定义就是
用小号来确定的。实际上也就是数学上的这个整数的大小的意思。那接下来我们来看一个
有点复杂,但却是你学得会就很有收获的一个例题。啊,这个例题呢,是一个学生成绩
录入和查询系统。我得把这个题目念一遍,啊。虽然很长,呃,这个系统呢,它接收以下两种输入:
就是 Add name id score或者query score。而这个内容呢,它是一个
字符串 ,这个字符串中间是不会有空格的。呃,它代表学生的姓名。
那么id 呢是个整数,代表学生的学号。Score是个整数,表示学生的这个分数。然後,学号
是不会重复的,那分数和姓名都有可能重复。那总之add的
这条语句就是添加一个学生的信息到这个系统里面去。
那query呢,呃,就是进行查询了。就是你碰到add的这样的,呃,输入的时候,
你就把一个学生的信息给存起来。嗯,碰到query score的时候呢,就表示
要查询。那看到这种输入,你输出已有记录中,啊,就前面已经出现过的学生里面,分数比这个score
低的最高分获得者的姓名、学号和分数。那如果有
多个学生都满足条件呢,我们就输出学号最大的那个学生的信息。
那找不到满足条件的学生就输出这个nobody
。好,我们看一下例子。呃,比方说,呃 你输入了add Jack
12 78,好,那你这个程序得记住啊,前面有一个学生叫Jack的他的学号是12
,他的分数是 78。接下来输入一个query
78,这就是要找分数低于78的
某一个学生。如果有不只,嗯,这个学生呢它是低于78分里面的最高分。如果有多个学生都满足这个条件
的话我们就输出学号最大的那个学生的信息。那到目前为止有,前面只有一个学生Jack,
那当然就,呃, 找不到符合条件的人,对吧?所以说对应query
78 这一行 会产生一个输出结果是nobody。接着query
81,啊,那当然啦,低于81的最高分就是这个jack嘛!所以就会输出一个
Jack,然后他的学号,他的成绩。然后Add Percy
9 81,把学号为9的 Percy同学加进去了,她的分数是81。然後把Mary同学加进去了。然后,query
82 就找分数低于82的的那个最高分的同学,有两个,嗯,但是呢Percy的学号大,所以说我们就可以输出
Percy 9 81。再加query 82 ,那么这已经讲过了。再加
Tom 11 79,有一个Tom同学进来了,分数是79分,呃,学号是7。
然后,query 80就找低于80分的那个最高分,当然就是这个Tom了,呃,对吧?然後query81
找低于81的这个最高分,还是 Tom,所以最后这两行都输出的是Tom的信息。
啊,就是这种东西。那这个程序呢,呃,我们看到它
一边要更新原有的信息,一边还要进行这个查询,当然你最蠢的的办法你可以说,我就是
用一个数组把这个,呃,所有的学生信息全部记下来。当你要查找一个学生的信息
的时候呢,我就从头到尾把这个数组说一遍不就得了吗?当然,你可以这么做。这么做也很简单,
但是,这样做的效率是很低的。呃,这样做的话,呃,你如果,那么添加学生信息
你可以采取用一个vector,然後在尾部进行添加的方式。那添加学生
信息的复杂度基本上可以认为是常数吧!可是,
查询一个学生信息的时候呢,你得从到到尾搜整个数组。那复杂度就是ON的了。
那我们现在是要求,呃,大家用一种办法来做,应该要使得,啊,
添加和查询都很快,比方说,添加的时间复杂度是log
n的,查询的时间复杂度也是log n的。
啊,关键是要查得快。这才符合我们的要求。我可以出一大堆的数据,比如说,有一、两百万条的记录,
那你每次进行查询都要搜一、两百万条的记录的话,这肯定就,就很慢了。
那我出个有一两百,一两百万个学生的信息的这个题目放到这个poj上面,
嗯,然后规定一个时限,比如说一秒什么的,那你用顺序查找的办法,用一个vector来存这些东西的话,你十有八九就要超时。
好了,那这个时候,我们该用什么办法来提高这个程序运行的速度?使得不停地更新学生的信息,
不停地进行查询,那它也能保持很高的效率。
就是,经常的状态就是,就是我们添加一个学生,时间复杂度是log
n了,查询一个,一个分数,时间复杂度仍然是log n呢?那这样的,
呃,一个题目,我们该用什么,呃什么样的数,什么样的办法去存这些学生的信息呢?
啊,大家刚才看到了,这个map 和multimap应该能
很容易想到啊,我们应该要用关联容器,然后呢,我们,关联容器里面呢,这个元素嘛,
它都有关键字和值部分对吧,然后是按照关键字,也就是first成员变量从小到大排序的。
然后根据first成员变量去进行查找的话,呃,这个速度也会很快。那在这个例子里面,我们
把一个学生的信息,哪一部分算作这个关键字呢?那当然是分数对吗?我们要根据这个分数查询。
那当然是分数对吗?我们要根据这个分数查询。我们要查询,嗯,低于某个分数的这个,呃,低于某个分数的那个学生,
这个学生是在所有低于这个分数的里面,他的分数最高的。啊,这种查询
是按分数查的,我们当然就把分数当做first成员变量。那剩下的部分呢,
那剩下的部分呢,有好几个有姓名,又有,有ID,它是两部分的内容啊?怎么对应到另外一个second成员变量上呢?
让我们来看看。好,我们首先确定要使用,这个,
要使用这个关联容器,但到底是要用map还是multimap呢?
因为这里面分数是关键字,刚才说了,这学生的分数是有可能重复的,
所以说我们必然要用允许关键字重复的那个关联容器,就是multimap。
好,现在我们要往这个multimap里面放着的东西,一定是一个pair模板类的对象。但实际上我们要往里头放的东西,
又是一个学生这样的记录,学生记录刚才有三部分,有姓名、id和分数。而一个pair模板类它只有first和second
这两个成员变量,那怎么把一个学生的记录对应到一个这个,呃,pair模板类的对象上面去呢?
这要求我们好好地设计学生这个类,啊,我们写了一个cstudent这个类。啊,在cstudent这个类里面呢,
再定义了一个内部的类。在C++里面,类内部还可以再定义一个新的类的,好。
那现在我们在这个定义的内部类里面呢,它的名字叫cinfo。
啊,这个内部类里面包含了两个成员变量,一个是id,就是学生的学号。一个是name,就是学生的姓名。
然后cstudent里面呢,
cstudent里面它有两个成员变量,一个是整形的,分数,另外一个成员变量就是, cinfo类型的一个对象。
啊,那么这个对象里面就存放了这个学生的其他信息,就是,就是这个id和姓名。
呃,然后呢我们typedef了一个类型叫做mapstd,
就是学生的map容器,这个mapstd是什么样呢?是multimap,映着cstudent,cinfo。
那也就是说,在这个,呃,map容器里面,关键字是整形的,就是first成员变量是整形的,然后second成员变量呢,是什么类型的呢?
是cstudent里面定义的cinfo,这种类型的。好,内部类的使用方法就这样。
你在使用内部类的时候,前面要加上这个包含它的那个外部类的名字。
好了,那现在我们定义出来的mapstd是一个multimap容器,这个容器里的每个元素,
都是一个pair类模板的对象,然后它的first成员变量是整形的,实际上,可以用来代表,呃,学生的成绩,
然后它的second成员变量呢,是cstudent,cinfo类型的。那这,那second成员变量里面存放的,
当然就是一个学生的id和他的姓名了,对吧?呃,那我们在实际
画出来mapstd这个类型的时候啊,我们,我们并没有指定这个,呃,关键字比大小的规则。那也就是说,
那也就是说,呃,这是一种缺省的情况。
我们当然就是用这个less int去比较关键字的大小,也就是说,归根到底,使用小于号
去比较关键字,也就是这个学生的分数的大小的。那当然,在这个mapstd里面,
又是按照学生的分数从小到大排序的。然后我们在main里面呢,
又定义了mapstd的对象nt,啊,有个cstudent的对象st,
然后有个string用来存放读取的命令,然后我们就读取这个,一个,一条条的命令了。
如果读取来,进来的命令是add,就代表我要添加一个学生的信息,
那么我们就把学生的信息都读到这个st这个对象里面来,啊,读了他们的姓名、id和分数。
接下来我们要做的事情就是要把这个,呃,学生的信息给它插入到这个mp里面,所以我们要调用mp.insert。
但问题是呃,这个mp里放的东西必须是pair
模板类的对象。而我们现在,呃, 学生的信息是放在一个cstudent对象里面的,
我们不能直接把这个st往这个mp里面插,对吧?那我们就必须用一个,
嗯,pair模板类的对象,来存放,这个
学生的信息才可以。那怎么做呢?那我们
就在这里生成了一个pair模板类的对象,这个pair模板类就是mapstd value type,啊。
因为这个value type就等于就是指明了, 一种类型,value type的类型是什么呢?就是mapstd,
这种,呃,multimap的里面的元素的类型,就是这个value type。
那现在这个mapstd value type是一个类型的名字,然后后面又跟了一个圆括号。
然后圆括号里面呢,又给出了,呃,具体的参数。
当然就是构造函数的参数,那也就是说,这个insert这个函数里面的整个参数呢,就是一个临时的对象,这个对象是
,这个对象是一个pair模板类的对象。它的first 成员变量呢会等于st点score,啊,就是学生的分数。
它的second成员变量呢,会等于st点info,啊,就是学生的其他信息,包括id和姓名。
好了,现在我们现在就把这样一个pair模板类的对象给它插入到mp里面去了,
这当然就是把一个学生的完整信息都给它插入到这个mp里面去了。
好了,那如果我们,嗯,收到的指令是query,也就是要进行查询。
那怎么办呢?那我们先把要查的那个分数给,补进来。
好,接下来,我们要查的就是比这个score分数低的, 那个最高分,它的学生。
那怎么来做这件事情呢?那我们知道,在这个mp里面,所有学生都已经按照分数从小到大排序了,
现在我们要找一个,比某个分数低的,
一个最大的那个分数。这时候用什么办法来做啊? 当然我们就用这个
lowerbound来做这件事情。那我们要回忆一个这个lowerbound是做什么的。
啊,这个multimap的lowerbound,呃,它返回一个迭代器,呃,它的参数是一个待查找的值va,
val, 呃,它返回的一个迭代器叫做it,这个it有什么特点呢?
这个迭代器,它使得一个左闭右开的区间begin到it中所有
的元素的first成员变量,也就是关键字都比待查找的值val要小。
然后我们看,呃,在这儿,我们是要查找一个比score小的那个最高分对吧,所以我们用这个lowerbound
来进行查找,然后我们会,把查找的结果放到这个迭代器p里面。
那p就相当于是这边的这个it。那我们查找出来的一个区间,
begin到这边it,它里面所有的,呃,元素,它的first成员变量,也就是分数,
都会比这个score要小。但是呢,这个it,
呃,本身所指向的那个学生,他的分数呢,并不会比score要小。
好,现在我们就查找这样一个,一个p,迭代器出来了。
呃,那当我们要继续下一步的时候,还要去判断一下p是不是等于mp点begin。
如果p等于mp点begin就意味着什么呢?就意味着这一块啊,这一块这个东西,这个it就是begin了。
那么这个左闭右开的区间,起点是begin,终点是begin, 那等于这个区间就是空的,
那也就是说,如果,如果这个p啊,它是等于mp点begin的话,
就说嘛我们根本就没有查找到任何一个能符合分数,呃, 分数低于score的这样的一个学生的记录。
那所以当p不等于mp点begin的时候才说明,我们能找到符合条件的这个,这个学生。
那,那这时候p所指向的学生是不是符合条件呢?不是符合条件。
啊,p所指向的学生,在前一个学生才是符合条件的。
他的分数才是低于score的最高分,所以我们就--p,
让p值往前指向一个学生,--p之后,p所指向的那个学生,
他的分数就是低于score的最高分了。所以这个时候,我们就把p->first,也就是这个 低于score的最高分,我们给它记下来,记到score里面。
然后呢,由于分数=score的学生可能有多个,如果有多个的话,
我们就得把这多个学生全部都看一遍,然后找出id最大的那个学生。
那这样的话,我们就先假设,一个迭代器maxp,它指向
当前已经找到的id最大的那个学生,那当前找到的
就是p,对吧,然后我们用一个maxid变量, 记录当前已经找到的那个符合条件的学生里面
id最大的那个id,
然后接着我们,我们接下来就要通过一个循环,让 p倒着往前走。
一直走到什么时候才停止呢?如果p已经走到了begin,
都走到头了那当然就停下来。或者说发现p所指向的那个分数,
呃, 已经不等于score了,那我们也会停下来,对吧。那也就是说
只要p还没有到begin,以及p所指向的分数一直都是score,就是这个 這個符合条件的最高分,那我们就
要进行循环,对这个p所指向的学生进行
查看。好,现在我们对p所指向的学生进行查看,就是看,按他的
second成员变量。second成员变量是什么啊?就是一个学生除了
分数以外的其它信息。然后second成员变量里面就有一个id,就记录了这个
呃,学生的这个 记录了这个学生的id,对吧,然后我们就看p所指向的那个学生
的id,看它跟我们当前记下来的那个最大id比怎么样,如果比
maxid还要大的话,那我们呢,当然就要更新这个maxid,对吧。然后我们还要更新这个maxp。
maxp是我们当前找到的最优学生的那个
迭代器。对吧,那我们就更新这个maxp,好了,那这个循环结束以后,它有可能
由于两种原因结束,一种原因就是p=mp.begin;另一种原因就是p->first已经不等于这个score了。
那在这两种情况下,是要分别处理的。如果这个循环终止是因为
p=mp,begin才终止的,
那我们总而言之吧,这个循环终止以后,我们就要看看,终止的条件是不是,呃,这个
我们就要看下循环终止的时候,这个p->first是不是还跟score相等?如果还跟
这个最高分score相等的话呢,那我们还是要去判断一下p所指向的这个学生,
他的id是不是更大,如果是的话,还要更新这个当前找到的最优学生的迭代器,以及最优学生的这个id。
那整个循环执行完以后,我们就找到了这个最优这个学生了。
所以找到最优学生以后呢,我们就把这最优学生的信息给他输出,就行啦。输出姓名,
这个id,还有他的这个分数。那我们再看这块的这个
else,else实际上是对应于前面这个
if的,对应于前面的这个if的,那也就是说,如果走到else这里,就意味着
这个lower_bound刚才查的结果就是begin,说明没有人分数比那个待查询的分数低,那么我们当然就输出这个Nobody。
那这个程序稍微有一点复杂,但是它确实很典型地指明了这个multimap的用途。
里面这个lower_bound是非常好用的,从这里我们能看出来。
总之吧,就是这个关联容器,它特别适合用于, 呃,不断地要更新数据,以及要不断地在数据里面查询的这种情况。
因为你不管是添加一项数据,还是删除一项数据,实际上复杂度都是
log n的,然后你进行查询的时候,实际上复度的也是log n的,都很快。
另外我们再补充一点,就是我们前面看,往这个mp里面插入一个
这个学生的信息的时候,是这么写的,这个写法看上去还不那么舒服。实际上你也可以写mp.insert(make_pair
(st.score.st.info))。那这个make_pair呢,就是STL里面一个
函数模板。它的返回值就是一个pair
模板类的对象。然后这个对象,它的first成员变量跟st.score
是一样的,类型也相同啊。second成员变量就跟st.info是相同的,
那multimap说完了,接下来我们再说一下map,
map跟multimap是很像的,它的最重要的差别就在于
map里面不能够有两个元素,它的first成员变量是相同的。
那map的定义跟multimap很像,Key是代表 关键字的类型,T是值的类型,然后这是比较大小的这个规则。
那么map缺省的情况下,也是用less<key>,就是用"<"来
比大小的。那map的用法上跟multimap还有一个
重要的不同就是,map它有[ ]这个成员函数。那[ ]成员函数已经很好用了。
就是如果一个pairs,它是map的模板类的对象,
那么pairs[key]这个表达式是有定义的,在这里面呢,key实际上应该是一个,
类型和关键字相同的
那种变量或者是常量。
等于说这个表达式,它能够返回 对于关键字等于key的那个元素的值,
什么叫值啊?值就是second成员变量,它返回的是这个second成员变量的引用。
那如果没有关键字为key的元素, 这个时候呢,就会往pairs里面插入一个关键字为
key的元素。然后这个元素,它的值,也就是second成员变量,
是用无参构造函数初始化的,然后这个表达式一样会返回刚才那个
新插入元素的值,也就是second成员变量的引用。
那我们举个例子,比如说有一个map<int.double>这样的
map的容器类的对象pairs。那么我们写表达式pairs[50 ]=5,
这个表达式呢,就会修改pairs中关键字,也就是first成员变量为50的元素,
把它的值,也就是second成员变量变成5。
那如果pairs里面,没有关键字等于50的元素,那这个时候
一个新的元素就会被插到pairs里面,而且新元素的
关键字,也就是first成员变量值就是50,然后second成员变量,也就是值的值,就是5。
下面我们来看一个具体的这个例子啊,
我们使用map,#include <map>这个图文件,然后呢,我们在这里有一个,
对于<运算符的重载,目的是为了把
一个pair对象的那个内容,在屏幕上给它输出。
输出的方式是先输出左括号,然后是输出first前面,然后再加个逗号,再输出右 p.second,然后再输出右括号。
然后在main里面呢,我们定义了一个类型,叫做mmid。这个mmid是个什么类型呢?
是map<int, double,less<int> >。当然这个less<int>你不写也是一样的,如果你要写的话呢,这两个
大于号之间要加一个空格,否则有的编译器就会把它看做是又一运算符,那编译就会出错了啊。这是很怪异的一个地方。
好了,现在,我们这个,总之这个mmid它的类型是这样的, 那么也就是说,它是一个map,然后这个map里面的元素。
它的first成员变量是int类型的,然后second成员变量是double类型的。然后它们
关键字,也就是first成员变量排序的,比大小的方式就是用less来
比大小。归根到底就是用小于号来比大小、好,现在我们定义了一个mmid的
对象pairs,然后我们就
一开始就输出,这个pairs里面有多少个事物,那当然是没有事物,对吧,所以就输出0。
然后呢,我们就插入一个 元素进去,这个元素呢,是一个pair
模板类的对象,然后它的first成员变量是15,second成员变量是2.7,
然后我们插入,在下面再插入另外一个元素,这时候我们用到make_pair。
第二个元素它的first是15,second是99.3。
那我们要知道,map里面,它的
元素first关键字是不能重复的,那前面已经有一个元素,它的
first成员变量是15了,那么这个插入肯定就不能成功。
对吧。所以我们接下来再计算有多少个15。算出来,有两个。那这里我们有讲如果判断这个
insert它的操作是不是成功的,这一点跟set的情况是很类似的,大家去参
考set的那个例子,就是在调用insert的时候,如果里面原来有元素,它的first等于你
要插入的这个first的话,插入就会失败。好了,那接下来我们可以插入另外一个元素,就是这个20,9.3。
然后我们便利整个pairs,把所有的元素都输出,输出的结果就是这个,(15,2.7),(20,9.3)。
一共有两个元素,是按first成员变量从小到大排序的。接下来我们再看,我们看n=pairs[40],
那pairs[40]这个表达式吧,它的返回值是关键字为40的那个元素,它的second成员
变量的引用。如果不存在关键字为40的元素,会怎么样呢?就有一个新的元素会被
插入到pairs里面去。这个新的元素,关键字上就是40,它的second呢,在这个例子里面是被初始成为0,实际上second
应该是用无参构造函数初始化哦。然后我们就便利整个
pairs,会发现,在这个标号为4的这个输出,它多了一个元素出来就是(40,0)
再接着往下走,我们呢,pairs[15]=6.28,因为pairs[15],它的
返回值是,关键字为15的那个元素,它的second成员变量引用。所以这条语句就会把关键字为15的元素
它的second成员变量改成6.28,于是我们把pairs内容全部输出的时候,就发现这个(15,2.7)变成了
(15,6.28)。啊,总算把multiset也和set都讲完了。
唉,不扔了。
再扔夫人会有意见了。