C++-树形关联式容器map的使用

1. map的介绍

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元 素。 2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的 内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型 value_type绑定在一起，为其取别名称为pair:

3. 在内部，map中的元素总是按照键值key进行比较排序的。 4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序 对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。 5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。 6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

2 map的使用

2.1 map的模板参数说明

key: 键值对中key的类型 T： 键值对中value的类型 Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比 较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户 自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递) Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的 空间配置器 注意：在使用map时，需要包含头文件.

2.2 insert

那么这个value_type是什么类型呢？也就是pair，在map中，value是可以修改的，key不能修改。

 第一种构造就是匿名对象构造，第二种就是有名构造，第三种是吧多参数构造函数的隐式类型转换，第四种则是库里面的一种方式。

	map<string, string> mp;
	mp.insert(pair<string, string>("sort","排序"));
	pair<string, string> kv = { "string", "字符串" };
	mp.insert(kv);

	// C++11 多参数隐式类型转换(构造函数)
	mp.insert({ "apple", "苹果" });

	// C++98
	mp.insert(make_pair("sort", "排序"));

如果key相同，但是value不同的话，不会再进行插入，也不会更新，就相当于插入失败。

2.3 迭代器

迭代器的用法还是一样的，需要注意的是*it是返回节点的数据，也就是pair，pair是没有重载<<和>>的，所以需要访问pair的成员。

 2.4 范围for

建议使用范围for遍历map对象时使用引用，减少拷贝。

2.5 operator[] 

大家看下面这种就是统计字符串出现次数的方式，但是使用operator[]的话更加方便。

只用了一行代码就完成了这些工作

3. multimap

 如果把map换成multimap的话，下面这段代码就会产生不一样的效果，就是插入时只看key，允许key的冗余。

---