1 白话map
map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力。由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map是内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，这和数据结构set一样，只不过map的键与值是不同的类型，而set中每个键值对是同一个值。
map键与值都可以是随意类型，例如我们想访问学生登分系统，通过定义一个姓名对应分数的map，这样键可以是string类型，而值可以是int类型，所以定义的map可以是map<string,int> score。此外我们还想在登分之前通过学号姓名的map，这样键值对我们就可以分别定义为int，string类型，所以定义的map又可以是map<int,string> name。
2 STL中map实战
2.1 包含map的头文件
#include<map>
using namespace std;
2.2 map对象声明
map的构造重载了好几种构造函数，但是都是涉及内存分配器，所以我们就按默认定义即可：
map<int,float> map_fir;
2.3 插入键值对
由于map是自动排序的，所以键值对插入什么地方无需关注，我们只要关心放入什么数据就行。map插入键值对有三种方式，如下：
map<int,float> map_sed;
map_sed.insert(pair<int,float>(100 , 0.1234)); //方法一
map_sed.insert(map<int,float>::value_type(110,100.86)); //方法二
map_sed[120] = 10000; // 方法三
以上三种用法，虽然都可以实现数据的插入，但是它们是有区别的。当然前两种方式是一样的，都是用insert函数插入数据。但是数据的插入涉及到集合的唯一性这个概念，即当map中有这个关键字时，insert操作是插入数据不了的，但是用operator[]重载的方式就不同了，它可以覆盖以前该关键字对应的值。如下：
map<int,float> map_sed;
map_sed.insert(pair<int,float>(100 , 0.1234));
map_sed.insert(pair<int,float>(100 , 0.5555)); //该键值对不会更新，100键对应的还是0.1234值.
map_sed[110] = 50;
map_sed[110] = 10086; //110键对应的值会发生改变，变成10086。
2.4 查询键值对
有时候我们希望查询一下当前map中是否存在某一键值，和set一样我们有两种方法，如下：
map<int,float> map_thd;
map_thd.count(110); // 统计map中某一关键字出现的个数，注意是关键字，不是值
上面程序统计110出现的个数，我们知道map中关键字只可以出现一次，所以返回结果要么是1要么是0。所以通过返回值可以确认map中是否存在该关键字。
map<int,float> map_for;
if(map_for.find(110)!=map_for.end()) // find()方法返回的是查询关键字的迭代器，如果没有查询到则指向end()
//...
2.5 边界元素
map<int,float>::iterator iter1 = map_fir.lower_bound(2); //返回map中>=2的索引(迭代器)，切记不是小于2的有意思
map<int,float>::iterator iter2 = map_fir.upper_bound(2); //返回map中>2的索引
2.6 查询键值对
关联式容器也可以通过迭代器间接访问每个元素，迭代器可以象征性的看成是指针。map和其他能够使用迭代器的容器一样，它的迭代器是双向的，我们可以从头到尾（正向迭代），也可以从尾到头（反向迭代）访问每个数据。
#include<iterator>
map<int,float>::iterator iter; //对应迭代器对象
//正向间接访问
for(iter=map_fir.begin();iter!=map_fir.end();iter++)
cout<<iter->first<<"="<<iter->second<<endl;
反向索引：
map<int,float>::reverse_iterator iter; //对应反向迭代器对象
//反向间接访问
for(iter=map_fir.rbegin();iter!=map_fir.rend();iter++)
cout<<iter->first<<"="<<iter->second<<endl;
上面begin()指向的是map中首元素地址，而end()指的是集合中尾部数据的下一位地址。在反向迭代器操作中，rbegin()指向的是map尾部数据，而rend()指向第一个元素前面一个位置的元素(这个元素被认为是反转后的尾部)。此外，切记上面反转迭代也是iter++，而不是我们想的iter- -，这个过程map内部已经帮忙转换。
2.7 删除操作
map<int,float>::iterator iter;
iter = map_fir.find(1);
map_fir.erase(iter); // 迭代器删除某一个键值对
int n = map_fir.erase(1); // 关键字删除，如果删除了会返回1，否则返回0
map_fir.erase(map_fir.begin(),map_fir.end()); // 成片删除
2.8 其他常用操作
map<int,float> map_fir;
map_fir.swap(map_sed); // 交换所有数据，需要确保map中元素类型相同
map_fir.clear(); // 清空map_fir
map_fir.size(); // 统计map_fir中元素个数
map_fir.empty(); // 判断map中是否为空，如果是空则返回1
3 小结
上面介绍了map数据结构特点以及STL中包含的接口。由于map和set一样是基于红黑树构建的数据结构，所以其存取，访问等时间复杂度都为O（logn），n为集合中元素的个数。
以上是个人学习记录，由于能力和时间有限，如果有错误望读者纠正，谢谢！
转载请注明出处：http://blog.csdn.net/FX677588/article/details/76375350
参考文献：
http://blog.csdn.net/it_yuan/article/details/22697205
