STL映射

1. 如何理解映射。

我们过去学过数组 , 例如 int a[100000]; 是定义了一个整数类型的数组，下标可以从0到99999，这里其实是一共有 100000 个下标，换句话说，就是有 100000 个数组元素。下标就是一个整数类型的数字，例如 a[5] 或者 a[71] 分别代表两个不同的数组元素，下标分别为 5 和 71 。

int a[1000000]; // 定义数组。程序运行到这里，会申请分配一片连续的内存，记住，是连续的。这片内存有 4*1000000 byte，分别用于存放从 a[0] 到 a[999999] 的值

//给数组的元素赋值
for(int i=0;i<1000000;i++)
    scanf("%d",&a[i]); 

//访问和输出数组元素
for(int i=0;i<1000000;i++)
    printf("a[%d]=%d\n",i,a[i]);

大家有没有想过，我们的下标能否换成别的东西，最常见的，我们能不能换成字符串？我们曾经做过大沥镇的一条竞赛题，叫小偷，一共有 6 个人，我们能否用一个数组记录着各个人在哪一个房间（假设这个数组叫 a ），我们能否执行这样的命令： a["Tom"] = "Room 1"; 去记录 Tom 去了 "Room 1"，如果行，那个程序就可以大大的简化。而今天我们学的 STL 映射模板就是可以解决这个问题的。

通过小偷这条题，我们可以初步的去理解映射（STL 的 map），它就是一种技术，解决 key-value 的快速对应关系的，map 的英文就是有相互对照的关系。如果有一个类似数组的东西，我通过人名 Tom 能对应出他在哪个房子（"Room 1"），这就是一种对应关系，在这里人名就是 key，对应的房子就是value。

回过头看我们过去学的数组，int a[100];，就是 int 到 int 的映射，int b=a[6];,我们用 key=6，去找出对应的value； bool c[100];,就是从 int 到 bool 的映射。今天，如果你喜欢，你可以把过去很多基于数组的题目改成基于映射的代码，大多数都没问题的。

2. 为什么要用映射

映射能提供很灵活的 key-value 对应关系的存储和查找，例如，我设置一个映射变量，专门记录各个单词在字典中的第几页，"country" 在第 17 页，"door" 在第 3 页。如果没有这个映射，你要写很多代码才能做同样的事情。

有一些题目，还是 int:int 的映射，表面上可以用数组，但是数据范围很大，如果你要定义一个很大很大的数组，你就爆内存的，用映射可以解决这样的问题。因为，映射其实不是通过静态内存来存放数据的，这个机制相当复杂，我就不展开介绍了。简单来说，就是你存的数据少，映射占的内存就少，你存的数据多，映射占的内存就多。如果数据很稀疏的时候，用 map 特别升内存。 - 数组的下标只能是非负数，而基于映射，那就没有这个限制了

3. 映射和数组相比，有什么坏处。

映射里面的数据，是经过了排序的（和二分法很有关系，但是更复杂），所以，你要操作数据的时候，STL 并不是按顺序的去查找的，而是类似于用二分查找的方法去定位你要访问的那个元素在什么地方。这个过程也挺快，但是再快也没有基于数组的方法快（数组的访问是基于位置便宜的算法，你填下标，直接算出你要访问的元素在内存的什么位置，一步到位，非常快）。所以，能用数组的时候还是继续用数组。

4. 迭代器

基于传统的数组技术，我们可以很容易访问数组中所有元素的值，弄一个 for 循环就行了。

//访问和输出数组元素，下标的范围是明确的，我列举了所有的下标就可以访问所有的数组元素
for(int i=0;i<1000000;i++)
    printf("a[%d]=%d\n",i,a[i]);

针对映射，key 的值往往是不太明确的，例如如果 key 是字符串，你们你很难用一个 for 语句来枚举。这时候，就要依靠迭代器。反正，迭代器及时给你枚举用的。

5. 代码样例

5.1 映射的定义

//映射的关键字是 map
// 尖括号内一定是有 2 个数据类型，不能多，也不能少。两个类型用逗号分隔，一个是 key 的类型，一个是 value 的类型。
map < int, int > m1;  // 定义 m1 映射，是从 int 映射到 int
map <string ,int > m2； //定义 m2 映射，是从 string 映射到 int
map <long long ,int > m3； //定义 m3 映射，是从 long long 映射到 int

5.2 映射的访问

映射的访问很像数组

例子 1

有 n 个学生，他们的名字不重复，我们输入他们的姓名和分数。

map < string, int > m; // 定义一个 从 string 到 int 的映射

int n;
cin>>n;

string name;
int score;
for (int i=0;i<n;i++){
    cin>>name>>score; // 输入到临时变量
    m[name] = score; // 把成绩信息记录到 映射 m 。这里 name 是字符串，是用来做下标
}

例子 2

有 1000 学生，他们每个学生有学号，学号是 15 位的数字，学号不重复。现在输入这 100 个学生的学号和成绩。

map <long long, int > m; // 定义一个 从 long long 到 int 的映射，学号是 15 位 数字，所以需要用 long long

long long id;
int score;
for (int i=0;i<1000;i++){
    cin>>id>>score; // 输入到临时变量
    m[id] = score; // 把成绩信息记录到 映射 m 。这里 id 是 long long 类型。如果定义一个数组 int x[1000000000000000]，内存一定爆了
}

5.3 迭代器

接着上面的例子 2 做延伸

