C++中std::map自定义排序与std::unordered_map自定义哈希函数__std map unordered_map

一、map按键值Key排序

1. 默认按照 `less<key>` 升序排列

输入8，Key升序，Value随机：
 1 #include<iostream>
 2 #include<map>
 3 using namespace std;
 4 int main()
 6     srand((unsigned)time(NULL));
 7     multimap<int,int>mp;
 8 // multimap第三个参数默认为less<Key>,即 less<int>
 9     int n;
10     cin>>n;
11     int a,b;
12     for(int i=0; i<n; i++)
13     {
14         a=rand()%4;
15         b=rand()%4;
16         //插入
17         mp.insert(pair<int,int>(a,b));
18     }
19     map<int,int>::iterator iter;
20     //遍历输出
21     for(iter=mp.begin(); iter!=mp.end(); iter++)
22         cout<<iter->first<<" "<<iter->second<<endl;
23     return 0;
View Code
2. 定义map时，用greater< Key>实现按Key值递减插入数据
1 multimap<int,int,greater<int> >mp;
2 //注意<int>后空一格
3. 当Key值为自定义的类时
　　方法1：写一个函数对象1（仿函数），重载operator()
　　注意：函数对象：即调用操作符的类，其对象常称为函数对象（function object），它们是行为类似函数的对象。表现出一个函数的特征，就是通过“对象名+(参数列表)”的方式使用一个 类，其实质是对operator()操作符的重载。
 1 #include<iostream>
 2 #include<map>
 3 using namespace std;
 4 typedef struct tagIntPlus
 6     int num,i;
 7 }IntPlus;
 8 //自定义比较规则
 9 //注意operator是(),不是＜
10 struct Cmp
12     bool operator () (IntPlus const &a,IntPlus const &b)const
13     {
14         if(a.num!=b.num)
15             return a.num<b.num;
16         else return a.i<b.i;
17     }
18 };
19 int main()
21     srand((unsigned)time(NULL));
22     //注意此处一定要有Cmp，否则无法排序会报错
23     multimap<IntPlus,int,Cmp>mp;
24     int n;
25     cin>>n;
26     int a,b;
27     IntPlus intplus;
28     for(int i=0; i<n; i++)
29     {
30         a=rand()%4;
31         b=rand()%4;
32         intplus.num=a;
33         intplus.i=b;
34         mp.insert(pair<IntPlus,int>(intplus,i));
35     }
36     map<IntPlus,int>::iterator iter;
37     for(iter=mp.begin(); iter!=mp.end(); iter++)
38         cout<<iter->first.num<<" "<<iter->first.i<<" "<<iter->second<<endl;
39     return 0;
View Code
　　方法2：在类里重载重载operator<
 1 typedef struct tagIntPlus
 3     int num,i;
 4     bool operator < (tagIntPlus const& intplus)const
 5     {
 6         //当num不等时
 7         //前一个对象的num>后一个时返回true,降序排列。
 8         //反之升序排列
 9         if(num!=intplus.num)
10             return num>intplus.num;
11         //当num相等时
12         //前一个对象的i<后一个时返回true,升序排列
13         else return i<intplus.i;
14     }
15 }IntPlus;
View Code
　　注意只重载小于号,不要去重载大于号，如果想改变为 升 / 降序列,只需改变判断条件即可。
1 multimap<IntPlus,int>mp;
　　主函数只需将第一种方法中的map中的Cmp去掉即可。
4. 用char*类型作为map的主键
　　find或count时，默认使用== 进行判断，char*只是指针，如果两个字符串值相同，但是地址不同，是无法匹配的。所以最好使用std::string。如果非要用char*，需要使用find_if函数并且用bind2sd函数指定比较函数。
 1 #include <map>
 2 #include <algorithm>
 3 #include <iostream>
 5 using namespace std;
 7 bool search(pair<char*, int> a, const char* b)
 9     return strcmp(a.first, b) == 0 ? true : false;
11 int main()
13     map<char*, int> test;
14     test.insert(pair<char*, int>("abc", 1));
16     map<char*, int>::const_iterator iter = find_if(test.begin(), test.end(),  bind2nd(ptr_fun(search), "abc"));
18     if (iter != test.end())
19     {
20         cout<< "find : " << iter->first << endl;
21     }
23     return 0;
二、map按值Value排序
　　再次强调不能用sort，只能将map中数据压入能用sort的容器，如vector
 1 #include<iostream>
 2 #include<map>
 3 #include<vector>
 4 #include<algorithm>//sort
 5 using namespace std;
 7 typedef struct tagIntPlus
 9     int num,i;
