set
set<T> s;
红黑树实现，自带$O(logn)$复杂度
没有重复元素，可用于去重。
对于区间sort且区间小范围平移的题，可优化暴力$O(nlogn)$整区间sort -> $O(logn)$单点修改set
- s.insert(val)
- s.erase(val)
- s.lower_bound(val) 返回大于等于val的第一个元素的迭代器
- s.upper_bound(val) 返回大于val的第一个元素的迭代器
- s.count(val) 由于非重，只有0 1
- s.find(val) 查找val，返回迭代器。若无，返回s.end()
声明迭代器：set<T>::iterator it;
++it --it 可查找前趋后继 复杂度$O(logn)$
multiset:
multiset<T> s;
红黑树实现，自带$O(logn)$复杂度
支持重复元素
操作与set基本相同，以下有区别：
- s.erase(val) 会删除所有值为val的元素。
- s.erase(迭代器) 删除迭代器引用的元素，而不影响其他
于是只删除一个元素要用 s.erase(s.find(val)) 当然要保证s.find(val)!=s.end()
- s.count(val) 返回 值为val的元素个数
迭代器类似于set
map
map<T1,T2> m;
红黑树实现，自带$O(logn)$复杂度，所以当数不大没有必要或时间复杂度吃紧时不用为好
非常好用的stl，当桶的直径过大但元素很少时适用。然而我今天才会
map<int,int> 1.大数映射小数 2.桶
map<string,int> 强行"hash"
map<pair<int,int>,int> 二维拍成一维
我们称T1为key，T2为value。
那么有一下用key访问value的方式：
- 下标访问：m[key] 返回key对应的value。此时的下标不同于数组下标，此下标不连续 更像是调用函数。
注意：m[key] 访问若不存在该key对应的value 则会强行赋值。int会赋0
- m.at(key) 不同于下标访问，当存在上一行的情况时会报错
pair:
pair<T1,T2> p;
基本操作：
- pair<T1,T2> p(t1,t2); 声明并赋值
- pair make_pair(t1,t2); 生成一个pair并返回
- p=make_pair(t1,t2); 赋值
- p.first
- p.second
- p1 ? p2 ? 属于 {< > == <= >= ......} 以p.first为第一关键字 p.second为第二关键字