注意pair函数自带cmp函数,所以有时候要用两个元素,那定义pair比定义struct更好,要不然要自己写cmp

Set

相关知识

1. 在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。
2. set由于不会检验定位器的合法性,所以要注意哨兵元素的使用.
3. • 可以利用set的有序性来查找大于等于给定值的最小值和小于等于给定值的最大值. 136. 邻值查找

相关API操作

s.lower_bound(key_value) //返回第一个大于等于key_value的定位器
s.upper_bound(key_value) //返回第一个一个大于key_value的定位器
set<int>::iterator it
迭代器不想定义可以用auto it=s.lower_bound(key_value);

• 元素只出现一次,可以用来检验是否存在过重复关系(即如果题目要求输入重复的话就不进行操作,那么可以用set存储)
  count() 用来查找set中某个某个键值出现的次数，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。 101. 最高的牛

s.count(val);

• 其他基础函数

begin()     　　     返回set容器的第一个迭代器
end() 　　　　       返回set容器的最后一个迭代器
clear()   　　       删除set容器中的所有的元素
empty() 　　　       判断set容器是否为空
max_size() 　        返回set容器可能包含的元素最大个数
size() 　　　　      返回当前set容器中的元素个数
insert()             插入元素进入set容器中
erase(iterator)      删除定位器iterator指向的值
erase(first,second)  删除定位器first和second之间的值
erase(key_value)     删除键值key_value的值

Multiset

相关基础知识

1. 它可以看成一个序列，插入一个数，删除一个数都能够在O(logn)的时间内完成
2. 而且他能时刻保证序列中的数是有序的，而且序列中可以存在重复的数
3. 可以利用set的有序性来查找大于等于给定值的最小值和小于等于给定值的最大值**区别是可以存在重复的元素.
   127. 任务
   67. 数字在排序数组中出现的次数

相关API操作

s.lower_bound(key_value) //返回第一个大于等于key_value的定位器
s.upper_bound(key_value) //返回第一个一个大于key_value的定位器
multiset<int>::iterator it
迭代器不想定义可以用auto it=s.lower_bound(key_value);

Map

相关知识

1. Map是一个存储键值对的数据结构——>所以每个键只能存在一次
2. 对其中的元素会按照Key进行自动升序排序——>所以可以进行二分查找
3. 通过红黑树实现——>根据key值寻找value,时间复杂度为O(logn)
4. map.end()指向map的最后一个元素之后的地址，无论执行map.erase(iter)还是map.add(key,value)，map.end()所返回的值永远不会发生变化，都是指向同一块内存。
   352. 将数据流变为多个不相交区间

相关API操作

 map<int, string> m;  
 m.insert({1,"xie"}) //键值重复会无法插入
 m[1]="xie" //键值重复会产生覆盖
 m.size()
 m.count(key)
 m.find(key)//返回数据所在位置的迭代器
 m.lower_bound(key)//返回迭代器
 m.upper_bound(key)//返回迭代器
 m.emplace(key,value)//避免复制和移动操作,只有当容器中现有元素的键与这个元素的键不同时,才会构造元素
 iterator.first
 iterator.second