10 } IntPlus;
12 typedef pair<tagIntPlus,int> PAIR;
　　必须有Cmp。虽然之后会sort，map的排序并不重要，但是map输入数据时需要比较Key值，没有会报错。注意这里说的是自定义类型作为key需要加Cmp函数。
1 struct Cmp
3     bool operator () (IntPlus const &a,IntPlus const &b)const
4     {
5         if(a.num!=b.num)
6             return a.num<b.num;
7         else return a.i<b.i;
8     }
View Code
　　map会按键值Key升序排列，Value值无要求。定义vector的排序接口如下
 1 bool vec_cmp(PAIR const&a,PAIR const&b)
 3     if(a.first.num!=b.first.num)
 4         return a.first.num<b.first.num;
 5     else
 6     {
 7         if(a.first.i!=b.first.i)
 8             return a.first.i<b.first.i;
 9         else return a.second>b.second;
10     }
　　上面需重新定义Key升序排列，否则sort之后仅按Value降序排列，Key值被打乱。
 1 int main()
 3     srand((unsigned)time(NULL));
 4     multimap<IntPlus,int,Cmp>mp;
 5     int n;
 6     cin>>n;
 7     int a,b;
 8     IntPlus intplus;
 9     for(int i=0; i<n; i++)
10     {
11         a=rand()%4;
12         b=rand()%4;
13         intplus.num=a;
14         intplus.i=b;
15         mp.insert(pair<IntPlus,int>(intplus,i));
16     }
17     map<IntPlus,int>::iterator iter;
18     cout<<"排序前:"<<endl;
19     for(iter=mp.begin(); iter!=mp.end(); iter++)
20         cout<<iter->first.num<<"|"<<iter->first.i<<"|"<<iter->second<<endl;
View Code
1     cout<<"排序后:"<<endl;
2     vector<PAIR>vec(mp.begin(),mp.end());
3     sort(vec.begin(),vec.end(),vec_cmp);
4     int size=vec.size();
5     for(int i=0;i<size;i++)
6         cout<<vec[i].first.num<<"|"<<vec[i].first.i<<"|"<<vec[i].second<<endl;
7     return 0;
 三、std::unorder_map自定义键值类型(转载)
