STL中map的使用详解

原文链接：STL中map的使用详解
发布时间：2018-11-14 18:34:04

map的本质

map本质上一个平衡二叉树（更准确地说是红黑树），那么每个节点存放一个数据，默认是key和value打包成一个数据pair，以pair的形式存放在节点的，由此来看，pair里面可以放任何数据，前提是pair必须可以比较大小，当然也可以自定义比较函数，而map的第三个参数就是指定自定义key的比较函数的。

map的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//map的定义
//第一 第二 是key和value的类型
//第三个参数是关于Key的比较函数 默认是less 参见less的定义——就是比较2个数据，小为真
//第四是节点数据存储的方式 默认是pair的方式 即key与value打包在一起
template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

//less 是一个函数对象 重载()运算符
//所谓的比较函数定义格式为 bool cmp(const T& x, const T& y) 实现这个函数即可
template <class T> struct less : binary_function <T,T,bool> 
{
  bool operator() (const T& x, const T& y) const {return x<y;}// 默认是降序排列
};

map的特点

  • map本质是一个红黑树
  • 每个节点存放一个数据
  • map的节点是有序的

正是因为map的内部数据是有序的，才能保证map的高效查找，数据有序，pair必须是可比较的，必须有比较函数。

如果key是整数、字符串，则不需要提供比较函数，但是如果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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <map>
#include <stdio.h>
#include <string>

using namespace std;
struct DATA {
	int uid;
	string name;
	bool operator()(const DATA& d1, const DATA& d2)
	{
		//大的排前面
		return d1.uid > d2.uid;
	}
};

typedef pair<DATA, string> DATA_PAIR;

struct CmpDATA //这样单独定义一个函数对象也可以的
{
	bool operator()(const DATA& d1, const DATA& d2)
	{
		//大的排前面
		return d1.uid > d2.uid;
	}
};

int main()
{
	//关键的一步，定义map时，传入自定义的比较函数
	map<DATA, string, DATA> mapData;
	//map<DATA, string, CmpDATA> mapData;

	DATA data1 = {1001, "jim"};
	DATA data2 = {1002, "jack" };
	DATA data3 = {1003, "lucy" };
	DATA data4 = {1004, "james" };

	//插入数据
	mapData.insert(pair<DATA, string>(data1, "China"));
	mapData.insert(pair<DATA, string>(data3, "English"));
	mapData.insert(pair<DATA, string>(data4, "Japan"));
    mapData.insert(pair<DATA, string>(data2, "American"));
    //遍历
	map<DATA, string>::iterator it;
	for (it = mapData.begin();
		it != mapData.end();
		it++)
	{
		printf("uid=%d, name:%s\n", it->first.uid, it->first.name.c_str());
	}

    //查找
	it = mapData.end();
	it = mapData.find(data2);
	if (it != mapData.end())
	{
		printf("find data2, uid=%d, value=%s\n", it->first.uid, it->second.c_str());
	}
	else
	{
		printf("not find data2");
	}
    //直接索引
	printf("print data3, value=%s\n", mapData[data3].c_str());

	return 0;
}

输出：

1
2
3
4
5
6
uid=1004, name:james
uid=1003, name:lucy
uid=1002, name:jack
uid=1001, name:jim
find data2, uid=1002, value=American
print data3, value=English

函数对象

就是定义的类重载了operator() 操作符。对象可以像函数指针一样使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
using namespace std;

class FuncObject
{
public:
	int operator()(int a, int b)
	{
		return a + b;
	}
};

int main()
{
	FuncObject f;
	int sum = f(10, 20);//调用对象
	printf("sum=%d\n", sum);
	return 0;
}

函数对象可以代替函数指针，比指针更加灵活，因为对象是可以有状态的。

标准库定义了一组算术、关系与逻辑函数对象类

例如 less、greater

1
2
3
4
5
6
7
8
9
10
int main()
{
	less<int> cmp;//定义对象
	printf("result1=%d\n", cmp(12,20));

	greater<string> cmpStr;//定义对象
	printf("result2=%d\n", cmpStr("C", "B"));

	return 0;
}

输出：

1
2
result1=1
result2=1

pair的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
namespace std {
     template < class T1, class T2 >
     struct pair {
         T1 first;
         T2 second;
         // constructors
                   };
}

//其实就是包含了2个对象分别是 first  second

std::make_pair(10, 'D');//可以用make_pair创建一个pair对象
template <class T1,class T2>
 pair<T1,T2> make_pair (T1 x, T2 y)
{
    return ( pair<T1,T2>(x,y) );//返回pair对象
}

insert操作

map的insert表示插入数据，如果key已经存在，将不做任何操作，key不存在，则插入数据。

1
pair<iterator,bool> insert (const value_type& val);

关于返回值：

  • 返回值是一个pair
  • pair 的 first 表示 在map中，等于k值在map中迭代器
  • pair的second的是一个bool值，false表示没有插入key，说明key已经存在map中了，true表示插入成功

由以上可知，insert操作，和通过下标索引操作还是不一样的。

通过下标操作一定会修改map，例如map[k1]=v1，如果k1存在，会修改k1的值，k1不存在，则插入key的键值对。