搜狗面试的经典题（map按值排序）

一：起因

（1）java  Map排序（key,value)，请看另一篇博客 java Map排序 

（2）c++ map排序（key,value)，可以对c++ map和java Map进行对比：之一，c++的map默认按照key值进行排序，而且就是map了；java Map HashMap是随

机的，不进行排序的。之二，c++声明对象直接Map map(^)的，不用= new的

（3）c++ 按value值排序，map是不能直接排序的，它虽然也是一个数据集合，第一反应是利用stl中提供的sort算法实现，这个想法是好的，不幸的是，sort算法

有个限制，利用sort算法只能对序列容器进行排序，就是线性的（如vector，list，deque）。map也是一个集合容器，但是它里面存储的元素是pair，它不是

线性存储的（前面提过，像红黑树），所以利用sort不能直接和map结合进行排序。

二：代码实现

（1）先看pair类

template <class T1, class T2> struct pair  
{  
	 typedef T1 first_type;  
	 typedef T2 second_type;    
	 T1 first;  
	 T2 second;  
	 pair() : first(T1()), second(T2()) {}  
	pair(const T1& x, const T2& y) : first(x), second(y) {}  
	template <class U, class V>  
    pair (const pair<U,V> &p) : first(p.first), second(p.second) { }  
}

（2）再看sort类

template <class RandomAccessIterator>  
void sort ( RandomAccessIterator first, RandomAccessIterator last );  
	  
template <class RandomAccessIterator, class Compare>  
void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp ); 

（3）完整代码

#include<map>
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<string, int> PAIR;
// 原来还可以这样的重载的(⊙o⊙)哦，长见识了
ostream& operator<<(ostream& out, const PAIR& p)
{
    return out << p.first << "\t" << p.second;
}
template<class T1>
struct compareByKeyLen
{// 从短到长
    bool operator()(const T1 &s1,const T1 &s2)
    {
        return s1.length()<=s2.length()?true:false;// 记得有等号的哦，否则，长度相等的就舍去了
    }
};
template<class T1>
struct compareByValue
{
    bool operator()(const T1 &lhs, const T1 &rhs)
    {
        return lhs.second<=rhs.second ? true:false;
    }
};

int main()
{
    //map<string, int> name_score_map;//字典的顺序，从小到大
    //默认的是map<string,int,less<string>>

    //map<string, int, greater<string> > name_score_map;// 注意> >有空格的，否则cin>>了；
    //字典的逆序，从大到小

    //map<string, int, compareByKeyLen<string> > name_score_map;
    // 自己写的compareByKeyLen<>结构体

    map<string, int> name_score_map;

    name_score_map["ZhaoBo2"] = 90;
    name_score_map["XuQingzhu"] = 79;
    name_score_map["LiBing"] = 92;
    name_score_map.insert(make_pair("ChiXiaotong",99));
    name_score_map.insert(make_pair("WangZhaoxian",86));

    vector<PAIR> name_score_vec(name_score_map.begin(),name_score_map.end());
    sort(name_score_vec.begin(),name_score_vec.end(),compareByValue<PAIR>());
    for(int i=0;i<name_score_vec.size();i++)
    {
        cout << name_score_vec[i] << endl;
    }
//    for (map<string, int>::iterator iter = name_score_map.begin();
//               iter != name_score_map.end();++iter)
//    {
//       cout << *iter << endl;
//    }
    return 0;
}

三：按key值排序（c++ map 带有比较类的，这和java一样，java也带有类似的比较类）

（1）compare类自己定义

比如，按照学生姓名的长短排序进行存储，那该怎么做呢？

其实很简单，只要我们自己写一个函数对象，实现想要的逻辑，定义map的时候把Compare指定为我们自己编写的这个就ok啦。

template<class T1>
struct compareByKeyLen
{// 从短到长
    bool operator()(const T1 &s1,const T1 &s2)
    {
        return s1.length()<=s2.length()?true:false;// 记得有等号的哦，否则，长度相等的就舍去了
    }
};

是不是很简单！这里我们不用把它定义为模板，直接指定它的参数为string类型就可以了。

#include<map>
#include<string>
#include<iostream>
using namespace std;

typedef pair<string, int> PAIR;
// 原来还可以这样的重载的(⊙o⊙)哦，长见识了
ostream& operator<<(ostream& out, const PAIR& p)
{
    return out << p.first << "\t" << p.second;
}
template<class T1>
struct compareByKeyLen
{// 从短到长
    bool operator()(const T1 &s1,const T1 &s2)
    {
        return s1.length()<=s2.length()?true:false;// 记得有等号的哦，否则，长度相等的就舍去了
    }
};
int main()
{
    //map<string, int> name_score_map;//字典的顺序，从小到大
    //默认的是map<string,int,less<string>>

    //map<string, int, greater<string> > name_score_map;// 注意> >有空格的，否则cin>>了；
    //字典的逆序，从大到小
    map<string, int, compareByKeyLen > name_score_map;
    name_score_map["ZhaoBo"] = 90;
    name_score_map["XuQingzhu"] = 79;
    name_score_map["LiBing"] = 92;
    name_score_map.insert(make_pair("ChiXiaotong",99));
    name_score_map.insert(make_pair("WangZhaoxian",86));
    for (map<string, int>::iterator iter = name_score_map.begin();
               iter != name_score_map.end();++iter)
    {
       cout << *iter << endl;
    }
    return 0;
}

这一点有点类似java的map 但是还是不一样的，感觉java倒是麻烦一些了。