完成学生的成绩信息输入之后，假设我们现在要输出这些学生的数据

// 定义迭代器，迭代器的前半段内容和定义 STL 模板（映射）的格式一样，尖括号后面发生变化
// :: iterator 是固定格式， 再后面是空格，然后是的迭代器的名字
// 名字是自己起的，只要符合变量描述符的要求就可以了
// :: 前面的内容要和映射的 key-value 特征完全一致
map < long long , int > :: iterator it; // 定义一个迭代器，叫 it，它可以用于迭代 <long long , int > 类型

// m 已经在例子 2 前面的代码里定义过了
for(it=m.begin();it!=m.end();it++){
    printf("学号是：%lld, ",it->first);
    printf("成绩是: %d\n", it->second);
    // 也可以用这个方法输出成绩 printf("成绩是： %d", m[it->second])
    // 下面的这种写法要做一次二分查找，所以慢一些。
}

上面的输出，是从 m.begin() 开始， begin 是映射的一个函数，返回的是映射的第一个成员的指针，end() 是返回一个空指针，如果迭代器不断加加，最后变成空指针，那么就是枚举完毕。

映射的迭代器有两个成员，first 指向 key，second 指向 value。所以 it->first 就是得到那一个元素的 key，it->second 得到的是那一个元素的 value。

迭代的过程中，是按照 key 从小到大的顺序。

接着上面的例子 1 做延伸

完成了学生姓名和成绩的输入之后，加入我们要输出这些数据

map <string, int> :: iterator it;
for(it=m.begin();it!=m.end();it++)
    cout<< it->first <<" "<< it->second << endl; 

//上面的输出是按照名字字典序从小到大

begin() 和 end( )

begin() 返回的是正向的第一个键值对的指针

end() 返回的是正向的最后一个键值对后面的一个空值的指针。

查找函数 find()

基于上面的例子 1 做延伸

假设我们想知道某个名字是否存在

string t;
cin>>t;
if( m.find(t)!=m.end() )
    cout<<"这位同学的成绩是:"<< m[t] <<endl;
else
    cout<<"不存在名字为 " << t << "的同学\n";

又或者是这么写

map <string , int> :: iterator it;
cin>>t;
it = m.find(t);
if(it!=m.end())
    cout<<"这位同学的成绩是:"<< it->second <<endl;
else
    cout<<"不存在名字为 " << t << "的同学\n";

// 这个代码比上面的代码更好，因为少了一次映射查找

简单来说，find 函数返回的是某一个 key 值对应的指针。如果找不到，这个指针就是空指针。

lower_bound() 和 upper_bound( )

STL 模板其实是按照顺序去整理各个 key-value 键值对的。上面的 find 函数是精确查找。除此以外，还有大于等于查找和大于查找。

lower_bound() 是查找大于等于某个一个 key 的键值对（返回的是指针）

upper_bound() 是查找大于某个一个 key 的键值对（返回的是指针）

找不到的时候，就是返回空指针（ end() ）

erase( )

erase 是删除一个 key-value 键值对。这个函数是多态函数，参数可以是一个 key ，也可以是一个指针。

延续上面的例子 1

string tmp;
cin>>tmp; // 输入要删除的人的名字
m.erase(tmp); // erase 的参数是字符串 （key）


map <string , int> :: iterator it;
cin>>tmp;
it = m.find(tmp); // 先找到 tmp 对应的指针

if(it!=m.end()) erase(it); // erase 的参数是指针

但是，这里有一个很隐秘的错误。如果通过迭代器来删键值对，而你又是在通过迭代器来遍历每一个键值对，那么删完之后，就会有问题。

例如，延续例子 1 ，假设我们要删掉成绩小于 60 分的键值对，错误程序如下

map <string, int> :: iterator it;
// 通过迭代器访问每一个键值对 （）
for(it=m.begin();it!=m.end();it++){
    if(it->score < 60){
        // 这位同学的分数少于 60 分，删除这个同学
        m.erase(it);
    }
}

假如有多个同学的成绩低于 60 分，上面的代码执行会有问题。原因是 erase 了 it 指向的那个键值对之后，it 就变成是空指针，基于这个空指针做 it++ 是有问题，也就是说没办法继续迭代下去了。

erase 函数返回的是删除一个键值对之后，后面跟着的那个键值对的指针。所以，要删除所有低于 60 分同学的成绩，代码是：

map <string, int> :: iterator it;
// 通过迭代器访问每一个键值对 （）
for(it=m.begin();it!=m.end();){
    if(it->score < 60){
        // 这位同学的分数少于 60 分，删除这个同学
        it = m.erase(it); // erase 返回下一个键值对的指针，所以就不用做 it++ 了
    }else{
        it++;
    }
}

size( )

size 函数是获得映射的键值对的个数。

rbegin() 和 rend()

我们学过 begin() 和 end() ,前面多了个 r ，意思是反向的（reverse 的单词）

rend() 返回的是最后一个键值对的指针（就是 end( ) 前面的那一个）

rbegin() 返回的是第一个键值对更前面的位置的指针（就是 begin( ) 前面的那一个，所以其实也是空指针）

接着上面的例子 1 ，如果想倒着来输出成绩信息，代码是

map <string, int> :: reverse_iterator it; // 反向迭代器
for(it=m.rbegin();it!=m.rend();it++)
    cout<< it->name <<" "<< it->second << endl; 

//上面的输出是按照名字字典序从大到小