map 底层

map 的底层和 set 一样，都是红黑树，即一种平衡的二叉搜索树。

map 中存储的数据类型类似 pair，即存储键值对 (key,value).

与 unordered_map 不同，map 不仅建立了键值对之间的 hash 映射关系，还在其内部对于每个键值对以 key 的字典序进行了排列，在进行某些处理的时候相对方便。

相对的，map 的搜索效率没有 unordered_map 高。

map 方法

增删查改

插入元素

• insert(pair/make_pair/(key, value))
• m["new key"] = "new value"

修改元素

• 下标操作符[]

m[3] = "new value";

若 key 存在，则更新其映射的 value，若不存在，则创建新的键值对。

• 使用 find 方法和迭代器

m.find(key)->second = "new value";

删除元素

mapStu.clear(); //删所有
mapStu.erase(it);//删迭代器指定
mapStu.erase(beg, end);//删key区间
mapStu.erase(key1);  //删key对应

查找

在修改里提过了，find() 方法返回要查找的键的迭代器，找不到就返回 end() 。

Tip pair 的前一个值为 first，后一个为 second。

set 功能

set 会根据特定的排序规则自动将内部元素排序，不同于 multiset，set 不允许内部元素的重复。

• 不能直接改变 set 中存储的值，那样会改变排序顺序，应先删除旧值再插入新值。

• 没有直接存取操作数的方法，只能使用迭代器存取

  set 支持高效的关键字查找操作。

和 sort 一样，sort 可以存储自定义类型，但是必须重载 < 运算符。

底层

set 的底层是红黑树，其 key 与 value 相同。

常用方法

• begin
• end
• clear
• count ?不能重复还 count 有啥意义
• empty
• equal_range ?返回与给定值相等的两个上下限的迭代器 意义存疑
• erase
• find 返回指定元素的迭代器
• insert
• lower_bound
• ket_cmp 返回比较函数
• size
• swap
• upper_bound
• value_cmp 同 key