　　对于unordered_map而言，当我们插入<key, value>的时候，需要哈希函数的函数对象对key进行hash，又要利用等比函数的函数对象确保插入的键值对没有重复。然而，当我们自定义类型时，c++标准库并没有对应的哈希函数和等比函数的函数对象。因此需要分别对它们进行定义。
　　因为都是函数对象，它们两个的实际定义方法并没有很大差别。不过后者比前者多了一个方法。因为等比函数的函数对象默认值std::equal_to<key>内部是通过调用操作符"=="进行等值判断，因此我们可以直接在自定义类里面进行operator==()重载（成员和友元都可以）。
　　因此，如果要将自定义类型作为unordered_map的键值，需如下两个步骤：
　　　　a-定义哈希函数的函数对象；
　　　　b-定义等比函数的函数对象或者在自定义类里重载operator==()。
　　为了避免重复，下文以讨论哈希函数的函数对象为主，参数4则是通过直接在自定义类里面对operator==()进行重载。
　　首先简要介绍一下函数对象 (在一、二部分已介绍) 的概念：在《C++ Primer Plus》里面，函数对象是可以以函数方式与()结合使用的任意对象。这包括函数名、指向函数的指针和重载了“operator()”操作符的类对象。基于此，我们提出3个方法。
方法1：std::function
　　利用std::function为person_hash()构建函数实例。初始化时，这个函数实例就会被分配那个指向person_hash()的指针（通过构造函数实现），如下所示。
 1 #include <iostream>
 2 #include <unordered_map>
 3 #include <string>
 4 #include <functional>
 6 using namespace std;
 8 class Person{
 9 public:
10     string name;
11     int age;
13     Person(string n, int a){
14         name = n;
15         age = a;
16     }
17     bool operator==(const Person & p) const 
18     {
19        return name == p.name && age == p.age;
20     }
21 };
23 size_t person_hash( const Person & p ) 
25     return hash<string>()(p.name) ^ hash<int>()(p.age);
28 int main(int argc, char* argv[])
30     //ERRO: unordered_map<Person,int,decltype(&person_hash)> ids;
31     //ERRO: unordered_map<Person,int,person_hash> ids(100, person_hash );
32     //OK: unordered_map<Person, int, decltype(&person_hash)> ids(100, person_hash );
33     unordered_map<Person,int,function<size_t( const Person& p )>> ids(100, person_hash); //需要把person_hash传入构造函数
34     ids[Person("Mark", 17)] = 40561;
35     ids[Person("Andrew",16)] = 40562;
36     for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
37         cout << ii->first.name 
38         << " " << ii->first.age 
39         << " : " << ii->second 
40         << endl;
41         return 0;
View Code
　　因为std::function构建对象的表达过于复杂，我们可以利用C++11新增的关键字decltype。它可以直接获取自定义哈希函数的类型，并把它作为参数传送。因此，ids的声明可以改成下面这样。
unordered_map<Person,int,decltype(&person_hash)> ids(100, person_hash);
　　另外，我们还可以引入c++11新支持的lambda expression，程序如下。
 1 #include <iostream>
 2 #include <unordered_map>
 3 #include <string>
 4 #include <functional>
 6 using namespace std;
 8 class Person{
 9 public:
10     string name;
11     int age;
13     Person(string n, int a){
14         name = n;
15         age = a;
16     }
18     bool operator==(const Person & p) const 
19     {
20         return name == p.name && age == p.age;
21     }
22 };
24 int main(int argc, char* argv[])
26     unordered_map<Person,int,std::function<size_t (const Person & p)>>
27     ids(100, []( const Person & p)
28              {
29                  return hash<string>()(p.name) ^ hash<int>()(p.age);
30              } );
31     ids[Person("Mark", 17)] = 40561;
32     ids[Person("Andrew",16)] = 40562;
33     for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
34         cout << ii->first.name 
35         << " " << ii->first.age
36         << " : " << ii->second 
37         << endl;
38         return 0;
View Code
　　但是，使用lambda有2个弊端：
我们就无法使用decltype获取函数对象的类型，而只能用更复杂的std::function方法。
程序的可读性下降。
方法2：重载operator()的类
　　方法2就是利用重载operator()的类，将哈希函数打包成可以直接调用的类。此时，虽然我们仍然需要第3个参数，但是我们不需要将函数对象的引用传入构造器里。因为unordered_map会追踪类定义，当需要获得哈希时，它可以动态地构造对象并传递数据，如下所示。
 1 #include <iostream>
 2 #include <string>
 3 #include <unordered_map>
 4 #include <functional>
 5 using namespace std;
 7 class Person{
 8 public:
 9     string name;
10     int age;
12     Person(string n, int a){
13         name = n;
14         age = a;
15     }
17     bool operator==(const Person & p) const 
18     {
19         return name == p.name && age == p.age;
20     }
21 };
23 struct hash_name{
24     size_t operator()(const Person & p) const{
25         return hash<string>()(p.name) ^ hash<int>()(p.age);
26     }
27 };
29 int main(int argc, char* argv[]){
30     unordered_map<Person, int, hash_name> ids; //不需要把哈希函数传入构造器
31     ids[Person("Mark", 17)] = 40561;
32     ids[Person("Andrew",16)] = 40562;
33     for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
34         cout << ii->first.name 
35         << " " << ii->first.age
36         << " : " << ii->second
37         << endl;
38     return 0;
View Code
方法3：模板定制
　　unordered_map第3个参数的默认参数是std::hash<Key>，实际上就是模板类。那么我们就可以对它进行模板定制，如下所示。
 1 #include <iostream>
 2 #include <unordered_map>
 3 #include <string>
 4 #include <functional>
 5 using namespace std;
 7 typedef pair<string,string> Name;
 9 namespace std {
10     template <> //function-template-specialization
11         class hash<Name>{
12         public :
13             size_t operator()(const Name &name ) const
14             {
15                 return hash<string>()(name.first) ^ hash<string>()(name.second);
16             }
17     };
18 };
20 int main(int argc, char* argv[])
22     unordered_map<Name,int> ids;
23     ids[Name("Mark", "Nelson")] = 40561;
24     ids[Name("Andrew","Binstock")] = 40562;
25     for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
26         cout << ii->first.first 
27              << " " << ii->first.second 
28              << " : " << ii->second
29              << endl;
30     return 0;
View Code
　　当我们将模板订制包含在定义类的头文件中时，其他人无需额外工作，就可以直接用我们的类作为任何无序容器的键。这对于要使用我们自定义类的人来说，绝对是最方便的。因此，如果你想要在多个地方用这个类，方法3是最好的选择。当然，你要确保自己的hash function不会影响std空间里的其他类。
————————————————
额外案例：等比函数的函数对象
　　下例是哈希函数对象和等比函数对象都采用模板定制的方法。
 1 #include <iostream>
 2 #include <string>
 3 #include <unordered_map>
 4 #include <functional>
 5 using namespace std;
 7 class Person{
 8 public:
 9     string name;
10     int age;
12     Person(string n, int a){
13         name = n;
14         age = a;
15     }
16 };
18 namespace std{
19     template<>
20     struct hash<Person>{//哈希的模板定制
21     public:
22         size_t operator()(const Person &p) const 
23         {
24             return hash<string>()(p.name) ^ hash<int>()(p.age);
25         }
27     };
29     template<>
30     struct equal_to<Person>{//等比的模板定制
31     public:
32         bool operator()(const Person &p1, const Person &p2) const
33         {
34             return p1.name == p2.name && p1.age == p2.age;
35         }
37     };
40 int main(int argc, char* argv[]){
41     unordered_map<Person, int> ids;
42     ids[Person("Mark", 17)] = 40561;
43     ids[Person("Andrew",16)] = 40562;
44     for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
45         cout << ii->first.name 
46         << " " << ii->first.age
47         << " : " << ii->second
48         << endl;
49     return 0;
View Code
————————————————
没有坚守就没有事业，没有执着就没有未来！
一、map按键值Key排序

1. 默认按照 less<key> 升序排列

2. 定义map时，用greater< Key>实现按Key值递减插入数据

3. 当Key值为自定义的类时

方法1：写一个函数对象1（仿函数），重载operator()

方法2：在类里重载重载operator<

4. 用char*类型作为map的主键

方法1：std::function

方法2：重载operator()的类

方法3：模板定制

额外案例：等比函数的函数对象

1. 默认按照 `less<key>` 升序排列

　　方法1：写一个函数对象1（仿函数），重载operator()

　　方法2：在类里重载重载operator<
