04-数据结构/04-map与unordered map

map 采用红黑树实现（有序），unordered_map 采用哈希表实现（无序，但常数小）。

map

定义

map<int, string> m;               // 键为 int，值为 string
map<string, int> mp[50];          // 50 个映射

常用操作

操作	说明
m[key] = value	插入或修改值
m.insert({key, value})	插入键值对（键重复时插入失败）
m.find(key)	查找键，返回迭代器；不存在则返回 m.end()
m.erase(key)	删除键值对
m.count(key)	判断键是否存在（返回 [math]\displaystyle{ 0 }[/math] 或 [math]\displaystyle{ 1 }[/math]）
m.clear()	清空
m.size()	返回键值对数量
m.empty()	判断是否为空

枚举

// 使用迭代器
for (map<int, string>::iterator it = m.begin(); it != m.end(); it++)
    cout << (*it).first << " " << (*it).second << "\n";

// 自动推导类型
for (auto it = m.begin(); it != m.end(); it++)
    cout << it->first << " " << it->second << "\n";

// 范围 for
for (auto now : m)
    cout << now.first << " " << now.second << "\n";

按值排序

map 默认按键排序，如果要按值排序需要转换到 vector：

vector<pair<int, string>> v(m.begin(), m.end());
sort(v.begin(), v.end(),
     [](auto &a, auto &b) { return a.second < b.second; });

unordered_map

用法与 map 基本相同，但：

- 基于哈希表，插入/查找/删除平均 [math]\displaystyle{ O(1) }[/math] - 元素无序存储 - 不能直接遍历有序输出

unordered_map<int, string> m;
m[1] = "apple";
if (m.find(2) != m.end())
    cout << m[2];

选择建议

- 需要有序遍历：用 map - 只关心快速查找：用 unordered_map - unordered_map 最坏情况可能退化到 [math]\displaystyle{ O(n) }[/math]，比赛时一般够用