C++-STL中Map的按Key排序和按Value排序

C++STL中Map的按Key排序和按Value排序map是用来存放key,value键值对的数据结构，可以很方便快速的根据key查到相应的value。假如存储学生和其成绩（假定不存在重名，当然可以对重名加以区分），我们用map来进行存储就是个不错的选择。我们这样定义，mapstring,int，其中学生姓名用string类型，作为Key；该学生的成绩用int类型，作为value。这样一来，我们可以根据学生姓名快速的查找到他的成绩。但是，我们除了希望能够查询某个学生的成绩，或许还想看看整体的情况。我们想把所有同学和他相应的成绩都输出来，并且按照我们想要的顺序进行输出：比如按照学生姓名的顺序进行输出，或者按照学生成绩的高低进行输出。换句话说，我们希望能够对map进行按Key排序或按Value排序，然后按序输出其键值对的内容。一、C++STL中Map的按Key排序其实，为了实现快速查找，map内部本身就是按序存储的（比如红黑树）。在我们插入key,value键值对时，就会按照key的大小顺序进行存储。这也是作为key的类型必须能够进行运算比较的原因。现在我们用string类型作为key，因此，我们的存储就是按学生姓名的字典排序储存的。【参考代码】1.#includemap2.#includestring3.#includeiostream4.usingnamespacestd;5.6.typedefpairstring,intPAIR;7.8.ostream&operator(ostream&out,constPAIR&p){9.returnoutp.first\tp.second;10.}11.12.intmain(){13.mapstring,intname_score_map;14.name_score_map[LiMin]=90;15.name_score_map[ZiLinMi]=79;16.name_score_map[BoB]=92;17.name_score_map.insert(make_pair(Bing,99));18.name_score_map.insert(make_pair(Albert,86));19.for(mapstring,int::iteratoriter=name_score_map.begin();20.iter!=name_score_map.end();21.++iter){22.cout*iterendl;23.}24.return0;25.}【运行结果】大家都知道map是stl里面的一个模板类，现在我们来看下map的定义：1.templateclassKey,classT,classCompare=lessKey,2.classAllocator=allocatorpairconstKey,Tclassmap;它有四个参数，其中我们比较熟悉的有两个:Key和Value。第四个是Allocator，用来定义存储分配模型的，此处我们不作介绍。现在我们重点看下第三个参数：classCompare=lessKey这也是一个class类型的，而且提供了默认值lessKey。less是stl里面的一个函数对象，那么什么是函数对象呢？所谓的函数对象：即调用操作符的类，其对象常称为函数对象（functionobject），它们是行为类似函数的对象。表现出一个函数的特征，就是通过“对象名+(参数列表)”的方式使用一个类，其实质是对operator()操作符的重载。现在我们来看一下less的实现：1.templateclassTstructless:binary_functionT,T,bool{2.booloperator()(constT&x,constT&y)const3.{returnxy;}4.};它是一个带模板的struct，里面仅仅对()运算符进行了重载，实现很简单，但用起来很方便，这就是函数对象的优点所在。stl中还为四则运算等常见运算定义了这样的函数对象，与less相对的还有greater：1.templateclassTstructgreater:binary_functionT,T,bool{2.booloperator()(constT&x,constT&y)const3.{returnxy;}4.};map这里指定less作为其默认比较函数(对象)，所以我们通常如果不自己指定Compare，map中键值对就会按照Key的less顺序进行组织存储，因此我们就看到了上面代码输出结果是按照学生姓名的字典顺序输出的，即string的less序列。我们可以在定义map的时候，指定它的第三个参数Compare，比如我们把默认的less指定为greater：【参考代码】1.#includemap2.#includestring3.#includeiostream4.usingnamespacestd;5.6.typedefpairstring,intPAIR;7.8.ostream&operator(ostream&out,constPAIR&p){9.returnoutp.first\tp.second;10.}11.12.intmain(){13.mapstring,int,greaterstringname_score_map;14.name_score_map[LiMin]=90;15.name_score_map[ZiLinMi]=79;16.name_score_map[BoB]=92;17.name_score_map.insert(make_pair(Bing,99));18.name_score_map.insert(make_pair(Albert,86));19.for(mapstring,int::iteratoriter=name_score_map.begin();20.iter!=name_score_map.end();21.++iter){22.cout*iterendl;23.}24.return0;25.}【运行结果】现在知道如何为map指定Compare类了，如果我们想自己写一个compare的类，让map按照我们想要的顺序来存储，比如，按照学生姓名的长短排序进行存储，那该怎么做呢？其实很简单，只要我们自己写一个函数对象，实现想要的逻辑，定义map的时候把Compare指定为我们自己编写的这个就ok啦。1.structCmpByKeyLength{2.booloperator()(conststring&k1,conststring&k2){3.returnk1.length()k2.length();4.}5.};是不是很简单！这里我们不用把它定义为模板，直接指定它的参数为string类型就可以了。【参考代码】1.intmain(){2.mapstring,int,CmpByKeyLengthname_score_map;3.name_score_map[LiMin]=90;4.name_score_map[ZiLinMi]=79;5.name_score_map[BoB]=92;6.name_score_map.insert(make_pair(Bing,99));7.name_score_map.insert(make_pair(Albert,86));8.for(mapstring,int::iteratoriter=name_score_map.begin();9.iter!=name_score_map.end();10.++iter){11.cout*iterendl;12.}13.return0;14.}【运行结果】二、C++STL中Map的按Value排序在第一部分中，我们借助map提供的参数接口，为它指定相应Compare类，就可以实现对map按Key排序，是在创建map并不断的向其中添加元素的过程中就会完成排序。现在我们想要从map中得到学生按成绩的从低到高的次序输出，该如何实现呢？换句话说，该如何实现Map的按Value排序呢？第一反应是利用stl中提供的sort算法实现，这个想法是好的，不幸的是，sort算法有个限制，利用sort算法只能对序列容器进行排序，就是线性的（如vector，list，deque）。map也是一个集合容器，它里面存储的元素是pair，但是它不是线性存储的（前面提过，像红黑树），所以利用sort不能直接和map结合进行排序。虽然不能直接用sort对map进行排序，那么我们可不可以迂回一下，把map中的元素放到序列容器（如vector）中，然后再对这些元素进行排序呢？这个想法看似是可行的。要对序列容器中的元素进行排序，也有个必要条件：就是容器中的元素必须是可比较的，也就是实现了操作的。那么我们现在就来看下map中的元素满足这个条件么？我们知道map中的元素类型为pair，具体定义如下：1.templateclassT1,classT2structpair2.{3.typedefT1first_type;4.typedefT2second_type;5.6.T1first;7.T2second;8.pair():first(T1()),second(T2()){}9.pair(constT1&x,constT2&y):first(x),second(y){}10.templateclassU,classV11.pair(constpairU,V&p):first(p.first),second(p.second){}12.}pair也是一个模板类，这样就实现了良好的通用性。它仅有两个数据成员first和second，即key和value，而且在utility头文件中，还为pair重载了运算符，具体实现如下：1.templateclass_T1,class_T22.inlinebool3.operator(constpair_T1,_T2&__x,constpair_T1,_T2&__y)4.{return__x.first__y.first5.||(!(__y.first__x.first)&&__x.second__y.second);}重点看下其实现：1.__x.first__y.first||(!(__y.first__x.first)&&__x.second__y.second)这个less在两种情况下返回true，第一种情况：__x.first__y.first这个好理解，就是比较key，如果__x的key小于__y的key则返回true。第二种情况有点费解：!(__y.first__x.first)&&__x.second__y.second当然由于||运算具有短路作用，即当前面的条件不满足是，才进行第二种情况的判断。第一种情况__x.first__y.first不成立，即__x.first=__y.first成立，在这个条件下，我们来分析下!(__y.first__x.first)&&__x.second__y.second!(__y.first__x.first)，看清出，这里是y的key不小于x的key，结合前提条件，__x.first__y.first不成立，即x的key不小于y的key即：!(__y.first__x.first)&&!(__x.first__y.first)等价于__x.first==__y.first,也就是说，第二种情况是在key相等的情况下，比较两者的value（second）。这里比较令人费解的地方就是，为什么不直接写__x.first==__y.first呢？这么写看似费解，但其实也不无道理：前面