【C++】set和map的使用

对于STL容器来说，有很多相似的功能，所以这里主要将与之前不同的功能说清楚

1.对于set与map的简单理解

vector/list/deque 作为序列式容器(类似于线性表的存储方式)
map与set作为关联式容器，里面存储的是<key,value>结构的键值对(数据之间有非常强的关联关系)
键值对：用来表示一 一对应的关系，key代表键值，value代表与key对应的信息
如：中英文互译字典，内部的英文必然有一个中文对应

---

map与set 底层是二叉搜索树

---

set作为key模型
map作为 key_value模型
不懂的可以点击了解：二叉搜索树的应用场景

2. set

set的官方文档

---

compare作为一个仿函数，
默认为升序，在重载operator()时 ，以小于比较
同样若将operator()重载中改为大于比较，则为降序
Alloc作为一个默认的空间配置器

insert

由于底层是二叉搜索树，所以要注意若插入相同的key值，就会造成插入失败

迭代器遍历

set底层是二叉搜索树，所以重复的值在树中插入会失败
相当于完成了去重操作

---

不能随便修改*it的数据，set底层作为二叉搜索树，若将其中一个key值进行修改，就没办法保证修改后是不是搜索树了

---

支持迭代器就是支持范围for，范围for底层就是迭代器

count

给一个值，判断在不在
若在返回非0，若不在返回0
但是由于set不支持重复的key值插入，所以count只能判断在不在

count的效果与二叉搜索树的应用场景的写法，效果是等价的
x作为key值，若存在则进入if 输出在，若不在则进入else 输出不在

multiset

---

与set的区别为 ：允许键值冗余

insert

---

再次使用迭代器遍历时，发现是有重复的值存在的

---

find

multiset的find函数，若有多个重复的key存在，实际上查找的是中序的第一个

---

验证查找为中序第一个key

若查找的为中序的第一个1，才可将后面的所有的1都显示出来

---

count

在multiset中由于有重复key的存在，
所以count函数能够返回该key值出现的个数
若key值没有出现，则返回0

3. map

map的官方文档

---

map作为 key_value模型
但是map并没有定义key与value，而是存在一个结构pair

---

pair是库自己定义的结构，用于存放key与value

带有两个模板参数分别是first与second，相当于key与value

insert与迭代器的使用

通过map将key与value都置成string类型，可以通过pair完成插入，但是pair写起来太长容易出错

---

若使用pair则需要借助匿名对象插入

---

所以为了减少代码长度，所以使用make_pair

make_pair为一个函数模板，实际上还是调用匿名构造返回

统计水果次数

方法1是在二叉搜索树的应用场景使用的
方法2是operator[]的使用
两种方法的作用是等价的
countmap[e]++： 传入key值e，并返回对应的value值，使value值+1

operator []

给一个key值，返回mapped_type类型

---

mapped_type代表第二个模板参数value

---

operator[]的实现理解

---

insert的返回值

pair的first是一个迭代器，指向新插入的元素或者指向与key值相等元素位置的迭代器
pair的second是bool类型，bool代表在不在，若插入成功返回true，插入失败返回false，但是会返回之前已经存在并且相同类型的迭代器

---

对整体的拆分理解

调用insert函数，函数的第二个参数为value类型的缺省值，调用默认构造
返回值是pair<iterator,bool>
pair.first 表示迭代器 ，解引用就为pair数据 ，pair数据取second就为value

---

operator[]的作用

1.插入
插入key值，若插入成功则返回true
2.修改
若key值已经存在，则返回false，同时也会返回之前已经存在并且相同类型的迭代器 ，使之对value值修改
3.插入+修改
插入key值，若插入成功则返回true，同时将对应的value值修改
4.查找
当key值已经存在时，就会寻找之前已经存在并且类型相同的迭代器

---

1.插入
插入 left，第二个给缺省值，而string缺省值为空串
2.修改
由于插入的left已经存在，所以插入失败，并寻找之前已经存在的left对应的迭代器
把left迭代器的返回值 value修改为左边
3.插入+修改
插入right，第二个缺省值为空串，并把返回值 value修改为右边
4.查找
直接返回对应的value值即可

multimap

与map的区别：允许键值冗余

---

---

但是multimap并没有operator[]
因为在map中，key和value是一对一的关系
在multimap中，key和value是一对多的关系
所以 没办法判断当前key值对应哪一个value