C++ 标准库中现在存在两种形式的Key-Value容器，map和unordered_map。
unordered_map是C++ 11后面新加入标准库的。
主要区别：
map:它是有序的，内部实现是一颗红黑树，相比unordered_map内存消耗少,因为unordered_map有一个巨大的数组，也就是哈希表，会有很多空间的浪费。
unordered_map:无序，通过哈希函数来生成key，插入和删除，查询的效率更高，但是需要注意的一点是如果提前不知道unordered_map的size，没有reserve的话，那么插入的时候会经常不断的reserve，那么所有的元素都需要rehash，这是比较耗时的。
还有一个需要注意的地方，map比unorderd_map要更加稳定，在循环迭代输出的时候，map要比unordered_map更快。
用法：
由于map是按照Key值有序的，所以map中作为key的类型必须要重载”<”，例如自定义类型：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#include <string>
#include <map>
using namespace std;
struct Person {
string name;
int age;
Person(string name_, int age_):name(name_)
, age(age_) {}
bool operator<(const Person& p) const {
return this->age < p.age;
}
};
int main()
{
map<Person, string> map;
map.emplace(Person("txm", 23), "huster");
return 0;
}
如果不重载”<”，则会报错，或者这样，声明一个比较器：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28#include <string>
#include <map>
using namespace std;
struct Person {
string name;
int age;
Person(string name_, int age_):name(name_)
, age(age_) {}
};
struct personCmp {
bool operator()(const Person& p,const Person &q) const {
return p.age < q.age;
}
};
int main()
{
map<Person, string,personCmp> map;
map.emplace(Person("txm", 23), "huster");
return 0;
}
那么，该如何实现按照value排序呢？
这里只能借助其他方法了，用库函数自带的sort()方法，sort()的定义是：
在第二个方法中，也可以自定义分类器，那么可以这样：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55#include <iostream>
#include <string>
#include <unordered_map>
#include <map>
#include <algorithm>
using namespace std;
struct Person {
string name;
int age;
Person(string name_, int age_):name(name_)
, age(age_) {}
};
typedef pair<Person, int> PAIR;
struct personCmp {
bool operator()(const Person& p,const Person &q) const {
return p.age < q.age;
}
};
struct PAIRCmp {
bool operator()(const PAIR& P, const PAIR& q) const {
return P.second < q.second;
}
};
int main()
{
map<Person, int, personCmp> map;
map.emplace(Person("txm", 2), 23);
map.emplace(Person("zoe", 3), 18);
map.emplace(Person("zy", 1), 19);
for (auto& p : map) {
cout << p.first.name << " : " << p.first.age << "age = " << p.second << endl;
}
cout << "--------------" << endl;
vector<PAIR> map_vec(map.begin(), map.end());
sort(map_vec.begin(), map_vec.end(), PAIRCmp());
for (auto& p : map_vec) {
cout << p.first.name << " : " << p.first.age << "age = " << p.second << endl;
}
return 0;
}
分上述程序输出：
zy : 1 age = 19
txm : 2 age = 23
zoe : 3 age = 18
-————————
zoe : 3 age = 18
zy : 1 age = 19
txm : 2 age = 23
unordered_map的用法
而unordered_map是哈希表的机制，也就是每个key会生成一个哈希码，根据哈希码来判断元素是否相同，故必须提供产生哈希码的函数，但是哈希码相同并不一定代表两个元素相同，所以还要实现”==”操作符。所以，可以这样：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#include <iostream>
#include <string>
#include <unordered_map>
#include <map>
using namespace std;
struct Person {
string name;
int age;
Person(string name_, int age_):name(name_)
, age(age_) {}
bool operator==(const Person& p) const {
return (this->age == p.age && this->name == p.name);
}
};
namespace std {
template <>
struct hash<Person> {
size_t operator()(const Person &p) const {
return hash<string>()(p.name) ^ hash<int>()(p.age);
}
};
}
int main()
{
unordered_map<Person, string> uno_map;
uno_map.emplace(Person("zoe", 23), "whuer");
return 0;
}
上面这种方法是在key的类型里实现了”==”，重载了std的hash函数。还可以下面这样：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34#include <iostream>
#include <string>
#include <unordered_map>
#include <map>
using namespace std;
struct Person {
string name;
int age;
Person(string name_, int age_):name(name_)
, age(age_) {}
bool operator==(const Person& p) const {
return (this->age == p.age && this->name == p.name);
}
};
struct hashGenerator {
size_t operator()(const Person& p) const {
return hash<string>()(p.name) ^ hash<int>()(p.age);
}
};
int main()
{
unordered_map<Person, string, hashGenerator> uno_map;
uno_map.emplace(Person("zoe", 23), "whuer");
return 0;
}
将哈希码生成器定义为一个新的类，声明一下即可，当然也可以将”==”的也定义为一个新的类：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#include <iostream>
#include <string>
#include <unordered_map>
#include <map>
using namespace std;
struct Person {
string name;
int age;
Person(string name_, int age_):name(name_)
, age(age_) {}
};
struct hashGenerator {
size_t operator()(const Person& p) const {
return hash<string>()(p.name) ^ hash<int>()(p.age);
}
};
struct personCmp {
bool operator()(const Person& p,const Person& q) const {
return (p->age == q.age && p->name == q.name);
}
};
int main()
{
unordered_map<Person, string, hashGenerator, personCmp> uno_map;
uno_map.emplace(Person("zoe", 23), "whuer");
return 0;
}
那么由上可以看出哈希函数的选择至关重要，哈希函数的好坏直接影响性能，比较推荐的做法是用boost库里的hash_value和hash_combine这两个函数，其实hash_value这个函数跟标准库里的hash1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#include <boost/functional/hash.hpp>
struct KeyHasher
{
std::size_t operator()(const Person& p) const
{
using boost::hash_value;
using boost::hash_combine;
// Start with a hash value of 0 .
std::size_t seed = 0;
// Modify 'seed' by XORing and bit-shifting in
// one member of 'Key' after the other:
hash_combine(seed,hash_value(p.name));
hash_combine(seed,hash_value(p.age));
// Return the result.
return seed;
}
};