STL的神奇容器之map

前言：

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
*/