C++ STL: map自定义键值类型

113 阅读 0 评论 75 点赞

我是靠谱客的博主直率雨，这篇文章主要介绍C++ STL: map自定义键值类型，现在分享给大家，希望可以做个参考。

map定义
map是STL里的一个模板类，用来存放<key, value>键值对的数据结构，它的定义如下。

复制代码

1
2
3
4
5
6
7
8
9
10
template < class Key,
//map::key_tpe
class T,
//map::mapped_type
class Compare = less<Key>,
//map::key_compare
class Alloc = allocator<pair<const Key, T>>
//map::allocator_type
> class map;

第1个参数存储了key。

第2个参数存储了mapped value。

第3个参数是比较函数的函数对象。map用它来判断两个key的大小，并返回bool类型的结果。利用这个函数，map可以确定元素在容器中遵循的顺序以及两个元素键是否相等（！comp（a，b）&&！comp（b，a）），确保map中没有两个元素可以具有等效键。这里，它的默认值是less，定义如下。

复制代码

1
2
3
4
5
6
7
8
template <class T>
struct less {
bool operator() (const T& x, const T& y) const {return x < y;}
typedef T first_argument_type;
typedef T second_argument_type;
typedef bool result_type;
};

第4个参数是用来定义存储分配模型的。

简单方法: 重载operator<()操作符
在我们插入<key, value>时，map会先通过比较函数地函数对象来比对key的大小，然后根据比对结果进行有序存储。c++标准库中，map比较函数的函数对象不可避免地会用到’<'运算，因此一种方法就是直接在自定义类里重载operator<()操作符，如下所示。

复制代码

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
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Person{
public:
string name;
int age;
Person(string n, int a){
name = n;
age = a;
}
bool operator<(const Person &p) const //注意这里的两个const
{
return (age < p.age) || (age == p.age && name.length() < p.name.length()) ;
}
};
int main(int argc, char* argv[]){
map<Person, int> group;
group[Person("Mark", 17)] = 40561;
group[Person("Andrew",18)] = 40562;
for (auto ii = group.begin() ; ii != group.end() ; ii++)
cout << ii->first.name
<< " " << ii->first.age
<< " : " << ii->second
<< endl;
return 0;
}

这里，我们需要注意的是，在重载operator<(){}时，无论是参数还是整个函数的const都不能少。参照less的定义，less的参数和函数整体都是const，那么被调用的operator<()必然也是同等要求。

其它方法：比较函数的函数对象
如果不重载operator<()是不是就不行了？当然不是。除了直接重载operator<()，我们可以直接自定义比较函数的函数对象。

首先简要介绍一下函数对象的概念：在《C++ Primer Plus》里面，函数对象是可以以函数方式与()结合使用的任意对象。这包括函数名、指向函数的指针和重载了“operator()”操作符的类对象。基于此，我们提出3种定义方法。

3.1 方法1: 利用std::function
方法1利用std::function。它是一种通用、多态、类型安全的函数封装，其实例可以对任何可调用目标实体（包括普通函数、Lambda表达式、函数指针、以及其它函数对象等）进行存储、复制和调用操作，方法如下。

复制代码

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
#include <iostream>
#include <map>
#include <string>
#include <functional>
using namespace std;
class Person{
public:
string name;
int age;
Person(string n, int a){
name = n;
age = a;
}
};
bool MyCompare(const Person &p1, const Person &p2) {//普通的函数
return (p1.age < p2.age) || (p1.age == p2.age && p1.name.length() < p2.name.length());
}
int main(int argc, char* argv[]){
map<Person, int, function<bool(const Person &, const Person &)>> group(MyCompare); //需要在构造函数中指明
group[Person("Mark", 17)] = 40561;
group[Person("Andrew",18)] = 40562;
for ( auto ii = group.begin() ; ii != group.end() ; ii++ )
cout << ii->first.name
<< " " << ii->first.age
<< " : " << ii->second
<< endl;
return 0;
}

我们利用std::function为MyCompare()构建函数实例。初始化时，这个函数实例就会被分配那个指向MyCompare()的指针。因此，在对group进行申明时，需要构造函数指明函数实例。

另外，c++11增加了一个新的关键词decltype，它可以直接获取自定义哈希函数的类型，并把它作为参数传送。因此，group的声明可以如下修改。

map<Person, int, decltype(&MyCompare)> group(MyCompare);
1
3.2 方法2: 重载operator()的类
方法2就是利用重载operator()的类，将比较函数打包成可以直接调用的类。

复制代码

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
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Person{
public:
string name;
int age;
Person(string n, int a){
name = n;
age = a;
}
};
struct MyCompare{
//Function Object
bool operator()(const Person &p1, const Person &p2) const{
return (p1.age < p2.age) || (p1.age == p2.age && p1.name.length() < p2.name.length());
}
};
int main(int argc, char* argv[]){
map<Person, int, MyCompare> group;
group[Person("Mark", 17)] = 40561;
group[Person("Andrew",18)] = 40562;
for ( auto ii = group.begin() ; ii != group.end() ; ii++ )
cout << ii->first.name
<< " " << ii->first.age
<< " : " << ii->second
<< endl;
return 0;
}

值得注意的是，这时group的声明不再需要将函数对象的引用传入构造器里。因为map会追踪类定义，当需要比较时，它可以动态地构造对象并传递数据。

3.3 方法3: less函数的模板定制
前面几种方法，无论我们怎么定义，在声明group的时候都需要指定第3个参数，有什么方法是需要指定的呢？当然有啦。

通过map的定义可知，第三个参数的默认值是less。显而易见，less属于模板类。那么，我们可以对它进行模板定制，如下所示。

复制代码

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
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Person{
public:
string name;
int age;
Person(string n, int a){
name = n;
age = a;
}
};
template <> //function-template-specialization
struct less<Person>{
public :
bool operator()(const Person &p1, const Person &p2) const {
return (p1.age < p2.age) || (p1.age == p2.age && p1.name.length() < p2.name.length());
}
};
int main(int argc, char* argv[]){
map<Person, int> group; //无需指定第三个参数啦
group[Person("Mark", 17)] = 40561;
group[Person("Andrew",18)] = 40562;
for ( auto ii = group.begin() ; ii != group.end() ; ii++ )
cout << ii->first.name
<< " " << ii->first.age
<< " : " << ii->second
<< endl;
return 0;
}