MENU

STL的神奇容器之map

April 4, 2020 • Read: 276 • 算法

前言:

STL是C++中的标准库之一,主要由迭代器,算法,容器,仿函数,内存配置器和配接器留部分组成,可以帮助程序员完成许多功能完善,形式多样的程序,而这在ACM竞赛中,STL也因此成为了AC利器

map与映射

其实,map就是一种映射,只不过相当灵活,他可以做到向Python中的字典一样,形成唯一的键值对,通过访问键,就能够完成对值的访问,当然我们再这里便不再深入的谈论Python的东西,如果有需要我以后会单独出一篇博文讲Python的数据类型

map的灵活之处就体现于他可以将一种数据类型,映射到另一种数据类型上去,就好比查字典一样,比如我们要查“language”这个单词,我们就只能去996页查找(我胡诌的,假设是在这页吧),而不能在233页查找,因此,language和996便有了一一对应的关系,这就是映射。

用map来表示,就可以写为:

map<string,int>dictionary;

当我们需要写入一对键值对的话,可以这样表示:

dictionary["language"]=996;

于是language=>996的键值对便被生成出来的,当我们访问“language”的时候,就会显示为:996

cout<<dictionary["language"]<<endl;
//输出:996

map的映射类型

map的一个厉害的地方就是在于他的映射对象十分灵活,可以是string-->int,也可以是string-->string,也可以是用struct定义的结构类型,map可以将任何基本类型(包括STL容器)映射到任何基本类型(包括STL容器),但是必须保证键和值得唯一

我何时应该选择map

  1. 需要建立字符串和整数之间的映射
  2. 判断大整数或者其他类型整数是否存在,可以吧map当做布尔类型的数组使用(哈希表)
  3. 字符串与字符串之间的映射

map该如何使用呢

使用map,应该先引入map头文件< map >,同时要有using namespace std;

然后再通过map<string,int>dictionary;来定义一个新的map

访问map的时候只能通过键或者迭代器访问,这点与Python不同

使用迭代器来访问map

通过迭代器来访问的话,要先做如下定义:

map<typename1,typename2>::iterator it;

这样便定义了一个新的迭代器 it,我们便可以通过迭代器来访问map了,

其中通过 it-->first 来访问键, it-->second 来访问值

map常见函数

函数用法
.size()用来获取映射的对数,时间复杂度为o(1)
.clear()用来清空map,时间复杂度为o(n)
.find(key)返回键为key的映射的迭代器,时间复杂度为o(log2 N),N为映射的对数
.erase()可以用来删除单个元素,也可以删除一个区间的所有函数,删除单个元素时可以用erase(it),it为要删除的映射的键,时间复杂度为o(log2 n),删除一个区间的所有元素用erase(first,last),first为去见的起始迭代器,last为区间的末尾迭代器的下一个地址,也就是左闭右开的区间[first,last),时间复杂度为o(last-first),例如,erase("indexx")可以删去indexx这个键及其映射

更多函数可以参考:

pair的定义和使用

pair是“二元结构体”的替代品,将两个元素捆绑在一起,节省编码时间,相当于以下定义:

struct pair{
    typename1 first;
    typename2 second;
}

使用pair的时候,一定记得要加头文件< utility > 和using namespace std;

因为map的内部实现中会涉及pair,所以用< map >也可以替代

pair有两个参数,分别对应first和second的数据类型,可以是基本数据类型或者容器:

//定义一个pair
pair <typename1,typename2> name;
//访问pair的第一个成员变量
name.first;
//访问pair的第二个成员变量
name.second;

此处一定要记得和map区分过来!!!

map的二维表示

1.map嵌套pair,二元结构体pair当map的键
//定义
map<pair<int,int>,int >vis;

pair 会自动将first从小到大排序,如果相同,则从大到小排序

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,x,y;
map<pair<ll,ll>,int>vis;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y;
        vis[{x,y}]++;//结构体当下标
    }
    printf("\n正向遍历\n");
    map<pair<ll,ll>,int>::iterator it;
    for(it=vis.begin();it!=vis.end();it++)//正向遍历
        printf("%lld %lld %d\n",it->first.first,it->first.second,it->second);
        //输出x,y,{x,y}出现次数
        //pair 访问用".", map访问用"->"
    printf("反向遍历\n");
    map<pair<ll,ll>,int>::reverse_iterator re_it;//注意反向遍历写的是reverse_iterator
    for(re_it=vis.rbegin();re_it!=vis.rend();re_it++)//反向遍历
        printf("%lld %lld %d\n",re_it->first.first,re_it->first.second,re_it->second);
        //输出x,y,{x,y}出现次数
    return 0;
}

/*
版权声明:本文为CSDN博主「nefu_ljw」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/ljw_study_in_CSDN/article/details/104355672
*/
2.map嵌套map,当俄罗斯套娃二维数组用
//定义
map<int,map<int,int> >vis;

示例:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,map<ll,int> >vis;
ll n,x,y;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y;
        vis[x][y]++;
    }
    map<ll,map<ll,int> >::iterator i;
    map<ll,int>::iterator j;
    printf("\n正向遍历\n");
    for(i=vis.begin();i!=vis.end();i++)
        for(j=i->second.begin();j!=i->second.end();j++)
            printf("%lld %lld %d\n",i->first,j->first,j->second);
    map<ll,map<ll,int> >::reverse_iterator re_i;
    printf("反向遍历\n");
    for(re_i=vis.rbegin();re_i!=vis.rend();re_i++)//i需要倒序,j不需要
        for(j=re_i->second.begin();j!=re_i->second.end();j++)
            printf("%lld %lld %d\n",re_i->first,j->first,j->second);
    return 0;
}
/*
版权声明:本文为CSDN博主「nefu_ljw」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/ljw_study_in_CSDN/article/details/104355672
*/
Archives Tip
QR Code for this page
Tipping QR Code