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

map

定义

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

常用操作

枚举

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

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

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

按值排序

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 基本相同，但：

• 基于哈希表，插入/查找/删除平均 $O(1)$
• 元素无序存储
• 不能直接遍历有序输出

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

选择建议

• 需要有序遍历：用 map
• 只关心快速查找：用 unordered_map
• unordered_map 最坏情况可能退化到 $O(n)$，比赛时一般够用