c++STL-Map的使用

$\text{map,unordered_map}​$是$\text{c++STL}​$ 中的一种数据结构，能够实现映射操作，在某些题目中可起到不可替代的作用，本文介绍它们的使用方法。

前言

$\text{map,unordered_map}​$是$\text{c++STL}​$ 中的一种数据结构，能够实现映射操作，在某些题目中可起到不可替代的作用，本文介绍它们的使用方法。

Map

用途

Map可用于将一种类型的变量映射到另一种类型的变量。所以，它应该保护两个关键字，从一个映射到另一个。其实，数组就是一种int到其他类型的映射。例如：$\text{int}$类型的数组a，a[x]=y也就是把$x$映射到$y​$。

有了数组，要map干什么？

数组只是数字到其他类型的映射，但是假如我们要字符串到数字的映射怎么办？比如，将字符串abc映射到数字$5​$，对于数组，a["abc"]=5显然会CE，但是有了map就不一样了。有$map​$，你甚至可以这样：a[10000000000000000000]++;。

使用方法

头文件

#include<map>

定义

map<int,int> a;
map<string,char> a;
map<string,int> a;
...

其中尖括号内，左面是第一关键字，右面是第二关键字。

插入、修改、访问

以map<string,int> a为例

下标访问即可a["abc"]=2;

遍历

方法一

循环遍历，下标访问,想数组一样。

for(int i=1;i<=100;i++)
	cout<<a[i];

如果储存值域过大，这种方式会导致TLE。

方法二

利用迭代器，可以只遍历存在的映射，跳过空位。

for(map<int,int>::iterator i=a.begin();i!=a.end();i++)
{
	printf("%d %d\n",i->first,i->second);
}

如果不会指针或迭代器，背下来即可，无需理解。
这种方式遍历的顺序是 第一关键字由小至大。

时间复杂度

内部实现是一颗平衡树，每次操作复杂度为$log$级别的。

Unordered_map

Unordered_map与Map的区别不大，这里不再重复介绍相同点。以下对其不同之处进行介绍。

遍历

遍历的方式是一样的，不过值得注意的是，用迭代器遍历时，遍历的元素顺序是乱的。

时间复杂度

由于内部实现是哈希表 ，插入和查询的复杂度均为$\theta(n)$