map按键排序和按值排序

前几天做了一个关于字符串的题，题目要求寻找一个字符串中出现最多的子串是哪一个，没想到什么很有技巧的想法，于是就打算遍历所有的子串，利用一个map实现，其键值为对应的子串，value为子串出现的个数，遍历玩所有的子串后，只要寻找最大的value的键值就可以了，这里就想到一个问题，map一般是按键排序，能否按value排序？

首先给出上述题目的一个解法，然后再继续讨论：map按键排序和按值排序的问题。如下所示，map查询采用find不要直接查询（find要是没找到则返回MAP.end()），否则会将map中不存在的键值直接插入。

void substrCount(string str)
{
    map<string,int> substr;
    string subs;
    for(int i =1; i<str.size();i++)
        for(int j =0; j<=str.size()-i;j++)
        {
            subs = str.substr(j,i);                 //遍历每一个子串
            if(substr.find(subs)==substr.end())     //判断map中是否存在，存在则+1,不存在则插入
                substr[subs] = 1;
            else
                substr[subs] = substr[subs]+1;
        }

    pair<string, int> maxpair = *(substr.begin());     //寻找出现次数最多的子串
    map<string,int>::iterator it = substr.begin();
    while(it!=substr.end())
    {
        if(it->second >maxpair.second )
            maxpair = *it;
    }
    cout<<maxpair.first<<endl;
    cout<<maxpair.second<<endl;
}

---

map按键排序和按值排序的问题内容来自C++ STL中Map的按Key排序和按Value排序

按键排序

• 为了实现快速查找，map内部本身就是按序存储的（比如红黑树）。在我们插入<key, value>键值对时，就会按照key的大小顺序进行存储，其中key的类型必须能够进行<运算，且唯一，默认排序是按照从小到大便利记忆联想到需要支持小于运算
• map的模板定义如下

template < class Key, class T, class Compare = less<Key>,  
           class Allocator = allocator<pair<const Key,T> > > class map;  

其中第三、四个均包含默认参数，可以不指定。我们可以通过指定Compare类来指定排序的顺序。其中less<Key>是stl里面的一个函数对象（即调用操作符的类，其对象常称为函数对象（function object），它们是行为类似函数的对象，表现出一个函数的特征，就是通过“对象名+(参数列表)”的方式使用一个 类，其实质是对operator()操作符的重载）其具体定义如下

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

它是一个带模板的struct，里面仅仅对()运算符进行了重载。与less相对的有greater，定义如下

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

• 因此我们在定义map的时候，可以指定如下

map<string,int,greater<string> >

或者定义自己的比较类comLen如下

struct comLen{
     bool operator(const string &lhs, const string &rhs)
     {return lhs.length()<rhs.length();}
}
map<string,int,comLen> LenLessMap;

按value排序

• 如何实现Map的按Value排序呢？
  第一反应是利用stl中提供的sort算法实现，这个想法是好的，不幸的是，sort算法有个限制，利用sort算法只能对序列容器进行排序，就是线性的（如vector，list，deque）。map是一个集合容器，它里面存储的元素是pair，不是线性存储的（前面提过，像红黑树），所以利用sort不能直接和map结合进行排序。
• 迂回一下，把map中的元素放到序列容器（如vector）中，然后再对这些元素进行排序。要对序列容器中的元素进行排序，也有个必要条件：就是容器中的元素必须是可比较的，也就是实现了<操作的。
• map是元素为pair，其已实现<操作符的重载

template<class T1, class T2>  
  inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y)  
  { return x.first < y.first   || (!(y.first < x.first) && x.second < y.second); }

• x.first < y.first指键值小于的情况
• (!(y.first < x.first) && x.second < y.second);结合前面的情况指键相等的情形下value的情况
• 为什么不直接写 x.first == y.first 呢？ 前面讲过，作为map的key必须实现<操作符的重载，但是并不保证==符也被重载了。
• 但上述的<操作过程不太符合我们的要求，从sort角度考虑，其定义如下

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

与map一样均可以指定比较的类。可以定义如下的比较的类或者对象

class combyValue
{
     bool operator()(pair<string,int> &lhs,pair<string,int> &rhs)
     {return lhs.second<rhs.second;}
}

• 最后可以如下实现按照value排序

map<string,int> m;
元素插入过程
vector<pair<string,int> > vec(m.begin(),m.end());
sort(vec.begin(),vec.end(),combyValue);

---

因此最开始的那道题如果需要排序的话可以按如下方式写

struct CmpByValue {  
  bool operator()(const pair<string,int> & lhs, const pair<string,int> & rhs)
  {return lhs.second > rhs.second;}  
};

void substrcount(string str)
{
    map<string,int> substr;
    string subs;
    for(int i =1; i<str.size();i++)
        for(int j =0; j<=str.size()-i;j++)
        {
            subs = str.substr(j,i);
            if(substr.find(subs)==substr.end())
                substr[subs] = 1;
            else
                substr[subs] = substr[subs]+1;
        }

    vector<pair<string,int>> counts(substr.begin(),substr.end());
    sort(counts.begin(),counts.end(),CmpByValue());
    cout<<counts.begin()->first<<endl;
    cout<<counts.begin()->second<<endl;
}

---

reference

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