STL | Map（映射）的使用（一）
写在前面：
Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力。由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。
Map
图片来源：https://www.cnblogs.com/empty16/p/6395813.html
这里说下map内部数据的组织，map内部自建一颗红黑树（一 种非严格意义上的平衡二叉树），这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。
这里略过红黑树，感兴趣的童鞋自行百度，可以先从二叉排序树入手。（后面有时间我再来总结）
进入正题：
一. 定义一个Map（映射）
map共提供了6个构造函数，这块涉及到内存分配器这些东西，我也没深入去了解。因此，我们就来介绍最常见的一种构造方法：
#include<map>// 头文件
map<char,int>Map;// 定义一个从char类型到int类型的映射Map
构造函数包含了两个参数，第一个参数是关键字Key，第二个参数是关键字的值Key_Value。这两个参数可以是任意类型。
通常，我们习惯用typedef来定义Map，为什么呢？因为在定义迭代器的时候，我们可以不用多写多余的重复代码，而且要修改Map的时候，也不需要修改多处地方。
#include<map>
typedef map<char,int> m;// 自定义一种类型——m
m Map;
二. 插入数据
定义好了映射Map，接下来就需要向Map插入数据。插入数据主要有以下三种方法。
- ① 用insert函数插入pair数据
（pair是什么，其实就是一个结构体，包含(first,second)这样的数据的结构体）
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
typedef map<char,int>m;
m Map;
int main()
{
char ch;
for(int i=0;i<10;i++)
{
cout<<"input character:";
cin>>ch;
// 方法一：用insert函数插入pair数据
Map.insert(pair<char,int>(ch,i));
}
}
- ② 用insert函数插入value_type数据
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
typedef map<char,int>m;
m Map;
int main()
{
char ch;
for(int i=0;i<10;i++)
{
cout<<"input character:";
cin>>ch;
// 方法二：用insert函数插入value_type数据
// 这里就可以看出用typedef定义Map的好处
Map.insert(m::value_type(ch,i));
}
}
- ③ 用数组方式插入数据
形式：Map[Key]=Key_Value;
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
typedef map<char,int>m;
m Map;
int main()
{
char ch;
for(int i=0;i<10;i++)
{
cout<<"input character:";
cin>>ch;
// 方法三：用数组方式插入数据
Map[ch]=i;
}
}
以上三种插入方法，虽然都可以实现数据的插入，但是它们是有区别的。当然，第一种和第二种在效果上是完成一样的。
用
insert函数插入数据，在数据的插入上涉及到集合的唯一性这个概念，即当map中有这个关键字时，想要再次插入该关键字，insert操作是插入不了的。但是用
数组方式就不同了，它可以覆盖以前该关键字对应的值。
下面用一个程序来验证。
#include<iostream>
#include<map>
using namespace std;
typedef map<char,int> m;
m Map_1;// 数组方式插入
m Map_2;// insert函数插入
int main()
{
char ch;
for(int i=0;i<4;i++)
{
cout<<"input the character:";
cin>>ch;
Map_1[ch]=i;
Map_2.insert(pair<char,int>(ch,i));
}
m::iterator iter_1,iter_2;// 前向迭代器
cout<<"--------------------------\n";
cout<<"数组：\n";
for(iter_1=Map_1.begin();iter_1!=Map_1.end();iter_1++)
{
cout<<iter_1->first<<"->"<<iter_1->second<<endl;
}
cout<<"--------------------------\n";
cout<<"insert：\n";
for(iter_2=Map_2.begin();iter_2!=Map_2.end();iter_2++)
{
cout<<iter_2->first<<"->"<<iter_2->second<<endl;
}
cout<<"\n";
// 重新插入已经存在的关键字Key
// 尝试将其Key_Value值改为520
cout<<"重新插入character：\n";
cin>>ch;
Map_1[ch]=520;
Map_2.insert(pair<char,int>(ch,520));
cout<<"--------------------------\n";
cout<<"数组：\n";
for(iter_1=Map_1.begin();iter_1!=Map_1.end();iter_1++)
{
cout<<iter_1->first<<"->"<<iter_1->second<<endl;
}
cout<<"--------------------------\n";
cout<<"insert：\n";
for(iter_2=Map_2.begin();iter_2!=Map_2.end();iter_2++)
{
cout<<iter_2->first<<"->"<<iter_2->second<<endl;
}
}
验证结果
三. Map容器的大小：
Map容器已经插入了数据，那么Map容器的大小（目前）是多大呢？或者说插入了多少组数据呢？
我们可以用size函数，这跟STL中其他容器（如vector）用法一致。
四. 遍历Map容器：
既然插入了数据，那么我们怎么去遍历呢？（借此也看看是不是插入成功）同样的，也有三种方法可以对Map容器进行遍历。
- ① 前向迭代器遍历
map<char,int>::iterator iter;// 前向迭代器
for(iter=Map.begin();iter!=Map.end();iter++)
{
cout<<iter->first<<" "<<iter->second<<endl;
}
- ② 反向迭代器遍历
所谓反向，就是从末尾开始遍历。
map<char,int>::reverse_iterator r_iter;// 反向迭代器
for(r_iter=Map.rbegin();r_iter!=Map.rend();r_iter++)
{
cout<<r_iter->first<<" "<<r_iter->second<<endl;
}
- ③ 数组的形式遍历
这种方法好像有bug，我的编译器是DEVC++，没在VS上跑。因此，这里就不加以说明了，有兴趣的童鞋也可以自己去尝试。不过一般情况下，用迭代器迭代就足够了。相关信息可以看看这篇博客
判定关键字是否在Map中：
这里有三种判断关键字是否在Map中的方法。
-
① 用
count()函数：
由于Map的特性，一对一的映射关系（且无重复元素），决定了count函数的返回值只有两个，要么是0，要么是1。若关键字在Map中，count函数返回1；不在则返回0。
使用形式：count(Key) -
② 用
find()函数：
用find函数来定位数据出现位置，它返回的一个迭代器。当数据出现时，它返回数据所在位置的迭代器，如果map中没有要查找的数据，它返回的迭代器等于end函数返回的迭代器。
map<char,int>Map;
map<char,int>::iterator iter=Map.find(Key);
if(iter==Map.end())cout<<"can't find"<<endl;
else cout<<"find"<<endl;
- ③ 用
lower_bound()函数和upper_bound()函数或者equal_value()函数：（虽然方法显示笨重了些，但是体现了Map数据的有序性）
-
lower_bound()：返回键值
给定元素的第一个位置（下界）
-
upper_bound()：返回键值
给定元素的第一个位置（上界）
-
equal_range()：返回特殊条目的迭代器对。具体表现为：
返回一个pair，pair里面第一个变量是lower_bound返回的迭代器，pair里面第二个迭代器是upper_bound返回的迭代器。
如果这两个迭代器（上、下界）相等的话，则说明Map中不存在这个关键字。
if(iter_1!=iter_2)cout<<"find"<<endl;
else cout<<"can't find"<<endl;
完整代码，测试lower_bound、upper_bound、equal_value函数 👇👇👇
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
typedef map<char,int>m;
m Map;
int main()
{
char ch;
for(int i=0;i<5;i++)
{
cout<<"input character:";
cin>>ch;
Map[ch]=i;
}
m::iterator iter_1,iter_2;
iter_1=Map.lower_bound('C');
iter_2=Map.upper_bound('C');
cout<<"lower_bound:\n";
cout<<iter_1->first<<"->"<<iter_1->second<<endl;
cout<<"upper_bound:\n";
cout<<iter_2->first<<"->"<<iter_2->second<<endl;
cout<<"*********************\n";
cout<<"queal_value:\n";
pair<m::iterator,m::iterator> p=Map.equal_range('C');
iter_1=p.first;
iter_2=p.second;
cout<<iter_1->first<<"->"<<iter_1->second<<endl;
cout<<iter_2->first<<"->"<<iter_2->second<<endl;
}
查找关键字：
find函数：返回一个pair对象，pair->first表示Key的值，pair->second表示Key_Value的值。
result = Map.find(Key);
cout << result->first << "->" << result->second << endl;
Map总结：
为什么选择Map？/ Map的功能作用？
-
自动建立Key－Key_Value的对应（映射）。Key 和 Key_Value可以是任意你需要的类型。
-
根据Key值快速查找记录，查找的复杂度基本是
，如果有
个记录，最多查找
次，
个记录，最多查找
次。
-
快速插入Key - Key_Value 记录。
-
快速删除记录。
-
根据Key 修改Key_Value记录。
-
遍历所有记录。
Map的基本操作函数：
| *begin() | 返回指向Map头部的迭代器 |
|---|---|
| *clear() | 删除所有元素 |
| *count() | 返回指定元素出现的次数，Map中只有0和1两个值 |
| *empty() | 如果Map为空，则返回true |
| *end() | 返回指向Map末尾的迭代器 |
| equal_range() | 返回特殊条目的迭代器对 |
| *erase() | 删除一个元素 |
| *find() | 查找一个元素 |
| get_allocator() | 返回Map的配置器 |
| *insert() | 插入元素 |
| key_comp() | 返回比较元素Key的函数 |
| lower_bound() | 返回键值 |
| max_size() | 返回可以容纳的最大元素个数 |
| *rbegin() | 返回一个指向Map尾部的反向迭代器 |
| *rend() | 返回一个指向Map头部的反向迭代器 |
| *size() | 返回map中元素的个数 |
| *swap() | 交换两个Map容器 |
| upper_bound() | 返回键值 |
| value_comp() | 返回比较元素Key_Value的函数 |
PS：带*的函数：表示我比较常用的函数。
写在最后：
参考资料：
因为文章篇幅原因，剩下一些内容（删除和排序）就留着下次再讲。
其实，对于STL，很多容器都具有功能相同的函数、迭代器。前面讲过vector容器，也是经常需要被用到的。就我而言，vector可能比map用的频率还大一些。
关于vector容器的文章：
