C++学习笔记--STL标准模板库的认识与使用--关联式容器--Maps

C++ Maps

（1）、C++ Maps是一种关联式容器，包含“关键字/值”对

（2）、map 是有序键值对容器，它的元素的键是唯一的。搜索、移除和插入操作拥有对数复杂度。map 通常实现为红黑树。你可能需要存储一些键值对，例如存储学生姓名对应的分数：Tom 0，Bob 100，Alan 100。但是由于数组下标只能为非负整数，所以无法用姓名作为下标来存储，这个时候最简单的办法就是使用 STL 中的 map 了！

（3）map 重载了 operator[]，可以用任意定义了 operator < 的类型作为下标（在 map 中叫做 key，也就是索引）：

1	map yourMap;

其中，Key 是键的类型，T 是值的类型，下面是使用 map 的实例：

1	map mp;

map 中不会存在键相同的元素，multimap 中允许多个元素拥有同一键。multimap 的使用方法与 map 的使用方法基本相同。

begin()	返回指向map头部的迭代器
clear()	删除所有元素
count()	返回指定元素出现的次数
empty()	如果map为空则返回true
end()	返回指向map末尾的迭代器
equal_range()	返回特殊条目的迭代器对
erase()	删除一个元素
find()	查找一个元素
get_allocator()	返回map的配置器
insert()	插入元素
key_comp()	返回比较元素key的函数
lower_bound()	返回键值>=给定元素的第一个位置
max_size()	返回可以容纳的最大元素个数
rbegin()	返回一个指向map尾部的逆向迭代器
rend()	返回一个指向map头部的逆向迭代器
size()	返回map中元素的个数
swap()	交换两个map
upper_bound()	返回键值>给定元素的第一个位置
value_comp()	返回比较元素value的函数

• 可以直接通过下标访问来进行查询或插入操作。例如 mp["Alan"]=100。
• 通过向 map 中插入一个类型为 pair 的值可以达到插入元素的目的，例如 mp.insert(pair("Alan",100));；
• erase(key) 函数会删除键为 key 的 所有 元素。返回值为删除元素的数量。
• erase(pos): 删除迭代器为 pos 的元素，要求迭代器必须合法。
• erase(first,last): 删除迭代器在  （first，last）范围内的所有元素。
• clear() 函数会清空整个容器。

• count(x): 返回容器内键为 x 的元素数量。复杂度为 （关于容器大小对数复杂度，加上匹配个数）。
• find(x): 若容器内存在键为 x 的元素，会返回该元素的迭代器；否则返回 end()。
• lower_bound(x): 返回指向首个不小于给定键的元素的迭代器。
• upper_bound(x): 返回指向首个大于给定键的元素的迭代器。若容器内所有元素均小于或等于给定键，返回 end()。
• empty(): 返回容器是否为空。
• size(): 返回容器内元素个数。

map 用于存储复杂状态

在搜索中，我们有时需要存储一些较为复杂的状态（如坐标，无法离散化的数值，字符串等）以及与之有关的答案（如到达此状态的最小步数）。map 可以用来实现此功能。其中的键是状态，而值是与之相关的答案。下面的示例展示了如何使用 map 存储以 string 表示的状态。

// 存储状态与对应的答案
map record;

// 新搜索到的状态与对应答案
string status;
int ans;
// 查找对应的状态是否出现过
map::iterator it = record.find(status);
if (it == record.end()) {
  // 尚未搜索过该状态，将其加入状态记录中
  record[status] = ans;
  // 进行相应操作……
} else {
  // 已经搜索过该状态，进行相应操作……
}