查看“︁04-数据结构/04-map与unordered map”︁的源代码


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

== map ==

=== 定义 ===

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

=== 常用操作 ===

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

=== 枚举 ===

<syntaxhighlight lang="cpp">
// 使用迭代器
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";
</syntaxhighlight>

=== 按值排序 ===

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

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

== unordered_map ==

用法与 <code>map</code> 基本相同，但：

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

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

== 选择建议 ==

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


[[Category:数据结构]]
[[Category:三三文档]]