STL | Map（映射）的使用（一）

作者: 0与1的邂逅 | 来源:发表于2019-06-11 16:28 被阅读0次

写在前面：

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值快速查找记录，查找的复杂度基本是 $O(log(N))$ ，如果有 $1000$ 个记录，最多查找 $10$ 次， $1,000,000$ 个记录，最多查找 $20$ 次。
快速插入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：带*的函数：表示我比较常用的函数。

写在最后：

参考资料：

博客：C++中的STL中map用法详解（文字来源）
360doc个人图书馆

因为文章篇幅原因，剩下一些内容（删除和排序）就留着下次再讲。

其实，对于STL，很多容器都具有功能相同的函数、迭代器。前面讲过vector容器，也是经常需要被用到的。就我而言，vector可能比map用的频率还大一些。

关于vector容器的文章：

网友评论

本文标题：STL | Map（映射）的使用（一）

本文链接：https://www.haomeiwen.com/subject/rwvffctx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！