STL—— map 超详解

map

在STL的头文件中<map>中定义了模版类map和multimap，用有序二叉树表存储类型为pair<const Key, T>的元素对序列。序列中的元素以const Key部分作为标识，map中所有元素的Key值必须是唯一的，multimap则允许有重复的Key值。

可以将map看作是由Key标识元素的元素集合，这类容器也被称为“关联容器”，可以通过一个Key值来快速决定一个元素，因此非常适合于需要按照Key值查找元素的容器。

map模版类需要四个模版参数，第一个是键值类型，第二个是元素类型，第三个是比较算子，第四个是分配器类型。其中键值类型和元素类型是必要的。

STL的容器map为我们处理有序key-value形式数据提供了非常大的便利，由于内部红黑树结构的存储，查找等操作的时间复杂度均为 $O (l o g N)$ 。

示例：

map<string,long long> m;

1.向map中插入元素

m[key] = value;

[key]操作是map很有特色的操作,如果在map中存在键值为key的元素对, 则返回该元素对的值域部分,否则将会创建一个键值为key的元素对,值域为默认值。所以可以用该操作向map中插入元素对或修改已经存在的元素对的值域部分。

m.insert(make_pair(key, value));

也可以直接调用insert方法插入元素对,insert操作会返回一个pair,当map中没有与key相匹配的键值时,其first是指向插入元素对的迭代器,其second为true;若map中已经存在与key相等的键值时,其first是指向该元素对的迭代器,second为false。

2.查找元素

int i = m[key];

要注意的是,当与该键值相匹配的元素对不存在时,会创建键值为key（当另一个元素是整形时，m[key]=0）的元素对。

map<string, int>::iterator it = m.find(key);

如果map中存在与key相匹配的键值时,find操作将返回指向该元素对的迭代器,否则,返回的迭代器等于map的end()

3.删除元素

erase的参数可以是key或者迭代器

m.erase(key);

删除与指定key键值相匹配的元素对,并返回被删除的元素的个数。

m.erase(it);

删除由迭代器it所指定的元素对,并返回指向下一个元素对的迭代器。

实例：


int main()
{
    map<int,int>h;
    h.insert(make_pair(1,2)),h.insert(make_pair(2,3));
    map<int,int>::iterator it=h.begin();
    pair<int,int>p=*it;

    h.erase(it);h.erase(2);
    cout<<p.first<<" "<<p.second<<endl;
}

输出：

1 2

4.默认排序和自定义排序

一般而言，使用map的时候直接采取 $m a p < t y p e n a m e A, t y p e n a m e B >$ 的形式即可，map的内部实现默认使用A类型变量的升序来排序map的值。

这里的自定义排序更多的是工程上的用法，对于竞赛的使用没有什么参考价值，所以我就不细究了，只需要知道map的内部实现默认使用A类型变量的升序来排序map的值就好，实际使用的时候需要可以直接利用这一特性自己更改数据来巧妙利用就好，想要了解的看这个博客
map的默认排序和自定义排序
具体利用到这一点的使用实例见下一节

5.map的upper_bound/lower_bound

iterator lower_bound( const key_type &key ): 返回一个迭代器，指向键值>= key的第一个元素。

iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值> key的第一个元素。

要注意返回的是一个迭代器！比较的标准是键值Key

#include <iostream>
#include <map>
 
using namespace std;
int main()
{
    map<int,string> mp;
    mp[1]="a";
    mp[2]="b";
    mp[3]="f";
    mp[4]="c";
    mp[5]="d";
    map<int,string>::iterator it,p1,p2;
    p1 = mp.lower_bound(3);
    p2 = mp.upper_bound(3);
    cout<<"lower_bound"<<p1->first<<"=>"<<p1->second.c_str()<<endl;
    cout<<"upper_bound"<<p2->first<<"=>"<<p2->second.c_str()<<endl;
 
    return 0;
}

输出：

lower_bound3=>f
upper_bound4=>c

再来一个实例：

因为返回的是一个迭代器，所以可以进行±操作进行移动，如果想要得到第一个不大于value的值，那么就可以用upper_bound得到第一个大于value的迭代器，然后it--;即可,因为map内部自动排序嘛

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<map>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！
const ll N=2507;
const ll mod=1e9+7;
const double EPS=1e-5;//-10次方约等于趋近为0

int n,m;
pair<int,int>cow[N];
int main()
{
    cin>>n>>m;
    map<int,int>spfs;
    over(i,1,n)scanf("%d%d",&cow[i].first,&cow[i].second);
    over(i,1,m){
        int spf,cover;
        scanf("%d%d",&spf,&cover);
        spfs[spf]+=cover;
    }
    sort(cow+1,cow+1+n);
    int res=0;
    spfs[0]=spfs[1001]=n;
    for(int i=n;i>=1;--i){
        auto spf=spfs.upper_bound(cow[i].second);
        //这里的spf是map<>spfs的一个iterator,第一个大于cow[i].max的防晒霜
        spf--;
        //--之后就是最后一个小于等于cow[i].max的防晒霜了
        if(spf->first>=cow[i].first){
            res++;
            if(--spf->second==0)
                spfs.erase(spf);
        }
    }
    printf("%d\n",res);
    return 0;
}

6.其他简单操作

m.size();

返回元素个数

m.empty();

判断是否为空

m.clear();

清空所有元素

m.begin();

返回首迭代器

m.end();

返回尾迭代器

7.实例：用map统计字符串出现的次数

给定n个字符串，m个问题，每个问题询问一个字符串出现的次数。 $n < = 20000$ ， $m < = 20000$ ，每个字符串的长度都不超过20。


int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    map<string,int>h;
    char str[50];
    for(int i=0;i<n;++i){
        scanf("%s",str);
        h[str]++;
    }
    for(int i=1;i<=m;++i){
        scanf("%s",str);
        if(h.find(str)==h.end())
            puts("0");
        else printf("%d\n",h[str]);
    }
    return 0;
}