# 概述

map 和 unordered_map 都是 STL 中的映射容器，但底层实现方式不同，对应的复杂度也不同。

map 基于红黑树实现，在插入过程中会将插入项按键进行排序，所以其支持双向迭代器。使用时需要头文件 <map> .

unordered_map 基于哈希表实现，仅支持前向迭代器。但 unordered_map 支持 begin() / cbegin() / end() / cend() , 因此可以对其中的元素进行遍历，但遍历是哈希序 (乱序) 的。使用 unordered_map 需要头文件 <unordered_map> 及 <hash> . 此外，还需注意 unordered_map 为 C++ 11 支持的新特性，在先前的 C++ 版本中并不支持。

cbegin() 和 cend() 是常量迭代器，与 begin() 和 end() 指向的内容相同，但不能修改容器中元素的值。使代码更安全。

# 存储形式

map 和 unordered_map 内部都采用 pair 进行存储。例如，输出一个映射 map1 的全体键值的代码如下：

for(auto it:map1) cout<<it.first<<" "<<it.second<<endl;

# 常用函数

函数	作用
`at(key)`	返回指定键所映射的值的引用，如果键不存在，则抛出 `std::out_of_range` 异常
`[key]`	返回指定键所映射的值的引用，如果键不存在，则创建该键并映射到默认值
`insert({key, val})`	插入一个键值对
`erase(key)`	尝试删除一个键值对，如不存在，则不进行任何操作
`size()`	返回映射的项数
`empty()`	返回映射是否为空映射
`clear()`	清空映射中的所有键值对
`bucket_count()`	返回映射中桶的数量 (仅对 unordered_map)
`load_factor()`	返回 unordered_map 当前的负载因子，即元素数量与桶的数量的比值