# 映射map

#include <map>

提供对数时间的有序键值对结构。底层原理是红黑树。

映射：

0\to3\\ 1\to2\\ 2\to2\\ 3\to1\\ 4\to5\\ ...

性质	解释	map	multimap	unordered_map
互异性	一个键仅可在映射中出现一次	yes	no（任意次）	yes
无序性	键是没有顺序的	no（从小到大）	no（从小到大）	yes

map可以实现任意类型到任意类型的映射：

//从int到int的映射与数组相似
int num[10];
num[0] = 3;
num[1] = 2;
//下标就相当于键

//从string到int的映射可用map
map<string, int> a;
a["abc"] = 0;
a["def"] = 1;
a["def"] = 2; //可改
cout << a["ghi"] << endl; //输出0，因为初值为0

1
2
3
4
5
6
7
8
9
10
11
12

# 1. 常用方法

# 构造

map<键类型, 值类型, 比较器> map

键类型：要存储键的数据类型
值类型：要存储值的数据类型
比较器：键比较大小使用的比较器，默认为less<类型>，可自定义

map<int, int> mp1;                //int->int的映射，键从小到大
map<int, int, greater<int>> mp2;  //int->int的映射，键从大到小

1
2

对于需要自定义比较器的情况，涉及一些初学时容易看迷糊的语法(重载小括号运算符/lambda 表达式)，在此就不展开讲了。

# 遍历

可使用迭代器进行遍历：

for(map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)
    cout << it->first << " " << it->second << endl;

1
2

基于范围的循环（C++ 11）：

for(auto &pr : mp)
    cout << pr.first << " " << pr.second << endl;

1
2

结构化绑定+基于范围的循环（C++ 17）：

for(auto &[key,val] : mp)
    cout << key << " " << val << endl;

1
2

# 其他

作用	用法	示例
增/改/查元素	中括号	`mp[1] = 2;`
查元素（返回迭代器）	`.find(元素)`	`auto it = mp.find(1);`
删除元素	`.erase(元素)`	`mp.erase(2);`
判断元素是否存在	`.count(元素)`	`mp.count(3);`
查看大小/清空/判空	略	略

增删改查时间复杂度为 $O(\log n)$

# 2. 适用情形

需要维护映射的场景可以使用：输入字符串，统计每种字符串的出现次数。（map<string, int> mp）

map<string, int> mp;
vector<string> v;
v.push_back("ab");
v.push_back("ab");
v.push_back("ab");
v.push_back("ab");
v.push_back("cd");
v.push_back("cd");
for(int i = 0; i < v.size(); i++)
    mp[v[i]]++;

for(auto &pr : mp)
    cout << pr.first << " " << pr.second << endl;

//输出：
//ab 4
//cd 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 3. 注意事项

# 中括号访问时默认值

如果使用中括号访问map时对应的键不存在，那么会新增这个键，并且值为默认值，因此中括号会影响键的存在性。

map<char, int> mp;
cout << mp.count('a') << endl; // 0
mp['a'];                       //即使什么都没做，但mp['a']=0已经插入了
cout << mp.count('a') << endl; //1
cout << mp['a'] << endl;       //0

1
2
3
4
5

# 不可用迭代器计算下标

map的迭代器不能像vector一样相减得到下标。下面是错误用法：

auto it = mp.find('a');
int idx = it - mp.begin();

1
2

← 集合set 字符串string →