C++：map自定义排序

自定义排序"/>

C++：map自定义排序

前言：
昨日做leetcode692：前K个高频单词(medium)这道题的时候，本来以为map可以使用直接用sort排序的，后来发现sort排序不能针对关联容器，因为sort会破环关联容器的底层数据结构，详细解释如下。

map：

map中的元素是pair类型对象，每个pair类型由关键字—值（key-value）组成：关键字起到索引的作用，值则表示与索引相关联的数据。字典是一个很好的map例子，可以将单词作为关键字，将单词释义作为值。
map使用的底层数据结构为一颗红黑树（红黑树是一颗高度平衡二叉排序树），因为map的各种操作接口，RB-Tree也都提供了，所以几乎所有的map操作行为，都只是转调用了RB-Tree的操作行为而已。TB-Tree中的key是按弱序排序的，因此map中的key也是按弱序排列的，所以任意更改map的key会严重破坏map组织的，也就是key不能修改（key也就不能使用sort排序。）

1、map按key排序

map的模板定义：

template <class _Key, class _Tp,           class _Compare __STL_DEPENDENT_DEFAULT_TMPL(less<_Key>),class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >class map;

• 1）一般情况下，我们定义一个map是直接使用前两个参数的，也就是说我们一般都指定key和value的类型，没有指定Compare类的类型。所以默认情况下，key的类型必须能够进行<运算，且唯一，也就说关键字类型key必须严格弱序。
• 2）当我们使用Compare类来自定义排序关键字类型key的时候，必须要保证“行为正常”的<运算符或>运算符。

补充：less和greater是两个关系类仿函数，可以用来指定关键字key的顺序，模板如下：

template <class T> struct less : binary_function <T,T,bool> {  bool operator() (const T& x, const T& y) const  {return x<y;}  
};
template <class T> struct greater : binary_function <T,T,bool> {  bool operator() (const T& x, const T& y) const  {return x>y;}  
};  

结论：

所以当我们打算用map的key排序时，就必须在定义一个map类型对象的时候，指定一个有严格弱序或强序的Compare类。

//自定义map的key排列顺序
map<string,int,greater<string>> m1;
struct myCompare {bool operator()(const string& l, const string& r)const{return l.length() > r.length();}
};
map<string,int,myCompare> m2;

2、map按value排序

如何实现Map的按Value排序呢？

第一反应是利用stl中提供的sort算法实现，这个想法是好的，不幸的是，sort算法有个限制，利用sort算法只能对线性容器进行排序（如vector，list，deque）。map是一个集合容器，它里面存储的元素是pair，不是线性存储的（前面提过，像红黑树），所以利用sort不能直接和map结合进行排序。

迂回一下，把map中的元素放到序列容器（如vector）中，然后再对这些元素进行排序。要对序列容器中的元素进行排序，也有个必要条件：就是容器中的元素必须是可比较的，也就是实现了<操作的。
map是元素为pair，其已实现<操作符的重载

代码如下：

bool compare(const pair<string,int>& a,const pair<string,int>& b){if(a.second==b.second)return a.first<b.first;else return a.second>b.second;
}
map<string,int> m{{"a",1},{"b",2},{"c",3}};vector<pair<string,int>> v(m.begin(),m.end());//将map中的元素拷贝到vector中sort(v.begin(),v.end(),compare);//实现value的排序